Programme

Tuesday

Opening

  • 08:40: Opening Remarks

Session 1 (chair: Peter Davies-Peck)

  • 08:45-09:05: Deterministic Distributed Algorithms for Short Disjoint Paths (Mohsen Ghaffari, Hsin-Hao Su)
  • 09:05-09:25: Girth Approximations in the CONGEST Model (Shiri Chechik, Gur Lifshitz, Doron Mukhtar)
  • 09:25-09:45: Distributed Treewidth Computation and Courcelle’s Theorem in the CONGEST Model (Benjamín Jauregui, Jason Li, Pedro Montealegre, Ioan Todinca)
  • 09:45-09:50: Brief Announcement: On Energy Complexity and Multi-Instance Computation in the Congested Clique (Dominick Banasik, Varsha Dani)
  • 09:50-09:55: Brief Announcement: Deterministic Edge Coloring with few Colors in CONGEST (Tijn de Vos, Yannic Maus, Joakim Blikstad)
  • 09:55-10:00: Brief Announcement: 2-Coloring Cycles in One Round (Maxime Flin, Alesya Raevskaya, Ronja Stimpert, Jukka Suomela, Qingxin Yang)

Coffee Break (10:00-10:30)

Session 2 (chair: Naama Ben-David)

  • 10:30-10:50: Simple and Efficient Randomized Wait-Free Locks (Kahbod Aeini, Dante Bencivenga, George Giakkoupis, Philipp Woelfel) Best Paper Award
  • 10:50-11:10: Generalized and Reinitializable Concurrent Fast Arrays (N. Efe Çekirge, Owen Chen, Siddhartha Jayanti, Evan Lucca)
  • 11:10-11:15: Brief Announcement: A Space-Efficient Lock-Free Linear-Probing Hash Table (Hagit Attiya, Rotem Oshman, Noa Schiller)
  • 11:15-11:20: Brief Announcement: Computing Least Fixed Points with Overwrite Semantics in Parallel and Distributed Systems (Vijay K. Garg, Rohan Garg)

Session 3 (chair: Isabella Ziccardi)

  • 11:20-11:40: Undecided State Dynamics with Many Opinions (Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, Takeharu Shiraga)
  • 11:40-12:00: Fast Gossip-Based Rumor Spreading Using Small Messages (Fabien Dufoulon, William K. Moses Jr., Gopal Pandurangan)
  • 12:00-12:20: Complementary Time–Space Tradeoff for Self-Stabilizing Leader Election (Yuichi Sudo)

Lunch Break (12:20-14:00)

Session 4 (chair: Sebastian Brandt)

  • 14:00-14:20: Informative Trains: A Memory-Efficient Journey to a Self-Stabilizing Leader Election Algorithm in Anonymous Graphs (Lélia Blin, Sylvain Gay, Isabella Ziccardi)
  • 14:20-14:40: Early-Stabilizing Counting (Christoph Lenzen, Julian Loss)
  • 14:40-15:00: Gradient Clock Synchronization with Practically Constant Local Skew (Christoph Lenzen)

Session 5 (chair: Gopal Pandurangan)

  • 15:05-15:25: Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes (Arnold Filtser, Orr Fischer)
  • 15:25-15:45: Distributed Algorithms for Potential Problems (Alkida Balliu, Thomas Boudier, Francesco d’Amore, Fabian Kuhn, Dennis Olivetti, Gustav Schmid, Jukka Suomela)
  • 15:45-15:50: Brief Announcement: Exponential Quantum Advantage for Message Complexity in Distributed Algorithms (Maël Luce, Mathieu Roget, Joseph Marchand, François Le Gall)
  • 15:50-15:55: Brief Announcement: Distributed Statistical Zero-Knowledge Proofs via Sumcheck (Benjamín Jauregui, Masayuki Miyamoto)
  • 15:55-16:00: Brief Announcement: Distributed Non-Interactive Zero-Knowledge Proofs (Alex Bredariol Grilo, Ami Paz, Mor Perry)

Coffee Break (16:00-16:25)

Keynote Talk (16:25-17:35): “Parallel Algorithm Engineering Reconsidered” – Peter Sanders (Karlsruhe Insitute of Technology)

Business Meeting (17:45)

Wednesday

