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