Schedule

High-Level Overview

Monday, July 25th

Tuesday, July 26th

8:30 – 8:40 Opening
8:40 – 9:40 Keynote 1
Michael L. Scott: How Should We Think about Persistent Data Structures?
Coffee break
10:00 – 11:56 Session 1
Lunch
13:30 – 15:14 Session 2
Coffee break
15:35 – 17:30 Session 3
17:30 – 19:30 Business Meeting

Wednesday, July 27th

8:40 – 9:40 Keynote 2
Seny Kamara: Encrypted Distributed Systems
Coffee break
10:00 – 12:01 Session 4
Lunch
13:30 – 15:14 Session 5
Coffee break
15:35 – 17:30 Session 6
Excursion and Banquet
Visit of the archaeological site of Paestum and social dinner in a nearby restaurant

Thursday, July 28th

8:40 – 9:40 Keynote 3
Merav Parter: A Graph Theoretic Approach for Resilient Distributed Algorithms
Coffee break
10:00 – 12:02 Session 7
Lunch
13:30 – 15:03 Session 8
Coffee break
15:25 – 16:34 Session 9
Break
16:50 – 18:05 Session 10

Friday, July 29th

Session Details

Session 1 (Tuesday, July 26th)

10:00 – 10:23 Node and Edge Averaged Complexities of Local Graph Problems. Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Dennis Olivetti.
10:23 – 10:46 Distributed Edge Coloring in Time Polylogarithmic in Δ. Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti.
10:46 – 11:09 Overcoming Congestion in Distributed Coloring. Magnus M. Halldorsson, Alexandre Nolin, Tigran Tonoyan.
11:09 – 11:32 The Landscape of Distributed Complexities on Trees and Beyond. Christoph Grunau, Václav Rozhoň, Sebastian Brandt.
11:32 – 11:38 Brief Announcement: On Polynomial-Time Local Decision. Eden Aldema Tshuva, Rotem Oshman.
11:38 – 11:44 Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds. John Augustine, William K. Moses Jr., Gopal Pandurangan.
11:44 – 11:50 Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear. Antoine El-Hayek, Monika Henzinger, Stefan Schmid.
11:50 – 11:56 Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams. Chhaya Trehan, Michael Elkin.

Session 2 (Tuesday, July 26th)

13:30 – 13:53 A Recursive Early-Stopping Phase King Protocol. Christoph Lenzen, Sahar Sheikholeslami.
13:53 – 14:16 Optimal Synchronous Approximate Agreement with Asynchronous Fallback. Diana Ghinea, Chen-Da Liu-Zhang, Roger Wattenhofer.
14:16 – 14:39 Internet Computer Consensus. Jan Camenisch, Manu Drijvers, Timo Hanke, Yvonne-Anne Pignolet, Victor Shoup, Dominic Williams.
14:39 – 15:02 Perfectly-Secure Synchronous MPC with Asynchronous Fallback Guarantees. Ananya Appan, Anirudh Chandramouli, Ashish Choudhury.
15:02 – 15:08 Brief Announcement: Asynchronous Randomness and Consensus without Trusted Setup. Luciano Freitas De Souza, Petr Kuznetsov, Andrei Tonkikh.
15:08 – 15:14 Brief Announcement: Deterministic Consensus and Checkpointing with Crashes: Time and Communication. Bogdan Chlebus, Dariusz Kowalski, Jan Olkowski.

Session 3 (Tuesday, July 26th)

15:35 – 15:58 A Framework for Distributed Quantum Queries in the CONGEST Model. Tijn de Vos, Joran van Apeldoorn
15:38 – 16:21 Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks. Xudong Wu, Penghui Yao.
16:21 – 16:44 What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs. Laurent Feuilloley, Nicolas Bousquet, Théo Pierron.
16:44 – 17:07 Distributed Computations in Fully-Defective Networks. Keren Censor-Hillel, Shir Cohen, Ran Gelles, Gal Sela.
17:07 – 17:30 Can’t See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners. Omri Kahalon, Hung Le, Lazar Milenković, Shay Solomon.

Session 4 (Wednesday, July 27th)