Session 6 (chair: Frederik Mallmann-Trenn)

  • 08:40-09:00: From Few to Many Faults: Optimal Adaptive Byzantine Agreement (Andrei Constantinescu, Marc Dufay, Anton Paramonov, Roger Wattenhofer)
  • 09:00-09:20: Reaching Univalency with Subquadratic Communication (Andrew Lewis-Pye)
  • 09:20-09:40: Why Canonical-Round Algorithms Fail for Optimal Byzantine Resilience (Hagit Attiya, Itay Flam, Jennifer Welch)
  • 09:40-09:45: Brief Announcement: Communication Efficient Byzantine Agreement with Predictions (Muhammad Ayaz Dzulfikar, Seth Gilbert)
  • 09:45-09:50: Brief Announcement: BumbleBee: Best-of-Both-Worlds MVBA with Optimal Communication, Latency and Resilience Tradeoffs (Fatima Elsheimy, Simon Kamp)
  • 09:50-09:55: Brief Announcement: What is Agreement About if not Common Knowledge? (Or David, Yoram Moses)
  • 09:55-10:00: Brief Announcement: Byzantine Machine Learning, MultiKrum and an Optimal Notion of Robustness (Gilles Bareilles, Wassim Bouaziz, Julien Fageot, El-Mahdi El-Mhamdi)

Coffee Break (10:00-10:30)

Dijkstra Prize Talk (10:30-11:30): “The Omega(D+sqrt(n)) Lower Bound Story of Distributed Algorithms” – Gopal Pandurangan (University of Houston)

Session 7 (chair: Avery Miller)

  • 11:35-11:55: Efficient Counting and Simulation in Content-Oblivious Rings (Jérémie Chalopin, Yi-Jun Chang, Giuseppe Antonio Di Luna, Haoran Zhou) Best Student Paper Award
  • 11:55-12:00: Brief Announcement: Toward Uniform Content-Oblivious Leader Election on General Graphs (Fabian Frei, Ran Gelles, Ahmed Ghazy, Alexandre Nolin)
  • 12:00-12:20: Distinct Gathering and the Virtue of Self-Consistency (Fabian Frei, Koichi Wada)

Lunch Break (12:20-14:00)

Session 8 (chair: Hagit Attiya)

  • 14:00-14:20: Nearly Quadratic Asynchronous Distributed Key Generation from Recursive Consensus (Ittai Abraham, Renas Bacho, Julian Loss, Gilad Stern)
  • 14:20-14:40: Information-Theoretic Optimistic Verifiable Secret Sharing (Chen-Da Liu-Zhang, Martin Hirt, Emanuele Marsicano)
  • 14:40-15:00: Balanced and Adaptively Secure Asynchronous Common Coin and Byzantine Agreement With Sub-Quadratic Communication (Hanwen Feng, Tiancheng Mai, Qiang Tang)
  • 15:00-15:20: Byzantine Consensus in the Partially Authenticated Setting (Christoph Lenzen, Julian Loss, Kecheng Shi, Benedikt Wagner)
  • 15:20-15:25: Brief Announcement: Cryptographically Secure Domain Extension for Byzantine Agreement with Improved Round Complexity (Ashish Choudhury, Madhav Natarajan H)
  • 15:25-15:30: Brief Announcement: Subcubic Coin Tossing in Asynchrony without PKI (Mose Mizrahi, Roger Wattenhofer)

Coffee Break (15:30-15:55)

Session 9 (chair: Yi-Jun Chang)

  • 15:55-16:15: New Hardness Results for the LOCAL Model via a Simple Self-Reduction (Alkida Balliu, Filippo Casagrande, Francesco d’Amore, Dennis Olivetti)
  • 16:15-16:35: The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size (Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, Timothe Picavet, Gustav Schmid)
  • 16:35-16:40: Brief Announcement: Is a LOCAL Algorithm Computable? (Antonio Cruciani, Avinandan Das, Massimo Equi, Henrik Lievonen, Diep Luong-Le, Augusto Modanese, Jukka Suomela)
  • 16:40-16:45: Brief Announcement: It Does Not Matter How You Define Locally Checkable Labelings (Antonio Cruciani, Avinandan Das, Alesya Raevskaya, Jukka Suomela)
  • 16:45-16:50: Brief Announcement: Fast Deterministic Distributed Degree Splitting (Yannic Maus, Alexandre Nolin, Florian Schager)
  • 16:50-16:55: Brief Announcement: Sinkless Orientation Made Trivial (Alexandre Nolin)

