PODC 2020 Program

3-6 August 2020, Virtual conference
www.podc.org and @podc_disc on twitter


PODC 2020 is held online as a virtual event.

Every paper’s talk is pre-recorded and about 20…25min. These talks will be available online, e.g., in a dedicated Youtube Channel. Second, during each conference session, there are live 5-min presentations (3 min for BAs) on each paper, followed by Q&A, and followed by a common discussion among a “panel” of the presenters and the audience. An additional chat is organized for 1-1 exchanges. Each such session takes about 1h.


A 4h-slot is allocated for the online meeting on four days, August 3-6, during the week planned for PODC.

  • Start: 15:00 CEST, 06:00 Pacific, 09:00 Eastern, 13:00 UTC, 22:00 JPN
  • End: 19:00 CEST, 10:00 Pacific, 13:00 Eastern, 17:00 UTC, 02:00 JPN


  • Monday, August 3
    • 15:00-16:30 CEST Opening, Keynote by Rachid Guerraoui, Q&A
    • 16:45-17:45 CEST Session: Concurrency
    • 18:00-19:00 CEST Session: Graph Algorithms I
  • Tuesday, August 4
    • 15:00-16:00 CEST Session: Consensus
    • 16:15-17:15 CEST Session: Concurrency, Self-* Algorithms and more
    • 17:30-19:00 CEST Awards session and business meeting
  • Wednesday, August 5
    • 15:00-16:30 CEST Keynote by James Aspnes and Q&A
    • 16:45-17:45 CEST Session: Wireless Protocols and Graph Models
    • 18:00-19:00 CEST Session: Graph Algorithms II
  • Thursday, August 6
    • 15:00-16:30 CEST Session: Byzantine Attacks and Consensus
    • 16:45-17:45 CEST Session: Coordination
    • 18:00-19:00 CEST Session: Graph Algorithms and CONGEST Model

Detailed Schedule

Monday, August 3

Opening and Keynote
15:00-16:30 CEST

  • Keynote: Rachid Guerraoui, “Journeys to the Center of Distributed Computing”

Session: Concurrency
16:45-17:45 CEST

  • Best Student Paper: An Adaptive Approach to Recoverable Mutual Exclusion
    • Sahil Dhoked (The University of Texas at Dallas)
    • Neeraj Mittal (The University of Texas at Dallas)
  • Upper and Lower Bounds on the Space Complexity of Detectable Objects
    • Ohad Ben-Baruch (Ben-Gurion University)
    • Danny Hendler (Ben-Gurion University)
    • Matan Rusanovsky (Ben-Gurion University & Israel Atomic Energy Commission)
  • Extending the Wait-free Hierarchy to Multi-Threaded Systems
    • Matthieu Perrin (LS2N, Université de Nantes)
    • Achour Mostéfaoui (LS2N, Université de Nantes)
    • Grégoire Bonin (LS2N, Université de Nantes)
  • Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity
    • Ahad Mirza Baig (IST Austria)
    • Danny Hendler (Ben-Gurion University)
    • Alessia Milani (LaBRI – Bordeaux INP)
    • Corentin Travers (LABRI – Bordeaux INP)
  • From Bezout’s Identity to Space-Optimal Election in Anonymous Memory Systems
    • Emmanuel Godard (Aix-Marseille University)
    • Damien Imbs (Aix-Marseille University)
    • Michel Raynal (IRISA)
    • Gadi Taubenfeld (IDC)
  • Brief Announcement: Store-Collect in the Presence of Continuous Churn with Application to Snapshots and Lattice Agreement
    • Hagit Attiya, Sweta Kumari (Technion)
    • Archit Somani (Technion)
    • Jennifer LWelch (TAMU)
  • Brief Announcement: Why Extension-Based Proofs Fail
    • Faith Ellen (University of Toronto)
    • Dan Alistarh (IST Austria)
    • James Aspnes (Yale University)
    • Leqi Zhu (University of Michigan)
    • Rati Gelashvili (University of Toronto)
  • Brief Announcement: The Only Undoable CRDTs are Counters
    • Stephen Dolan (OCaml Labs)

