3-6 August 2020, Virtual conference
www.podc.org and @podc_disc on twitter
Format
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.
Overview
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
Schedule
- 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
Session chair: Yuval Emek
- Keynote: “Journeys to the Center of Distributed Computing” (video)
- Rachid Guerraoui
Session: Concurrency
16:45-17:45 CEST
Session chair: Lewis Tseng
- Best Student Paper: An Adaptive Approach to Recoverable Mutual Exclusion (video)
- 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 (video)
- 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 (video)
- 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 (video)
- 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 (video)
- 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 (video)
- Hagit Attiya, Sweta Kumari (Technion)
- Archit Somani (Technion)
- Jennifer LWelch (TAMU)
- Brief Announcement: Why Extension-Based Proofs Fail (video)
- 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 (video)
- Stephen Dolan (OCaml Labs)
Session: Graph Algorithms I
18:00-19:00 CEST
Session chair: Przemek Uznanski
- Best Paper: Exponentially Faster Shortest Paths in the Congested Clique (video)
- Michal Dory (Technion)
- Merav Parter (Weizmann Institute)
- Truly Tight-in-Delta Bounds for Bipartite Maximal Matching and Variants (video)
- Sebastian Brandt (ETH Zurich)
- Dennis Olivetti (University of Freiburg)
- Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets (video)
- Sepehr Assadi (Rutgers University)
- Gillat Kol (Princeton University)
- Rotem Oshman (Tel Aviv University)
- Seeing Far vs Seeing Wide: Volume Complexity of Local Graph Problems (video)
- Will Rosenbaum (Amherst College)
- Jukka Suomela (Aalto University)
- Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity (video)
- Soumyottam Chatterjee (Georgetown University)
- Robert Gmyr (Microsoft)
- Gopal Pandurangan (University of Houston)
- Computing Shortest Paths and Diameter in the Hybrid Network Model (video)
- Philipp Schneider (University of Freiburg)
- Fabian Kuhn (University of Freiburg)
- Massively Parallel Algorithms for Minimum Cut (video)
- Mohsen Ghaffari (ETH Zurich)
- Krzysztof Nowicki (University of Wroclaw)
Tuesday, August 4
Session: Consensus
15:00-16:00 CEST
Session chair: Robert Elsässer
- Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited (video)
- 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 (video)
- Ittai Abraham (VMware Research)
- Danny Dolev (Hebrew University)
- Gilad Stern (Hebrew University)
- Asynchronous Byzantine Approximate Consensus in Directed Networks (video)
- Dimitris Sakavalas (Boston College)
- Lewis Tseng (Boston College)
- Nitin H. Vaidya (Georgetown University)
- On the Subject of Non-Equivocation (video)
- 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 (video)
- Ashish Choudhury (IIIT Bangalore)
- Brief Announcement: On the Significance of Consecutive Ballots in Paxos (video)
- 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 (video)
- Shir Cohen (Technion)
- Idit Keidar (Technion)
- Alexander Spiegelman (Novi)
- Brief Announcement: Byzantine Agreement with Unknown Participants and Failures (video)
- Pankaj Khanchandani (ETH Zurich)
- Roger Wattenhofer (ETH Zurich)
Session: Concurrency, Self-* Algorithms and more
16:15-17:15 CEST
Session chair: Christoph Lenzen
- Recoverable Mutual Exclusion with Constant Amortized RMR Complexity from Standard Primitives (video)
- 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 (video)
- 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 (video)
- Kaile Huang (Nanjing University)
- Yu Huang (Nanjing University)
- Hengfeng Wei (Nanjing University)
- Self-Stabilizing Leader Election in Regular Graphs (video)
- 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 (video)
- Petra Berenbrink (Universität Hamburg)
- George Giakkoupis (INRIA)
- Peter Kling (Universität Hamburg)
- Brief Announcement: Intermediate Value Linearizability: A Quantitative Correctness Criterion (video)
- Arik Rinberg (Technion)
- Idit Keidar (Technion)
- Brief Announcement: On Implementing Software Transactional Memory in the C++ Memory Model (video)
- Matthew Rodriguez (Lehigh University)
- Michael Spear (Lehigh University)
- Brief Announcement: Self-stabilizing Systems in Spite of High Dynamics (video)
- 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 (video)
- Maged M. Michael (Facebook)
Awards session and business meeting
17:30-19:00 CEST
Session chair: Jennifer Welch
Wednesday, August 5
Keynote
15:00-16:30 CEST
Session chair: Christian Cachin
- Keynote: “Population Protocols” (video)
- James Aspnes
Session: Wireless Protocols and Graph Models
16:45-17:45 CEST
Session chair: Andréa Richa
- Distance-2 Coloring in the CONGEST Model (video)
- Magnus M. Halldorsson (Reykjavik University)
- Fabian Kuhn (Freiburg University)
- Yannic Maus (Technion)
- Efficient Deterministic Distributed Coloring with Small Bandwidth (video)
- Philipp Bamberger (University of Freiburg)
- Fabian Kuhn (University of Freiburg)
- Yannic Maus (Technion)
- Want to Gather? No Need to Chatter! (video)
- 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 (video)
- Ali Pourmiri (Macquarie University)
- Bernard Mans (Macquarie University)
- The Energy Complexity of BFS in Radio Networks (video)
- 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 (video)
- 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 (video)
- Haimin Chen (Nanjing University)
- Chaodong Zheng (Nanjing University)
Session: Graph Algorithms II
18:00-19:00 CEST
Session chair: Ami Paz
- Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta (video)
- Alkida Balliu, Fabian Kuhn (University of Freiburg)
- Dennis Olivetti (University of Freiburg)
- On Distributed Listing of Cliques (video)
- Keren Censor-Hillel (Technion)
- François Le Gall (Nagoya University)
- Dean Leitersdorf (Technion)
- How much does randomness help with locally checkable problems? (video)
- Alkida Balliu (University of Freiburg)
- Sebastian Brandt (ETH Zurich)
- Dennis Olivetti (University of Freiburg)
- Jukka Suomela (Aalto University)
- Compact Distributed Certification of Planar Graphs (video)
- 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 (video)
- Sebastian Brandt (ETH Zurich)
- Christoph Grunau (ETH Zurich)
- Vaclav Rozhon (ETH Zurich)
- Multiple Source Replacement Path Problem (video)
- Manoj Gupta (IIT Gandhinagar)
- Rahul Jain (IIT Gandhinagar)
- Nitiksha Modi (IIT Gandhinagar)
- Brief Announcement: Classification of distributed binary labeling problems (video)
- 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 (video)
- Dennis Olivetti (University of Freiburg)
Thursday, August 6
Session: Byzantine Attacks and Consensus
15:00-16:30 CEST
Session chair: Bernardo David
- Genuinely Distributed Byzantine Machine Learning (video)
- 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 (video)
- Nirupam Gupta (Georgetown University)
- Nitin H. Vaidya (Georgetown University)
- Probably Approximately Knowing (video)
- Yoram Moses (Technion)
- Nitzan Zamir (Technion)
- Positive Aging Admits Fast Asynchronous Plurality Consensus (video)
- 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 (video)
- Adam Shimi (IRIT, University of Toulouse)
- Armando Castaneda (UNAM)
- Brief Announcement: On Using Null Messages in a Byzantine Setting (video)
- Guy Goren (Technion)
- Yoram Moses (Technion)
Session: Coordination
16:45-17:45 CEST
Session chair: Jared Saia
- Can Uncoordinated Beeps tell Stories? (video)
- Fabien Dufoulon (Technion – Israel Institute of Technology)
- Janna Burman (Université Paris-Saclay, CNRS, LRI)
- Joffroy Beauquier (Université Paris-Saclay, CNRS, LRI)
- Noisy Beeps (video)
- Klim Efremenko (Ben Gurion University)
- Gillat Kol (Princeton University)
- Raghuvansh RSaxena (Princeton University)
- Perigee: Efficient Peer-to-Peer Network Design for Blockchains (video)
- 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 (video)
- 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 (video)
- Othon Michail (University of Liverpool)
- George Skretas (University of Liverpool)
- Paul Spirakis (University of Liverpool)
- Brief Announcement: Noisy Beeping Networks (video)
- 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 (video)
- 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
Session chair: Alkida Balliu
- Single-Source Shortest Paths in the CONGEST Model with Improved Bound (video)
- Shiri Chechik (Tel Aviv University)
- Doron Mukhtar (Tel Aviv University)
- Distributed Construction of Light Networks (video)
- Michael Elkin (Ben-Gurion University of the Negev)
- Arnold Filtser (Columbia University)
- Ofer Neiman (Ben-Gurion University of the Negev)
- Simple, Deterministic, Constant-Round Coloring in the Congested Clique (video)
- Artur Czumaj (University of Warwick)
- Peter Davies (IST Austria)
- Merav Parter (Weizmann Institute of Science)
- Efficient and Simple Algorithms for Fault Tolerant Spanners (video)
- Michael Dinitz (Johns Hopkins University)
- Caleb Robelle (University of Maryland, Baltimore County)
- Distributed Approximation on Power Graphs (video)
- 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 (video)
- Yuval Efron (Technion)
- Ofer Grossman (MIT)
- Seri Khoury (UC Berkeley)