DISC 2014 The 28th International Symposium on Distributed Computing

Accepted Papers

Seth Gilbert, Calvin Newport and Chaodong Zheng
Who Are You? Secure Identities in Ad Hoc Networks

Hagit Attiya, Alexey Gotsman, Sandeep Hans and Noam Rinetzky
Safety of Live Transactions in Transactional Memory: TMS is Necessary and Sufficient

Abbas Mehrabian and Ali Pourmiri
Randomized Rumor Spreading in Poorly Connected Small-World Networks

Liam Roditty and Roei Tov
Close to Linear Space Routing Schemes

Irina Calciu, Hammurabi Mendes and Maurice Herlihy
The Adaptive Priority Queue with Elimination and Combining

Calvin Newport
Radio Network Lower Bounds Made Easy

Calvin Newport
Lower Bounds for Structuring Unreliable Radio Networks

Mohsen Lesani and Jens Palsberg
Decomposing Opacity

Shaolei Ren, Yuxiong He and Kathryn Mckinley
A Theoretical Foundation for Scheduling and Designing Heterogeneous Processors for Interactive Applications

Merav Parter
Vertex Fault Tolerant Additive Spanners

Aris Pagourtzis, Giorgos Panagiotakos and Dimitris Sakavalas
Reliable Broadcast with Respect to Topology Knowledge

Klaus-Tycho Förster, Jochen Seidel and Roger Wattenhofer
Deterministic Leader Election in Multi-Hop Beeping Networks

Maurice Herlihy and Zhiyu Liu
Approximate Local Sums and Their Applications in Radio Networks

Mohsen Ghaffari and Christoph Lenzen
Near-Optimal Distributed Tree Embedding

Pierre Fraigniaud, Eli Gafni, Sergio Rajsbaum and Matthieu Roy
Automatically Adjusting Concurrency to the Level of Synchrony

Jurek Czyzowicz, Leszek Gasieniec, Thomas Gorry, Evangelos Kranakis, Russell Martin and Dominik Pajak
Evacuating Robots from an Unknown Exit in a Disk

Claire Capdevielle, Colette Johnen and Alessia Milani
Solo-fast Universal Constructions for Deterministic Abortable Objects

Kfir Lev-Ari, Gregory Chockler and Idit Keidar
On Correctness of Data Structures under Reads-Write Concurrency

Magnús Halldórsson and Christian Konrad
Distributed Algorithms for Coloring Interval Graphs

Shay Kutten, Danupon Nanongkai, Gopal Pandurangan and Peter Robinson
Distributed Symmetry Breaking in Hypergraphs

François Bonnet, Xavier Défago, Thanh Dang Nguyen and Maria Gradinariu Potop-Butucaru
Tight Bound on Mobile Byzantine Agreement

Danupon Nanongkai and Hsin-Hao Su
Almost-Tight Distributed Minimum Cut Algorithms

Armando Castaneda, Yannai A. Gonczarowski and Yoram Moses
Unbeatable Consensus

Dan Alistarh, James Aspnes, Valerie King and Jared Saia
Communication-Efficient Randomized Consensus

Yukiko Yamauchi and Masafumi Yamashita
Randomized Pattern Formation Algorithm for Asynchronous Oblivious Mobile Robots

Oksana Denysyuk and Luis Rodrigues
Random Walks on Evolving Graphs with Recurring Topologies

James W. Hegeman, Sriram V. Pemmaraju, and Vivek B. Sardeshmukh
Near-Constant-Time Distributed Algorithms on a Congested Clique

Seth Gilbert and Wojciech Golab
Making Sense of Relativistic Distributed Systems

Edward Talmage and Jennifer Welch
Improving Average Performance by Relaxing Distributed Data Structures Abstract

Maryam Helmi, Lisa Higham and Philipp Woelfel
On the Space Complexity of Renaming

Alejandro Cornejo, Anna Dornhaus, Nancy Lynch and Radhika Nagpal
Task Allocation in Ant Colonies

Erik Demaine, Piotr Indyk, Sepideh Mahabadi and Ali Vakilian
On the Space and Communication Complexity of the Set Cover Problem

Tobias Langner, David Stolz, Jara Uitto and Roger Wattenhofer
Fault-Tolerant ANTS

Ho-Lin Chen, Rachel Cummings, David Doty and David Soloveichik
Speed faults in computation by chemical reaction networks

Yi Li, Xiaoming Sun, Chengu Wang and David Woodruff
On The Communication Complexity of Linear Algebraic Problems in the Message Passing Model

Brief Announcements

Christoph Lenzen and Pierre Bertrand
The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm

Stephan Holzer, Sebastian Kohler and Roger Wattenhofer
k-Selection and Sorting in the SINR Model

Stephan Holzer, David Peleg, Liam Roditty and Roger Wattenhofer
Distributed 3/2-Approximation of the Diameter

Shahar Timnat, Maurice Herlihy and Erez Petrank
A Practical Transactional Memory Interface

Adam Sealfon and Aikaterini Sotiraki
Agreement in Partitioned Dynamic Networks

Nikolaos Kallimanis and Panagiota Fatourou
The Power of Scheduling-Aware Synchronization

Matthieu Perrin, Achour Mostéfaoui and Claude Jard
Update Consistency in Partitionable Systems

Konrad Siek and Paweł T. Wojciechowski
Relaxing Opacity in Pessimistic Transactional Memory

Lelia Blin and Pierre Fraigniaud
Space-Optimal Silent Self-Stabilizing Spanning Tree Constructions Inspired by Proof-Labeling Schemes

Sebastiano Peluso, Roberto Palmieri, Paolo Romano, Binoy Ravindran and Francesco Quaglia
Breaching the Wall of Impossibility Results on Disjoint-Access Parallel TM

Noy Rotbart, Søren Dahlgaard and Mathias Bæk Tejs Knudsen
On Dynamic and Multi-Functional Labeling Schemes

Leander Jehl, Tormod Erevik Lea and Hein Meling
Replacement: The Smart Way to Handle Failures in a Replicated State Machine

Foto Afrati, Shlomi Dolev, Ephraim Korach, Shantanu Sharma and Jeffrey Ullman
Assignment Problems of Different-Sized Inputs in MapReduce

Wei-Lun Hung, Himanshu Chauhan and Vijay Garg
ActiveMonitor: Non-Blocking Monitor Executions for Increased Parallelism

Hillel Avni and Adi Suissa-Peleg
COP Composition Using Transaction Suspension in the Compiler

Mahnush Movahedi, Jared Saia and Mahdi Zamani
Secure Anonymous Broadcast

Costas Busch, Maurice Herlihy, Miroslav Popovic and Gokarna Sharma
Scheduling Multiple Objects in Distributed Transactional Memory

Mahnush Movahedi and Mahdi Zamani
Secure Location Sharing

Disc 2014 Sponsors