International Symposium on DIStributed Computing (DISC) 2021

Accepted Papers

Regular Papers

  1. Optimal Error-Free Multi-Valued Byzantine Agreement
    Jinyuan Chen (Louisiana Tech University)
  2. Fast Nonblocking Persistence for Concurrent Data Structures
    Wentao Cai, Haosen Wen, Vladimir Maksimovski, Mingzhe Du, Rafaello
    Sanna, Shreif Abdallah, and Michael L. Scott (University of Rochester)
  3. Massively Parallel Correlation Clustering in Bounded Arboricity Graphs
    Davin Choo (ETH Zürich); Mélanie Cambus, Havu Miikonen, and Jara
    Uitto (Aalto University)
  4. Fully Read/Write Fence-Free Work-Stealing with Multiplicity
    Armando Castañeda Rojano and Miguel Angel Piña Avelino (UNAM)
  5. Deterministic Logarithmic Completeness in the Distributed Sleeping Model
    Tzalik Maimon (The Ben Gurion University of The Negev); Leonid
    Barenboim (The Open University of Israel)
  6. Game theoretical framework for analyzing blockchain robustness
    Marianna Belotti (BDTD 60, Caisse des Depots, Cedric, CNAM, Paris,
    France); Maria Potop-Butucaru (LIP6, Sorbonne University, Paris,
    France); Stefano Secci (Cedric, CNAM, Paris); Paolo Zappala (Orange
    Labs, LIA Avignon University)
  7. Deterministic Size Discovery and Topology Recognition in Radio
    Networks with Short Labels
    Adam Gańczorz, Tomasz Jurdziński, and Mateusz Lewko (Institute of
    Computer Science, University of Wrocław); Andrzej Pelc (Département
    d’informatique, Université du Québec en Outaouais)
  8. Frugal Byzantine Computing
    Marcos K. Aguilera and Naama Ben-David (VMware Research); Rachid
    Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi (EPFL)
  9. The Canonical Amoebot Model: Algorithms and Concurrency Control
    Joshua J. Daymude and Andréa W. Richa (Arizona State University);
    Christian Scheideler (Paderborn University)
  10. Detectable Sequential Specifications for Recoverable Shared Objects
    Nan Li and Wojciech Golab (University of Waterloo)
  11. Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions
    Liat Maor and Gadi Taubenfeld (The Interdisciplinary Center (IDC))
  12. Extension-Based Proofs for Synchronous Message Passing
    Yilun Sheng (Institute for Interdisciplinary Information Sciences,
    Tsinghua University); Faith Ellen (University of Toronto)
  13. Singularly Near Optimal Leader Election in Asynchronous Networks
    Shay Kutten (Technion – Israel Institute of Technology); William K.
    Moses Jr. and Gopal Pandurangan (University of Houston); David Peleg
    (Weizmann Institute of Science)
  14. Fast Arrays: Atomic Arrays with Constant Time Initialization
    Siddhartha Jayanti and Julian Shun (MIT)
  15. A tight local algorithm for the minimum dominating set problem in
    outerplanar graphs
    Marthe Bonamy (CNRS, LaBRI, Université de Bordeaux); Linda Cook
    (Princeton University); Carla Groenland (Utrecht University);
    Alexandra Wesolek (Simon Fraser University)
  16. Algorithms for the Minimum Dominating Set Problem in Bounded
    Arboricity Graphs: Simpler, Faster, and Combinatorial
    Adir Morgan and Shay Solomon (Tel Aviv University); Nicole Wein (MIT)
  17. Optimal Communication Complexity of Authenticated Byzantine Agreement
    Atsuki Momose (Nagoya University); Ling Ren (University of Illinois at
  18. Randomized Local Fast Rerouting for Datacenter Networks with Almost
    Optimal Congestion
    Gregor Bankhamer and Robert Elsässer (University of Salzburg); Stefan
    Schmid (University of Vienna)
  19. VBR: Version Based Reclamation
    Gali Sheffi (Technion); Maurice Herlihy (Brown University); Erez
    Petrank (Technion)
  20. Impossibility of Strongly-Linearizable Message-Passing Objects via
    Simulation by Single-Writer Registers
    Hagit Attiya (Technion); Constantin Enea (University Paris Diderot
    (Paris 7)); Jennifer Welch (Texas A&M University)
  21. Improved Weighted Additive Spanners
    Michael Elkin, Yuval Gitlitz, and Ofer Neiman (Ben-Gurion University
    of the Negev)
  22. Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model
    Ioannis Anagnostides (National Technical University of Athens); Themis
    Gouleakis (Max Planck Institute for Informatics)
  23. Tame the Wild with Byzantine Linearizability: Reliable Broadcast,
    Snapshots, and Asset Transfer
    Shir Cohen and Idit Keidar (Technion)
  24. Permissionless and Asynchronous Asset Transfer
    Petr Kuznetsov (LTCI, Télécom Paris, Institut Polytechnique de Paris);
    Yvonne-Anne Pignolet (DFINITY); Pavel Ponomarev (ITMO University);
    Andrei Tonkikh (National Research University Higher School of
  25. Truthful Information Dissemination in General Asynchronous Networks
    Lior Solodkin and Rotem Oshman (Tel Aviv University)
  26. Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention
    Dan Alistarh and Giorgi Nadiradze (IST Austria); Rati Gelashvili (Novi Research)
  27. Wait-free CAS-based Algorithms: the Burden of the Past
    Denis Bédin, François Lépine, Achour Mostéfaoui, Damien Perez, and
    Matthieu Perrin (Université de Nantes)
  28. In Search for an Optimal Authenticated Byzantine Agreement
    Alexander Spiegelman (Novi Research)
  29. Byzantine Consensus with Local Multicast Channels
    Muhammad Samir Khan (University of Illinois at Urbana-Champaign);
    Nitin H. Vaidya (Georgetown University)
  30. Locally Checkable Labelings with Small Messages
    Alkida Balliu (University of Freiburg); Keren Censor-Hillel and Yannic
    Maus (Technion); Dennis Olivetti (University of Freiburg); Jukka
    Suomela (Aalto University)
  31. Ruling Sets in Random Order and Adversarial Streams
    Sepehr Assadi and Aditi Dudeja (Rutgers University)
  32. Broadcast CONGEST Algorithms against Adversarial Edges
    Yael Hitron and Merav Parter (Weizmann Institute of Science)
  33. General CONGEST Compilers against Adversarial Edges
    Yael Hitron and Merav Parter (Weizmann Institute of Science)
  34. Smoothed Analysis of Population Protocols
    Gregory Schwartzman (JAIST); Yuichi Sudo (Hosei University)
  35. Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal
    Matching in Radio Networks
    Varsha Dani (Ronin Institute); Aayush Gupta and Thomas Hayes
    (University of New Mexico); Seth Pettie (University of Michigan)
  36. Efficient Distribution of Quantum Circuits
    Ranjani Sundaram, Himanshu Gupta, and C.R. Ramakrishnan (Stony Brook University)
  37. Time-optimal Loosely-stabilizing Leader Election in Population Protocols
    Yuichi Sudo (Hosei University); Ryota Eguchi (Nagoya Institute of
    Technology); Taisuke Izumi and Toshimitsu Masuzawa (Osaka University)
  38. Efficient CONGEST Algorithms for the Lovász Local Lemma
    Jara Uitto (Aalto University); Yannic Maus (Technion)
  39. Space and Time Bounded Multiversion Garbage Collection
    Naama Ben-David (VMware Research); Guy E. Blelloch (Carnegie Mellon
    University); Panagiota Fatourou (FORTH ICS and University of Crete,
    Greece); Eric Ruppert (York University, Canada); Yihan Sun (University
    of California, Riverside); Yuanhao Wei (Carnegie Mellon University)
  40. The Power of Random Symmetry-Breaking in Nakamoto Consensus
    Lili Su (Northeastern University); Quanquan Liu and Neha Narula (MIT)

Brief Announcements

  1. Brief Announcement: Twins: BFT Systems Made Robust
    S. Bano, A. Sonnino, A. Chursin, D. Perelman, Z. Li, A. Ching, D. Malkhi
  2. Brief Announcement: Revisiting signature-free asynchronous Byzantine consensus
    C. Cachin, L. Zanolini
  3. Brief Announcement: Using Nesting to Push the Limits of Transactional Data Structure Libraries
    G. Assa, H. Meir, G. Gueta, I. Keidar, A. Spiegelman
  4. Brief Announcement: Design and Verification of a Logless Dynamic Reconfiguration Protocol in MongoDB Replication
    W. Schultz, S. Zhou, S. Tripakis
  5. Brief Announcement: On Strong Observational Refinement and Forward Simulation
    John, Simon, Brijesh, Gerhard, Heike
  6. Brief Announcement: Probabilistic Indistinguishability and the Quality of Validity in Byzantine Agreement
    G. Goren, Y. Moses, A. Spiegelman
  7. Brief Announcement: How to Trust Strangers – Composition of Byzantine Quorum Systems
    O. Alpos, C. Cachin, L. Zanolini
  8. Brief Announcement: Accountability and Reconfiguration: Self-Healing Lattice Agreement
    L. Freitas de Souza, P. Kuznetsov, T. Rieutord, S. Tucci-Piergiovanni
  9. Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption
    S. Yandamuri, I. Abraham, K. Nayak, M. Reiter
  10. Brief Announcement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models
    P. Bastide, P. Fraigniaud
  11. Brief Announcement: Fast Graphical Population Protocols
    D. Alistarh, R. Gelashvil, J. Rybicki
  12. Brief Announcement: Auditable Register Emulations
    V. Cogo, A. Bessani
  13. Brief Announcement: Non-blocking Dynamic Unbounded Graphs with Worst-case Amortized Bounds
    B. Chatterjee, S. Peri, M. Sa
  14. Brief Announcement: Crystalline: Fast and Memory Efficient Wait-Free Reclamation
    R. Nikolaev, B. Ravindran
  15. Brief Announcement: Simple Majority Consensus in Networks with Unreliable Communication
    A. Livshits, Y. Shadmi, R. Tamir (Averbuch)
  16. Brief Announcement: Ordered Reliable Broadcast and Fast Ordered Byzantine Consensus for Cryptocurrency
    P. Zarbafian, V. Gramoli
  17. Brief Announcement: Automating and Mechanising Cutoff Proofs for Parameterized Verification of Distributed Protocols
    S. Bhat, K. Nagar
  18. Brief Announcement: Persistent Software Combining
    P. Fatourou, N. Kallimanis, E. Kosmas
  19. Brief Announcement: Local certification of graph decompositions and applications to minor-free classes
    L. Feuilloley, N. Bousquet, T. Pierron
  20. Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees
    R. Latypov, J. Uitto, S. Brandt
  21. Brief Announcement: sinkless orientation is hard also in the supported LOCAL model
    J. Korhonen, A. Paz, S. Schmid, J. Suomela, J. Rybicki