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