10:00 – 10:23 Balanced Allocations with the Choice of Noise. Dimitrios Los, Thomas Sauerwald. (Best Student Paper Award)
10:23 – 10:46 The Space Complexity of Consensus from Swap. Sean Ovens. (Best Paper Award)
10:46 – 11:09 Fast and Fair Randomized Wait-Free Locks. Naama Ben-David, Guy E. Blelloch.
11:09 – 11:32 When is Recoverable Consensus Harder Than Consensus? Carole Delporte-Gallet, Panagiota Fatourou, Hugues Fauconnier, Eric Ruppert.
11:32 – 11:55 Blunting an Adversary Against Randomized Concurrent Programs with Linearizable Implementations. Hagit Attiya, Constantin Enea, Jennifer Welch.
11:38 – 11:44 Brief Announcement: Towards a Theory of Wear Leveling in Persistent Data Structures. Xialin Liu, Wojciech Golab.

Session 5 (Wednesday, July 27th)

13:30 – 13:53 Population Protocols for Exact Plurality Consensus: How a small chance of failure helps to eliminate insignificant opinions. Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, Peter Kling.
13:53 – 14:16 Early Adapting to Trends: Self-Stabilizing Information Spread using Passive Communication. Amos Korman, Robin Vacus.
14:16 – 14:39 Near-Optimal Leader Election in Population Protocols on Graphs. Dan Alistarh, Joel Rybicki, Sasha Voitovych.
14:39 – 15:02 State Complexity of Protocols With Leaders. Jérôme Leroux.
15:02 – 15:08 Brief Announcement: Computability and Anonymous Storage-Efficient Consensus with an Abstract MAC Layer. Lewis Tseng, Qinzi Zhang.
15:08 – 15:14 Brief Announcement: The weakest failure detector for genuine atomic multicast. Pierre Sutra.

Session 6 (Wednesday, July 27th)

15:35 – 15:58 Deterministic Near-Optimal Distributed Listing of Cliques. Keren Censor-Hillel, Dean Leitersdorf, David Vulakh.
15:58 – 16:21 Universally-Optimal Distributed Exact Min-Cut. Mohsen Ghaffari, Goran Zuzic.
16:21 – 16:44 Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs. Michal Dory, Mohsen Ghaffari, Saeed Ilchi
16:44 – 17:07 Narrowing the LOCAL–CONGEST Gaps in Sparse Networks via Expander Decompositions. Yi-Jun Chang, Hsin-Hao Su.
17:07 – 17:30 From Switch Scheduling to Datacenter Scheduling: Matching-Coordinated Greed is Good. Shijin Rajakrishnan, Rachit Agarwal, David Shmoys.

Session 7 (Thursday, July 28th)

10:00 – 10:23 Constant-Round Near-Optimal Spanners in Congested Clique. Shiri Chechik, Tianyi Zhang.
10:23 – 10:46 The Laplacian Paradigm in the Broadcast Congested Clique. Tijn de Vos, Sebastian Forster.
10:46 – 11:09 Massively Parallel Computation in a Heterogeneous Regime. Orr Fischer, Adi Horowitz, Rotem Oshman.
11:09 – 11:32 A Massively Parallel Modularity-Maximizing Algorithm With Provable Guarantees. Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic.
11:32 – 11:38 Brief Announcement: Deterministic Massively Parallel Algorithms for Ruling Sets. Shreyas Pai, Sriram V. Pemmaraju.
11:38 – 11:44 Brief Announcement: Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model. Vignesh Manoharan, Vijaya Ramachandran.
11:44 – 11:50
Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver. Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, Themis Gouleakis.
11:50 – 11:56 Brief Announcement: Gathering Despite a Linear Number of Weakly Byzantine Agents. Jion Hirose, Junya Nakamura, Fukuhito Ooshita, Michiko Inoue.
11:56 – 12:02 Brief Announcement: Probabilistic Dynamic Input/Output Automata. Pierre Civit, Maria Potop-Butucaru.

Session 8 (Thursday, July 28th)

