List of DISC 2023 accepted papers with links

List of papers accepted to DISC 2023, with links to the paper when available. (Thanks to Tijn de Vos for helping out.)

Regular papers

• Treasure hunt with volatile pheromones. Evangelos Bampas, Joffroy Beauquier, Janna Burman and William Guy-Obé. pdf.

• Optimal Computation in Leaderless and Multi-Leader Disconnected Anonymous Dynamic Networks. Giovanni Viglietta and Giuseppe Antonio Di Luna. pdf, arxiv page.

• One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks. Hagit Attiya, Pierre Fraigniaud, Ami Paz and Sergio Rajsbaum. pdf, arxiv page.

• Distributed Certification for Classes of Dense Graphs. Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport and Ioan Todinca. pdf, arxiv page.

• List Defective Colorings: Distributed Algorithms and Applications. Marc Fuchs and Fabian Kuhn. pdf, arxiv page.

• Self-Stabilizing Clock Synchronization in Probabilistic Networks. Bernadette Charron-Bost and Louis Penet de Monterno. pdf, arxiv page.

• Fast Deterministic Rendezvous in Labeled Lines. Avery Miller and Andrzej Pelc.

• Conditionally Optimal Parallel Coloring of Forests. Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai and Jara Uitto. pdf, arxiv page.

• Modular Recoverable Mutual Exclusion Under System-Wide Failures. Sahil Dhoked, Wojciech Golab and Neeraj Mittal.

• Memory-anonymous Starvation-free Mutual Exclusion: Possibility and Impossibility Results. Gadi Taubenfeld.

• Base Fee Manipulation In Ethereum’s EIP-1559 Transaction Fee Mechanism. Sarah Azouvi, Guy Goren, Lioba Heimbach and Alexander Hicks. pdf, arxiv page.

• Improved and Partially-Tight Lower Bounds for Message-Passing Implementations of Multiplicity Queues. Anh Tran and Edward Talmage. pdf, arxiv page.

• Gorilla: Safe Permissionless Byzantine Consensus. Youer Pu, Ali Farahbakhsh, Lorenzo Alvisi and Ittay Eyal. pdf, arxiv page.

• A Topology by Geometrization for Sub-Iterated Immediate Snapshot Message Adversaries and Applications to Set-Agreement. Emmanuel Godard and Yannis Coutouly. pdf, arxiv page.

• On the power of quorum subsumption for heterogeneous quorum systems. Xiao Li, Eric Chan and Mohsen Lesani.

• Colordag: An Incentive-Compatible Blockchain. Ittai Abraham, Danny Dolev, Ittay Eyal and Joseph Halpern. pdf.

• Null Messages, Information and Coordination. Raïssa Nataf, Guy Goren and Yoram Moses. pdf, arxiv page.

• The FIDS Theorems: Tensions between Multinode and Multicore Performance in Transactional Systems. Naama Ben-David, Gal Sela and Adriana Szekeres. pdf, arxiv page.

• Network Agnostic Perfectly Secure MPC Against General Adversaries. Ananya Appan, Anirudh Chandramouli and Ashish Choudhury. pdf, arxiv page.

• Breadth-First Depth-Next: Optimal Collaborative Exploration of Trees with Low Diameter. Romain Cosson, Laurent Massoulié and Laurent Viennot. pdf, arxiv page.

• Distributed Sketching Lower Bounds for k-Edge Connected Spanning Subgraph, Breadth-First Search Tree, and LCL Problems. Peter Robinson.

• Cordial Miners: Fast and Efficient Consensus for Every Eventuality Idit Keidar, Oded Naor, Ouri Poupko and Ehud Shapiro.

• Topological Characterization of Task Solvability in General Models of Computation Hagit Attiya, Armando Castañeda and Thomas Nowak. pdf, arxiv page.

• Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining Prasad Jayanti, Siddhartha Jayanti and Sucharita Jayanti. pdf, arxiv page.

• Communication Lower Bounds for Cryptographic Broadcast Protocols Erica Blum, Elette Boyle, Ran Cohen and Chen-Da Liu-Zhang.

• Certified Round Complexity of Self-Stabilizing Algorithms Karine Altisen, Stéphane Devismes and Pierre Corbineau.

• On the Inherent Anonymity of Gossiping Rachid Guerraoui, Anne-Marie Kermarrec, Anastasiia Kucherenko, Rafael Pinot and Sasha Voitovych. pdf, arxiv page.

• On the Node-Averaged Complexity of Locally Checkable Problems on Trees Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti and Gustav Schmid. pdf, arxiv page.

• Send/Receive Patterns versus Read/Write Patterns Mathilde Déprés, Achour Mostéfaoui, Matthieu Perrin and Michel Raynal. pdf, HAL page.

• Time and Space Optimal Massively Parallel Algorithm for the 2-ruling Set Problem Mélanie Cambus, Fabian Kuhn, Shreyas Pai and Jara Uitto. pdf, arxiv page.

• Fast Reconfiguration for Programmable Matter Irina Kostitsyna, Tom Peters and Bettina Speckmann. pdf, arxiv page.

• Fast Coloring Despite Congested Relays Maxime Flin, Magnus Halldorsson and Alexandre Nolin. pdf, arxiv page.

• Every Bit Counts in Consensus Pierre Civit, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Matteo Monti and Manuel Vidigueira. pdf, arxiv page.

• The Synchronization Power (Consensus Number) of Access-Control Objects: The Case of AllowList and DenyList Davide Frey, Mathieu Gestin and Michel Raynal. pdf, arxiv page.

Brief Announcements

• Let It TEE: Asynchronous Byzantine Atomic Broadcast with n >= 2f+1 Marc Leinweber and Hannes Hartenstein. pdf, arxiv page.

• BatchBoost: Universal Batching for Concurrent Data Structures Vitaly Aksenov, Michael Anopenko, Alexander Fedorov and Michael Spear.

• Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit Hagit Attiya and Jennifer Welch. pdf, arxiv page.

• Relations between Space-Bounded and Adaptive Massively Parallel Computations Michael Chen, A. Pavan and N. V. Vinodchandran.

• Scalable Agreement Protocols with Optimal Optimistic Efficiency Yuval Gelles and Ilan Komargodski. pdf, IACR page.

• Linearization in Silent Programmable Matter Alfredo Navarra and Francesco Piselli.

• On Implementing Wear Leveling in Persistent Synchronization Structures Jakeb Chouinard, Kush Kansara, Xialin Liu, Nihal Potdar and Wojciech Golab.

• Distributed derandomization revisited Sameep Dahal, Francesco d’Amore, Henrik Lievonen, Timothé Picavet and Jukka Suomela. pdf, arxiv page.

• Recoverable and Detectable Self-Implementations of Swap Tomer Lev Lehman, Hagit Attiya and Danny Hendler. pdf, arxiv page.

• Byzantine Consensus Under Dynamic Participation with a Well-Behaved Majority Giuliano Losa and Eli Gafni. pdf.

• Grassroots Distributed Systems: Concept, Examples, Implementation and Applications Ehud Shapiro. pdf, arxiv page.

• The Space Complexity of Set Agreement Using Swap Sean Ovens.

• Subquadratic Multivalued Asynchronous Byzantine Agreement WHP Shir Cohen and Idit Keidar. pdf arxiv page