Schedule

All times are in Central European Summer Time (CEST = UTC + 2).

Monday, July 26
15:00 – 15:05	Opening Remarks
15:05 – 16:35	Keynote Session: Cynthia Dwork
Break (15 minutes)
16:50 – 17:50	Session 1: Robots, Dynamics, and Population Protocols
Break (15 minutes)
18:05 – 19:05	Session 2: Biological Algorithms, Contention Resolution, and Radio Networks

Tuesday, July 27
15:00 – 15:40	Gem Session: Laurent Feuilloley
Break (5 minutes)
15:45 – 16:30	Session 3: Blockchains
Break (15 minutes)
16:45 – 17:30	Session 4: Shortcuts, Spanners, and Message Complexity
Break (15 minutes)
17:45 – 19:15	Awards Session and Business Meeting

Wednesday, July 28
15:00 – 15:40	Gem Session: Naama Ben-David
Break (5 minutes)
15:45 – 16:30	Session 5: Local Graph Problems
Break (15 minutes)
16:45 – 17:30	Session 6: Byzantine Agreement and Broadcast
Break (15 minutes)
17:45 – 18:30	Session 7: Distributed ML, Topology, and Parallel Algorithms

Thursday, July 29
15:00 – 16:30	Keynote Session: Kyle Kingsbury
Break (15 minutes)
16:45 – 17:30	Session 8: Fault Tolerance, MPC, and Shortest Paths
Break (15 minutes)
17:45 – 18:45	Session 9: Concurrency and Shared Memory
18:45 – 18:50	Closing Remarks

Workshops & Tutorials – Thursday, July 29
19:00 – 21:00	Biological Distributed Algorithms (BDA) – Day 1

Workshops & Tutorials – Friday, July 30
13:00 – 21:00	Distributed Algorithms on Realistic Network Models (DARe)
15:00 – 19:20	Workshop on Advanced Tools, Programming Languages, and Platforms for Implementing and Evaluating Algorithms for Distributed Systems (ApPLIED)
15:00 – 18:00	Byzantine Agreement and Leader Election: From Classical to the Modern
15:00 – 18:00	Interaction-Oriented Programming: An Application Semantics Approach for Engineering Decentralized Applications
17:00 – 19:00	Biological Distributed Algorithms (BDA) – Day 2

Workshops & Tutorials – Saturday, July 31
15:00 – 17:45	Security and Privacy for Distributed Optimization & Distributed Machine Learning

Program

All times are in Central European Summer Time (CEST = UTC + 2).
Click on the time to see it in your own time zone.
Click on the name of a talk to access the paper.
Click on “video” next to a talk to access the long version of the talk.

Monday, July 26

15:00 – 15:05 Opening Remarks

15:05 – 16:35 Keynote Session: Cynthia Dwork

16:50-17:50 Session 1: Robots, Dynamics, and Population Protocols

Session Chair: Gadi Taubenfeld

D. Kirkpatrick, I. Kostitsyna, A. Navarra, G. Prencipe, N. Santoro	Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility	video
K. Altisen, S. Devismes, A. Durand, C. Johnen, F. Petit	On Implementing Stabilizing Leader Election with Weak Assumptions on Network Dynamics	video
J. Burman, H. Chen, H. Chen, D. Doty, T. Nowak, E. Severson, C. Xu	Time-Optimal Self-Stabilizing Leader Election in Population Protocols	video
P. Czerner, J. Esparza	Lower Bounds on the State Complexity of Population Protocols	video
D. Alistarh, M. Töpfer, P. Uznański	Fast and Robust Comparison Dynamics in Population Protocols	video
N. Kang, F. Mallmann-Trenn, N. Rivera	Diversity, Fairness and Sustainability in Population Protocols	video
D. Doty, M. Eftekhari, L. Gąsieniec, E. Severson, G. Stachowiak, P. Uznański	Brief Announcement: A Time and Space Optimal Stable Population Protocol Solving Exact Majority	video

