Accepted Papers 2020

Regular Papers

1. Improved Bounds for Distributed Load Balancing
   Sepehr Assadi, Aaron Bernstein, and Zachary Langley
   (Best paper)
2. Intermediate Value Linearizability: A Quantitative Correctness Criterion
   Arik Rinberg and Idit Keidar
   (Best student paper)
3. Efficient Multi-word Compare and Swap
   Rachid Guerraoui, Alex Kogan, Virendra J. Marathe, and Igor Zablotchi
4. The Splay-List: A Distribution-Adaptive Concurrent Skip-List
   Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami
5. LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations using only pointer-width CAS
   Guy E. Blelloch and Yuanhao Wei
6. Who started this rumor? Quantifying the natural differential privacy of gossip protocols
   Aurélien Bellet, Rachid Guerraoui, and Hadrien Hendrikx
7. Spread of Information and Diseases via Random Walks in Sparse Graphs
   George Giakkoupis, Hayk Saribekyan, and Thomas Sauerwald
8. Message complexity of population protocols
   Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric Severson
9. Distributed Computation with Continual Population Growth
   Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, and Quentin Soubeyran
10. Spiking Neural Networks Through the Lens of Streaming Algorithms
    Yael Hitron, Cameron Musco, and Merav Parter
11. Communication Efficient Self-Stabilizing Leader Election (Extended Abstract)
    Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, and Yasumasa Tamura
12. Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots
    Giuseppe A. Di Luna, Ryuhei Uehara, Giovanni Viglietta, and Yukiko Yamauchi
13. Tight Bounds for Deterministic High-Dimensional Grid Exploration
    Sebastian Brandt, Julian Portmann, and Jara Uitto
14. Distributed Dispatching in the Parallel Server Model
    Guy Goren, Shay Vargaftik, and Yoram Moses
15. Distributed Dense Subgraph Detection and Low Outdegree Orientation
    Hsin-Hao Su and Hoa T. Vu
16. Local Conflict Coloring Revisited: Linial for Lists
    Yannic Maus and Tigran Tonoyan
17. Classification of distributed binary labeling problems
    Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela
18. The Complexity Landscape of Distributed Locally Checkable Problems on Trees
    Yi-Jun Chang
19. Improved Hardness of Approximation of Diameter in the CONGEST Model
    Ofer Grossman, Seri Khoury, and Ami Paz
20. Twenty-Two New Approximate Proof Labeling Schemes
    Yuval Emek and Yuval Gil
21. Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers
    Merav Parter
22. Singularly Optimal Randomized Leader Election
    Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg
23. Making Byzantine Consensus Live
    Manuel Bravo, Gregory Chockler, and Alexey Gotsman
24. Leaderless State-Machine Replication: Specification, Properties, Limits
    Tuanir França Rezende and Pierre Sutra
25. Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
    Shir Cohen, Idit Keidar, and Alexander Spiegelman
26. Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR
    Oded Naor and Idit Keidar
27. Asynchronous Reconfiguration with Byzantine Failures
    Petr Kuznetsov and Andrei Tonkikh
28. Improved Extension Protocols for Byzantine Broadcast and Agreement
    Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang
29. From Partial to Global Asynchronous Reliable Broadcast
    Diana Ghinea, Martin Hirt, and Chen-Da Liu-Zhang
30. Fast agreement in networks with Byzantine nodes
    Bogdan S. Chlebus, Dariusz R. Kowalski, and Jan Olkowski
31. Byzantine Lattice Agreement in Synchronous Message Passing Systems
    Xiong Zheng and Vijay Garg
32. Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols
    John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia
33. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs
    Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman
34. Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
    Mohsen Ghaffari, Christoph Grunau, and Ce Jin
35. Improved Distributed Approximations for Maximum Independent Set
    Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman
36. Models of Smoothing in Dynamic Networks
    Uri Meir, Ami Paz, and Gregory Schwartzman
37. Distributed Maximum Matching Verification in CONGEST
    Mohamad Ahmadi and Fabian Kuhn
38. Distributed Planar Reachability in Nearly Optimal Time
    Merav Parter
39. Coloring Fast Without Learning Your Neighbors’ Colors
    Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin

Brief Announcements

40. Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping
    Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto
41. Brief Announcement: Distributed Graph Problems through an Automata-theoretic Lens
    Yi-Jun Chang, Jan Studený, and Jukka Suomela
42. Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model
    Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo
43. Brief Announcement: Distributed Quantum Proofs for Replicated Data
    Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz
44. Brief Announcement: Optimally-resilient Unconditionally-secure Asynchronous Multi-party Computation Revisited
    Ashish Choudhury
45. Brief Announcement: Polygraph: Accountable Byzantine Agreement
    Pierre Civit, Seth Gilbert, and Vincent Gramoli
46. Brief Announcement: What Can(not) Be Perfectly Rerouted Locally
    Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan
47. Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-case Latency
    Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang
48. Brief Announcement: Multi-Threshold Asynchronous Reliable Broadcast and Consensus
    Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang
49. Brief Announcement: Game theoretical framework for analyzing Blockchains Robustness
    Paolo Zappalà, Marianna Belotti, Maria Potop-Butucaru, and Stefano Secci
50. Brief Announcement: Jiffy: A Fast, Memory Efficient, Wait-Free Multi-Producers Single-Consumer Queue
    Dolev Adas and Roy Friedman
51. Brief Announcement: Concurrent Fixed-Size Allocation and Free in Constant Time
    Guy E. Blelloch and Yuanhao Wei
52. Brief Announcement: Building Fast Recoverable Persistent Data Structures with Montage
    Haosen Wen, Wentao Cai, Mingzhe Du, Benjamin Valpey, and Michael L. Scott
53. Brief Announcement: Reach Approximate Consensus when Everyone may Crash
    Lewis Tseng, Qinzi Zhang, and Yifan Zhang
54. Brief Announcement: On Decidability of 2-Process Affine Models
    Petr Kuznetsov and Thibault Rieutord