Distributed Computing

1. Front Matter

   PDF

2. Invited Lecture & Best Student Paper: Rendezvous (Session 1a)

   1. DISC 2011 Invited Lecture: Deterministic Rendezvous in Networks: Survey of Models and Results

      • Andrzej Pelc

      Pages 1-15

   2. Fast and Scalable Rendezvousing

      • Yehuda Afek, Michael Hakimi, Adam Morrison

      Pages 16-31

3. Distributed Graph Algorithms (Session 1b)

   1. Beeping a Maximal Independent Set

      • Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn

      Pages 32-50

   2. Trading Bit, Message, and Time Complexity of Distributed Algorithms

      • Johannes Schneider, Roger Wattenhofer

      Pages 51-65

   3. Combinatorial Algorithms for Distributed Graph Coloring

      • Leonid Barenboim, Michael Elkin

      Pages 66-81

   4. Physical Expander in Virtual Tree Overlay

      • Taisuke Izumi, Maria Gradinariu Potop-Butucaru, Mathieu Valero

      Pages 82-96

4. Shared Memory (Session 1c)

   1. Sub-logarithmic Test-and-Set against a Weak Adversary

      • Dan Alistarh, James Aspnes

      Pages 97-109

   2. Tight Space Bounds for ℓ-Exclusion

      • Gadi Taubenfeld

      Pages 110-124

   3. SMV: Selective Multi-Versioning STM

      • Dmitri Perelman, Anton Byshevsky, Oleg Litmanovich, Idit Keidar

      Pages 125-140

5. Brief Announcements I (Session 1d)

   1. Brief Announcement: Leaderless Byzantine Paxos

      • Leslie Lamport

      Pages 141-142

   2. Brief Announcement: When You Don’t Trust Clients: Byzantine Proposer Fast Paxos

      • Keith Marzullo, Hein Meling, Alessandro Mei

      Pages 143-144

   3. Brief Announcement: On the Meaning of Solving a Task with a Failure Detector

      • Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Petr Kuznetsov

      Pages 145-146

   4. Brief Announcement: Algorithmic Mechanisms for Internet-Based Computing under Unreliable Communication

      • Evgenia Christoforou, Antonio Fernández Anta, Chryssis Georgiou, Miguel A. Mosteiro

      Pages 147-149

6. Fault-Tolerance and Security (Session 1e)

   1. Maximum Metric Spanning Tree Made Byzantine Tolerant

      • Swan Dubois, Toshimitsu Masuzawa, Sébastien Tixeuil

      Pages 150-164

   2. Performing Dynamically Injected Tasks on Processes Prone to Crashes and Restarts

      • Chryssis Georgiou, Dariusz R. Kowalski

      Pages 165-180

   3. Leakage-Resilient Coin Tossing

      • Elette Boyle, Shafi Goldwasser, Yael Tauman Kalai

      Pages 181-196

7. Brief Announcements II (Session 1f)

   1. Brief Announcement: Composition Games for Distributed Systems: The EU Grants Games

      • Shay Kutten, Ron Lavi, Amitabh Trehan

      Pages 197-199

   2. Brief Announcement: Distributed Approximations for the Semi-matching Problem

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

      Pages 200-201

   3. Brief Announcement: Opportunistic Information Dissemination in Mobile Ad-Hoc Networks:

      • Martín Farach-Colton, Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro, Shmuel Zaks

      Pages 202-204

This book constitutes the refereed proceedings of the 25th International Symposium on Distributed Computing, DISC 2011, held in Rome, Italy, in September 2011. The 31 revised full papers presented together with invited lectures and brief announcements were carefully reviewed and selected from 136 submissions. The papers are organized in topical sections on distributed graph algorithms; shared memory; brief announcements; fault-tolerance and security; paxos plus; wireless; network algorithms; aspects of locality; consensus; concurrency.

• communication complexity
• distributed algorithms
• finite state automata
• local computing
• reliable communication
• algorithm analysis and problem complexity

• Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel

  David Peleg

Policies and ethics