Distributed Computing (Paperback)

DISC, the International Symposium on DIStributed Computing, is an inter- tional forum on the theory, design, analysis, implementation and application of distributed systems and networks. DISC is organized in cooperation with the European Association for Theoretical Computer Science (EATCS). This volume contains the papers presented at DISC 2010, the 24th Inter- tional Symposium on Distributed Computing, held on September 13–15,2010 in Cambridge, Massachusetts. The volume also includes the citation for the 2010 Edsger W. Dijkstra Prize in Distributed Computing, jointly sponsored by DISC and PODC (the ACM Symposium on Principles of Distributed Computing), which was presented at PODC 2010 in Zurich to Tushar D. Chandra, Vassos Hadzilacos, and Sam Toueg for their work on failure detectors. Therewere135paperssubmittedtothesymposium(inadditiontherewere14 abstract-only submissions). The Program Committee selected 32 contributions out of the 135 full-paper submissions for regular presentations at the sym- sium. Each presentation is accompanied by a ?fteen-page paper in this volume. Everysubmitted paper was read and evaluated by at least three members of the ProgramCommittee. The committee was assisted by more than 120 external - viewers. The Program Committee made its ?nal decisions during the electronic meeting held on June 18–29, 2010. Revised and expanded versions of several selected papers will be consideredfor publication in a special issue of the journal Distributed Computing. TheprogramalsoincludedthreeinvitedlecturesbyRachidGuerraoui(EPFL, Switzerland), Barbara Liskov (MIT, USA), and Nitin Vaidya (University of Il- nois, USA).

The 2010 Edsger W. Dijkstra Prize in Distributed Computing.- The 2010 Edsger W. Dijkstra Prize in Distributed Computing.- Invited Lecture I: Consensus (Session 1a).- The Power of Abstraction.- Fast Asynchronous Consensus with Optimal Resilience.- Transactions (Session 1b).- Transactions as the Foundation of a Memory Consistency Model.- The Cost of Privatization.- A Scalable Lock-Free Universal Construction with Best Effort Transactional Hardware.- Window-Based Greedy Contention Management for Transactional Memory.- Shared Memory Services and Concurrency (Session 1c).- Scalable Flat-Combining Based Synchronous Queues.- Fast Randomized Test-and-Set and Renaming.- Concurrent Computing and Shellable Complexes.- Brief Announcements I (Session 1d).- Brief Announcement: Hybrid Time-Based Transactional Memory.- Brief Announcement: Quasi-Linearizability: Relaxed Consistency for Improved Concurrency.- Brief Announcement: Fast Local-Spin Abortable Mutual Exclusion with Bounded Space.- Wireless Networks (Session 1e).- What Is the Use of Collision Detection (in Wireless Networks)?.- Deploying Wireless Networks with Beeps.- Distributed Contention Resolution in Wireless Networks.- A Jamming-Resistant MAC Protocol for Multi-Hop Wireless Networks.- Brief Announcements II (Session 1f).- Brief Announcement: Simple Gradecast Based Algorithms.- Brief Announcement: Decentralized Network Bandwidth Prediction.- Brief Announcement: Synchronous Las Vegas URMT Iff Asynchronous Monte Carlo URMT.- Invited Lecture II: Best Student Paper (Session 2a).- Foundations of Speculative Distributed Computing.- Anonymous Asynchronous Systems: The Case of Failure Detectors.- Consensus and Leader Election (Session 2b).- The Computational Structure of Progress Conditions.- Scalable Quantum Consensus for Crash Failures.- How Much Memory Is Needed for Leader Election.- Leader Election Problem versus Pattern Formation Problem.- Mobile Agents (Session 2c).- Rendezvous of Mobile Agents in Directed Graphs.- Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids.- Exclusive Perpetual Ring Exploration without Chirality.- Drawing Maps with Advice.- Invited Lecture III: Wireless Networks (Session 3a).- Network-Aware Distributed Algorithms: Challenges and Opportunities in Wireless Networks.- Connectivity Problem in Wireless Networks.- Computing in Wireless and Mobile Networks (Session 3b).- Trusted Computing for Fault-Prone Wireless Networks.- Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony.- Brief Announcements III (Session 3c).- Brief Announcement: Failure Detectors Encapsulate Fairness.- Brief Announcement: Automated Support for the Design and Validation of Fault Tolerant Parameterized Systems - A Case Study.- Brief Announcement: On Reversible and Irreversible Conversions.- Brief Announcement: A Decentralized Algorithm for Distributed Trigger Counting.- Brief Announcement: Flash-Log – A High Throughput Log.- Brief Announcement: New Bounds for Partially Synchronous Set Agreement.- Modeling Issues and Adversity (Session 3d).- It’s on Me! The Benefit of Altruism in BAR Environments.- Beyond Lamport’s Happened-Before: On the Role of Time Bounds in Synchronous Systems.- On the Power of Non-spoofing Adversaries.- Implementing Fault-Tolerant Services Using State Machines: Beyond Replication.- Self-stabilizing and Graph Algortihms (Session 3e).- Low Communication Self-stabilization through Randomization.- Fast Self-stabilizing Minimum Spanning Tree Construction.- The Impact of Topology on Byzantine Containment in Stabilization.- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity.- Brief Announcements IV (Session 3f).- Brief Announcement: Sharing Memory in a Self-stabilizing Manner.- Brief Announcement: Stabilizing Consensus with the Power of Two Choices.