High-Level Overview
Monday, July 25th
- Workshop: Workshop on Advanced Tools, Programming Languages, and Platforms for Implementing and Evaluating Algorithms for Distributed Systems (ApPLIED)
- Workshop: Principles of Distributed Learning (PODL)
- PODC reception
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
- Workshop: 2nd Workshop on Distributed Algorithms on Realistic Network Models
- Tutorial: Dispersion of Mobile Robots
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/