International Symposium on DIStributed Computing (DISC) 2017

Program

The DISC conference and workshops will take place at Austria Trend Hotel Park Royal Palace, Schlossallee 8, 1140 Wien.

  • Workshops TPC (Oct. 16) and HDT (Oct. 20) are located in room Edison I
  • Workshops FRIDA (Oct. 16) and CoDyn (Oct. 20) are located in room Edison II
  • Workshops BTT (Oct. 16) and ADGA (Oct. 20) are located in room Edison III

The welcome reception will be held at the Vienna Technical Museum, Mariahilfer Straße 2121140 Wien.

Monday, October 16

Rooms Edison I, Edison II, and Edison III

During the day
(time TBA)
Workshops BTT, FRIDA, and TPC
Early evening
(time TBA)
DISC Welcome Reception at the Vienna Technical Museum.

Tuesday, October 17

Room Edison II+III

8:30 – 8:40 Opening
8:40 – 9:40 Keynote talk
Recommenders: from the lab to the wild
Anne-Marie Kermarrec (INRIA Rennes)
9:40 – 10:00 Coffee break
Session 1: 10:00 – 12:01 (Distributed Models and Computation)
Session Chair: TBA
10:00 – 10:23 Self-stabilizing Byzantine Clock Synchronization is Almost as Easy as Consensus
Christoph Lenzen and Joel Rybicki
10:23 – 10:46 Feasibilities and Infeasibilities for Achieving Responsiveness in Permissionless Consensus
Rafael Pass and Elaine Shi
10:46 – 11:09 Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems
Hammurabi Mendes and Maurice Herlihy
11:09 – 11:32 Which Broadcast Abstraction Captures k-Set Agreement?
Damien Imbs, Achour Mostefaoui, Matthieu Perrin and Michel Raynal
11:32 – 11:55 On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects
David Yu Cheng Chan, Vassos Hadzilacos and Sam Toueg
11:55 – 12:01 Brief Announcement: Practical Synchronous Byzantine Consensus
Ittai Abraham, Srinivas Devadas, Kartik Nayak and Ling Ren
12:01 – 13:20 Lunch
Session 2: 13:20 – 15:33 (Dynamic and Overlay Networks)
Session Chair: TBA
13:20 – 13:43 Demand-Aware Network Designs of Bounded Degree
Chen Avin, Kaushik Mondal and Stefan Schmid
13:43 – 14:06 Certification of Compact Low-Stretch Routing Schemes
Alkida Balliu and Pierre Fraigniaud
14:06 – 14:29 Some Lower Bounds in Dynamic Networks with Oblivious Adversaries
Irvan Jahja, Haifeng Yu and Yuda Zhao
14:29 – 14:52 Dynamic Analysis of the Arrow Distributed Directory Protocol in General Networks
Abdolhamid Ghodselahi and Fabian Kuhn
14:52 – 15:15 Improved Deterministic Distributed Construction of Spanners
Ofer Grossman and Merav Parter
15:15 – 15:21 Brief Announcement Concurrent Self-Adjusting Distributed Tree Networks
Bruna Peres, Olga Goussevskaia, Stefan Schmid and Chen Avin
15:21 – 15:27 Brief Announcement: Lower Bounds for Asymptotic Consensus in Dynamic Networks
Matthias Függer, Thomas Nowak and Manfred Schwarz
15:27 – 15:33 Brief Announcement: Compact Self-Stabilizing Leader Election for General Networks
Lelia Blin and Sebastien Tixeuil
15:33 – 15:50 Coffee break
Yoram Moses Celebration: 15:50 – 18:05
18:05 – 19:30 Business meeting

Wednesday, October 18

Room Edison II+III

