International Symposium on DIStributed Computing (DISC) 2021

Program

Format

DISC 2021 is held online as a hybrid event. All live talks can be attended and given online through Zoom or physically in Freiburg.

Talks:

Every paper’s talk is pre-recorded and takes 15-25 minutes (10-15 minutes for brief announcements). These talks will be available online on the PODC-DISC Youtube channel.
During each conference session, there are live 7 minutes presentations on each paper (with two minutes for questions) and 3 minutes presentations for brief announcements (with one minute for questions). In each case, one minute of buffer time is left for transitioning between speakers.

Keynote Talks:

There are two keynote talks given by Dahlia Malkhi and Bernhard Haeupler.

Junior-Senior and MoPS (Meet other Postdocs and Students) Meetings:

 

 

Program Overview: Main DISC Conference

All times are in Central European Summer Time = CEST = Berlin time = UTC+02:00.

To access the Zoom sessions, go to the participant access page. The password for this page is mailed to all participants in the “Welcome to DISC 2021” email and it has also been posted in the first welcome message on the #disc2021 stream on the PODC-DISC Zulip platform.

Tuesday, October 5

15:00 – 15:05 Introduction
15:05 – 15:50 Session A
15:50 – 16:25 Session B
16:25 – 16:45 Break
16:45 – 18:00 Keynote by Bernhard Haeupler
18:00 – 18:20 Break
18:20 – 18:50 Session C
18:50 – 19:30 Session D

Wednesday, October 6

14:45 – 15:45 Session E
15:45 – 16:00 Break
16:00 – 16:55 Session F
16:55 – 17:05 Break
17:05 – 17:55 Session G
17:55 – 18:15 Break
18:15- 19:00 Session H
19:00 – 20:00 Business Meeting

Thursday, October 7

14:45 – 15:30 Session I
15:30 – 16:10 Session J
16:10 – 16:30 Break
16:30 – 17:45 Keynote by Dahlia Malkhi
17:45 – 18:00 Break
18:00 – 18:45 Session K
18:45 – 19:15 Session L

 

 

Detailed Program: Main DISC Conference

All times are in Central European Summer Time = CEST = Berlin time = UTC+02:00.

To access the Zoom sessions, go to the participant access page. The password for this page is mailed to all participants in the “Welcome to DISC 2021” email and it has also been posted in the first welcome message on the #disc2021 stream on the PODC-DISC Zulip platform.

Tuesday, October 5

15:00 – 15:05 Introduction: Foreword in the Proceedings
15:05 – 15:50 Session A: Optimality and Byzantine Agreement
Session Chair: Seth Gilbert, Technical Chair: Alkida Balliu

  • In Search for an Optimal Authenticated Byzantine Agreement
    Alexander Spiegelman (Novi Research)
    Full presentation
    Paper
  • Brief Announcement: Ordered Reliable Broadcast and Fast Ordered Byzantine Consensus for Cryptocurrency
    Pouriya Zarbafian (University of Sydney); Vincent Gramoli (University of Sydney and EPFL)
    Full presentation
    Paper
  • Optimal Communication Complexity of Authenticated Byzantine Agreement
    Atsuki Momose (Nagoya University); Ling Ren (University of Illinois at Urbana-Champaign)
    Full presentation
    Paper
  • Brief Announcement: Revisiting signature-free asynchronous Byzantine consensus
    Christian Cachin and Luca Zanolini (University of Bern)
    Full presentation
    Paper
  • Optimal Error-Free Multi-Valued Byzantine Agreement
    Jinyuan Chen (Louisiana Tech University)
    Full presentation
    Paper
  • Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption
    Sravya Yandamuri (Duke University); Ittai Abraham (VMware); Kartik Nayak and Michael Reiter (Duke University)
    Full presentation
    Paper
15:50 – 16:25 Session B: Graph Algorithms
Session Chair: Michal Dory, Technical Chair: Salwa Faour

  • Improved Weighted Additive Spanners
    Michael Elkin, Yuval Gitlitz, and Ofer Neiman (Ben-Gurion University of the Negev)
    Full presentation
    Paper
  • Locally Checkable Labelings with Small Messages
    Alkida Balliu (University of Freiburg); Keren Censor-Hillel (Technion); Yannic Maus (TU Graz); Dennis Olivetti (University of Freiburg); Jukka Suomela (Aalto University)
    Full presentation
    Paper
  • Ruling Sets in Random Order and Adversarial Streams
    Sepehr Assadi and Aditi Dudeja (Rutgers University)
    Full presentation
    Paper
  • Brief Announcement: Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees
    Rustam Latypov and Jara Uitto (Aalto University); Sebastian Brandt (ETH Zurich)
    Full presentation
    Paper
