Distributed Computing

1. Front Matter

   PDF

2. Graph Problems in the Message Passing Model

   1. Distributed Minimum Cut Approximation

      • Mohsen Ghaffari, Fabian Kuhn

      Pages 1-15

   2. When Distributed Computation Is Communication Expensive

      • David P. Woodruff, Qin Zhang

      Pages 16-30

3. Topology, Leader Election, and Spanning Trees

   1. Use Knowledge to Learn Faster: Topology Recognition with Advice

      • Emanuele Guido Fusco, Andrzej Pelc, Rossella Petreschi

      Pages 31-45

   2. An \(O(\sqrt n)\) Space Bound for Obstruction-Free Leader Election

      • George Giakkoupis, Maryam Helmi, Lisa Higham, Philipp Woelfel

      Pages 46-60

   3. Distributed Protocols for Leader Election: A Game-Theoretic Perspective

      • Ittai Abraham, Danny Dolev, Joseph Y. Halpern

      Pages 61-75

   4. Compact Deterministic Self-stabilizing Leader Election

      • Lélia Blin, Sébastien Tixeuil

      Pages 76-90

   5. Time Optimal Synchronous Self Stabilizing Spanning Tree

      • Alex Kravchik, Shay Kutten

      Pages 91-105

4. Software Transactional Memory

   1. Proving Non-opacity

      • Mohsen Lesani, Jens Palsberg

      Pages 106-120

   2. Exploiting Locality in Lease-Based Replicated Transactional Memory via Task Migration

      • Danny Hendler, Alex Naiman, Sebastiano Peluso, Francesco Quaglia, Paolo Romano, Adi Suissa

      Pages 121-133

   3. Generic Multiversion STM

      • Li Lu, Michael L. Scott

      Pages 134-148

   4. Practical Parallel Nesting for Software Transactional Memory

      • Nuno Diegues, João Cachopo

      Pages 149-163

5. Shared Memory Executions

   1. Asynchronous Resilient Linearizability

      • Sagar Chordia, Sriram Rajamani, Kaushik Rajan, Ganesan Ramalingam, Kapil Vaswani

      Pages 164-178

   2. Fair Synchronization

      • Gadi Taubenfeld

      Pages 179-193

6. Gossip and Rumor

   1. Gossip Protocols for Renaming and Sorting

      • George Giakkoupis, Anne-Marie Kermarrec, Philipp Woelfel

      Pages 194-208

   2. Faster Rumor Spreading: Breaking the logn Barrier

      • Chen Avin, Robert Elsässer

      Pages 209-223

7. Shared Memory Tasks and Data Structures

   1. Lock-Free Data-Structure Iterators

      • Erez Petrank, Shahar Timnat

      Pages 224-238

   2. Practical Non-blocking Unordered Lists

      • Kunlong Zhang, Yujiao Zhao, Yajun Yang, Yujie Liu, Michael Spear

      Pages 239-253

   3. Atomic Snapshots in O(log³ n) Steps Using Randomized Helping

      • James Aspnes, Keren Censor-Hillel

      Pages 254-268

   4. Adaptive Register Allocation with a Linear Number of Registers

      • Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Leslie Lamport

      Pages 269-283

This book constitutes the proceedings of the 27th International Symposium on Distributed Computing, DISC 2013, held in Jerusalem, Israel, in October 2013. The 27 full papers presented in this volume were carefully reviewed and selected from 142 submissions; 16 brief announcements are also included. The papers are organized in topical sections named: graph distributed algorithms; topology, leader election, and spanning trees; software transactional memory; shared memory executions; shared memory and storage; gossip and rumor; shared memory tasks and data structures; routing; radio networks and the SINR model; crypto, trust, and influence; and networking.

• cognitive radio access protocols
• distributed algorithms
• non-blocking trees
• synchronization
• wireless networks
• algorithm analysis and problem complexity

• Blavatnik School of Computer Sciences, Tel Aviv University, Tel-Aviv, Israel

  Yehuda Afek

Policies and ethics