DISC 2016

Program

A PDF version of the program can be found here.

The DISC conference will be held at Université Pierre & Marie Curie at Amphi Durand in the building Esclangon, Campus de Jussieu, 4 place Jussieu, 75005 Paris.

The workshops will be held at Université Pierre & Marie Curie at 1st floor of Tower 26, Campus de Jussieu, 4 place Jussieu, 75005 Paris:

  • Workshop ADGA (26th September) is located in room 25-26/105 (that is, first floor from Tower 26, corridor 26-25, room 105),
  • Workshop MAC (26th September) is located in room 26-00/101 (that is, first floor from Tower 26, corridor 26-00, room 101),
  • Workshop DGDC (30th September) is located in room 25-26/105 (that is, first floor from Tower 26, corridor 26-25, room 105).

The DISC Welcome Reception will be held at Université Pierre & Marie Curie at 24th floor of the Zamansky Tower, Campus de Jussieu, 4 place Jussieu, 75005 Paris.

Monday, September 26

9:00 – 18:00 Workshops ADGA and MAC
At 1st floor of Tower 26 (rooms 25-26/105 for ADGA, 26-00/101 for MAC)
18:30 DISC Welcome Reception
At 24th floor of Zamanski Tower, UPMC

Tuesday, September 27

8:50 – 9:00 Opening of DISC
9:00 – 10:00 Keynote talk by Javier Esperza
Verification of Population Protocols
10:00 – 10:30 Coffee break
Session 1: 10:30 – 12:10 (Shared Memory)
Session Chair: Panagiota Fatourou
10:30 – 10:55 k-Abortable Objects: Progress under High Contention
Naama Ben-David, David Yu Cheng Chan, Vassos Hadzilacos and Sam Toueg
10:55 – 11:20 Linearizability of Persistent Memory Objects under a Full-System-Crash Failure Model
Joseph Izraelevitz, Hammurabi Mendes and Michael L. Scott
11:20 – 11:45 On Composition and Implementation of Sequential Consistency
Matthieu Perrin, Matoula Petrolia, Achour Mostéfaoui and Claude Jard
11:45 – 12:10 Upper Bounds for Boundless Tagging with Bounded Objects
Zahra Aghazadeh and Philipp Woelfel
12:15 – 14:00 Lunch break
Session 2: 14:00 – 15:40 (Distributed Graph Algorithm)
Session Chair: Christoph Lenzen
14:00 – 14:25 Fast Distributed Algorithms for Testing Graph Properties
Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman and Yadu Vasudev
14:25 – 14:50 Distributed Testing of Excluded Subgraphs
Pierre Fraigniaud, Ivan Rapaport, Ville Salo and Ioan Todinca
14:50 – 15:15 Deterministic Leader Election in O(D + log n) Time with Messages of Size O(1)
Arnaud Casteigts, Yves Métivier, John Michael Robson and Akka Zemmari
15:15 – 15:40 Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems
François Le Gall
15:40 – 16:10 Coffee break
Session 3: 16:10 – 17:49 (Information Spreading)
Session Chair: Swan Dubois
16:10 – 16:35 Fast Two-Robot Disk Evacuation with Wireless Communication
Ioannis Lamprou, Russell Martin and Sven Schewe
16:35 – 17:00 Buffer Size for Routing Limited-Rate Adversarial Traffic
Avery Miller and Boaz Patt-Shamir
17:00 – 17:25 Information Spreading in Dynamic Networks under Oblivious Adversaries
John Augustine, Chen Avin, Mehraneh Liaee, Gopal Pandurangan and Rajmohan Rajaraman
17:25 – 17:33 Brief Announcement: Mending the Big-Data Missing Information
Hadassa Daltrophe, Shlomi Dolev and Zvi Lotker
17:33 – 17:41 Brief Announcement: Public vs. Private Randomness in Simultaneous Multi-Party Communication Complexity
Orr Fischer, Rotem Oshman and Uri Zwick
17:41 – 17:49 Brief Announcement: Beeping a Maximal Independent Set Fast
Stephan Holzer and Nancy Lynch
18:00 – 19:00 Business meeting

Wednesday, September 28