16:25 – 16:45 Break
16:45 – 18:00 Keynote by Bernhard Haeupler
18:00 – 18:20 Break
18:20 – 18:50 Session C: New Models, New Problems
Session Chair: Dennis Olivetti, Technical Chair: Philipp Bamberger

  • The Canonical Amoebot Model: Algorithms and Concurrency Control
    Joshua J. Daymude and Andréa W. Richa (Arizona State University); Christian Scheideler (Paderborn University)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper
  • Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model
    Ioannis Anagnostides (National Technical University of Athens); Themis Gouleakis (Max Planck Institute for Informatics)
    Full presentation
    Paper
18:50 – 19:30 Session D: Network Algorithms
Session Chair: Michal Dory, Technical Chair: Jan Studený

  • 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)
    Full presentation
    Paper
  • Brief Announcement: Accountability and Reconfiguration: Self-Healing Lattice Agreement
    Luciano Freitas de Souza (CEA List); Petr Kuznetsov (LTCI, Télécom Paris, Institut Polytechnique de Paris); Thibault Rieutord and Sara Tucci-Piergiovanni (CEA List)
    Full presentation
    Paper
  • Brief Announcement: Auditable Register Emulations
    Vinicius Vielmo Cogo and Alysson Neves Bessani (LASIGE, Dep. de Informática, Faculdade de Ciências, Universidade de Lisboa)
    Full presentation
    Paper
  • Deterministic Logarithmic Completeness in the Distributed Sleeping Model
    Tzalik Maimon (The Ben Gurion University of The Negev); Leonid Barenboim (The Open University of Israel)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper

Wednesday, October 6

14:45 – 15:45 Session E: Graph Algorithms
Session Chair: Gregory Schwartzman, Technical Chair: Dennis Olivetti

  • Efficient CONGEST Algorithms for the Lovász Local Lemma
    Jara Uitto (Aalto University); Yannic Maus (TU Graz)
    Full presentation
    Paper
  • Brief Announcement: sinkless orientation is hard also in the supported LOCAL model
    Janne H. Korhonen (IST Austria); Ami Paz and Stefan Schmid (University of Vienna); Jukka Suomela (Aalto University); Joel Rybicki (IST Austria)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper
  • Brief Announcement: Local certification of graph decompositions and applications to minor-free classes
    Laurent Feuilloley and Nicolas Bousquet (LIRIS, CNRS, Université Lyon 1); Théo Pierron (LIRIS, Université Lyon 1)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper
  • Brief Announcement: Non-blocking Dynamic Unbounded Graphs with Worst-case Amortized Bounds
    Bapi Chatterjee (IST Austria); Sathya Peri (Indian Institute of Technology Hyderabad); Muktikanta Sa (Telecom-SudParis)
    Full presentation
    Paper
  • Massively Parallel Correlation Clustering in Bounded Arboricity Graphs
    Davin Choo (ETH Zürich); Mélanie Cambus, Havu Miikonen, and Jara Uitto (Aalto University)
    Full presentation
    Paper
  • Brief Announcement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models
    Paul Bastide (ENS Rennes); Pierre Fraigniaud (Université de Paris and CNRS)
    Full presentation
    Paper
15:45 – 16:00 Break
16:00 – 16:55 Session F: Concurrency and Memory Management
Session Chair: Kuba Lacki, Technical Chair: Juho Hirvonen

  • Fast Arrays: Atomic Arrays with Constant Time Initialization
    Siddhartha Jayanti and Julian Shun (MIT)
    Full presentation
    Paper
  • Brief Announcement: Crystalline: Fast and Memory Efficient Wait-Free Reclamation
    Ruslan Nikolaev and Binoy Ravindran (Virginia Tech)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper
  • Brief Announcement: Using Nesting to Push the Limits of Transactional Data Structure Libraries
    Gal Assa (Technion); Hagar Meir (IBM Research); Guy Gueta (Independent Researcher); Idit Keidar (Technion); Alexander Spiegelman (Novi Research)
    Full presentation
    Paper
  • VBR: Version Based Reclamation
    Gali Sheffi (Technion); Maurice Herlihy (Brown University); Erez Petrank (Technion)
    Full presentation
    Paper
  • Brief Announcement: Persistent Software Combining
    Panagiota Fatourou (FORTH ICS and University of Crete, Greece); Nikolaos D. Kallimanis (FORTH ICS); Eleftherios Kosmas (University of Crete, Greece)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper
16:55 – 17:05 Break
17:05 – 17:55 Session G: New Models, New Problems
Session Chair: Yuval Emek, Technical Chair: Chetan Gupta

  • Smoothed Analysis of Population Protocols
    Gregory Schwartzman (JAIST); Yuichi Sudo (Hosei University)
    Full presentation
    Paper
  • Brief Announcement: Fast Graphical Population Protocols
    Dan Alistarh (IST Austria); Rati Gelashvil (University of Toronto); Joel Rybicki (IST Austria)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper
  • Truthful Information Dissemination in General Asynchronous Networks
    Lior Solodkin and Rotem Oshman (Tel Aviv University)
    Full presentation
    Paper
  • Brief Announcement: Simple Majority Consensus in Networks with Unreliable Communication
    Ariel Livshits, Yonatan Shadmi, and Ran Tamir (Averbuch) (Technion – Israel Institute of Technology)
    Full presentation
    Paper
  • Efficient Distribution of Quantum Circuits
    Ranjani Sundaram, Himanshu Gupta, and C.R. Ramakrishnan (Stony Brook University)
    Full presentation
    Paper
