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 (LSN, 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)