9:00 – 10:00 Keynote talk by Serge Abiteboul
Personal Information Management Systems and Knowledge Integration
10:00 – 10:30 Coffee break
Session 4: 10:30 – 12:10 (Asynchrony)
Session Chair: Panagiota Fatourou
10:30 – 10:55 Anonymity-Preserving Failure Detectors
Zohir Bouzid and Corentin Travers
10:55 – 11:20 Asynchronous Computability Theorems for t-Resilient Systems
Vikram Saraph, Maurice Herlihy and Eli Gafni
11:20 – 11:45 Priority Mutual Exclusion: Specification and Algorithm
Chien-Chung Huang and Prasad Jayanti
11:45 – 12:10 Opacity vs TMS2: Expectations and Reality
Sandeep Hans, Ahmed Hassan, Roberto Palmieri, Sebastiano Peluso and Binoy Ravindran
12:15 – 14:00 Lunch break
Session 5: 14:00 – 15:39 (Local Model)
Session Chair: Cyril Gavoille
14:00 – 14:25 Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model (Best Paper Award)
Dan Hefetz, Fabian Kuhn, Yannic Maus and Angelika Steger
14:25 – 14:50 Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs
Bernhard Haeupler, Taisuke Izumi and Goran Zuzic
14:50 – 15:15 Distributed Construction of Purely Additive Spanners
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz and Amir Yehudayoff
15:15 – 15:23 Brief Announcement: A Log*-Time Local MDS Approximation Scheme for Bounded Genus Graphs
Saeed Akhoondian Amiri and Stefan Schmid
15:23 – 15:31 Brief Announcement: Local Distributed Verification
Alkida Balliu, Gianlorenzo D’Angelo, Pierre Fraigniaud and Dennis Olivetti
15:31 – 15:39 Brief Announcement: Deterministic MST Sparsification in the Congested Clique
Janne H. Korhonen
15:40 – 16:10 Coffee break
Session 6: 16:10 – 17:50 (Best Student Paper Election)
Session Chair: Cyril Gavoille
16:10 – 16:35 Non-Bayesian Learning in the Presence of Byzantine Agents
Lili Su and Nitin H. Vaidya
16:35 – 17:00 Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
Amir Abboud, Keren Censor-Hillel and Seri Khoury
17:00 – 17:25 Lower Bound on the Step Complexity of Anonymous Binary Consensus
Hagit Attiya, Ohad Ben-Baruch and Danny Hendler
17:25 – 17:50 Best student paper election
Social Event
19:00 – 23:00 Conference Banquet on boat

Thursday, September 29

9:00 – 10:00 Keynote talk by Graham Cormode
Matching and Covering in Streaming Graphs
10:00 – 10:30 Coffee break
Session 7: 10:30 – 12:10 (Distributed Data-Structures and Algorithms)
Session Chair: Philipp Woelfel
10:30 – 10:55 Optimal Consistent Network Updates in Polynomial Time
Pavol Cerny, Nate Foster, Nilesh Jagnik and Jedidiah McClurg
10:55 – 11:20 Depth of a Random Binary Search Tree with Concurrent Insertions
James Aspnes and Eric Ruppert
11:20 – 11:45 Sublinear-Space Distance Labeling using Hubs
Pawel Gawrychowski, Adrian Kosowski and Przemyslaw Uznanski
11:45 – 12:10 Online Balanced Repartitioning
Chen Avin, Andreas Loukas, Maciej Pacut and Stefan Schmid
12:15 – 14:00 Lunch break
Session 8: 14:00 – 15:40 (Distributed Models and Computation)
Session Chair: Emmanuel Godard
14:00 – 14:25 Are Byzantine Failures Really Different from Crash Failures?
Damien Imbs, Michel Raynal and Julien Stainer
14:25 – 14:50 Optimal Fair Computation
Rachid Guerraoui and Jingjing Wang
14:50 – 15:15 Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks
Christian Scheideler, Alexander Setzer and Thim Strothmann
15:15 – 15:40 Non-Local Probes Do Not Help with Many Graph Problems
Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina and Jukka Suomela
15:40 – 16:10 Coffee break
Session 9: 16:10 – 17:57 (Robots and Shared Memory)
Session Chair: David Ilcinkas
16:10 – 16:35 How to Discreetly Spread a Rumor in a Crowd
Mohsen Ghaffari and Calvin Newport
16:35 – 17:00 Certified Universal Gathering in R² for Oblivious Mobile Robots
Pierre Courtieu, Lionel Rieg, Sébastien Tixeuil and Xavier Urbain
17:00 – 17:25 Asynchronous Embedded Pattern Formation without Orientation
Serafino Cicerone, Gabriele Di Stefano and Alfredo Navarra
17:25 – 17:33 Brief Announcement: Symmetricity in 3D-space – Characterizing Formable Patterns by Synchronous Mobile Robots
Yukiko Yamauchi, Taichi Uehara and Masafumi Yamashita
17:33 – 17:41 Brief Announcement: Set-Consensus Collections are Decidable
Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni and Petr Kuznetsov
17:41 – 17:49 Brief Announcement: On the Space Complexity of Conflict Detector Objects
Claire Capdevielle, Colette Johnen and Alessia Milani
17:49 – 17:57 Brief Announcement: A Step Optimal Implementation of Large Single-Writer Registers
Tian Ze Chen and Yuanhao Wei
18:00 – 18:15 Closing of DISC

Friday, September 30

8:30 – 16:00 Workshop DGDC
At 1st floor of Tower 26 (room 25-26/105)
Disc 2016 Sponsors