17:55 – 18:15 Break
18:15- 19:00 Session H: Award Session
Session Chair: Seth Gilbert, Technical Chair: Philipp Bamberger

  • Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention
    Dan Alistarh and Giorgi Nadiradze (IST Austria); Rati Gelashvili (Novi Research)
    Full presentation
    Paper
  • Broadcast CONGEST Algorithms against Adversarial Edges
    Yael Hitron and Merav Parter (Weizmann Institute of Science)
    Full presentation
    Paper
  • General CONGEST Compilers against Adversarial Edges
    Yael Hitron and Merav Parter (Weizmann Institute of Science)
    Full presentation
    Paper
19:00 – 20:00 Business Meeting

Thursday, October 7

14:45 – 15:30 Session I: Byzantine Agreement and Blockchains
Session Chair: Alex Kogan, Technical Chair: Amirreza Akbari

  • Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer
    Shir Cohen and Idit Keidar (Technion)
    Full presentation
    Paper
  • 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 Economics)
    Full presentation
    Paper
  • Brief Announcement: How to Trust Strangers – Composition of Byzantine Quorum Systems
    Orestis Alpos, Christian Cachin, and Luca Zanolini (University of Bern)
    Full presentation
    Paper
  • The Power of Random Symmetry-Breaking in Nakamoto Consensus
    Lili Su (Northeastern University); Quanquan Liu and Neha Narula (MIT)
    Full presentation
    Paper
  • Brief Announcement: Twins: BFT Systems Made Robust
    Shehar Bano, Alberto Sonnino, Andrey Chursin, Dmitri Perelman, Zekun Li, Avery Ching, and Dahlia Malkhi (Facebook Novi)
    Full presentation
    Paper
  • Brief Announcement: Probabilistic Indistinguishability and the Quality of Validity in Byzantine Agreement
    Guy Goren and Yoram Moses (Technion IIT); Alexander Spiegelman (Novi Research)
    Full presentation
    Paper
15:30 – 16:10 Session J: Concurrent Algorithms and Data Structures
Session Chair: Naama Ben-David, Technical Chair: Shreyas Pai

  • 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)
    Full presentation
    Paper
  • Fully Read/Write Fence-Free Work-Stealing with Multiplicity
    Armando Castañeda Rojano and Miguel Angel Piña Avelino (UNAM)
    Full presentation
    Paper
  • Detectable Sequential Specifications for Recoverable Shared Objects
    Nan Li and Wojciech Golab (University of Waterloo)
    Full presentation
    Paper
  • Constant RMR Group Mutual Exclusion for Arbitrarily Many Processes and Sessions
    Liat Maor and Gadi Taubenfeld (The Interdisciplinary Center (IDC))
    Full presentation
    Paper
16:10 – 16:30 Break
16:30 – 17:45 Keynote by Dahlia Malkhi
17:45 – 18:00 Break
18:00 – 18:45 Session K: Message Passing and Lower Bounds
Session Chair: Jennifer Welch, Technical Chair: Darya Melnyk

  • Extension-Based Proofs for Synchronous Message Passing
    Yilun Sheng (Institute for Interdisciplinary Information Sciences,Tsinghua University); Faith Ellen (University of Toronto)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper
  • Brief Announcement: On Strong Observational Refinement and Forward Simulation
    John (Derrick); Simon (Doherty); Brijesh (Dongol); Gerhard (Schellhorn); Heike (Wehrheim)
    Full presentation
    Paper
  • Brief Announcement: Design and Verification of a Logless Dynamic Reconfiguration Protocol in MongoDB Replication
    William Schultz (Northeastern University); Siyuan Zhou (MongoDB); Stavros Tripakis (Northeastern University)
    Full presentation
    Paper
  • Brief Announcement: Automating and Mechanising Cutoff Proofs for Parameterized Verification of Distributed Protocols
    Shreesha Bhat and Kartik Nagar (Department of CSE, IIT Madras)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper
18:45 – 19:15 Session L: Byzantine Agreement and Blockchains
Session Chair: Seth Gilbert, Technical Chair: Marc Fuchs

  • Byzantine Consensus with Local Multicast Channels
    Muhammad Samir Khan (University of Illinois at Urbana-Champaign); Nitin H. Vaidya (Georgetown University)
    Full presentation
    Paper
  • 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)
    Full presentation
    Paper
  • Frugal Byzantine Computing
    Marcos K. Aguilera and Naama Ben-David (VMware Research); Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi (EPFL)
    Full presentation
    Paper

Workshop Overview and Workshop Programs