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