DISC 2015 29th International Symposium on Distributed Computing


A PDF version of the program can be found here.

Program at a glance

The conference will be held at the Boissonade Tower in HOSEI University (Ichigaya Campus).

Tuesday, October 6

6:00 – 9:00 pm Conference reception
At the DEISETSU room on the 5th floor of the Arcadia Ichigaya hotel.

Wednesday, October 7

Held on the 26th floor of Boissonade Tower in HOSEI University (Ichigaya Campus).

8:00 – 8:30 am Coffee
Session Chair: Yukiko Yamauchi
8:30 – 8:45 am Welcome remarks
8:45 – 9:45 am Keynote talk by Thomas Moscibroda
System Algorithms in the Cloud and Big Data
9:45 – 10:05 am Benjamin Fish, Jeremy Kun, Ádám D. Lelkes, Lev Reyzin and György Turán
On the Computational Complexity of MapReduce
10:05 – 10:30 am Coffee Break
Session Chair: Achour Mostefaoui
10:30 – 10:50 am Christoph Lenzen and Joel Rybicki
Efficient Counting with Optimal Resilience
10:50 – 11:10 am Seth Gilbert and Calvin Newport
The Computational Power of Beeps
11:10 – 11:30 am Rachid Guerraoui and Alexandre Maurer
Byzantine Fireflies
11:30 – 11:50 am Oksana Denysyuk and Philipp Woelfel
Wait-Freedom is Harder Than Lock-Freedom Under Strong Linearizability
11:50 – 12:10 pm Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar and Jennifer L. Welch
Simulating a Shared Register in an Asynchronous System that Never Stops Changing
12:10 – 1:30 pm Lunch break
Session Chair: Gregory Chockler
1:30 – 1:50 pm Yukiko Yamauchi, Taichi Uehara, Shuji Kijima and Masafumi Yamashita
Plane Formation by Synchronous Mobile Robots in the Three Dimensional Euclidean Space
1:50 – 2:10 pm Jěrémie Chalopin, Emmanuel Godard and Antoine Naudin
Anonymous Graph Exploration with Binoculars
2:10 – 2:30 pm Jěrémie Chalopin, Shantanu Das, Pawel Gawrychowski, Adrian Kosowski, Arnaud Labourel and Przemysław Uznański
Limit Behavior of the Multi-agent Rotor-Router System
2:30 – 2:50 pm Hillel Avni, Eliezer Levy and Avi Mendelson
Hardware Transactions in Nonvolatile Memory
2:50 – 3:10 pm Maya Arbel, Guy Golan-Gueta, Eshcar Hillel and Idit Keidar
Towards Automatic Lock Removal for Scalable Synchronization
3:10 – 3:30 pm Leander Jehl, Roman Vitenberg and Hein Meling
SmartMerge: A New Approach to Reconfiguration for Atomic Storage
3:30 – 4:00 pm Coffee Break
Brief Announcement Session
Session Chair: Pierre Fraigniaud
4:00 – 4:06 pm Dominik Kaaser, Frederik Mallmann-Trenn and Emanuele Natale
Brief Announcement: On the Voting Time of the Deterministic Majority Process
4:06 – 4:12 pm Sebastian Daum, Fabian Kuhn and Yannic Maus
Brief Announcement: Rumor Spreading with Bounded In-Degree
4:12 – 4:18 pm Artur Menc, Dominik Pająk and Przemysław Uznański
Brief Announcement: On the Power of One Bit in Graph Exploration Without Backtracking
4:18 – 4:24 pm Li Ning, Dongxiao Yu, Yong Zhang, Yuexuan Wang, Francis C.M. Lau and Shengzhong Feng
Brief Announcement: Uniform Information Exchange in Multi-channel Wireless Ad Hoc Networks
4:24 – 4:30 pm Shlomi Dolev, Chryssis Georgiou, Ioannis Marcoullis and Elad M. Schiller
Brief Announcement: Self-Stabilizing Virtual Synchrony
4:30 – 4:36 pm Anna Dornhaus, Nancy Lynch, Tsvetomira Radeva and Hsin-Hao Su
Brief Announcement: Distributed Task Allocation in Ant Colonies
Session Chair: Taisuke Izumi
4:36 – 4:56 pm Dan Alistarh, Justin Kopinsky, Petr Kuznetsov, Srivatsan Ravi and Nir Shavit
Inherent Limitations of Hybrid Transactional Memory
4:56 – 5:16 pm Joel Gibson and Vincent Gramoli
Why Non-Blocking Operations Should be Selfish
5:16 – 5:36 pm Wenjia Ruan and Michael Spear
Hybrid Transactional Memory Revisited
5:36 – 5:56 pm Petr Kuznetsov and Srivatsan Ravi
Grasping the Gap between Blocking and Non-Blocking Transactional Memories
6:00 – 6:45 pm Business Meeting

Thursday, October 8

Held on the 26th floor of Boissonade Tower in HOSEI University (Ichigaya Campus).