13:30 – 13:53 Efficient and Adaptively Secure Asynchronous Binary Agreement via Binding Crusader Agreement. Ittai Abraham, Naama Ben David, Sravya Yandamuri.
13:53 – 14:16 Gradecast in Synchrony and Reliable Broadcast in Asynchrony with Optimal Resilience, Efficiency, and Unconditional Security. Ittai Abraham, Gilad Asharov.
14:16 – 14:39 Balanced Byzantine Reliable Broadcast with Near-Optimal Communication and Improved Computation. Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, Haibin Zhang.
14:39 – 14:45 Brief Announcement: Asynchronous Verifiable Information Dispersal with Near-Optimal Communication. Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, Haibin Zhang.
14:45 – 14:51 Brief Announcement: Make Every Word Count: Adaptive Byzantine Agreement with Fewer Words. Shir Cohen, Idit Keidar, Alexander Spiegelman.
14:51 – 11:50
Brief Announcement: Holistic Verification of Blockchain Consensus. Nathalie Bertrand, Vincent Gramoli, Marijana Lazic, Igor Konnov, Pierre Tholoniat, Josef Widder.
14:57 – 15:03 Brief Announcement: How to Tame Multiple Spending in Decentralized Cryptocurrencies. João Paulo Bezerra de Araújo, Petr Kuznetsov.

Session 9 (Thursday, July 28th)

15:25 – 15:48 Adaptively Secure Single Secret Leader Election from DDH. Dario Catalano, Dario Fiore, Emanuele Giunta.
15:48 – 16:11 Optimal Clock Synchronization with Signatures. Christoph Lenzen, Julian Loss.
16:11 – 16:34 Revisiting the Power of Non-Equivocation in Distributed Protocols. Naama Ben-David, Benjamin Chan, Elaine Shi.

Session 10 (Thursday, July 28th)

16:50 – 17:13 A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement. Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum.
17:13 – 17:36 A Distributed Combinatorial Topology Approach to Arrow’s Impossibility Theorem. Sergio Rajsbaum, Armajac Raventós-Pujol.

17:36 – 17:59

 Parameterized Verification under Release Acquire is PSPACE-complete. Shankaranarayanan Krishna, Adwait Godbole, Roland Meyer, Soham Chakraborty.
17:59 – 18:05 Brief Announcement: Fault Tolerant Coloring of the Asynchronous Cycle. Pierre Fraigniaud, Patrick Lambein-Monette, Mikaël Rabie.

Workshop & Tutorial Details

Workshop – ApPLIED (Monday, July 25th)

8:55 – 9:00 Welcome
9:00 – 10:00 [Keynote] Graph Neural Networks as Application of Distributed Algorithms. Roger Wattenhofer.

10:00 – 10:30

 Coffee Break
10:30 – 11:00

Towards an Approximation-Aware Computational Workflow Framework for Accelerating Large-Scale Discovery Tasks. Michael Johnston and Vassils Vassiliadis.
11:00 – 11:30

Colder than the warm start and warmer than the cold start! Experience the spawn start in FaaS providers. Sashko Ristov, Christian Hollaus, and Mika Hautz.
11:30 – 11:45

Research Summary: Deterministic, Explainable and Efficient Stream Processing. Dimitrios Palyvos-Giannas, Marina Papatriantafilou, and Vincenzo Gulisano.
11:45 – 13:00

Lunch Break
13:00 – 14:00

[Keynote] Cascade: An Edge Computing Platform for Real-time Machine Intelligence. Ken Birman (joint work with Weijia Song, Yuting Yang, Thompson Liu, Andrea Merlina, Thiago Garrett, Roman Vitenberg, Lorenzo Rosa, Aahil Awatramani, and Zheng Wang).
14:00 14:05

Short Break
14:05 – 14:35

DARTS: Distributed IoT Architecture for Real-Time, Resilient and AI-Compressed Workflows. Ragini Gupta, Bo Chen, Shengzhong Liu, Tianshi Wang, Klara Nahrstedt, Tarek Abdelzaher, Sandeep Singh Sandha, Mani Srivastava, Abel Souza, Prashant Shenoy, Jeffrey Smith, Maggie Wigness, and Niranjan Suri.
14:35 – 15:05

