International Symposium on DIStributed Computing (DISC) 2018


The online publication is also available.

The DISC conference and workshops will take place at Hampton Inn & Suites New Orleans-Convention Center 1201 Convention Center Blvd.

  • Sessions are located in Riverside I&II
  • Workshops are located in Dauphine I&II

The welcome reception will take place on Monday, October 15, at 18:00.
The conference banquet will start on Wednesday, October 17, at 18:00.

Monday, October 15

During the Day ADGA: Workshop on Advances in Distributed Graph Algorithms
18:00 DISC welcome reception.

Tuesday, October 16

8:00 Registration: registration desk open throughout the day
Session 1A: 8:30 – 10:45 (Distributed Storage)
Session Chair: U. Schmid
8:30 – 9:30 Keynote talk
Challenges for Machine Learning on Distributed Platforms
Tom Goldstein
9:30 – 9:50 Co-Best Paper: Multi-Shot Distributed Transaction Commit
Gregory Chockler and Alexey Gotsman
9:50 – 10:10 Integrated Bounds for Disintegrated Storage
Alon Berger, Idit Keidar and Alexander Spiegelman
10:10 – 10:30 Order out of Chaos: Proving Linearizability Using Local Views
Yotam M. Y. Feldman, Constantin Enea, Adam Morrison, Noam Rinetzky and Sharon Shoham
10:30 – 10:38 Brief Announcement: Generalising Concurrent Correctness to Weak Memory
Simon Doherty, Brijesh Dongol, Heike Wehrheim and John Derrick
10:38 – 10:45 Brief Announcement: On the impossibility of detecting concurrency
Éric Goubault, Jérémy Ledent and Samuel Mimram
10:45 – 11:15 Break
Session 1B: 11:15 – 12:23 (Shared Memory Systems)
Session Chair: I. Keidar
11:15 – 11:35 Allocate-On-Use Space Complexity of Shared-Memory Algorithms
James Aspnes, Bernhard Haeupler, Alexander Tong and Philipp Woelfel
11:35 – 11:55 NUMASK: High Performance Scalable Skip List for NUMA
Henry Daly, Ahmed Hassan, Michael Spear and Roberto Palmieri
11:55 – 12:15 An Almost Tight RMR Lower Bound for Abortable Test-And-Set
Aryaz Eghbali and Philipp Woelfel
12:15 – 12:23 Brief Announcement: Fast and Scalable Group Mutual Exclusion
Shreyas Gokhale and Neeraj Mittal
12:23 – 14:00 Lunch Break
Session 1C: 14:00 – 15:15 (Graph Algorithms 1)
Session Chair: C. Newport
14:00 – 14:20 Almost Global Problems in the LOCAL Model
Alkida Balliu, Sebastian Brandt, Dennis Olivetti and Jukka Suomela
14:20 – 14:40 Local verification of global proofs
Laurent Feuilloley and Juho Hirvonen
14:40 – 15:00 Redundancy in Distributed Proofs
Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz and Mor Perry
15:00 – 15:08 Brief Announcement: Local Distributed Algorithms in Highly Dynamic Networks
Philipp Bamberger, Fabian Kuhn and Yannic Maus
15:08 – 15:15 Brief Announcement: Exact size counting in uniform population protocols in nearly logarithmic time
David Doty, Mahsa Eftekhari, Othon Michail, Paul Spirakis and Michail Theofilatos
15:15 – 15:45 Break
Session 1D: 15:45 – 17:05 (Graph Algorithms 2)
Session Chair: N. Santoro
15:45 – 16:05 Distributed Set Cover Approximation: Primal-Dual with Optimal Locality
Guy Even, Mohsen Ghaffari and Moti Medina
16:05 – 16:25 Distributed Recoloring
Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela and Jara Uitto
16:25 – 16:45 Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping
Mohsen Ghaffari and Fabian Kuhn
16:45 – 17:05 Time-Message Trade-offs in Distributed Algorithms
Robert Gmyr and Gopal Pandurangan
17:05 Happy hour
17:30 Business Meeting

Wednesday, October 17

8:00 Registration: registration desk open throughout the day
Session 2A: 8:30 – 10:10 (Multi-Agent Systems)
Session Chair: Y. Moses
8:30 – 9:30 Keynote talk
Autonomous Vehicles: From Individual Navigation to Challenges of Distributed Swarms
Sándor P. Fekete
9:30 – 9:50 A Tight Bound for Semi-Synchronous Collaborative Grid Exploration
Sebastian Brandt, Jara Uitto and Roger Wattenhofer
9:50 – 10:10 TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility and its Applications
Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro and Giovanni Viglietta
10:10 – 10:40 Break
Session 2B: 10:40 – 12:03 (Wireless Networks)
Session Chair: J. Welch
10:40 – 11:00 Co-Best Paper: Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model
Ali Mashreghi and Valerie King
11:00 – 11:20 Local queuing under contention
Paweł Garncarek, Tomasz Jurdzinski and Dariusz Kowalski
11:20 – 11:40 Deterministic Blind Radio Networks
Artur Czumaj and Peter Davies
11:40 – 11:48 Brief Announcement:Randomized Blind Radio Networks
Artur Czumaj and Peter Davies
11:48 – 11:56 Brief Announcement: On Simple Back-Off in Unreliable Radio Networks
Seth Gilbert, Nancy Lynch, Calvin Newport and Dominik Pajak
11:56 – 12:03 Brief Announcement: Deterministic contention resolution on a shared channel
Gianluca De Marco, Dariusz Kowalski and Grzegorz Stachowiak
12:03 – 14:00 Lunch Break
Session 2C: 14:00 – 15:08 (Leader Election)
Session Chair: G. Sharma
14:00 – 14:20 Beeping a Deterministic Time-Optimal Leader Election
Fabien Dufoulon, Janna Burman and Joffroy Beauquier
14:20 – 14:40 The Role of A-priori Information in Networks of Rational Agents
Yehuda Afek, Shaked Rafaeli and Moshe Sulamy
14:40 – 15:00 Selecting a Leader in a Network of Finite State Machines
Yehuda Afek, Yuval Emek and Noa Kolikant
15:00 – 15:08 Brief Announcement: Loosely-stabilizing Leader Election with Polylogarithmic Convergence Time
Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa and Toshimitsu Masuzawa
15:08 – 15:40 Break
Session 2D: 15:40 – 17:00 (Randomized Network Algorithms)
Session Chair: R. Gmyr
15:40 – 16:00 New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
Mohsen Ghaffari and Jason Li
16:00 – 16:20 A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics
Manuela Fischer and Mohsen Ghaffari
16:20 – 16:40 A population protocol for exact majority with O(log^{5/3} n) stabilization time and Theta(log n) states
Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling and Tomasz Radzik
16:40 – 17:00 A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols
Yael Kalai, Ilan Komargodski and Ran Raz
17:00-18:00 Break
18:00 Banquet Reception
18:30 Banquet and Award Ceremony

Thursday, October 18

8:00 Registration: registration desk open throughout the day
Session 3A: 8:30 – 10:38 (Distributed Agreement 1)
Session Chair: C. Busch
8:30 – 9:30 Keynote talk
Logical Analysis of Distributed Systems: The Importance of Being Constructive
Michael Mendler
9:30 – 9:50 Deterministic Objects Give Life to Non-Deterministic 1-Consensus Tasks
Eli Daian, Giuliano Losa, Yehuda Afek and Eli Gafni
9:50 – 10:10 Lattice Agreement in Distributed Message Passing Systems
Xiong Zheng, Changyong Hu and Vijay Garg
10:10 – 10:30 Strong Separations Between Broadcast and Authenticated Channels
Julian Loss, Ueli Maurer and Daniel Tschudi
10:30 – 10:38 Brief Announcement: A Tight Lower Bound for Clock Synchronization in Odd-Ary M-Toroids
Reginald Frank and Jennifer Welch
10:38 – 11:10 Break
Session 3B: 11:10 – 12:18 (Distributed Agreement 2)
Session Chair: G. Chockler
11:10 – 11:30 Fast Multidimensional Asymptotic and Approximate Consensus
Matthias Függer and Thomas Nowak
11:30 – 11:50 State Machine Replication is More Expensive Than Consensus
Karolos Antoniadis, Rachid Guerraoui, Dahlia Malkhi and Dragos-Adrian Seredinschi
11:50 – 12:10 Fault-Tolerant Consensus with an Abstract MAC Layer
Calvin Newport and Peter Robinson
12:10 – 12:18 Brief Announcement: Effects of Topology Knowledge and Relay Depth on Asynchronous Consensus
Dimitris Sakavalas, Lewis Tseng and Nitin Vaidya
12:18 – 14:00 Lunch Break
Session 3C: 14:00 – 15:20 (CONGEST Model 1)
Session Chair: P. Robinson
14:00 – 14:20 Detecting cliques in CONGEST networks
Artur Czumaj and Christian Konrad
14:20 – 14:40 Congested Clique Algorithms for Graph Spanners
Merav Parter and Eylon Yogev
14:40 – 15:00 (Delta+1)-Coloring in O(log* Delta) Congested-Clique Rounds
Merav Parter and Hsin-Hao Su
15:00 – 15:20 Adapting Local Sequential Algorithms to the Distributed Setting
Ken-Ichi Kawarabayashi and Gregory Schwartzman
15:20 – 15:50 Break
Session 3D: 15:50 – 16:50 (CONGEST Model 2)
Session Chair: R. Elsässer
15:50 – 16:10 Distributed Approximate Maximum Matching in the CONGEST Model
Mohamad Ahmadi, Fabian Kuhn and Rotem Oshman
16:10 – 16:30 Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
Mohsen Ghaffari and Fabian Kuhn
16:30 – 16:50 Faster Distributed Shortest Path Approximations via Shortcuts
Jason Li and Bernhard Haeupler
16:50 Closing Remarks

Friday, October 19

During the Day SCNDS: Workshop on Storage, Control, Networking in Dynamic Systems
DISC 2018 Sponsors