Distributed Computing

1. Front Matter

   PDF

2. Concurrency

   1. Automatically Adjusting Concurrency to the Level of Synchrony

      • Pierre Fraigniaud, Eli Gafni, Sergio Rajsbaum, Matthieu Roy

      Pages 1-15

3. Biological and Chemical Networks

   1. Speed Faults in Computation by Chemical Reaction Networks

      • Ho-Lin Chen, Rachel Cummings, David Doty, David Soloveichik

      Pages 16-30

   2. Fault-Tolerant ANTS

      • Tobias Langner, Jara Uitto, David Stolz, Roger Wattenhofer

      Pages 31-45

   3. Task Allocation in Ant Colonies

      • Alejandro Cornejo, Anna Dornhaus, Nancy Lynch, Radhika Nagpal

      Pages 46-60

4. Agreement Problems

   1. Communication-Efficient Randomized Consensus

      • Dan Alistarh, James Aspnes, Valerie King, Jared Saia

      Pages 61-75

   2. Tight Bound on Mobile Byzantine Agreement

      • François Bonnet, Xavier Défago, Thanh Dang Nguyen, Maria Potop-Butucaru

      Pages 76-90

   3. Unbeatable Consensus

      • Armando Castañeda, Yannai A. Gonczarowski, Yoram Moses

      Pages 91-106

   4. Reliable Broadcast with Respect to Topology Knowledge

      • Aris Pagourtzis, Giorgos Panagiotakos, Dimitris Sakavalas

      Pages 107-121

5. Robot Coordination, Scheduling

   1. Evacuating Robots via Unknown Exit in a Disk

      • Jurek Czyzowicz, Leszek Gąsieniec, Thomas Gorry, Evangelos Kranakis, Russell Martin, Dominik Pajak

      Pages 122-136

   2. Randomized Pattern Formation Algorithm for Asynchronous Oblivious Mobile Robots

      • Yukiko Yamauchi, Masafumi Yamashita

      Pages 137-151

   3. A Theoretical Foundation for Scheduling and Designing Heterogeneous Processors for Interactive Applications

      • Shaolei Ren, Yuxiong He, Kathryn S. McKinley

      Pages 152-166

6. Graph Distances and Routing

   1. Vertex Fault Tolerant Additive Spanners

      • Merav Parter

      Pages 167-181

   2. Close to Linear Space Routing Schemes

      • Liam Roditty, Roei Tov

      Pages 182-196

   3. Near-Optimal Distributed Tree Embedding

      • Mohsen Ghaffari, Christoph Lenzen

      Pages 197-211

7. Radio Networks

   1. Deterministic Leader Election in Multi-hop Beeping Networks

      • Klaus-Tycho Förster, Jochen Seidel, Roger Wattenhofer

      Pages 212-226

   2. Who Are You? Secure Identities in Ad Hoc Networks

      • Seth Gilbert, Calvin Newport, Chaodong Zheng

      Pages 227-242

   3. Approximate Local Sums and Their Applications in Radio Networks

      • Zhiyu Liu, Maurice Herlihy

      Pages 243-257

   4. Radio Network Lower Bounds Made Easy

      • Calvin Newport

      Pages 258-272

8. Shared Memory

   1. On Correctness of Data Structures under Reads-Write Concurrency

      • Kfir Lev-Ari, Gregory Chockler, Idit Keidar

      Pages 273-287

This book constitutes the proceedings of the 28th International Symposium on Distributed Computing, DISC 2014, held in Austin, TX, USA, in October 2014. The 35 full papers presented in this volume were carefully reviewed and selected from 148 full paper submissions. In the back matter of the volume a total of 18 brief announcements is presented. The papers are organized in topical sections named: concurrency; biological and chemical networks; agreement problems; robot coordination and scheduling; graph distances and routing; radio networks; shared memory; dynamic and social networks; relativistic systems; transactional memory and concurrent data structures; distributed graph algorithms; and communication.

• ad hoc networks
• concurrent programming
• data-structures
• distributed algorithms
• dynamic networks
• fault-tolerance
• knowledge
• mobile robot
• parallelism
• randomized algorithm
• ratio networks
• space complexity
• topology knowledge
• transactional memory
• algorithm analysis and problem complexity

• Department of Computer Science, University of Freiburg, Freiburg, Germany

  Fabian Kuhn

Policies and ethics