DISC 2014 The 28th International Symposium on Distributed Computing


Program as pdf-file.

Sunday, October 12

6:00 – 8:00 pm DISC Reception

Monday, October 13

All DISC sessions take place at the Double Tree Hilton Hotel.

8:00 – 8:30 am Breakfast
SESSION I (Keynote Talk, Concurrency)
Session Chair: Fabian Kuhn
8:30 – 8:45 am Welcome remarks
8:45 – 9:30 am Keynote talk by K. Mani Chandy (Caltech)
Concurrent Computing over the Last 40 Years: What’s Changed and What Hasn’t
9:30 – 9:55 am Pierre Fraigniaud, Eli Gafni, Sergio Rajsbaum and Matthieu Roy
Automatically Adjusting Concurrency to the Level of Synchrony
10:00 – 10:30 am Coffee Break
SESSION II (Chemical and Biological Networks)
Session Chair: Amos Korman
10:30 – 10:55 am Ho-Lin Chen, Rachel Cummings, David Doty and David Soloveichik
Speed Faults in Computation by Chemical Reaction Networks
(best paper award)
10:55 – 11:20 am Tobias Langner, David Stolz, Jara Uitto and Roger Wattenhofer
Fault-Tolerant ANTS
11:20 – 11:45 am Alejandro Cornejo, Anna Dornhaus, Nancy Lynch and Radhika Nagpal
Task Allocation in Ant Colonies
11:45 – 11:52 am Brief Announcement: Leander Jehl, Tormod Erevik Lea and Hein Meling
Replacement: The Smart Way to Handle Failures in a Replicated State Machine
11:52 – 11:59 am Brief Announcement: Panagiota Fatourou and Nikolaos Kallimanis
The Power of Scheduling-Aware Synchronization
12:00 – 1:30 pm Lunch
SESSION III (Agreement Problems)
Session Chair: Victor Luchangco
1:30 – 1:55 pm Dan Alistarh, James Aspnes, Valerie King and Jared Saia
Communication-Efficient Randomized Consensus
1:55 – 2:20 pm François Bonnet, Xavier Défago, Thanh Dang Nguyen and Maria Gradinariu Potop-Butucaru
Tight Bound on Mobile Byzantine Agreement
2:20 – 2:45 pm Armando Castaneda, Yannai A Gonczarowski and Yoram Moses
Unbeatable Consensus
2:45 – 3:10 pm Aris Pagourtzis, Giorgos Panagiotakos and Dimitris Sakavalas
Reliable Broadcast with Respect to Topology Knowledge
3:10 – 3:40 pm Coffee Break
SESSION IV (Robot Coordination, Scheduling)
Session Chair: Christoph Lenzen
3:40 – 4:05 pm Jurek Czyzowicz, Leszek Gasieniec, Thomas Gorry, Evangelos Kranakis, Russell Martin and Dominik Pajak
Evacuating Robots from an Unknown Exit in a Disk
4:05 – 4:30 pm Yukiko Yamauchi and Masafumi Yamashita
Randomized Pattern Formation Algorithm for Asynchronous Oblivious Mobile Robots
4:30 – 4:55 pm Shaolei Ren, Yuxiong He and Kathryn McKinley
A Theoretical Foundation for Scheduling and Designing Heterogeneous Processors for Interactive Applications
4:55 – 5:02 pm Brief Announcement: Foto Afrati, Shlomi Dolev, Ephraim Korach, Shantanu Sharma and Jeffrey Ullman
Assignment Problems of Different-Sized Inputs in MapReduce
5:02 – 5:09 pm Brief Announcement: Costas Busch, Maurice Herlihy, Miroslav Popovic and Gokarna Sharma
Scheduling Multiple Objects in Distributed Transactional Memory
5:09 – 5:16 pm Brief Announcement: Konrad Siek and Paweł T. Wojciechowski
Relaxing Opacity in Pessimistic Transactional Memory
5:16 – 5:23 pm Brief Announcement: Shahar Timnat, Maurice Herlihy and Erez Petrank
A Practical Transactional Memory Interface
5:50 – 7:30 pm Award Ceremony & Business Meeting

Tuesday, October 14