18:05 – 19:05 Session 2: Biological Algorithms, Contention Resolution, and Radio Networks

Session Chair: Boaz Patt-Shamir

A. Clementi, F. d’Amore, G. Giakkoupis, E. Natale	Search via Parallel Lévy Walks on Z^2	video
Y. Emek, E. Keren	A Thin Self-Stabilizing Asynchronous Unison Algorithm with Applications to Fault Tolerant Biological Networks	video
F. Dufoulon, S. Kutten, W. Moses Jr.	Efficient Deterministic Leader Election for Programmable Matter	video
P. Czerner, R. Guttenberg, M. Helfrich, J. Esparza	Decision Power of Weak Asynchronous Models of Distributed Computing	video
S. Gilbert, C. Newport, N. Vaidya, A. Weaver	Contention Resolution with Predictions	video
H. Chen, Y. Jiang, C. Zheng	Tight Trade-off in Contention Resolution without Collision Detection	video
V. Dani, A. Gupta, T. Hayes, S. Pettie	Brief Announcement: Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks	video

Tuesday, July 27

15:00 – 15:40 Gem Session: Laurent Feuilloley

15:45 – 16:30 Session 3: Blockchains

Session Chair: Yoram Moses

Y. Xue, M. Herlihy	Hedging Against Sore Loser Attacks in Cross-Chain Transactions	video
I. Keidar, E. Kokoris-Kogias, O. Naor, A. Spiegelman	All You Need is DAG	video
M. Schett, G. Danezis	Embedding a Deterministic BFT Protocol in a Block DAG	video
R. Gelashvili, L. Kokoris-Kogias, A. Spiegelman, Z. Xiang	Brief Announcement: Be Prepared When Network Goes Bad: An Asynchronous View-Change Protocol	video
N. Ben-David, K. Nayak	Brief Announcement: Classifying Trusted Hardware via Unidirectional Communication	video
M. Rambaud, T. Attema, M. Abspoel	Brief Announcement: Malicious Security Comes for Free in Consensus with Leaders	video
E. Chan, M. Lesani	Brief Announcement: Brokering with Hashed Timelock Contracts is NP-Hard	video

16:45 – 17:30 Session 4: Shortcuts, Spanners, and Message Complexity

Session Chair: Peter Davies

S. Kogan, M. Parter	Low-Congestion Shortcuts in Constant Diameter Graphs	video
M. Ghaffari, B. Haeupler	Low-Congestion Shortcuts for Graphs Excluding Dense Minors	video
M. Dory, O. Fischer, S. Khoury, D. Leitersdorf	Constant-Round Spanners and Shortest Paths in Congested Clique and MPC	video
M. Elkin, S. Matar	Ultra-Sparse Near-Additive Emulators	video
S. Pai, G. Pandurangan, S. Pemmaraju, P. Robinson	Can We Break Symmetry with o(m) Communication?	video
M. Kumar, A. Molla	Brief Announcement: On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement	video

17:45 – 19:15 Awards Session and Business Meeting

Wednesday, July 28

15:00 – 15:40 Gem Session: Naama Ben-David

15:45 – 16:30 Session 5: Local Graph Problems

Session Chair: Ran Gelles

A. Balliu, S. Brandt, D. Olivetti, J. Studený, J. Suomela, A. Tereshchenko	Locally Checkable Problems in Rooted Trees	video
Y. Chang, M. Ghaffari	Strong-Diameter Network Decomposition	video
A. Balliu, S. Brandt, F. Kuhn, D. Olivetti	Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees	video
D. Harris, H. Su, H. Vu	On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition	video
S. Brandt, C. Grunau, V. Rozhon	The Randomized Local Computation Complexity of the Lovász Local Lemma	video

16:45 – 17:30 Session 6: Byzantine Agreement and Broadcast

Session Chair: Alexander Spiegelman