8:00 – 8:30 am Coffee
Session Chair: Xavier Defago
8:30 – 8:50 am Colin Cooper, Tomasz Radzik, Robert Elsässer, Takeharu Shiraga and Nicolás Rivera
Fast Consensus for Voting on General Expander Graphs
8:50 – 9:10 am Jochen Seidel, Jara Uitto and Roger Wattenhofer
Randomness vs. Time in Anonymous Networks
9:10 – 9:30 am John Augustine, Gopal Pandurangan and Peter Robinson
Fast Byzantine Leader Election in Dynamic Networks
9:30 – 9:50 am Yuezhou Lv and Thomas Moscibroda
Local Information in Influence Networks
(best student paper award)
9:50 – 10:00 am Spotlight session – Flash introduction of posters
10:00 – 11:00 am Combined Poster session and extended coffee break
Session Chair: Armando Castaneda
11:00 – 11:20 am Keren Censor-Hillel, Erez Kantor, Nancy Lynch and Merav Parter
Computing in Additive Networks with Bounded-Information Codes
11:20 – 11:40 am Sebastian Daum and Fabian Kuhn
Tight Bounds for MIS in Multichannel Radio Networks
11:40 – 12:00 pm Erez Kantor, Zvi Lotker, Merav Parter and David Peleg
Nonuniform SINR+Voroni Diagrams are Effectively Uniform
12:00 – 1:15 pm Lunch break
Session Chair: Dan Alistarh
1:15 – 1:35 pm Kfir Lev-Ari, Gregory Chockler and Idit Keidar
A Constructive Approach for Proving Data Structures’ Linearizability
1:35 – 1:55 pm Nir Hemed, Noam Rinetzky and Viktor Vafeiadis
Modular Verification of Concurrency-Aware Linearizability
1:55 – 2:15 pm Andrea Cerone, Alexey Gotsman and Hongseok Yang
Transaction Chopping for Parallel Snapshot Isolation
2:15 – 2:35 pm Yehuda Afek, Alexander Matveev, Oscar R. Moll and Nir Shavit
Amalgamated Lock-Elision
2:35 – 2:55 pm Ahmed Hassan, Roberto Palmieri and Binoy Ravindran
Transactional Interference-Less Balanced Tree
2:55 – 3:15 pm Aras Atalar, Paul Renaud-Goud and Philippas Tsigas
Analyzing the Performance of Lock-Free Data Structures: A Conflict-Based Model
Social Event
3:30 – 7:30 pm Excursion
7:40 – 9:40 pm Conference Banquet

Friday, October 9

Held on the 26th floor of Boissonade Tower in HOSEI University (Ichigaya Campus).

8:00 – 8:30 am Coffee
Session Chair: Danny Dolev
8:30 – 9:30 am Keynote talk by Michael Ben-Or (Hebrew University)
Quantum Distributed Computing
9:30 – 9:50 am Rati Gelashvili
On the Optimal Space Complexity of Consensus for Anonymous Processes
(best paper award)
9:50 – 10:15 am Coffee Break
Brief Announcement Session
Session Chair: Juan Garay
10:15 – 10:21 am Vincent Gramoli, Petr Kuznetsov, Srivatsan Ravi and Di Shang
Brief Announcement: A Concurrency-Optimal List-Based Set
10:21 – 10:27 am Alex Kogan and Yossi Lev
Brief Announcement: HTM-Assisted Combining
10:27 – 10:33 am Pedro Ramalhete and Andreia Correia
Brief Announcement: Left-Right – A Concurrency Control Technique with Wait-Free Population Oblivious Reads
10:33 – 10:39 am Leqi Zhu
Brief Announcement: Tight Space Bounds for Memoryless Anonymous Consensus
10:39 – 10:45 am Claire Capdevielle, Colette Johnen, Petr Kuznetsov and Alessia Milani
Brief Announcement: On the Uncontended Complexity of Anonymous Consensus
10:45 – 10:51 am Zohir Bouzid, Michel Raynal and Pierre Sutra
Brief Announcement: Anonymous Obstruction-free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers
10:51 – 10:57 am Trevor Brown
Brief Announcement: Faster Data Structures in Transactional Memory Using Three Paths
10:57 – 11:03 am Gregory Chockler, Dan Dobre, Alexander Shraer and Alexander Spiegelman
Brief Announcement: Space Bounds for Reliable Multi-Writer Data Store: Inherent Cost of Read/Write Primitives
Session Chair: Noam Rinetzky
11:05 – 11:25 am Yael Tauman Kalai and Ilan Komargodski
Compressing Communication in Distributed Protocols
11:25 – 11:45 am George Giakkoupis, Rachid Guerraoui, Arnaud Jégou, Anne-Marie Kermarrec and Nupur Mittal
Privacy-Conscious Information Diffusion in Social Networks
11:45 – 12:05 pm Juan A. Garay, Björn Tackmann and Vassilis Zikas
Fair Distributed Computation of Reactive Functions
12:05 – 1:20 pm Lunch break
Session Chair: Rotem Oshman
1:20 – 1:40 pm Michael Dinitz, Jeremy Fineman, Seth Gilbert and Calvin Newport
Smoothed Analysis of Dynamic Networks
1:40 – 2:00 pm Keerti Choudhary, Surender Baswana and Liam Roditty
Fault Tolerant Reachability for Directed Graphs
2:00 – 2:20 pm Laurent Feuilloley, Juho Hirvonen and Jukka Suomela
Locally Optimal Load Balancing
2:20 – 2:40 pm Magnus M. Halldorsson and Christian Konrad
Distributed Large Independent Sets in One Round On Bounded-Independence Graphs
2:40 – 3:00 pm Armando Castañeda, Sergio Rajsbaum and Michel Raynal
Specifying Concurrent Problems: Beyond Linearizability and up to Tasks
3:00 – 3:20 pm Éric Goubault, Samuel Mimram and Christine Tasson
From Geometric Semantics to Asynchronous Computability
3:20 – 3:45 pm Coffee Break
Session Chair: Petr Kuznetsov
3:45 – 4:05 pm David Doty and David Soloveichik
Stable Leader Election in Population Protocols Requires Linear Time
4:05 – 4:25 pm Joffroy Beauquier, Janna Burman, Simon Clavière and Devan Sohier
Space-Optimal Counting in Population Protocols
4:25 – 4:45 pm Eli Gafni and Dahlia Malkhi
Elastic Configuration Maintenance via a Parsimonious Speculating Snapshot Solution
4:45 pm Closing remarks