Distributed Computing

1. Front Matter

   PDF

2. Shared Memory I

   1. CBTree: A Practical Concurrent Self-Adjusting Search Tree

      • Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, Robert E. Tarjan

      Pages 1-15

   2. Efficient Fetch-and-Increment

      • Faith Ellen, Vijaya Ramachandran, Philipp Woelfel

      Pages 16-30

   3. Show No Weakness: Sequentially Consistent Specifications of TSO Libraries

      • Alexey Gotsman, Madanlal Musuvathi, Hongseok Yang

      Pages 31-45

3. Mobile Agents and Overlay Networks

   1. Collecting Information by Power-Aware Mobile Agents

      • Julian Anaya, Jérémie Chalopin, Jurek Czyzowicz, Arnaud Labourel, Andrzej Pelc, Yann Vaxès

      Pages 46-60

   2. Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology

      • Ofer Feinerman, Amos Korman

      Pages 61-75

   3. A Generalized Algorithm for Publish/Subscribe Overlay Design and Its Fast Implementation

      • Chen Chen, Roman Vitenberg, Hans-Arno Jacobsen

      Pages 76-90

4. Wireless and Multiple Access Channel Networks

   1. Bounded-Contention Coding for Wireless Networks in the High SNR Regime

      • Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, Muriel Médard

      Pages 91-105

   2. Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks

      • Tomasz Jurdzinski, Dariusz R. Kowalski

      Pages 106-120

   3. Distributed Online and Stochastic Queuing on a Multiple Access Channel

      • Marcin Bienkowski, Tomasz Jurdzinski, Miroslaw Korzeniowski, Dariusz R. Kowalski

      Pages 121-135

5. Dynamic Networks

   1. Fast Distributed Computation in Dynamic Networks via Random Walks

      • Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan

      Pages 136-150

   2. Dense Subgraphs on Dynamic Networks

      • Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Amitabh Trehan

      Pages 151-165

   3. Lower Bounds on Information Dissemination in Dynamic Networks

      • Bernhard Haeupler, Fabian Kuhn

      Pages 166-180

6. Distributed Graph Algorithms

   1. No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover

      • Mika Göös, Jukka Suomela

      Pages 181-194

   2. “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting

      • Danny Dolev, Christoph Lenzen, Shir Peled

      Pages 195-209

   3. Distributed 2-Approximation Algorithm for the Semi-matching Problem

      • Andrzej Czygrinow, Michal Hanćkowiak, Edyta Szymańska, Wojciech Wawrzyniak

      Pages 210-222

7. Wireless and Loosely Connected Networks

   1. Bounds on Contention Management in Radio Networks

      • Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch, Calvin Newport

      Pages 223-237

   2. Efficient Symmetry Breaking in Multi-Channel Radio Networks

      • Sebastian Daum, Fabian Kuhn, Calvin Newport

      Pages 238-252

   3. On Byzantine Broadcast in Loosely Connected Networks

      • Alexandre Maurer, Sébastien Tixeuil

      Pages 253-266

8. Shared Memory II

   1. RMR-Efficient Randomized Abortable Mutual Exclusion

      • Abhijeet Pareek, Philipp Woelfel

      Pages 267-281

This book constitutes the refereed proceedings of the 26th International Symposium on Distributed Computing, DISC 2012, held in Salvador, Brazil, in October 2012.
The 27 revised full papers presented together with 24 brief announcements were carefully reviewed and selected from 119 submissions. The papers are organized in topical sections on shared memory, mobile agents and overlay networks, wireless and multiple access channel networks, dynamic networks, distributed graph algorithms, wireless and loosely connected networks, robots, and lower bounds and separation.

• distributed optimization
• fault tolerance
• oblivious robots
• synchronization
• wireless networks
• algorithm analysis and problem complexity

• Microsoft Corporation, Mountain View, USA

  Marcos K. Aguilera

Policies and ethics