8:30 – 9:30 Keynote talk
Blockchain Consensus Protocols in the Wild
Christian Cachin (IBM Research Zurich)
9:30 – 9:50 Coffee break
Session 3: 9:50 – 11:58 (Distributed Graph Algorithms/Best Papers)
Session Chair: TBA
9:50 – 10:13 Improved Distributed Degree Splitting and Edge Coloring (Best Paper Award)
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela and Jara Uitto
10:13 – 10:36 Improved Deterministic Distributed Matching via Rounding (Best Student Paper Award)
Manuela Fischer
10:36 – 10:59 Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger and Christoph Lenzen
10:59 – 11:22 Simple and Near-Optimal Distributed Coloring for Sparse Graphs
Mohsen Ghaffari and Christiana Lymouri
11:22 – 11:52 Three Notes on Distributed Property Testing
Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport and Ioan Todinca
11:52 – 11:58 Brief Announcement: Crash-tolerant Consensus in Directed Graph Revisited
Ashish Choudhury, Gayathri Garimella, Arpita Patra, Divya Ravi and Pratik Sarkar
12:00 – 13:30 Lunch break
Session 4: 13:30 – 15:37 (Shared Memory)
Session Chair: TBA
13:30 – 13:53 Reuse, don’t Recycle: Transforming Lock-free Algorithms that Throw Away Descriptors
Maya Arbel-Raviv and Trevor Brown
13:53 – 14:16 Recovering Shared Objects Without Stable Storage
Ellis Michael, Dan Ports, Naveen Sharma and Adriana Szekeres
14:16 – 14:39 Recoverable FCFS Mutual Exclusion with Wait-Free Recovery
Prasad Jayanti and Anup Joshi
14:39 – 15:02 Consistency Models with Global Operation Sequencing and their Composition
Alexey Gotsman and Sebastian Burckhardt
15:02 – 15:25 Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution
Alexander Spiegelman, Idit Keidar and Dahlia Malkhi
15:25 – 15:31 Brief Announcement: Compact Topology of Shared-Memory Adversaries
Petr Kuznetsov, Thibault Rieutord and Yuan He
15:31 – 15:37 Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory
Michal Friedman, Maurice Herlihy, Virendra Marathe and Erez Petrank
15:37 – 15:57 Coffee break
Session 5: 15:57 – 17:47 (LOCAL/CONGEST model)
Session Chair: TBA
15:57 – 16:20 Quadratic and Near-Quadratic Lower Bounds for the CONGEST model
Keren Censor-Hillel, Seri Khoury and Ami Paz
16:20 – 16:43 Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets
Shreyas Pai, Gopal Pandurangan, Sriram Pemmaraju, Talal Riaz and Peter Robinson
16:43 – 17:06 Sublogarithmic Distributed Algorithms for Lovász Local Lemma with Implications on Complexity Hierarchies
Manuela Fischer and Mohsen Ghaffari
17:06 – 17:29 Near-Optimal Distributed DFS in Planar Graphs
Mohsen Ghaffari and Merav Parter
17:29 – 17:35 Brief Announcement: On Connectivity in the Broadcast Congested Clique
Tomasz Jurdzinski and Krzysztof Nowicki
17:35 – 17:41 Brief Announcement: Towards a complexity theory for the congested clique
Janne H. Korhonen and Jukka Suomela
17:41 – 17:47 Brief Announcement: A Local Algorithm for the Sparse Spanning Graph Problem
Reut Levi and Christoph Lenzen
Social Event
Time TBA Conference banquet at Schönbrunn Palace

Thursday, October 19

Room Edison II+III

