Program
Format
DISC 2020 is held online as a virtual event.
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 5 minutes presentations on each paper (3 minutes for brief announcements), followed by Q&A.
Keynote Talks:
There are two keynote talks given by Idit Keidar and Torsten Hoefler. You can find informations about the topics and speakers here.
Junior-Senior Meetings:
You can find a detailed description here.
MoPS Meetings:
Meet other Students and Postdocs. MoPS meetings take place on October 10, 11, 13, 17 and 18. You can find detailed times and a description here.
Ask Me Anything:
The session allows the audience to pose questions to members of the community on a diverse set of topics (“anything”), either through chat or on a dedicated Zulip thread.
Program Overview
All times are in Central European Summer Time = CEST = Berlin time = UTC+02:00.
October 12 (Monday)
October 13 (Tuesday)
October 14 (Wednesday)
October 15 (Thursday)
Detailed Program
All times are in Central European Summer Time = CEST = Berlin time = UTC+02:00.
October 12 (Monday)
| 14:00 – 15:00 |
Junior-senior meeting |
| 15:00 – 16:15 |
Keynote 1
Idit Keidar: Concurrent Big Data Processing – Data Structures & Semantics
(Conference Room DISC) |
| 16:15 – 16:30 |
Break |
| 16:30 – 17:30 |
Session 1 (Conference Room DISC)
Session Chair: Jennifer Welch
- (10 mins) Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols
John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia
Full Video Presentation
Paper
- (10 mins) Improved Extension Protocols for Byzantine Broadcast and Agreement
Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang
Full Video Presentation
Paper
- (10 mins) From Partial to Global Asynchronous Reliable Broadcast
Diana Ghinea, Martin Hirt, and Chen-Da Liu-Zhang
Full Video Presentation
Paper
- (10 mins) Fast agreement in networks with Byzantine nodes
Bogdan S. Chlebus, Dariusz R. Kowalski, and Jan Olkowski
Full Video Presentation
Paper
- (10 mins) Byzantine Lattice Agreement in Synchronous Message Passing Systems
Xiong Zheng and Vijay Garg
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Polygraph: Accountable Byzantine Agreement
Pierre Civit, Seth Gilbert, and Vincent Gramoli
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Optimally-resilient Unconditionally-secure Asynchronous Multi-party Computation Revisited
Ashish Choudhury
Full Video Presentation
Paper
|
| 17:30 – 18:05 |
Break + ASK ME ANYTHING: Alkida Balliu hosting Pierre Fraigniaud
(Conference Room DISC) |
| 18:05 – 19:00 |
Session 2 (Conference Room DISC)
Session Chair: Armando Castañeda
- (10 mins) Intermediate Value Linearizability: A Quantitative Correctness Criterion (Best student paper)
Arik Rinberg and Idit Keidar
Full Video Presentation
Paper
- (10 mins) The Splay-List: A Distribution-Adaptive Concurrent Skip-List
Vitaly Aksenov, Dan Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami
Full Video Presentation
Paper
- (10 mins) Efficient Multi-word Compare and Swap
Rachid Guerraoui, Alex Kogan, Virendra J. Marathe, and Igor Zablotchi
Full Video Presentation
Paper
- (10 mins) LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations using only pointer-width CAS
Guy E. Blelloch and Yuanhao Wei
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Building Fast Recoverable Persistent Data Structures with Montage
Haosen Wen, Wentao Cai, Mingzhe Du, Benjamin Valpey, and Michael L. Scott
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Concurrent Fixed-Size Allocation and Free in Constant Time
Guy E. Blelloch and Yuanhao Wei
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Jiffy: A Fast, Memory Efficient, Wait-Free Multi-Producers Single-Consumer Queue
Dolev Adas and Roy Friedman
Full Video Presentation
Paper
|
| 19:15 – 20:15 |
Junior-senior meeting |
October 13 (Tuesday)
| 14:00 – 15:00 |
MoPS meeting |
| 15:00 – 15:55 |
Session 3 (Conference Room DISC)
Session Chair: Alessia Milani
- (10 mins) Improved Bounds for Distributed Load Balancing (Best paper)
Sepehr Assadi, Aaron Bernstein, and Zachary Langley
Full Video Presentation
Paper
- (10 mins) Message complexity of population protocols
Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric Severson
Full Video Presentation
Paper
- (10 mins) Distributed Computation with Continual Population Growth
Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, and Quentin Soubeyran
Full Video Presentation
Paper
- (10 mins) Spread of Information and Diseases via Random Walks in Sparse Graphs
George Giakkoupis, Hayk Saribekyan, and Thomas Sauerwald
Full Video Presentation
Paper
- (10 mins) Who started this rumor? Quantifying the natural differential privacy of gossip protocols
Aurélien Bellet, Rachid Guerraoui, and Hadrien Hendrikx
Full Video Presentation
Paper
- (5 mins) Brief Announcement: On Decidability of 2-Process Affine Models
Petr Kuznetsov and Thibault Rieutord
Full Video Presentation
Paper
|
| 15:55 – 16:30 |
Break + ASK ME ANYTHING: Achour Mostefaoui hosting Maurice Herlihy
(Conference Room DISC) |
| 16:30 – 17:30 |
Session 4 (Conference Room DISC)
Session Chair: Sebastian Forster
- (10 mins) Distributed Dense Subgraph Detection and Low Outdegree Orientation
Hsin-Hao Su and Hoa T. Vu
Full Video Presentation
Paper
- (10 mins) Improved Hardness of Approximation of Diameter in the CONGEST Model
Ofer Grossman, Seri Khoury, and Ami Paz
Full Video Presentation
Paper
- (10 mins) Improved Distributed Approximations for Maximum Independent Set
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman
Full Video Presentation
Paper
- (10 mins) 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
Full Video Presentation
Paper
- (10 mins) Distributed Maximum Matching Verification in CONGEST
Mohamad Ahmadi and Fabian Kuhn
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Phase Transitions of the k-Majority Dynamics in a Biased Communication Model
Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Distributed Quantum Proofs for Replicated Data
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz
Full Video Presentation
Paper
|
| 17:30 – 17:45 |
Break |
| 17:45 – 19:00 |
Awards + Business Meeting
(Conference Room DISC) |
| 19:00 – 19:30 |
Discussion on Conference Models
(Conference Room DISC) |
| 19:30 – 20:30 |
MoPS meeting |
October 14 (Wednesday)
| 14:00 – 15:00 |
Junior-senior meeting |
| 15:00 – 16:15 |
Keynote 2
Torsten Hoefler: High-performance distributed memory systems – from supercomputers to data centers
(Conference Room DISC) |
| 16:15 – 16:30 |
Break |
| 16:30 – 17:30 |
Session 5 (Conference Room DISC)
Session Chair: Matthias Fitzi
- (10 mins) Making Byzantine Consensus Live
Manuel Bravo, Gregory Chockler, and Alexey Gotsman
Full Video Presentation
Paper
- (10 mins) Leaderless State-Machine Replication: Specification, Properties, Limits
Tuanir França Rezende and Pierre Sutra
Full Video Presentation
Paper
- (10 mins) Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP
Shir Cohen, Idit Keidar, and Alexander Spiegelman
Full Video Presentation
Paper
- (10 mins) Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR
Oded Naor and Idit Keidar
Full Video Presentation
Paper
- (10 mins) Asynchronous Reconfiguration with Byzantine Failures
Petr Kuznetsov and Andrei Tonkikh
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-case Latency
Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Game theoretical framework for analyzing Blockchains Robustness
Paolo Zappalà, Marianna Belotti, Maria Potop-Butucaru, and Stefano Secci
Full Video Presentation
Paper
|
| 17:30 – 18:00 |
Break + ASK ME ANYTHING: Keren Censor Hillel and Seth Gilbert
(Conference Room DISC) |
| 18:00 – 19:00 |
Session 6 (Conference Room DISC)
Session Chair: Boaz Patt-Shamir
- (10 mins) Local Conflict Coloring Revisited: Linial for Lists
Yannic Maus and Tigran Tonoyan
Full Video Presentation
Paper
- (10 mins) Coloring Fast Without Learning Your Neighbors’ Colors
Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin
Full Video Presentation
Paper
- (10 mins) Twenty-Two New Approximate Proof Labeling Schemes
Yuval Emek and Yuval Gil
Full Video Presentation
Paper
- (10 mins) Classification of distributed binary labeling problems
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela
Full Video Presentation
Paper
- (10 mins) The Complexity Landscape of Distributed Locally Checkable Problems on Trees
Yi-Jun Chang
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Distributed Graph Problems through an Automata-theoretic Lens
Yi-Jun Chang, Jan Studený, and Jukka Suomela
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping
Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto
Full Video Presentation
Paper
|
| 19:15 – 20:15 |
Junior-senior meeting |
October 15 (Thursday)
| 14:00 – 15:00 |
Junior-senior meeting |
| 15:00 – 16:00 |
Session 7 (Conference Room DISC)
Session Chair: Christian Scheideler
- (10 mins) Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots
Giuseppe A. Di Luna, Ryuhei Uehara, Giovanni Viglietta, and Yukiko Yamauchi
Full Video Presentation
Paper
- (10 mins) Spiking Neural Networks Through the Lens of Streaming Algorithms
Yael Hitron, Cameron Musco, and Merav Parter
Full Video Presentation
Paper
- (10 mins) Communication Efficient Self-Stabilizing Leader Election
Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, and Yasumasa Tamura
Full Video Presentation
Paper
- (10 mins) Tight Bounds for Deterministic High-Dimensional Grid Exploration
Sebastian Brandt, Julian Portmann, and Jara Uitto
Full Video Presentation
Paper
- (10 mins) Distributed Dispatching in the Parallel Server Model
Guy Goren, Shay Vargaftik, and Yoram Moses
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Reaching Approximate Consensus when Everyone may Crash
Lewis Tseng, Qinzi Zhang, and Yifan Zhang
Full Video Presentation
Paper
- (5 mins) Brief Announcement: What Can(not) Be Perfectly Rerouted Locally
Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan
Full Video Presentation
Paper
|
| 16:00 – 16:15 |
Break |
| 16:15 – 17:10 |
Session 8 (Conference Room DISC)
Session Chair: James Aspnes
- (10 mins) Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
Mohsen Ghaffari, Christoph Grunau, and Ce Jin
Full Video Presentation
Paper
- (10 mins) Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers
Merav Parter
Full Video Presentation
Paper
- (10 mins) Singularly Optimal Randomized Leader Election
Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg
Full Video Presentation
Paper
- (10 mins) Models of Smoothing in Dynamic Networks
Uri Meir, Ami Paz, and Gregory Schwartzman
Full Video Presentation
Paper
- (10 mins) Distributed Planar Reachability in Nearly Optimal Time
Merav Parter
Full Video Presentation
Paper
- (5 mins) Brief Announcement: Multi-Threshold Asynchronous Reliable Broadcast and Consensus
Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang
Full Video Presentation
Paper
|
| 17:10 – 18:00 |
ASK ME ANYTHING with industrial researchers:
Marcos Aguilera, Moti Yung, Dave Dice (Moderator: Dan Alistarh)
(Conference Room DISC) |