Drone-Truck Cooperated Delivery Under Time Varying Dynamics. Arindam Khanda, Federico Corò, and Sajal K Das.
15:05 – 15:10

Short Break
15:10 – 15:40

QUANTAS: Quantitative User-friendly Adaptable Networked Things Abstract Simulator. Joseph Oglio, Kendric Hood, Mikhail Nesterenko, and Sebastien Tixeuil.
15:40 – 16:10

A Roadmap To Post-Moore Era for Distributed Systems. Vincenzo De Maio, Atakan Aral, and Ivona Brandic.
16:10 – 16:40

Coffee Break
16:40 – 17:10

Exploring the use of Strongly Consistent Distributed Shared Memory in 3D NVEs. Theophanis Hadjistasi, Nicolas Nicolaou, and Efstathios Stavrakis.
17:10 – 17:40

A Closer Look at Detectable Objects for Persistent Memory. Mohammad Moridi, Erica Wang, Amelia Cui, and Wojciech Golab.
17:40 – 17:45

Closing

For more details, please see http://www.cse.chalmers.se/~elad/ApPLIED2022/ApPLIED22program.pdf

Workshop – PODL (Monday, July 25th)

9:00 – 9:10 Welcome
9:10 – 9:35 Tissue vs Silicon: Musings on the Future of Deep Learning Hardware and Software. Nir Shavit.

9:35 – 10:00

 Hammer or Gavel. Or How I Learnt to Stop Learning and Love the Old-Fashioned Algorithm. Indranil Gupta.
10:00 – 10:30

Coffee Break
10:30 – 10:55

Asynchronous Distributed Machine Learning. Hagit Attiya.
10:55 – 11:20

A Non-Parametric View of FEDAVG and FEDPROX: Beyond Stationary Points. Lili Su.
11:20 – 11:45

Elastic Consistency: A General Consistency Model for Distributed Optimization. Dan Alistarh.
11:50 – 13:30

Lunch Break
13:30 – 13:55

Frugal Distributed Learning. Anne-Marrie Kermarrec.
13:55 – 14:20

Scaling Up Distributed Learning with System Relaxations: Bagua and Beyond. Ce Zhang.
14:20 – 14:45

Scalable Algorithms for Distributed Principal Component Analysis. Waheed Bajwa.
14:45 – 15:10

Marina: Faster Non-Convex Distributed Learning with Compression. Konstantin Burlachenko.
15:10 – 15:35

On Privacy and Security in Federated Learning. Suhas Diggavi.
15:35 – 16:00

The Role of Momentum in Byzantine Learning. Nirupam Gupta.
16:00 – 16:30

Coffee Break
16:30 – 16:55

Machine Learning without Jeopardizing the Data. Arnaud Grivet Sébert.
16:55 – 17:20

Can Byzantine Learning be Private? Rafael Pinot.
17:20 – 17:30

Closing

For more details, please see https://dcl.epfl.ch/site/podc2022

Workshop – DARe (Friday, July 29th)

9:00 – 9:10 Welcome
9:10 – 10:00 A Brief Introduction to Network Geometry. Marián Boguñá Espinal.

10:00 – 10:30

 Coffee Break
10:30 – 11:20

Catching Up on the Internet Computer. Yvonne-Anne Pignolet.
11:20 – 12:00

TBD
12:00 – 13:30

Lunch Break
13:30 – 14:20

Large Scale Algorithms, Clustering and the MPC Model. Silvio Lattanzi.
14:20 – 15:10

Distributed Discharging: Global Guarantees of Local Behaviors. Marthe Bonamy.
15:10 – 15:20

Closing

 

For more details, please see https://podc-dare.github.io

Tutorial – Dispersion of Mobile Robots (Friday, July 29th)

09:00 – 09:05 Welcome
9:05 – 10:00 Vanilla Setting. Anisur Rahaman Molla.

10:00 – 10:30

 Coffee Break
10:30 – 11:55

Extensions. William K. Moses Jr.
11:55 – 12:00

Closing

For more details, please see https://sites.google.com/view/dispersion-mobilerobots-podc22/