Session 10 (chair: Fabien Dufoulon)

  • 17:00-17:20: Supervised Distributed Computing: Efficiency and Robustness under a Majority of Adversarial Workers (John Augustine, Henning Hillebrandt, Manish Kumar, Christian Scheideler, Julian Werthmann)
  • 17:20-17:40: The Task Completion Problem and its Application to Crash-Resilient Computation (Orr Fischer, Ran Gelles)
  • 17:40-18:00: A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput (Matthias Bentert, Chen Avin, Stefan Schmid)

Barbecue (19:30)

Thursday

Session 11 (chair: Alexandre Nolin)

  • 08:40-09:00: Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition (Peter Davies-Peck)
  • 09:00-09:20: Meta-Theorems for Cuttable Distributed Problems (Marthe Bonamy, Cyril Gavoille, Avinandan Das, Jukka Suomela, Timothé Picavet, Alexandra Wesolek)
  • 09:20-09:40: Distributed Stochastic Graph Algorithms (Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis)
  • 09:40-10:00: Improved Bounds for Distributed Random Walks and Spanning Trees (Gopal Pandurangan, Sriram V. Pemmaraju, Sourya Roy, Joshua Z. Sobel)

Coffee Break (10:00-10:30)

Session 12 (chair: Robin Vacus)

  • 10:30-10:50: Ranking Opinions with Few States in Population Protocols (Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, Stefan Schmid)
  • 10:50-11:10: Order Statistics in Population Protocols via Simple Dynamics (Niccolò D’Archivio, Hind AlMahmoud, Emanuele Natale, Frederik Mallmann-Trenn)
  • 11:10-11:15: Brief Announcement: DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus (Francesco d’Amore, Niccolò D’Archivio, George Giakkoupis, Frédéric Giroire, Emanuele Natale)
  • 11:15-11:20: Brief Announcement: Limit Laws for Consensus Protocols on the Complete Graph (Julian Becker, Konstantinos Panagiotou)

Session 13 (chair: Faith Ellen)

  • 11:20-11:40: Impossibility Results for Strong Linearizability: The Difficulty of Consistent Refereeing (Hagit Attiya, Armando Castañeda, Constantin Enea)
  • 11:40-12:00: Conflict-Freedom as a Progress Condition (Petr Kuznetsov, Pierre Sutra, Guillermo Toyos-Marfurt)
  • 12:00-12:20: Generalized Compare-and-Swap and Space-Efficient Universal Constructions for the Infinite-Arrival Model (Vassos Hadzilacos, Myles Thiessen, Sam Toueg)

Lunch Break (12:20-14:00)

Session 14 (chair: Diana Ghinea)

  • 14:00-14:20: Forget-IT: Optimal Good-Case Latency For Information-Theoretic BFT (Ittai Abraham, Sourav Das, Yuval Efron, Jovan Komatovic)
  • 14:20-14:40: FEAT: Fair and Efficient Adversarial Transaction Ordering (Tien Tuan Anh Dinh, Dakai Kang, Mohammad Sadoghi)
  • 14:40-15:00: Fast Byzantine Total Order Broadcast (Matteo Monti, Martina Camaioni, Pierre-Louis Roman)
  • 15:00-15:05: Brief Announcement: Delay-Optimal Transaction Order Fairness (Zhuo Cai, Amir K. Goharshady)

Session 15 (chair: Eric Ruppert)

  • 15:10-15:30: Distributed Renaming with Subquadratic Bits via Scalable Committee Election (Sirui Bai, Xinyu Fu, Yuyi Wang, Chaodong Zheng)
  • 15:30-15:50: Network-Agnostic Multidimensional Approximate Agreement with Optimal Resilience (Diana Ghinea, Darya Melnyk, Tijana Milentijević)
  • 15:50-16:10: Round and Resilience-Optimal Approximate Agreement on Trees and Block Graphs (Marc Fuchs, Diana Ghinea, Zahra Parsaeian, Joel Rybicki)
  • 16:10-16:15: Brief Announcement: Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience (Michael Yiqing Hu, Hong Yao Alvin Yan, Jialin Li)

Coffee Break (16:15-16:45)

Keynote Talk (16:45-17:55): “Highly Asynchronous Concurrency in Data Structures” – Robert Tarjan (Princeton University)

Closing Remarks (17:55)