International Symposium on DIStributed Computing (DISC) 2022

Program

Format

DISC 2022 is held both in-person and online as a hybrid event. All live talks can be attended and given online through Zoom or physically at the Georgia Cyber Center.

Talks:

Every regular paper has a slot of 20 minutes and every brief announcement a slot of 10 minutes, including questions.

Keynote Talks:

There are three keynote talks given by Sepehr Assadi, Roberto Baldoni, and Jennifer Welch.

 

 

Detailed Program: Main DISC Conference

All times are in US Eastern Daylight Time = EDT = UTC-04:00 but use 24-hour format

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 2022” email and it has also been posted in the first welcome message on the #disc2022 stream on the PODC-DISC Zulip platform.

Tuesday, October 25

08:50 – 09:00 Welcome address by Christian Scheideler and Alexander Schwarzmann
09:00 – 10:00 Keynote by Roberto Baldoni
Session Chair: Alexander Schwarzmann
10:00 – 10:30 Coffee Break
10:30 – 11:40 Session 1: Consensus
Session Chair: TBA

  • Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira
    Byzantine Consensus is Theta(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!
  • Youer Pu, Lorenzo Alvisi, and Ittay Eyal
    Safe Permissionless Consensus
  • Petr Kuznetsov, Luciano Freitas de Souza, and Andrei Tonkikh
    Distributed Randomness from Approximate Agreement
  • Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern
    Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults
11:40 – 11:50 Break
11:50 – 12:30 Session 2: Routing
Session Chair: TBA

  • Will Rosenbaum
    Packet Forwarding with a Locally Bursty Adversary
  • Anatoliy Zinovyev
    Space-Stretch Tradeoff in Routing Revisited.
12:30 – 14:00 Lunch
14:00 – 15:30 Session 3: Network Algorithms I
Session Chair: TBA

  • Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin
    Fast Distributed Vertex Splitting With Applications
  • Merav Parter and Asaf Petruschka
    Near-Optimal Distributed Computation of Small Vertex Cuts
  • Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis
    Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
  • Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg
    An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
  • Sharareh Alipour and Mohammadhadi Salari
    Brief Announcement: Distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach
15:30 – 16:00 Coffee Break
16:00 – 17:20 Session 4: Wireless Networks and BAs
Session Chair: TBA

  • Hadi Khodabandeh and David Eppstein
    Distributed Construction of Lightweight Spanners for Unit Ball Graphs
  • Varsha Dani and Thomas Hayes
    How to Wake Up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks
  • Gianluca De Marco, Dariusz Kowalski, and Grzegorz Stachowiak
    Contention Resolution without Collision Detection: Constant Throughput and Logarithmic Energy
  • Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko
    Brief Announcement: Temporal Locality in Online Algorithms
  • Francois Le Gall, Masayuki Miyamoto, and Harumichi Nishimura
    Brief Announcement: Distributed Quantum Interactive Proofs
17:20 – 17:30 Break
17:30 – 19:00 Business Meeting

Wednesday, October 26

09:00 – 10:00 Keynote by Jennifer Welch
Session Chair: Christian Scheideler
10:00 – 10:30 Coffee Break
10:30 – 11:40 Session 5: Verification
Session Chair: TBA

  • Gal Amram, Avi Hayoun, Lior Mizrahi, and Gera Weiss
    Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure
  • Nathalie Bertrand, Vincent Gramoli, Igor Konnov, Marijana Lazic, Pierre Tholoniat, and Josef Widder
    Holistic Verification of Blockchain Consensus
  • Pierre Civit and Maria Potop-Butucaru
    Dynamic Probabilistic Input Output Automata
  • Naama Ben-David, Michal Friedman, and Yuanhao Wei
    Brief Announcement: Survey of Persistent Memory Correctness Conditions
11:40 – 11:50 Break
11:50 – 12:30 Session 6: Massive Parallel Computing
Session Chair: TBA

  • Rustam Latypov, Jara Uitto, Dennis Olivetti, Alkida Balliu, Yannic Maus, Manuela Fischer, and Sebastian Brandt
    Exponential Speedup Over Locality in MPC with Optimal Memory
  • Manuela Fischer, Jeff Giliberti, and Christoph Grunau
    Improved Deterministic Connectivity in Massively Parallel Computation
12:30 – 14:00 Lunch
14:00 – 15:30 Session 7: Byzantine and Crash Failures
Session Chair: TBA

  • Manuel Bravo, Gregory Chockler, and Alexey Gotsman
    Liveness and Latency of Byzantine State-Machine Replication
  • Timothé Albouy, Davide Frey, Michel Raynal, and Francois Taiani
    Good-case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case
  • Martina Camaioni, Rachid Guerraoui, Matteo Monti, and Manuel Vidigueira
    Oracular Byzantine Reliable Broadcast
  • Pierre Sutra
    The Weakest Failure Detector for Genuine Atomic Multicast
  • Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard, and Florian Suri-Payer
    Brief Announcement: It’s Not Easy to Relax: Liveness in Chained BFT Protocols
15:30 – 16:00 Coffee Break
16:00 – 17:30 Session 8: Labeling Schemes
Session Chair: TBA

  • Yuval Emek, Yuval Gil, and Shay Kutten
    Locally Restricted Proof Labeling Schemes
  • Merav Parter and Asaf Petruschka
    Optimal Dual Vertex Failure Connectivity Labels
  • Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studený, and Jukka Suomela
    Efficient Classification of Locally Checkable Problems in Regular Trees
  • Subhash Bhagat and Andrzej Pelc
    How to Meet at a Node of any Connected Graph
  • Raissa Nataf, Guy Goren, and Yoram Moses
    Brief Announcement: Null Messages, Information and Coordination
17:30 – 18:00 Break
18:00 – 21:00 Excursion and Banquet

Thursday, October 27

09:00 – 10:00 Keynote by Sepehr Assadi
Session Chair: TBA
10:00 – 10:30 Coffee Break
10:30 – 11:40 Session 9: Network Algorithms II
Session Chair: TBA

  • Philipp Schneider and Fabian Kuhn
    Routing Schemes and Distance Oracles in the Hybrid Model
  • Yael Hitron, Merav Parter, and Eylon Yogev
    Broadcast CONGEST Algorithms Against Eavesdroppers
  • John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, and Yadu Vasudev
    Byzantine Connectivity Testing in the Congested Clique
  • Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos Wilson, and Ioan Todinca
    Brief Announcement: Computing Power of Hybrid Models in Synchronous Networks
11:40 – 11:50 Break
11:50 – 12:30 Session 10: Moving and Computing
Session Chair: TBA

  • Leszek Gasieniec, Paul Spirakis, and Grzegorz Stachowiak
    Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols
  • Irina Kostitsyna, Tom Peters, and Bettina Speckmann
    Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter
  • Shunhao Oh, Dana Randall, and Andrea Richa
    Brief Announcement: Foraging in Particle Systems via Self-Induced Phase Changes
  • Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa
    Brief Announcement: Gathering Despite Defected View
12:30 – 14:00 Lunch
14:00 – 15:20 Session 11: Shared Memory
Session Chair: TBA

  • Sean Ovens
    The Space Complexity of Scannable Objects with Bounded Components
  • Chryssis Georgiou, Nicolas Nicolaou, and Andria Trigeorgi
    Fragmented ARES: Dynamic Storage for Large Objects
  • Xing Hu and Sam Toueg
    On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures
  • Jacob Nelson-Slivon, Lewis Tseng, and Roberto Palmieri
    Brief Announcement: Asymmetric Mutual Exclusion for RDMA
  • Rosina Kharal and Trevor Brown
    Brief Announcement: Benchmarking the Benchmarks: Discovering the Source of Performance Differences in Concurrent Microbenchmarks
15:20 – 15:50 Coffee Break
15:50 – 17:00 Session 12: Diverse Topics
Session Chair: TBA

  • Pierre Fraigniaud, Mikaël Rabie, and Patrick Lambein-Monette
    Fault Tolerant Coloring of the Asynchronous Cycle
  • Oded Naor and Idit Keidar
    On Payment Channels in Asynchronous Money Transfer Systems
  • Michael Dinitz, Jeremy Fineman, Seth Gilbert, and Calvin Newport
    Smoothed Analysis of Information Spreading in Dynamic Networks
  • Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid
    Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies.
17:30 – 19:30 Excursion

Workshop Overview and Workshop Programs