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 |
