List of accepted papers

Full Papers

A Framework for Distributed Quantum Queries in the CONGEST Model
T. de Vos, J. van Apeldoorn

Early Adapting to Trends: Self-Stabilizing Information Spread using Passive Communication
A. Korman, R. Vacus

What can be certified compactly?
L. Feuilloley, N. Bousquet, T. Pierron

Perfectly-Secure Synchronous MPC with Asynchronous Fallback Guarantees
A. Appan, A. Chandramouli, A. Choudhury

When is Recoverable Consensus Harder Than Consensus?
C. Delporte-Gallet, P. Fatourou, H. Fauconnier, E. Ruppert

Node and Edge Averaged Complexities of Local Graph Problems
A. Balliu, M. Ghaffari, F. Kuhn, D. Olivetti

The Space Complexity of Consensus from Swap
S. Ovens

State Complexity of Protocols With Leaders
J. Leroux

Narrowing the LOCAL – CONGEST Gaps in Sparse Networks via Expander Decompositions
Y. Chang, H. Su

A Recursive Early-Stopping Phase King Protocol
C. Lenzen, S. Sheikholeslami

Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader Agreement
I. Abraham, N. Ben-David, S. Yandamuri

Universally-Optimal Distributed Exact Min-Cut
M. Ghaffari, G. Zuzic

Distributed Computations in Fully-Defective Networks
K. Censor-Hillel, S. Cohen, R. Gelles, G. Sela

A Distributed Combinatorial Topology Approach to Arrow’s Impossibility
S. Rajsbaum, A. Raventós-Pujol

Deterministic Near-Optimal Distributed Listing of Cliques
K. Censor-Hillel, D. Leitersdorf, D. Vulakh

Near-Optimal Leader Election in Population Protocols on Graphs
D. Alistarh, J. Rybicki, S. Voitovych

The Laplacian Paradigm in the Broadcast Congested Clique
T. de Vos, S. Forster

Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
M. Dory, M. Ghaffari, S. Ilchi

Overcoming Congestion in Distributed Coloring
M. Halldorsson, A. Nolin, T. Tonoyan

Constant-Round Near-Optimal Spanners in Congested Clique
S. Chechik, T. Zhang

Distributed Edge Coloring in Time Polylogarithmic in Δ
A. Balliu, S. Brandt, F. Kuhn, D. Olivetti

Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks
X. Wu, P. Yao

Optimal Synchronous Approximate Agreement with Asynchronous Fallback
D. Ghinea, C. Liu-Zhang, R. Wattenhofer

From Switch Scheduling to Datacenter Scheduling: Matching-Coordinated Greed is Good
S. Rajakrishnan, R. Agarwal, D. Shmoys

Optimal Clock Synchronization with Signatures
C. Lenzen, J. Loss

Parameterized Verification under Release Acquire is PSPACE-complete
S. Krishna, A. Godbole, R. Meyer, S. Chakraborty

Blunting an Adversary Against Randomized Concurrent Programs with Linearizable Implementations
H. Attiya, C. Enea, J. Welch

Population Protocols for Exact Plurality Consensus
G. Bankhamer, P. Berenbrink, F. Biermeier, R. Elsässer, H. Hosseinpour, D. Kaaser, P. Kling

Fast and Fair Lock-Free Locks
N. Ben-David, G. Blelloch

A Massively Parallel Modularity-Maximizing Algorithm With Provable Guarantees
V. Cohen-Addad, F. Mallmann-Trenn, D. Saulpic

Massively Parallel Computation in a Heterogeneous Regime
O. Fischer, A. Horowitz, R. Oshman

Gradecast in Synchrony and Reliable Broadcast in Asynchrony with Optimal Resilience, Efficiency, and Unconditional Security
I. Abraham, G. Asharov

The Landscape of Distributed Complexities on Trees and Beyond
C. Grunau, V. Rozhoň, S. Brandt

Can’t See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners
O. Kahalon, H. Le, L. Milenković, S. Solomon

A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement
P. Fraigniaud, A. Paz, S. Rajsbaum

Adaptively Secure Single Secret Leader Election from DDH
D. Catalano, D. Fiore, E. Giunta

Revisiting the Power of Non-Equivocation in Distributed Protocols
N. Ben-David, B. Chan, E. Shi

Balanced Allocations with the Choice of Noise
D. Los, T. Sauerwald

Internet Computer Consensus
J. Camenisch, M. Drijvers, T. Hanke, Y. Pignolet, V. Shoup, D. Williams

Balanced Byzantine Reliable Broadcast with Near-Optimal Communication and Improved Computation
N. Alhaddad, S. Das, S. Duan, L. Ren, M. Varia, Z. Xiang, H. Zhang

Brief Announcements

Brief Announcement: Fault Tolerant Coloring of the Asynchronous Cycle
P. Fraigniaud, P. Lambein-Monette, M. Rabie

Brief Announcement: Towards a Theory of Wear Leveling in Persistent Data Structures
X. Liu, W. Golab

Brief Announcement: Make Every Word Count: Adaptive BA with Fewer Words
S. Cohen, I. Keidar, A. Spiegelman

Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds
J. Augustine, W. Moses Jr., G. Pandurangan

Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear
A. El-Hayek, M. Henzinger, S. Schmid

Brief Announcement: Asynchronous Randomness and Consensus without Trusted Setup
L. De Souza, P. Kuznetsov, A. Tonkikh

Brief Announcement: Computability and Anonymous Storage-Efficient Consensus with an Abstract MAC Layer
L. Tseng, Q. Zhang

Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets
S. Pai, S. Pemmaraju

Brief Announcement: Deterministic Consensus and Checkpointing with Crashes: Time and Communication Efficiency
B. Chlebus, D. Kowalski, J. Olkowski

Brief Announcement: The weakest failure detector for genuine atomic multicast
P. Sutra

Brief Announcement: How to Tame Multiple Spending in Decentralized Cryptocurrencies
J. Bezerra de Araújo, P. Kuznetsov

Brief Announcement: Gathering despite a linear number of weakly Byzantine agents
J. Hirose, J. Nakamura, F. Ooshita, M. Inoue

Brief Announcement: Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
V. Manoharan, V. Ramachandran

Brief Announcement: (1+ϵ)-Approximate Shortest Paths in Dynamic Streams.
C. Trehan, M. Elkin

Brief Announcement: A Hierarchy of Time-Bounded Local Decision
E. Tshuva, R. Oshman

Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver
I. Anagnostides, C. Lenzen, B. Haeupler, G. Zuzic, T. Gouleakis

Brief Announcement: Probabilistic Dynamic Input/Output Automata
P. Civit, M. Potop-Butucaru

Brief Announcement: Holistic Verification of Blockchain Consensus
N. Bertrand, V. Gramoli, M. Lazic, I. Konnov, P. Tholoniat, J. Widder

Brief Announcement: Asynchronous Verifiable Information Dispersal with Near-Optimal Communication
N. Alhaddad, S. Das, S. Duan, L. Ren, M. Varia, Z. Xiang, H. Zhang