Session: Graph Algorithms I
18:00-19:00 CEST

  • Exponentially Faster Shortest Paths in the Congested Clique
    • Michal Dory (Technion)
    • Merav Parter (Weizmann Institute) BEST PAPER
  • Truly Tight-in-Delta Bounds for Bipartite Maximal Matching and Variants
    • Sebastian Brandt (ETH Zurich)
    • Dennis Olivetti (University of Freiburg)
  • Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
    • Sepehr Assadi (Rutgers University)
    • Gillat Kol (Princeton University)
    • Rotem Oshman (Tel Aviv University)
  • Seeing Far vsSeeing Wide: Volume Complexity of Local Graph Problems
    • Will Rosenbaum (Amherst College)
    • Jukka Suomela (Aalto University)
  • Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity
    • Soumyottam Chatterjee (Georgetown University)
    • Robert Gmyr (Microsoft)
    • Gopal Pandurangan (University of Houston)
  • Computing Shortest Paths and Diameter in the Hybrid Network Model
    • Philipp Schneider (University of Freiburg)
    • Fabian Kuhn (University of Freiburg)
  • Massively Parallel Algorithms for Minimum Cut
    • Mohsen Ghaffari (ETH Zurich)
    • Krzysztof Nowicki (University of Wroclaw)

Tuesday, August 4

Session: Consensus
15:00-16:00 CEST

  • Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited
    • Yuan Lu (New Jersey Institute of Technology)
    • Zhenliang Lu, Qiang Tang (New Jersey Institute of Technology
    • JDD-NJIT-ISCAS Joint Blockchain Lab)
    • Guiling Wang (New Jersey Institute of Technology)
  • Revisiting Asynchronous Fault Tolerant Computation with Optimal Resilience
    • Ittai Abraham (VMware Research)
    • Danny Dolev (Hebrew University)
    • Gilad Stern (Hebrew University)
  • Asynchronous Byzantine Approximate Consensus in Directed Networks
    • Dimitris Sakavalas (Boston College)
    • Lewis Tseng (Boston College)
    • Nitin HVaidya (Georgetown University)
  • On the Subject of Non-Equivocation
    • Mads Frederik Madsen (IT University of Copenhagen)
    • Søren Debois (IT University of Copenhagen)
  • Brief Announcement: Almost-surely Terminating Asynchronous Byzantine Agreement Protocols with a Constant Expected Running Time
    • Ashish Choudhury (IIIT Bangalore)
  • Brief Announcement: On the Significance of Consecutive Ballots in Paxos
    • Eli Goldweber (University of Michigan)
    • Nuda Zhang (University of Michigan)
    • Manos Kapritsos (University of Michigan)
  • Brief Announcement: Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
    • Shir Cohen (Technion)
    • Idit Keidar (Technion)
    • Alexander Spiegelman (Novi)
  • Brief Announcement: Byzantine Agreement with Unknown Participants and Failures
    • Pankaj Khanchandani (ETH Zurich)
    • Roger Wattenhofer (ETH Zurich)

Session: Concurrency, Self-* Algorithms and more
16:15-17:15 CEST

  • Recoverable Mutual Exclusion with Constant Amortized RMR Complexity from Standard Primitives
    • David Yu Cheng Chan (University of Calgary)
    • Philipp Woelfel (University of Calgary)
  • An O(log3/2 n) Parallel Time Population Protocol for Majority with O(logn) States
    • Stav Ben-Nun (Bar-Ilan University)
    • Tsvi Kopelowitz (Bar-Ilan University)
    • Matan Kraus (Bar-Ilan University)
    • Ely Porat (Bar-Ilan University)
  • Fine-grained Analysis on Fast Implementations of Distributed Multi-writer Atomic Registers
    • Kaile Huang (Nanjing University)
    • Yu Huang (Nanjing University)
    • Hengfeng Wei (Nanjing University)
  • Self-Stabilizing Leader Election in Regular Graphs
    • Hsueh-Ping Chen (Department of Electrical Engineering, National Taiwan University)
    • Ho-Lin Chen (Department of Electrical Engineering, National Taiwan University)
  • Brief Announcement: Optimal Time and Space Leader Election in Population Protocols
    • Petra Berenbrink (Universität Hamburg)
    • George Giakkoupis (INRIA)
    • Peter Kling (Universität Hamburg)
  • Brief Announcement: Intermediate Value Linearizability: A Quantitative Correctness Criterion
    • Arik Rinberg (Technion)
    • Idit Keidar (Technion)
  • Brief Announcement: On Implementing Software Transactional Memory in the C++ Memory Model
    • Matthew Rodriguez (Lehigh University)
    • Michael Spear (Lehigh University)
  • Brief Announcement: Self-stabilizing Systems in Spite of High Dynamics
    • Karine Altisen (VERIMAG)
    • Stéphane Devismes (VERIMAG)
    • Anaïs Durand (LIMOS)
    • Colette Johnen (CNRS and UnivBordeaux, LaBRI, Talence, France)
    • Franck Petit (LIP6)
  • Brief Announcement: Hazard Pointer Protection of Structures with Immutable Links
    • Maged M. Michael (Facebook)

