List of Accepted Papers

Full Papers

Breaking the $O(\sqrt n)$-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party
E. Boyle, R. Cohen, A. Goel

Time-Optimal Self-Stabilizing Leader Election in Population Protocols
J. Burman, H. Chen, H. Chen, D. Doty, T. Nowak, E. Severson, C. Xu

Good-case Latency of Byzantine Broadcast: a Complete Categorization
I. Abraham, K. Nayak, L. Ren, Z. Xiang

Efficient Deterministic Leader Election for Programmable Matter
F. Dufoulon, S. Kutten, W. Moses Jr.

Approximate Byzantine Fault-Tolerance in Distributed Optimization
S. Liu, N. Gupta, N. Vaidya

Hedging Against Sore Loser Attacks in Cross-Chain Transactions
Y. Xue, M. Herlihy

All You Need is DAG
I. Keidar, E. Kokoris-Kogias, O. Naor, A. Spiegelman

Reductions and Extension-Based Proofs
K. Brusse, F. Ellen

On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
D. Harris, H. Su, H. Vu

Can We Break Symmetry with o(m) Communication ?
S. Pai, G. Pandurangan, S. Pemmaraju, P. Robinson

Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility
D. Kirkpatrick, I. Kostitsyna, A. Navarra, G. Prencipe, N. Santoro

Contention Resolution with Predictions
S. Gilbert, C. Newport, N. Vaidya, A. Weaver

Lower Bounds on the State Complexity of Population Protocols
P. Czerner, J. Esparza

Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
G. Bodwin, M. Parter

Reaching Consensus for Asynchronous Distributed Key Generation
G. Stern, I. Abraham, P. Jovanovic, S. Meiklejohn, A. Tomescu, M. Maller

Fast and Robust Comparison Dynamics in Population Protocols
D. Alistarh, M. Töpfer, P. Uznański

On Implementing Stabilizing Leader Election with Weak Assumptions on Network Dynamics
K. Altisen, S. Devismes, A. Durand, C. Johnen, F. Petit

Decision Power of Weak Asynchronous Models of Distributed Computing
P. Czerner, R. Guttenberg, M. Helfrich, J. Esparza

Differential Privacy and Byzantine Resilience in SGD: Do They Add Up?
R. Guerraoui, N. Gupta, R. Pinot, S. Rouault, J. Stephan

Tight Trade-off in Contention Resolution without Collision Detection
H. Chen, Y. Jiang, C. Zheng

Search via Parallel Lévy Walks on Z^2
A. Clementi, F. d’Amore, G. Giakkoupis, E. Natale

A Thin Self-Stabilizing Asynchronous Unison Algorithm with Applications to Fault Tolerant Biological Networks
Y. Emek, E. Keren

Stochastic Coordination in Heterogeneous Load Balancing Systems
G. Goren, S. Vargaftik, Y. Moses

Revisiting Optimal Resilience of Fast Byzantine Consensus
P. Kuznetsov, A. Tonkikh, Y. Zhang

Low-Congestion Shortcuts in Constant Diameter Graphs
S. Kogan, M. Parter

Constant-Round Spanners and Shortest Paths in Congested Clique and MPC
M. Dory, O. Fischer, S. Khoury, D. Leitersdorf

Fault-Tolerant Labeling and Compact Routing Schemes
M. Dory, M. Parter

Embedding a Deterministic BFT Protocol in a Block DAG
M. Schett, G. Danezis

Randomized Local Computation Complexity of the Lovász Local Lemma
S. Brandt, C. Grunau, V. Rozhon

Time-Optimal Construction of Overlay Networks
T. Götte, K. Hinnenthal, C. Scheideler, J. Werthmann

Strong-Diameter Network Decomposition
Y. Chang, M. Ghaffari

Locally Checkable Problems in Rooted Trees
A. Balliu, S. Brandt, D. Olivetti, J. Studený, J. Suomela, A. Tereshchenko

Low-Congestion Shortcuts for Graphs Excluding Dense Minors
M. Ghaffari, B. Haeupler

The Topology of Randomized Symmetry-Breaking Distributed Computing
P. Fraigniaud, R. Gelles, Z. Lotker

A Tight Lower Bound for the RMR Complexity of Recoverable Mutual Exclusion 
D. Chan, P. Woelfel

An Efficient Adaptive Partial Snapshot Implementation
B. Bashari, P. Woelfel

Diversity, Fairness and Sustainability in Population Protocols
N. Kang, F. Mallmann-Trenn, N. Rivera

Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
A. Balliu, S. Brandt, F. Kuhn, D. Olivetti

Improved Deterministic $(\Delta+1)$ Coloring in Low-Space MPC
 A. Czumaj, P. Davies, M. Parter

Component Stability in Low-Space Massively Parallel Computation
A. Czumaj, P. Davies, M. Parter

A New Way to Achieve Round-Efficient Byzantine Agreement
M. Fitzi, C. Liu-Zhang, J. Loss

The Space Complexity of Scannable Binary Objects
S. Ovens

On Register Linearizability and Termination
V. Hadzilacos, X. Hu, S. Toueg

Ultra-Sparse Near-Additive Emulators
M. Elkin, S. Matar

Brief Announcements

Brief Announcement: Be Prepared When Network Goes Bad: An Asynchronous View-Change Protocol
R. Gelashvili, L. Kokoris-Kogias, A. Spiegelman, Z. Xiang

Brief Announcement: A Time and Space Optimal Stable Population Protocol Solving Exact Majority
D. Doty, M. Eftekhari, L. Gąsieniec, E. Severson, G. Stachowiak, P. Uznański

Brief Announcement: An Improved Distributed Approximate Single Source Shortest Paths Algorithm
N. Cao, J. Fineman, K. Russell

Brief Announcement: Classifying Trusted Hardware via Unidirectional Communication
N. Ben-David, K. Nayak

Brief Announcement: Variants of approximate agreement on graphs and simplicial complexes
J. Ledent

Brief Announcement: Making Synchronous BFT Protocols Secure in the Presence of Mobile Sluggish Faults
J. Kim, V. Mehta, K. Nayak, N. Shrestha

Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity
M. Charikar, W. Ma, L. Tan

Brief Announcement: Brokering with Hashed Timelock Contracts is NP-Hard
E. Chan, M. Lesani

Brief Announcement: Detectable Sequential Specifications for Recoverable Shared Objects
N. Li, W. Golab

Brief Announcement: Linearizability: a Typo
G. Sela, M. Herlihy, E. Petrank

Brief Announcement: What’s Live? Understanding Distributed Consensus
S. Chand, Y. Liu

Brief Announcement: On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement
M. Kumar, A. Molla

Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks
V. Dani, A. Gupta, T. Hayes, S. Pettie

Brief Announcement: Malicious Security Comes for Free in Consensus with Leaders
M. Rambaud, T. Attema, M. Abspoel