International Symposium on DIStributed Computing (DISC) 2022

Accepted Papers

Regular Papers

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

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

Xing Hu and Sam Toueg.
On implementing SWMR registers from SWSR registers in systems with Byzantine failures.

Will Rosenbaum.
Packet Forwarding with a Locally Bursty Adversary.

Pierre Sutra.
The Weakest Failure Detector for Genuine Atomic Multicast.

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

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

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

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

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

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

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

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

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

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

Philipp Schneider and Fabian Kuhn.
Routing Schemes and Distance Oracles in the Hybrid Model.

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

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

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

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

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

Yuval Emek, Yuval Gil and Shay Kutten.
Locally Restricted Proof Labeling Schemes.

Merav Parter and Asaf Petruschka.
Optimal Dual Vertex Failure Connectivity Labels.

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

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

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

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

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

Anatoliy Zinovyev.
Space-stretch tradeoff in routing revisited.

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

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

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

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

Oded Naor and Idit Keidar.
On Payment Channels in Asynchronous Money Transfer Systems.

Brief Announcements

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

Irina Kostitsyna, Tom Peters and Bettina Speckmann.
Fast Reconfiguration for Programmable Matter.

Raissa Nataf, Guy Goren and Yoram Moses.
Null Messages, Information and Coordination.

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

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

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

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

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

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

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

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

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

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

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