8:30 – 9:30 Keynote talk
Phase Transitions and Emergent Phenomena in Random Structures and Algorithms
Dana Randall (Georgia Tech)
9:30 – 9:50 Coffee break
Session 6: 9:50 – 12:03 (Distributed Randomization and Testing)
Session Chair: TBA
9:50 – 10:13 Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
Keren Censor-Hillel, Merav Parter and Gregory Schwartzman
10:13 – 10:36 Neuro-RAM unit with Applications to Similarity Testing and Compression in Spiking Sigmoidal Networks
Nancy Lynch, Cameron Musco and Merav Parter
10:36 – 10:59 How large is your graph?
Frederik Mallmann-Trenn, Varun Kanade and Victor Verdugo
10:59 – 11:22 Fast plurality consensus in regular expanders
Colin Cooper, Tomasz Radzik, Nicolas Rivera and Takeharu Shiraga
11:22 – 11:45 Error-Sensitive Proof-Labeling Schemes
Laurent Feuilloley and Pierre Fraigniaud
11:45 – 11:51 Brief Announcement: Rapid Mixing of Local Dynamics on Graphs
Rémi Varloot and Laurent Massoulié
11:51 – 11:57 Brief Announcement: Black-box Concurrent Data Structures for NUMA Architectures
Irina Calciu, Siddhartha Sen, Mahesh Balakrishnan and Marcos Aguilera
11:57 – 12:03 Brief Announcement: The Synergy of Finite State Machines
Yehuda Afek, Yuval Emek and Noa Kolikant
12:03 – 13:30 Lunch break
Session 7: 13:30 – 15:37 (Transactional Memory and Communication Complexity)
Session Chair: TBA
13:30 – 13:53 Cost of Concurrency in Hybrid Transactional Memory
Trevor Brown and Srivatsan Ravi
13:53 – 14:16 Extending Hardware Transactional Memory Capacity via Rollback-Only Transactions and Suspend/Resume
Shady Issa, Pascal Felber, Alexander Matveev and Paolo Romano
14:16 – 14:39 Dali: A Periodically Persistent Hash Map
Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey, Dhruva Chakrabarti and Michael L. Scott
14:39 – 15:02 Two-Party Direct-Sum Questions through the Lens of Multiparty Communication Complexity
Itay Hazan and Eyal Kushilevitz
15:02 – 15:25 Interactive Compression for Multi-Party Protocols
Gillat Kol, Rotem Oshman and Dafna Sadeh
15:25 – 15:31 Brief Announcement: A Note on Hardness of Diameter Approximation
Karl Bringmann and Sebastian Krinninger
15:31 – 15:37 Brief Announcement: Towards Reduced Instruction Sets for Synchronization
Rati Gelashvili, Idit Keidar, Alexander Spiegelman and Roger Wattenhofer
15:37 – 15:57 Coffee break
Session 8: 15:57 – 17:30 (Wireless Algorithms and Mobile Agents)
Session Chair: TBA
15:57 – 16:20 An Efficient Communication Abstraction for Dense Wireless Networks
Magnus Halldorsson, Fabian Kuhn, Nancy Lynch and Calvin Newport
16:20 – 16:43 Asynchronous approach in the plane: A deterministic polynomial algorithm
Sébastien Bouchard, Marjorie Bournat, Yoann Dieudonné, Swan Dubois and Franck Petit
16:43 – 17:06 Meeting in a Polygon by Anonymous Oblivious Robots
Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta and Masafumi Yamashita
17:06 – 17:12 Brief Announcement: Shape Formation by Programmable Particles
Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta and Yukiko Yamauchi
17:12 – 17:18 Brief Announcement: Fast Aggregation in Population Protocols
Ryota Eguchi and Taiske Izumi
17:18 – 17:24 Brief Announcement: On the Parallel Undecided-State Dynamics with Two Colors
Andrea Clementi, Luciano Gualà, Francesco Pasquale and Giacomo Scornavacca
17:24 – 17:30 Brief Announcement: Applying Predicate Detection to the Stable Marriage Problem
Vijay Garg
17:30 – 17:40 Closing of DISC

Friday, October 20

Rooms Edison I, Edison II, and Edison III

During the day
(time TBA)
Workshops ADGA, CoDyn, and HDT
Disc 2017 Sponsors TU Wien IST Austria bmvit Technisches Museum Wien VMware Research Oracle TTTech WWTF FWF