List of DISC 2022 accepted papers with links

Same as the previous post, but for DISC.

Regular papers

• Fast Distributed Vertex Splitting With Applications. Magnús M. Halldórsson, Yannic Maus and Alexandre Nolin. pdf, arxiv page.

• Exponential Speedup Over Locality in MPC with Optimal Memory. Rustam Latypov, Jara Uitto, Dennis Olivetti, Alkida Balliu, Yannic Maus, Manuela Fischer and Sebastian Brandt. pdf, arxiv page.

• On implementing SWMR registers from SWSR registers in systems with Byzantine failures. Xing Hu and Sam Toueg. pdf, arxiv page.

• Packet Forwarding with a Locally Bursty Adversary. Will Rosenbaum. pdf, arxiv page.

• The Weakest Failure Detector for Genuine Atomic Multicast. Pierre Sutra. pdf, arxiv page.

• The Space Complexity of Scannable Objects with Bounded Components. Sean Ovens.

• Liveness and Latency of Byzantine State-Machine Replication. Manuel Bravo, Gregory Chockler and Alexey Gotsman. pdf, arxiv page.

• Contention Resolution without Collision Detection: Constant Throughput and Logarithmic Energy. Gianluca De Marco, Dariusz Kowalski and Grzegorz Stachowiak.

• Holistic Verification of Blockchain Consensus. Nathalie Bertrand, Vincent Gramoli, Igor Konnov, Marijana Lazic, Pierre Tholoniat and Josef Widder. pdf, arxiv page.

• Byzantine Consensus is Theta(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony! Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic and Manuel Vidigueira. pdf, arxiv page.

• Fragmented ARES: Dynamic Storage for Large Objects. Andria Trigeorgi, Chryssis Georgiou and Nicolas Nicolaou. pdf, arxiv page.

• An Almost Singularly Optimal Asynchronous Distributed MST Algorithm. Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan and David Peleg.

• Distributed Randomness from Approximate Agreement. Petr Kuznetsov, Luciano Freitas de Souza and Andrei Tonkikh. pdf, arxiv page.

• Broadcast CONGEST Algorithms Against Eavesdroppers. Yael Hitron, Merav Parter and Eylon Yogev.

• Dynamic Probabilistic Input Output Automata. Pierre Civit and Maria Potop-Butucaru. a pdf.

• Routing Schemes and Distance Oracles in the Hybrid Model. Philipp Schneider and Fabian Kuhn. pdf, arxiv page.

• Efficient Classification of Locally Checkable Problems in Regular Trees. Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený and Jukka Suomela. pdf, arxiv page.

• How to Meet at a Node of any Connected Graph. Subhash Bhagat and Andrzej Pelc.

• Byzantine Connectivity Testing in the Congested Clique. John Augustine, Anisur Rahaman Molla, Gopal Pandurangan and Yadu Vasudev.

• Safe Permissionless Consensus. Youer Pu, Lorenzo Alvisi and Ittay Eyal. pdf

• Near-Optimal Distributed Computation of Small Vertex Cuts. Merav Parter and Asaf Petruschka.

• Locally Restricted Proof Labeling Schemes. Yuval Emek, Yuval Gil and Shay Kutten. pdf, arxiv page.

• Õptimal Dual Vertex Failure Connectivity Labels. Merav Parter and Asaf Petruschka. pdf, arxiv page.

• Fault Tolerant Coloring of the Asynchronous Cycle. Pierre Fraigniaud, Mikaël Rabie and Patrick Lambein-Monette. pdf, arxiv page.

• Good-case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case. Timothé Albouy, Davide Frey, Michel Raynal and Francois Taiani.

• Distributed Construction of Lightweight Spanners for Unit Ball Graphs. Hadi Khodabandeh and David Eppstein.

• How to Wake Up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks. Varsha Dani and Thomas Hayes. pdf, arxiv page.

• Smoothed Analysis of Information Spreading in Dynamic Networks. Michael Dinitz, Jeremy Fineman, Seth Gilbert and Calvin Newport. pdf, arxiv page.

• Space-stretch tradeoff in routing revisited. Anatoliy Zinovyev. pdf

• Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts. Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic and Themis Gouleakis.

• Improved Deterministic Connectivity in Massively Parallel Computation. Manuela Fischer, Jeff Giliberti and Christoph Grunau. pdf, arxiv page.

• Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure. Gal Amram, Avi Hayoun, Lior Mizrahi and Gera Weiss.

• Oracular Byzantine Reliable Broadcast. Martina Camaioni, Rachid Guerraoui, Matteo Monti and Manuel Vidigueira.

• On Payment Channels in Asynchronous Money Transfer Systems. Oded Naor and Idit Keidar. pdf, arxiv page.

Brief Announcements

• New Clocks, Fast Line Formation and Self-Replication Population Protocols. Leszek Gasieniec, Paul Spirakis and Grzegorz Stachowiak.

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

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

• Survey of Persistent Memory Correctness Conditions. Naama Ben-David, Michal Friedman and Yuanhao Wei. pdf, arxiv page.

• Computing Power of Hybrid Models in Synchronous Networks. Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos Wilson and Ioan Todinca. pdf, arxiv page.

• Authenticated Consensus in Synchronous Systems with Mixed Faults. Ittai Abraham, Danny Dolev, Alon Kagan and Gilad Stern. pdf.

• Minimizing Congestion in Hybrid Demand-Aware Network Topologies. Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster and Stefan Schmid.

• Asymmetric Mutual Exclusion for RDMA. Jacob Nelson-Slivon, Lewis Tseng and Roberto Palmieri. pdf, arxiv page.

• Benchmarking the Benchmarks: Discovering the Source of Performance Differences in Concurrent Microbenchmarks. Rosina Kharal and Trevor Brown.

• Foraging in Particle Systems via Self-Induced Phase Changes. Shunhao Oh, Dana Randall and Andrea Richa. pdf, arxiv page.

• Gathering Despite Defected View. Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama and Toshimitsu Masuzawa. pdf, arxiv page.

• Distributed algorithms for minimum dominating set problem and beyond, a new approach. Sharareh Alipour and Mohammadhadi Salari. pdf, arxiv page.

• Temporal Locality in Online Algorithms. Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela and Aleksandr Tereshchenko. pdf, arxiv page.

• It’s not easy to relax: liveness in chained BFT protocols. Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard and Florian Suri-Payer. pdf, arxiv page.

• Distributed Quantum Interactive Proofs. Francois Le Gall, Masayuki Miyamoto and Harumichi Nishimura.