39th ACM Symposium on Principles of Distributed Computing
3-7 August 2020, Virtual Online Event

http://www.podc.org/
Twitter: @podc_disc


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.


REGISTRATION

The participation in PODC 2020 is free of charge, but requires registration
at the following link and before August 3:
  http://www.podc.org/podc2020/registration/


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

  Mon, 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 

  Tue, 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

  Wed, 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

  Thu, 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


Mon, August 3 ***************************************************************


15:00-16:30 CEST      Opening, Keynote by Rachid Guerraoui, Q&A


16:45-17:45 CEST      Session: Concurrency

An Adaptive Approach to Recoverable Mutual Exclusion
Sahil Dhoked, Neeraj Mittal (The University of Texas at Dallas)
BEST STUDENT PAPER

Upper and Lower Bounds on the Space Complexity of Detectable Objects
Ohad Ben-Baruch, 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, Achour Mostéfaoui, Grégoire Bonin (LSN, 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, 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, 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)


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

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, Fabian Kuhn (University of Freiburg)

Massively Parallel Algorithms for Minimum Cut
Mohsen Ghaffari (ETH Zurich); Krzysztof Nowicki (University of Wroclaw)



Tue, August 4 *****************************************************************


15:00-16:00 CEST      Session: Consensus

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, Gilad Stern (Hebrew University)

Asynchronous Byzantine Approximate Consensus in Directed Networks 
Dimitris Sakavalas, Lewis Tseng (Boston College); Nitin HVaidya (Georgetown University)

On the Subject of Non-Equivocation 
Mads Frederik Madsen, 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, Nuda Zhang, Manos Kapritsos (University of Michigan)

Brief Announcement: Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
Shir Cohen, Idit Keidar (Technion); Alexander Spiegelman (Novi)

Brief Announcement: Byzantine Agreement with Unknown Participants and Failures 
Pankaj Khanchandani, Roger Wattenhofer (ETH Zurich)


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

Recoverable Mutual Exclusion with Constant Amortized RMR Complexity from Standard Primitives
David Yu Cheng Chan, Philipp Woelfel (University of Calgary)

An O(log3/2 n) Parallel Time Population Protocol for Majority with O(logn) States
Stav Ben-Nun, Tsvi Kopelowitz, Matan Kraus, Ely Porat (Bar-Ilan University)

Fine-grained Analysis on Fast Implementations of Distributed Multi-writer Atomic Registers 
Kaile Huang, Yu Huang, Hengfeng Wei (Nanjing University)

Self-Stabilizing Leader Election in Regular Graphs 
Hsueh-Ping Chen, 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, Idit Keidar (Technion)

Brief Announcement: On Implementing Software Transactional Memory in the C++ Memory Model 
Matthew Rodriguez, Michael Spear (Lehigh University)

Brief Announcement: Self-stabilizing Systems in Spite of High Dynamics 
Karine Altisen, 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)


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



Wed, 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 

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, 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, Bernard Mans (Macquarie University)

The Energy Complexity of BFS in Radio Networks 
Yi-Jun Chang (ETH Zürich); Varsha Dani, 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, Chaodong Zheng (Nanjing University)


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

Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
Alkida Balliu, Fabian Kuhn, 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, Christoph Grunau, Vaclav Rozhon (ETH Zurich)

Multiple Source Replacement Path Problem 
Manoj Gupta, Rahul Jain, 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)



Thu, August 6 *****************************************************************


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

Genuinely Distributed Byzantine Machine Learning 
El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, Lê Nguyên Hoang, Sébastien Rouault (EPFL)

Fault-Tolerance in Distributed Optimization: The Case of Redundancy
Nirupam Gupta, Nitin HVaidya (Georgetown University)

Probably Approximately Knowing 
Yoram Moses, Nitzan Zamir (Technion)

Positive Aging Admits Fast Asynchronous Plurality Consensus 
Gregor Bankhamer, 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, Yoram Moses (Technion)


16:45-17:45 CEST      Session: Coordination

Can Uncoordinated Beeps tell Stories? 
Fabien Dufoulon (Technion - Israel Institute of Technology); Janna Burman, Joffroy Beauquier (Université Paris-Saclay, CNRS, LRI)

Noisy Beeps 
Klim Efremenko (Ben Gurion University); Gillat Kol, 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, George Skretas, Paul Spirakis (University of Liverpool)

Brief Announcement: Noisy Beeping Networks 
Yagel Ashkenazi, Ran Gelles, Amir Leshem (Bar-Ilan University)

Brief Announcement: Deterministic Lower Bound for Dynamic Balanced Graph Partitioning 
Maciej Pacut, Mahmoud Parham, Stefan Schmid (University of Vienna)


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

Single-Source Shortest Paths in the CONGEST Model with Improved Bound 
Shiri Chechik, 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, Keren Censor-Hillel, Yannic Maus (Technion); Shreyas Pai, 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)