8:00 – 8:30 am Breakfast
SESSION V (Graph Distances and Routing)
Session Chair: Dahlia Malkhi
8:30 – 8:55 am Merav Parter
Vertex Fault Tolerant Additive Spanners
(best student paper award)
8:55 – 9:20 am Liam Roditty and Roei Tov
Close to Linear Space Routing Schemes
9:20 – 9:45 am Mohsen Ghaffari and Christoph Lenzen
Near-Optimal Distributed Tree Embedding
9:45 – 9:52 am Brief Announcement: Noy Rotbart, Søren Dahlgaard and Mathias Bæk Tejs Knudsen
On Dynamic and Multi-Functional Labeling Schemes
9:52 – 9:59 am Brief Announcement: Matthieu Perrin, Achour Mostéfaoui and Claude Jard
Update Consistency in Partitionable Systems
10:00 – 10:30 am Coffee Break
SESSION VI (Radio Networks)
Session Chair: Bernhard Haeupler
10:30 – 10:55 am Klaus-Tycho Förster, Jochen Seidel and Roger Wattenhofer
Deterministic Leader Election in Multi-Hop Beeping Networks
10:55 – 11:20 am Seth Gilbert, Calvin Newport and Chaodong Zheng
Who Are You? Secure Identities in Ad Hoc Networks
11:20 – 11:45 am Maurice Herlihy and Zhiyu Liu
Approximate Local Sums and Their Applications in Radio Networks
11:45 am – 12:10 pm Calvin Newport
Radio Network Lower Bounds Made Easy
12:10 – 1:30 pm Lunch
SESSION VII (Shared Memory)
Session Chair: Yoram Moses
1:30 – 1:55 pm Kfir Lev-Ari, Gregory Chockler and Idit Keidar
On Correctness of Data Structures under Reads-Write Concurrency
1:55 – 2:20 pm Claire Capdevielle, Colette Johnen and Alessia Milani
Solo-Fast Universal Constructions for Deterministic Abortable Objects
2:20 – 2:45 pm Maryam Helmi, Lisa Higham and Philipp Woelfel
On the Space Complexity of Renaming
2:45 – 2:52 pm Brief Announcement: Sebastiano Peluso, Roberto Palmieri, Paolo Romano, Binoy Ravindran and Francesco Quaglia
Breaching the Wall of Impossibility Results on Disjoint-Access Parallel TM
2:52 – 2:59 pm Brief Announcement: Hillel Avni and Adi Suissa-Peleg
COP Composition Using Transaction Suspension in the Compiler
2:59 – 3:06 pm Brief Announcement: Wei-Lun Hung, Himanshu Chauhan and Vijay Garg
ActiveMonitor: Non-Blocking Monitor Executions for Increased Parallelism
3:06 – 3:40 pm Coffee Break
SESSION VIII (Dynamic and Social Networks)
Session Chair: Keren Censor-Hillel
3:40 – 4:05 pm Calvin Newport
Lower Bounds for Structuring Unreliable Radio Networks
4:05 – 4:30 pm Oksana Denysyuk and Luis Rodrigues
Random Walks on Evolving Graphs with Recurring Topologies
4:30 – 4:55 pm Abbas Mehrabian and Ali Pourmiri
Randomized Rumor Spreading in Poorly Connected Small-World Networks
Video of the talk 
4:55 – 5:02 pm Brief Announcement: Adam Sealfon and Aikaterini Sotiraki
Agreement in Partitioned Dynamic Networks
5:02 – 5:09 pm Brief Announcement: Christoph Lenzen and Pierre Bertrand
The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm
5:09 – 5:16 pm Brief Announcement: Lelia Blin and Pierre Fraigniaud
Space-Optimal Silent Self-Stabilizing Spanning Tree Constructions Inspired by Proof-Labeling Schemes
6:00 – 10:00 pm Conference Banquet

Wednesday, October 15

8:00 – 8:30 am Breakfast
SESSION IX (Keynote Talk, Relativistic Systems)
Session Chair: Fabian Kuhn
8:30 – 9:35 am Keynote talk by Phil Bernstein (Microsoft Research)
Project Orleans: A Programming Framework for Cloud Computing
9:35 – 10:00 am Seth Gilbert and Wojciech Golab
Making Sense of Relativistic Distributed Systems
10:00 – 10:30 am Coffee Break
SESSION X (Transactional Memory & Concurrent Data Structures)
Session Chair: James Aspnes
10:30 – 10:55 am Hagit Attiya, Alexey Gotsman, Sandeep Hans and Noam Rinetzky
Safety of Live Transactions in Transactional Memory: TMS is Necessary and Sufficient
10:55 – 11:20 am Mohsen Lesani and Jens Palsberg
Decomposing Opacity
11:20 – 11:45 am Irina Calciu, Hammurabi Mendes and Maurice Herlihy
The Adaptive Priority Queue with Elimination and Combining
11:45 am – 12:10 pm Edward Talmage and Jennifer Welch
Improving Average Performance by Relaxing Distributed Data Structures
12:10 – 1:30 pm Lunch
SESSION XI (Distributed Graph Algorithms)
Session Chair: Jukka Suomela
1:30 – 1:55 pm Danupon Nanongkai and Hsin-Hao Su
Almost-Tight Distributed Minimum Cut Algorithms
1:55 – 2:20 pm Magnús Halldórsson and Christian Konrad
Distributed Algorithms for Coloring Interval Graphs
2:20 – 2:45 pm Shay Kutten, Danupon Nanongkai, Gopal Pandurangan and Peter Robinson
Distributed Symmetry Breaking in Hypergraphs
2:45 – 2:52 pm Brief Announcement: Stephan Holzer, Sebastian Kohler and Roger Wattenhofer
k-Selection and Sorting in the SINR Model
2:52 – 2:59 pm Brief Announcement: Stephan Holzer, David Peleg, Liam Roditty and Roger Wattenhofer
Distributed 3/2-Approximation of the Diameter
3:00 – 3:40 pm Coffee Break
SESSION XII (Communication)
Session Chair: Danupon Nanongkai
3:40 – 4:05 pm Erik Demaine, Piotr Indyk, Sepideh Mahabadi and Ali Vakilian
On Streaming and Communication Complexity of the Set Cover Problem
4:05 – 4:30 pm Yi Li, Xiaoming Sun, Chengu Wang and David Woodruff
On The Communication Complexity of Linear Algebraic Problems in the Message Passing Model
4:30 – 4:55 pm James Hegeman, Sriram V. Pemmaraju and Vivek B. Sardeshmukh
Near-Constant-Time Distributed Algorithms on a Congested Clique
4:55 – 5:02 pm Brief Announcement: Mahnush Movahedi, Jared Saia and Mahdi Zamani
Secure Anonymous Broadcast
5:02 – 5:09 pm Brief Announcement: Mahnush Movahedi and Mahdi Zamani
Privacy-Preserving Location-Based Services
Disc 2014 Sponsors