E. Boyle, R. Cohen, A. Goel	Breaking the O(sqrt n)-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party	video
I. Abraham, K. Nayak, L. Ren, Z. Xiang	Good-case Latency of Byzantine Broadcast: a Complete Categorization	video
P. Kuznetsov, A. Tonkikh, Y. Zhang	Revisiting Optimal Resilience of Fast Byzantine Consensus	video
M. Fitzi, C. Liu-Zhang, J. Loss	A New Way to Achieve Round-Efficient Byzantine Agreement	video
G. Stern, I. Abraham, P. Jovanovic, S. Meiklejohn, A. Tomescu, M. Maller	Reaching Consensus for Asynchronous Distributed Key Generation	video
J. Kim, V. Mehta, K. Nayak, N. Shrestha	Brief Announcement: Making Synchronous BFT Protocols Secure in the Presence of Mobile Sluggish Faults	video

17:45 – 18:30 Session 7: Distributed ML, Topology, and Parallel Algorithms

Session Chair: Christian Scheideler

S. Liu, N. Gupta, N. Vaidya	Approximate Byzantine Fault-Tolerance in Distributed Optimization	video
R. Guerraoui, N. Gupta, R. Pinot, S. Rouault, J. Stephan	Differential Privacy and Byzantine Resilience in SGD: Do They Add Up?	video
G. Goren, S. Vargaftik, Y. Moses	Stochastic Coordination in Heterogeneous Load Balancing Systems	video
P. Fraigniaud, R. Gelles, Z. Lotker	The Topology of Randomized Symmetry-Breaking Distributed Computing	video
J. Ledent	Brief Announcement: Variants of Approximate Agreement on Graphs and Simplicial Complexes	video
M. Charikar, W. Ma, L. Tan	Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity	video

Thursday, July 29

15:00 – 16:30 Keynote Session: Kyle Kingsbury

16:45 – 17:30 Session 8: Fault Tolerance, MPC, and Shortest Paths

Session Chair: Valerie King

G. Bodwin, M. Parter	Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs (best paper award)	video
M. Dory, M. Parter	Fault-Tolerant Labeling and Compact Routing Schemes	video
T. Götte, K. Hinnenthal, C. Scheideler, J. Werthmann	Time-Optimal Construction of Overlay Networks	video
A. Czumaj, P. Davies, M. Parter	Improved Deterministic $(Delta+1)$ Coloring in Low-Space MPC	video
A. Czumaj, P. Davies, M. Parter	Component Stability in Low-Space Massively Parallel Computation	video
N. Cao, J. Fineman, K. Russell	Brief Announcement: An Improved Distributed Approximate Single Source Shortest Paths Algorithm	video

17:45 – 18:45 Session 9: Concurrency and Shared Memory

Session Chair: Trevor Brown

K. Brusse, F. Ellen	Reductions and Extension-Based Proofs	video
S. Ovens	The Space Complexity of Scannable Binary Objects	video
V. Hadzilacos, X. Hu, S. Toueg	On Register Linearizability and Termination	video
D. Chan, P. Woelfel	A Tight Lower Bound for the RMR Complexity of Recoverable Mutual Exclusion	video
B. Bashari, P. Woelfel	An Efficient Adaptive Partial Snapshot Implementation	video
N. Li, W. Golab	Brief Announcement: Detectable Sequential Specifications for Recoverable Shared Objects	video
G. Sela, M. Herlihy, E. Petrank	Brief Announcement: Linearizability: A Typo	video
S. Chand, Y. Liu	Brief Announcement: What’s Live? Understanding Distributed Consensus	video

18:45 – 18:50 Closing Remarks

Workshops & Tutorials – Thursday, July 29

19:00 – 21:00 Biological Distributed Algorithms (BDA) – Day 1

Workshops & Tutorials – Friday, July 30

13:00 – 21:00 Distributed Algorithms on Realistic Network Models (DARe)

15:00 – 19:20 Workshop on Advanced Tools, Programming Languages, and Platforms for Implementing and Evaluating Algorithms for Distributed Systems (ApPLIED)