Awards session and business meeting
17:30-19:00 CEST

Wednesday, August 5

15:00-16:30 CEST

  • Keynote: James Aspnes, “Population Protocols”

Session: Wireless Protocols and Graph Models
16:45-17:45 CEST

  • Distance-2 Coloring in the CONGEST Model
    • Magnus M. Halldorsson (Reykjavik University)
    • Fabian Kuhn (Freiburg University)
    • Yannic Maus (Technion)
  • Efficient Deterministic Distributed Coloring with Small Bandwidth
    • Philipp Bamberger (University of Freiburg)
    • Fabian Kuhn (University of Freiburg)
    • Yannic Maus (Technion)
  • Want to Gather? No Need to Chatter!
    • Sébastien Bouchard (Université du Québec en Outaouais & Sorbonne Université, CNRS, Inria, LIP6 UMR)
    • Yoann Dieudonné (MIS Lab., Université de Picardie Jules Verne)
    • Andrzej Pelc (Université du Québec en Outaouais)
  • Tight Analysis of Asynchronous Rumor Spreading in Dynamic Networks
    • Ali Pourmiri (Macquarie University)
    • Bernard Mans (Macquarie University)
  • The Energy Complexity of BFS in Radio Networks
    • Yi-Jun Chang (ETH Zürich)
    • Varsha Dani (University of New Mexico)
    • Thomas PHayes (University of New Mexico)
    • Seth Pettie (University of Michigan)
  • Brief Announcement: Improved Distributed Approximations for Maximum-Weight Independent Set
    • Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo)
    • Seri Khoury (UC Berkeley)
    • Aaron Schild (University of Washington)
    • Gregory Schwartzman (National Institute of Informatics, Japan)
  • Brief Announcement: Resource Competitive Broadcast against Adaptive Adversary in Multi-channel Radio Networks
    • Haimin Chen (Nanjing University)
    • Chaodong Zheng (Nanjing University)

Session: Graph Algorithms II
18:00-19:00 CEST

  • Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
    • Alkida Balliu, Fabian Kuhn (University of Freiburg)
    • Dennis Olivetti (University of Freiburg)
  • How much does randomness help with locally checkable problems?
    • Alkida Balliu (University of Freiburg)
    • Sebastian Brandt (ETH Zurich)
    • Dennis Olivetti (University of Freiburg)
    • Jukka Suomela (Aalto University)
  • Simple, Deterministic, Constant-Round Coloring in the Congested Clique
    • Artur Czumaj (University of Warwick)
    • Peter Davies (IST Austria)
    • Merav Parter (Weizmann Institute of Science)
  • Compact Distributed Certification of Planar Graphs
    • Laurent Feuilloley (Universidad de Chile, Chile)
    • Pierre Fraigniaud (CNRS and Université de Paris, France)
    • Pedro Montealegre (Universidad Adolfo Ibanez, Chile)
    • Ivan Rapaport (Universidad de Chile, Chile)
    • Eric Rémila (University of Saint-Etienne, France)
    • Ioan Todinca (University of Orléans, France)
  • Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
    • Sebastian Brandt (ETH Zurich)
    • Christoph Grunau (ETH Zurich)
    • Vaclav Rozhon (ETH Zurich)
  • Multiple Source Replacement Path Problem
    • Manoj Gupta (IIT Gandhinagar)
    • Rahul Jain (IIT Gandhinagar)
    • Nitiksha Modi (IIT Gandhinagar)
  • Brief Announcement: Classification of distributed binary labeling problems
    • Alkida Balliu (University of Freiburg)
    • Sebastian Brandt (ETH Zurich)
    • Yuval Efron (Technion)
    • Juho Hirvonen (Aalto University)
    • Yannic Maus (Technion)
    • Dennis Olivetti (University of Freiburg)
    • Jukka Suomela (Aalto University)
  • Brief Announcement: Round eliminator: a tool for automatic speedup simulation
    • Dennis Olivetti (University of Freiburg)

