Monday, June 16
08:55 – 18:00 | Workshop: Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems (ApPLIED) Room: Cacaluta-Arenal |
10:00 – |
Tutorial: Machine-Verifying Concurrent Algorithms by Siddhartha Jayanti Room: Tangolunda |
10:00 – 12:00 14:30 – 16:30 |
DC Mexico Summer School Room: Conejo |
12:25 – 13:50 | Lunch break at Restaurante Solarium |
18:00 – 21:00 | Welcome cocktail at Salón Maguey |
Tuesday, June 17
PODC Room: Coyote09:00 – 09:05 | Opening remarks |
09:05 – 10:10 | Keynote: Disaggregated Memory and the Revival of Memory Research by Marcos Aguilera |
10:10 – 10:40 | Coffee break |
10:40 – 12:25 | Session 1 (chair: Gregory Chockler) |
12:25 – 13:50 | Lunch break at Restaurante Solarium |
13:50 – 15:35 | Session 2 (chair: Dennis Olivetti) |
15:35 – 16:05 | Coffee break |
16:05 – 17:45 | Session 3 (chair: Alessia Milani) |
18:00 – 19:30 | Business Meeting |
Wednesday, June 18
09:00 – 10:10 | Session 4 (chair: Wojciech Golab) Best Paper Award Session |
10:10 – 10:40 | Coffee Break |
10:40 – 12:25 | Session 5 (chair: Yoram Moses) |
12:25 – 13:50 | Lunch Break at Restaurante Solarium |
13:50 – 15:35 | Session 6 (chair: Rotem Oshman) |
15:35 – 16:05 | Coffee Break |
16:05 – 17:45 | Session 7 (chair: Seth Gilbert) |
19:00 – 21:00 | Banquet at Salón Maguey |
10:00 – 12:00 14:30 – 16:30 |
DC Mexico Summer School Room: Conejo |
Thursday, June 19
PODC Room: Coyote09:00 – 10:10 | Keynote: Examples of Mantras as a Beacon in Guiding Research by Eli Gafni |
10:10 – 10:40 | Coffee Break |
10:40 – 12:25 | Session 8 (chair: Christoph Grunau) |
12:25 – 13:50 | Lunch Break at Restaurante Solarium |
13:50 – 15:35 | Session 9 (chair: Philipp Woelfel) |
15:35 – 16:05 | Coffee Break |
16:05 – 17:45 | Session 10 (chair: Andrea Richa) |
17:45 – 18:00 | Closing Remarks |
Friday, June 20
09:00 – 15:00 | Tutorial: Information Theory and Applications by Rotem Oshman Room: Cacaluta-Arenal |
12:25 – 13:50 | Lunch break at Restaurante Solarium |
10:00 – 12:00 14:30 – 16:30 | DC Mexico Summer School Room: Conejo |
Keynotes
Disaggregated Memory and the Revival of Memory Research
by Marcos K. Aguilera (VMware Research by Broadcom)
Emerging hardware technologies bring exciting new capabilities and challenges to our research menu. One such technology is disaggregated memory. While its roots date back to the early 1990s, it is only now that this technology is getting rolled out. Disaggregated memory allows servers in a data center to share a memory that is externally connected. This form of sharing differs conceptually from traditional shared memory in many ways: performance, fault model, coherence, and the ability to communicate with other mechanisms. These differences open up new applications and research questions on how to best use this memory effectively. In this talk, we explore some recent and ongoing work in this area.
Examples of Mantras as a Beacon in Guiding Research
by Eli Gafni (University of California Los Angeles, eli@cs.ucla.edu)
Not knowing if something can be done and doing it = research.
Doing something knowing it has been done = solving a puzzle.
Deep belief in a mantra that implies that something can be done = transforms doing research into solving puzzles.
Over the years, my research has been guided by a deep belief in certain mantras. To name two:
- The integer 1 is not special in DC – hence “generalized universality.”
- There is no “proliferation of models” in distributed computing (DC) – hence “message adversary.”
My mantras are based on my belief that deterministic DC when formulated cleanly is a branch of mathematics that studies interleaving, and like Mathematics should be structured and elegant.
I will show some mantras in action, by first discussing Shared Memory (SM) as a task and message adversary. I will show that the properties of SM constitute a lattice with a single path at the bottom, and transitive closure (immediate snapshot) at the top. I will then show that the mantra of “asynchrony = synchrony with mobile failures,” removes the anomaly that eventually synchronous Byzantine agreement with signatures requires less than a third faults. The anomaly vanishes if signatures are replaced by the appropriate constraints on a Byzantine message adversary.
Sessions
Session 1 (June 17, 10:40 – 12:25)
Chair: Gregory Chockler
- 10:40 – 11:01: Byzantine Agreement with Predictions (N. Ben-David, M. Dzulfikar, F. Ellen, S. Gilbert)
- 11:01 – 11:22: Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement (P. Civit, M. Dzulfikar, S. Gilbert, R. Guerraoui, J. Komatovic, M. Vidigueira)
- 11:22 – 11:43: Asynchronous Algorand: Reaching Agreement with Near Linear Communication and Constant Expected Time (I. Abraham, E. Chouatt, Y. Gilad, G. Stern, S. Yakoubov)
- 11:43 – 12:04: Communication-Optimal Convex Agreement (D. Ghinea, C. Liu-Zhang, R. Wattenhofer)
- 12:04 – 12:09: Brief Announcement: Extending Asynchronous Byzantine Agreement with Crusader Agreement (M. Mizrahi Erbes, R. Wattenhofer)
- 12:09 – 12:14: Brief Announcement: Towards Round-Optimal Approximate Agreement on Trees (M. Fuchs, D. Ghinea, Z. Parsaeian)
- 12:14 – 12:19: Brief Announcement: Revisiting Lower Bounds for Two-Step Consensus (F. Ryabinin, A. Gotsman, P. Sutra)
- 12:19 – 12:24: Brief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers (M. Anoprenko, P. Kuznetsov, V. Aksenov)
Session 2 (June 17, 13:50 – 15:35)
Chair: Dennis Olivetti
- 13:50 – 14:11: Towards Optimal Deterministic LOCAL Algorithms on Trees (S. Brandt, A. Narayanan)
- 14:11 – 14:32: Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors (M. Bonamy, C. Gavoille, T. Picavet, A. Wesolek)
- 14:32 – 14:53: Nearly-Optimal Distributed Ruling Sets for Trees And High-Girth Graphs (M. Baumecker, Y. Maus, J. Uitto)
- 14:53 – 15:14: Optimal Local Certification on Graphs of Bounded Pathwidth (D. Baterisna, Y. Chang)
- 15:14 – 15:35: A Tight Meta-Theorem for Local Certification of MSO2 Properties Within Bounded Treewidth Graphs (L. Cook, E. Kim, T. Masařík)
Session 3 (June 17, 16:05 – 17:45)
Chair: Alessia Milani
- 16:05 – 16:26: Perfectly-secure Network-agnostic MPC with Optimal Resiliency (S. Patil, A. Patra)
- 16:26 – 16:47: Model Checking and Synthesis for Optimal Use of Knowledge in Consensus Protocols (K. Alpturer, G. Huang, R. van der Meyden)
- 16:47 – 17:18: You Can Lie but Not Deny: SWMR Registers with Signature Properties in Systems with Byzantine Processes (X. Hu, S. Toueg)
- 17:18 – 17:29: DAG-based Consensus with Asymmetric Trust (I. Amores-Sesar, C. Cachin, J. Villacis, L. Zanolini)
- 17:29 – 17:34: Brief Announcement: Towards Scalable YOSO MPC via Packed Secret-Sharing (D. Escudero, E. Masserova, A. Polychroniadou)
- 17:34 – 17:39: Brief Announcement: Distributed Download from an External Data Source in Byzantine Majority Settings (J. Augustine, S. Chatterjee, V. King, M. Kumar, S. Meir, D. Peleg)
- 17:39 – 17:44: Brief Announcement: Fast and Gas-efficient Private Sealed-bid Auctions (J. Ballweg, A. Goharshady, Z. Lin)
Session 4 (June 18, 09:00 – 10:10)
Chair: Wojciech Golab
- 09:00 – 09:22: Improved Byzantine Agreement under an Adaptive Adversary (F. Dufoulon, G. Pandurangan), Best Paper Award
- 09:22 – 09:44: Byzantine Stable Matching (A. Constantinescu, M. Dufay, D. Ghinea, R. Wattenhofer), Best Paper Award
- 09:44 – 10:05: On Interplanetary and Relativistic Distributed Computing (S. Jayanti)
- 10:05 – 10:10: Brief Announcement: Stranger-Free Tasks (E. Gafni, G. Losa, M. Raynal, G. Taubenfeld)
Session 5 (June 18, 10:40 – 12:25)
Chair: Yoram Moses
- 10:40 – 11:01: 3-Majority and 2-Choices with Many Opinions (N. Shimizu, T. Shiraga)
- 11:01 – 11:22: Asynchronous Fault-Tolerant Language Decidability for Runtime Verification of Distributed Systems (A. Castañeda, G. Rodríguez)
- 11:22 – 12:43: Quantum Communication Advantage for Leader Election and Agreement (F. Dufoulon, F. Magniez, G. Pandurangan)
- 11:43 – 12:04: When is Liquid Democracy Possible? (K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, M. Yeo)
- 12:04 – 12:09: Brief Announcement: Using Detectability to Simplify the Design of Concurrent Algorithms for Persistent Memory (A. Fahmy, W. Golab, N. Mittal)
- 12:09 – 12:14: Brief Announcement: Self-Stabilizing Recoverable Mutual Exclusion (W. Golab, E. Schiller)
- 12:14 – 12:19: Brief Announcement: Fast Atomic Snapshot and Asynchronous Latency (J. Bezerra, P. Kuznetsov, L. de Souza)
- 12:19 – 12:24: Brief Announcement: Robust and Scalable Renaming with Subquadratic Bits (S. Bai, X. Fu, Y. Wang, Y. Wang, C. Zheng)
Session 6 (June 18, 13:50 – 15:35)
Chair: Rotem Oshman
- 13:50 – 14:11 : Deterministic Distributed DFS via Cycle Separators in Planar Graphs (B. Jauregui, P. Montealegre, I. Rapaport)
- 14:11 – 14:32: Distributed Maximum Flow in Planar Graphs (Y. Abd-Elhaleem, M. Dory, M. Parter, O. Weimann)
- 14:32 – 14:53: Optimal Distributed Replacement Paths (Y. Chang, Y. Chen, D. Dey, G. Mishra, H. Nguyen, B. Sanchez)
- 14:53 – 15:14: Message Optimality and Message-Time Trade-offs for APSP and Beyond (F. Dufoulon, S. Pai, G. Pandurangan, S. Pemmaraju, P. Robinson)
- 15:14 – 15:19: Brief Announcement: Deciding FO Formulas Efficiently in Congested Networks (F. Fomin, P. Fraigniaud, P. Golovach, P. Montealegre, I. Rapaport, I. Todinca)
- 15:19 – 15:24: Brief Announcement: The Complexity Landscape of Dynamic Distributed Subgraph Finding (Y. Chang, L. Chen, Y. Chen, G. Mishra, M. Yang)
- 15:24 – 15:29: Brief Announcement: Towards Optimal Distributed Delta Coloring (M. Jakob, Y. Maus)
- 15:29 – 15:34: Brief Announcement: Distributed Graph Algorithms with Predictions (J. Boyar, F. Ellen, K. Larsen)
Session 7 (June 18, 16:05 – 17:45)
Chair: Seth Gilbert
- 16:05 – 16:26: All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free (O. Fischer, M. Parter)
- 16:26 – 16:47: Sublinear-Time Sampling of Spanning Trees in the Congested Clique (S. Pemmaraju, S. Roy, J. Sobel)
- 16:47 – 17:08: Density-Dependent Graph Orientation and Coloring in Scalable MPC (M. Ghaffari, C. Grunau)
- 17:08 – 17:29: Round and Communication Efficient Graph Coloring (Y. Chang, G. Mishra, H. Nguyen, F. Salim)
- 17:29 – 17:34: Brief Announcement: Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them (C. Canonne, Y. Li, S. Umboh)
- 17:34 – 17:39: Brief Announcement: New Distributed Interactive Proofs for Planarity: A Matter of Left and Right (Y. Gil, M. Parter)
- 17:39 – 17:44: Brief Announcement: Strong and Hiding Distributed Certification of k-Coloring (A. Modanese, P. Montealegre, M. Ríos-Wilson)
Session 8 (June 19, 10:40 – 12:25)
Chair: Christoph Grunau
- 10:40 – 11:01: Distributed Freeze Tag: a sustainable solution to discover and wake-up a robot swarm (C. Gavoille, N. Hanusse, G. Le Bouder, T. Marcé)
- 11:01 – 11:22: Decentralized Distributed Graph Coloring: Cluster Graphs (M. Flin, M. Halldórsson, A. Nolin)
- 11:22 – 11:43: Minimalist Leader Election Under Weak Communication (R. Vacus, I. Ziccardi)
- 11:43 – 12:04: Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost (A. Balliu, P. Fraigniaud, D. Olivetti, M. Rabie)
- 12:04 – 12:09: Brief Announcement: Towards Energy-Efficient Distributed Agreement (H. Mirault, P. Robinson)
- 12:09 – 12:14: Brief Announcement: Energy-Efficient Maximal Independent Sets in Radio Networks (D. Banasik, V. Dani, F. Dufoulon, A. Gupta, T. Hayes, G. Pandurangan)
- 12:14 – 12:19: Brief Announcement: Optimal Deterministic Rendezvous in Labeled Lines (Y. Bourreau, A. Narayanan, A. Nolin)
- 12:19 – 12:24: Brief Announcement: Rise and Shine Efficiently! The Complexity of Adversarial Wake-up (P. Robinson, M. Tan)
Session 9 (June 19, 13:50 – 15:35)
Chair: Philipp Woelfel
- 13:50 – 14:11: Tight Bounds on Channel Reliability via Generalized Quorum Systems (A. Naser-Pastoriza, G. Chockler, A. Gotsman, F. Ryabinin)
- 14:11 – 14:32: Auditing without Leaks Despite Curiosity (H. Attiya, A. Anta, A. Milani, A. Rapetti, C. Travers)
- 14:32 – 14:53: A Shared Archive of Snapshots (P. Jayanti, S. Jayanti)
- 14:53 – 15:14: An Exact Characterization of the Two-shot Deterministic Objects Solving Two-process Consensuss (M. Nguyen, P. Sutra)
- 15:14 – 15:35: Solvability Characterization for General Three-Process Tasks (H. Attiya, P. Fraigniaud, A. Paz, S. Rajsbaum)
Session 10 (June 19, 16:05 – 17:45)
Chair: Andrea Richa
- 16:05 – 16:26: Clock Distribution with Gradient TRIX (S. Srinivas, C. Lenzen)
- 16:26 – 16:47: Improving Efficiency in Near-State and State-Optimal Self-Stabilising Leader Election Population Protocols (L. Gasieniec, T. Grodzicki, G. Stachowiak)
- 16:37 – 17:08: A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols (H. Austin, P. Berenbrink, T. Friedetzky, T. Götte, L. Hintze)
- 17:08 – 17:29: An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model (A. El-Hayek, R. Elsässer, S. Schmid)
- 17:29 – 17:34: Brief Announcement: Amnesiac Flooding: Easy to Break, Difficult to Escape (H. Austin, M. Gadouleau, G. Mertzios, A. Trehan)
- 17:34 – 17:39: Brief Announcement: Fast and Robust Information Spreading in the Noisy PULL Model (N. D’Archivio, E. Natale, A. Korman, R. Vacus)
- 17:39 – 17:44: Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population ProtocolsT. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid)