Final program (pdf)
Workshops program at a glance (pdf)
October 14 (Monday)
17:45 – 20:00 | Welcome reception |
October 15 (Tuesday)
09:00 – 10:00 | Keynote Chair: Jukka Suomela |
09:00 – 10:00 | Distributed and Concurrent Optimization for Machine Learning Dan Alistarh Slides (pdf) |
10:00 – 10:30 | Coffee |
10:30 – 11:16 | Session Chair: Christian Cachin |
10:30 – 10:50 | Monotonically relaxing concurrent data-structure semantics for increasing performance: An efficient 2D design framework Adones Rukundo, Aras Atalar and Philippas Tsigas |
10:50 – 11:10 | Polynomial-time Fence Insertion For Structured Programs Seyed Mohammad Taheri Otaghsara, Arash Pourdamghani and Mohsen Lesani |
11:10 – 11:16 | Brief Announcement: Towards Byzantine Broadcast in Generalized Communication and Adversarial Models Chen-Da Liu-Zhang, Varun Maram and Ueli Maurer |
11:16 – 11:30 | Break |
11:30 – 12:30 | Session Chair: Seth Gilbert |
11:30 – 11:50 | Distributed Algorithms for Low Stretch Spanning Trees Ruben Becker, Yuval Emek, Mohsen Ghaffari and Christoph Lenzen |
11:50 – 12:10 | Low-Congestion Shortcut and Graph Parameters Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi and Taisuke Izumi |
12:10 – 12:30 | Reachability and Shortest Paths in the Broadcast CONGEST Model Shiri Chechik and Doron Mukhtar |
12:30 – 14:00 | Lunch |
14:00 – 14:46 | Session Chair: Janna Burman |
14:00 – 14:20 | Fast Distributed Algorithms for LP-Type Problems of Low Dimension Kristian Hinnenthal, Christian Scheideler and Martijn Struijs |
14:20 – 14:40 | Distributed Data Summarization in Well-Connected Networks Hoa Vu and Hsin-Hao Su |
14:40 – 14:46 | Brief Announcement: On Self-Adjusting Skip List Networks Chen Avin, Iosif Salem and Stefan Schmid |
14:46 – 15:00 | Break |
15:00 – 16:00 | Session Chair: Dan Alistarh |
15:00 – 15:20 | On the Round Complexity of Randomized Byzantine Agreement Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland and Alex Samorodnitsky |
15:20 – 15:40 | Stellar Consensus by Instantiation Eli Gafni, Giuliano Losa and David Mazières |
15:40 – 15:46 | Brief Announcement: Asymmetric Distributed Trust Christian Cachin and Björn Tackmann |
15:46 – 15:53 | Brief Announcement: Implementing Byzantine Tolerant Distributed Ledger Objects Vicent Cholvi, Antonio Fernandez Anta, Chryssis Georgiou and Nicolas Nicolaou |
15:53 – 16:00 | Brief Announcement: Revisiting Consensus Protocols through Wait-free Parallelization Suyash Gupta, Jelle Hellings and Mohammad Sadoghi |
16:00 – 16:30 | Coffee |
16:30 – 17:10 | Highlight Session Chair: Pierre Fraigniaud |
16:30 – 16:50 | A Distributed Algorithm for Directed Minimum-Weight Spanning Tree Orr Fischer and Rotem Oshman (Best Paper) |
16:50 – 17:10 | Putting Strong Linearizability in Context: Preserving Hyperproperties in Programs that Use Concurrent Objects Hagit Attiya and Constantin Enea |
17:10 – 18:40 | Business meeting Chair: Yoram Moses |
October 16 (Wednesday)
09:00 – 10:00 | Keynote Chair: András Pataricza |
09:00 – 10:00 | Network science – a bridge between social and “hard” sciences János Kertész |
10:00 – 10:30 | Coffee |
10:30 – 11:16 | Session Chair: Yukiko Yamauchi |
10:30 – 10:50 | Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models Nobutaka Shimizu and Takeharu Shiraga |
10:50 – 11:10 | On Bioelectric Algorithms Seth Gilbert and Calvin Newport |
11:10 – 11:16 | Brief Announcement: Integrating Temporal Information to Spatial Information in a Neural Circuit Mien Brabeeba Wang and Nancy Lynch |
11:16 – 11:30 | Break |
11:30 – 12:30 | Session Chair: Hsin-Hao Su |
11:30 – 11:50 | Improved Network Decompositions using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond Mohsen Ghaffari and Julian Portmann |
11:50 – 12:10 | Message Reduction in the LOCAL Model is a Free Lunch Shimon Bitton, Yuval Emek, Taisuke Izumi and Shay Kutten |
12:10 – 12:30 | Parameterized Distributed Algorithms Ran Ben Basat, Ken-Ichi Kawarabayashi and Gregory Schwartzman |
12:30 – 14:00 | Lunch |
14:00 – 14:46 | Session Chair: Eric Ruppert |
14:00 – 14:20 | Consensus with max registers James Aspnes and He Yang Er |
14:20 – 14:40 | Wait-free Solvability of Equality Negation Tasks Éric Goubault, Marijana Lazić, Jérémy Ledent and Sergio Rajsbaum |
14:40 – 14:46 | Brief Announcement: Wait-Free Universality of Consensus in the Infinite Arrival Model Grégoire Bonin, Achour Mostéfaoui and Matthieu Perrin |
14:46 – 15:00 | Break |
15:00 – 16:00 | Session Chair: Christoph Lenzen |
15:00 – 15:20 | Trade-offs in Distributed Interactive Proofs Pierluigi Crescenzi, Pierre Fraigniaud and Ami Paz |
15:20 – 15:40 | The Complexity of Symmetry Breaking in Massive Graphs Christian Konrad, Sriram Pemmaraju, Talal Riaz and Peter Robinson |
15:40 – 15:46 | Brief Announcement: Massively Parallel Approximate Distance Sketches Yasamin Nazari and Michael Dinitz |
15:46 – 15:53 | Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring Soheil Behnezhad, Mahsa Derakhshan, Mohammadtaghi Hajiaghayi, Marina Knittel and Hamed Saleh |
15:53 – 16:00 | Brief Announcement: Faster asynchronous MST and low diameter tree construction with sublinear communication Ali Mashreghi and Valerie King |
16:00 – 16:30 | Coffee |
16:30 – 17:30 | Highlight Session Chair: Valerie King |
16:30 – 16:50 | Scalable Byzantine Reliable Broadcast Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic and Dragos-Adrian Seredinschi (Best Paper) |
16:50 – 17:10 | Small Cuts and Connectivity Certificates: A Fault Tolerant Approach Merav Parter |
17:10 – 17:30 | Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn and Rotem Oshman |
17:30 – 18:00 | Break |
18:00 – 21:30 | Banquet |
October 17 (Thursday)
09:00 – 10:00 | Keynote Chair: Yoram Moses |
09:00 – 10:00 | When is an algorithm robust? Seth Gilbert Slides (pdf) |
10:00 – 10:30 | Coffee |
10:30 – 11:16 | Session Chair: Antonio Fernandez Anta |
10:30 – 10:50 | Byzantine Approximate Agreement on Graphs Thomas Nowak and Joel Rybicki |
10:50 – 11:10 | Privatization-Safe Transactional Memories Artem Khyzha, Hagit Attiya and Alexey Gotsman |
11:10 – 11:16 | Brief Announcement: On the Correctness of Transaction Processing with External Dependency Masoomeh Javidi Kishi, Ahmed Hassan and Roberto Palmieri |
11:16 – 11:30 | Break |
11:30 – 12:30 | Session Chair: Tomasz Jurdzinski |
11:30 – 11:50 | Erasure Correction for Noisy Radio Networks Keren Censor-Hillel, Bernhard Haeupler, D Ellis Hershkowitz and Goran Zuzic |
11:50 – 12:10 | On the Computational Power of Radio Channels Mark Braverman, Gillat Kol, Rotem Oshman and Avishay Tal |
12:10 – 12:30 | The Capacity of Smartphone Peer-to-Peer Networks Michael Dinitz, Magnús M. Halldórsson, Calvin Newport and Alex Weaver |
12:30 – 14:00 | Lunch |
14:00 – 14:46 | Session Chair: Hagit Attiya |
14:00 – 14:20 | Parallel Finger Search Structures Wei Quan Lim and Seth Gilbert |
14:20 – 14:40 | A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue Ruslan Nikolaev |
14:40 – 14:46 | Brief Announcement: The Fault-Tolerant Cluster-sending Problem Jelle Hellings and Mohammad Sadoghi |
14:46 – 15:00 | Break |
15:00 – 16:00 | Session Chair: Andrea Richa |
15:00 – 15:20 | Stable Memoryless Queuing under Contention Paweł Garncarek, Tomasz Jurdzinski and Dariusz Kowalski |
15:20 – 15:40 | Space-Optimal Naming in Population Protocols Janna Burman, Joffroy Beauquier and Devan Sohier |
15:40 – 15:46 | Brief Announcement: Neighborhood Mutual Remainder and its Self-Stabilizing Implementation of Look-Compute-Move Robots Shlomi Dolev, Sayaka Kamei, Yoshiaki Katayama, Fukuhito Ooshita and Koichi Wada |
15:46 – 15:53 | Brief Announcement: Model Checking Rendezvous Algorithms for Robots with Lights in Euclidean Space Xavier Défago, Adam Heriban, Sébastien Tixeuil and Koichi Wada |
15:53 – 16:00 | Brief Announcement: Memory Lower Bounds for Self-Stabilization Laurent Feuilloley, Lélia Blin and Gabriel Le Bouder |
16:00 – 16:30 | Coffee |
16:30 – 17:10 | Highlight Session Chair: Jukka Suomela |
16:30 – 16:50 | Long-Lived Counters with Polylogarithmic Amortized Step Complexity Ahad Baig, Danny Hendler, Alessia Milani and Corentin Travers |
16:50 – 17:10 | Optimal Distributed Covering Algorithms Ran Ben Basat, Guy Even, Ken-Ichi Kawarabayashi and Gregory Schwartzman |