Thursday, August 6

Session: Byzantine Attacks and Consensus
15:00-16:30 CEST

  • Genuinely Distributed Byzantine Machine Learning
    • El-Mahdi El-Mhamdi (EPFL)
    • Rachid Guerraoui (EPFL)
    • Arsany Guirguis (EPFL)
    • Lê Nguyên Hoang (EPFL)
    • Sébastien Rouault (EPFL)
  • Fault-Tolerance in Distributed Optimization: The Case of Redundancy
    • Nirupam Gupta (Georgetown University)
    • Nitin HVaidya (Georgetown University)
  • Probably Approximately Knowing
    • Yoram Moses (Technion)
    • Nitzan Zamir (Technion)
  • Positive Aging Admits Fast Asynchronous Plurality Consensus
    • Gregor Bankhamer (University of Salzburg)
    • Robert Elsässer (University of Salzburg)
    • Dominik Kaaser (University of Hamburg)
    • Matjaž Krnc (University of Primorska)
  • K set-agreement bounds in round-based models through combinatorial topology
    • Adam Shimi (IRIT, University of Toulouse)
    • Armando Castaneda (UNAM)
  • Brief Announcement: On Using Null Messages in a Byzantine Setting
    • Guy Goren (Technion)
    • Yoram Moses (Technion)

Session: Coordination
16:45-17:45 CEST

  • Can Uncoordinated Beeps tell Stories?
    • Fabien Dufoulon (Technion – Israel Institute of Technology)
    • Janna Burman (Université Paris-Saclay, CNRS, LRI)
    • Joffroy Beauquier (Université Paris-Saclay, CNRS, LRI)
  • Noisy Beeps
    • Klim Efremenko (Ben Gurion University)
    • Gillat Kol (Princeton University)
    • Raghuvansh RSaxena (Princeton University)
  • Perigee: Efficient Peer-to-Peer Network Design for Blockchains
    • Yifan Mao (The Ohio State University)
    • Soubhik Deb (University of Washington Seattle)
    • Shaileshh Bojja Venkatakrishnan (The Ohio State University)
    • Sreeram Kannan (University of Washington Seattle)
    • Kannan Srinivasan (The Ohio State University)
  • DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead
    • Seth Gilbert (NUS Singapore)
    • Gopal Pandurangan (University of Houston)
    • Peter Robinson (City University of Hong Kong)
    • Amitabh Trehan (Loughborough University)
  • Distributed Computation and Reconfiguration in Actively Dynamic Networks
    • Othon Michail (University of Liverpool)
    • George Skretas (University of Liverpool)
    • Paul Spirakis (University of Liverpool)
  • Brief Announcement: Noisy Beeping Networks
    • Yagel Ashkenazi (Bar-Ilan University)
    • Ran Gelles (Bar-Ilan University)
    • Amir Leshem (Bar-Ilan University)
  • Brief Announcement: Deterministic Lower Bound for Dynamic Balanced Graph Partitioning
    • Maciej Pacut (University of Vienna)
    • Mahmoud Parham (University of Vienna)
    • Stefan Schmid (University of Vienna)

Session: Graph Algorithms and CONGEST Model
18:00-19:00 CEST

  • Single-Source Shortest Paths in the CONGEST Model with Improved Bound
    • Shiri Chechik (Tel Aviv University)
    • Doron Mukhtar (Tel Aviv University)
  • On Distributed Listing of Cliques
    • Keren Censor-Hillel (Technion)
    • François Le Gall (Nagoya University)
    • Dean Leitersdorf (Technion)
  • Distributed Construction of Light Networks
    • Michael Elkin (Ben-Gurion University of the Negev)
    • Arnold Filtser (Columbia University)
    • Ofer Neiman (Ben-Gurion University of the Negev)
  • Efficient and Simple Algorithms for Fault Tolerant Spanners
    • Michael Dinitz (Johns Hopkins University)
    • Caleb Robelle (University of Maryland, Baltimore County)
  • Distributed Approximation on Power Graphs
    • Reuven Bar-Yehuda (Technion)
    • Keren Censor-Hillel (Technion)
    • Yannic Maus (Technion)
    • Shreyas Pai (The University of Iowa)
    • Sriram VPemmaraju (The University of Iowa)
  • Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
    • Yuval Efron (Technion)
    • Ofer Grossman (MIT)
    • Seri Khoury (UC Berkeley)