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)
|