International Symposium on DIStributed Computing (DISC) 2020

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

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