This book constitutes the refereed proceedings of the 24th International Symposium on Distributed Computing, DISC 2010, held in Cambridge, CT, USA, in September 2010. The 32 revised full papers, selected from 135 submissions, are presented together with 14 brief announcements of ongoing works; all of them were carefully reviewed and selected for inclusion in the book. The papers address all aspects of distributed computing, and were organized in topical sections on, transactions, shared memory services and concurrency, wireless networks, best student paper, consensus and leader election, mobile agents, computing in wireless and mobile networks, modeling issues and adversity, and self-stabilizing and graph algorithms.
Author(s): Marcos K. Aguilera, Michel Raynal (auth.), Nancy A. Lynch, Alexander A. Shvartsman (eds.)
Series: Lecture Notes in Computer Science 6343 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 532
Tags: Computer Communication Networks; Software Engineering; Information Systems Applications (incl.Internet); Algorithm Analysis and Problem Complexity; Programming Techniques; Artificial Intelligence (incl. Robotics)
Front Matter....Pages -
The 2010 Edsger W. Dijkstra Prize in Distributed Computing....Pages 1-2
The Power of Abstraction....Pages 3-3
Fast Asynchronous Consensus with Optimal Resilience....Pages 4-19
Transactions as the Foundation of a Memory Consistency Model....Pages 20-34
The Cost of Privatization....Pages 35-49
A Scalable Lock-Free Universal Construction with Best Effort Transactional Hardware....Pages 50-63
Window-Based Greedy Contention Management for Transactional Memory....Pages 64-78
Scalable Flat-Combining Based Synchronous Queues....Pages 79-93
Fast Randomized Test-and-Set and Renaming....Pages 94-108
Concurrent Computing and Shellable Complexes....Pages 109-123
Brief Announcement: Hybrid Time-Based Transactional Memory....Pages 124-126
Brief Announcement: Quasi-Linearizability: Relaxed Consistency for Improved Concurrency....Pages 127-129
Brief Announcement: Fast Local-Spin Abortable Mutual Exclusion with Bounded Space....Pages 130-132
What Is the Use of Collision Detection (in Wireless Networks)?....Pages 133-147
Deploying Wireless Networks with Beeps....Pages 148-162
Distributed Contention Resolution in Wireless Networks....Pages 163-178
A Jamming-Resistant MAC Protocol for Multi-Hop Wireless Networks....Pages 179-193
Brief Announcement: Simple Gradecast Based Algorithms....Pages 194-197
Brief Announcement: Decentralized Network Bandwidth Prediction....Pages 198-200
Brief Announcement: Synchronous Las Vegas URMT Iff Asynchronous Monte Carlo URMT....Pages 201-203
Foundations of Speculative Distributed Computing....Pages 204-205
Anonymous Asynchronous Systems: The Case of Failure Detectors....Pages 206-220
The Computational Structure of Progress Conditions....Pages 221-235
Scalable Quantum Consensus for Crash Failures....Pages 236-250
How Much Memory Is Needed for Leader Election....Pages 251-266
Leader Election Problem versus Pattern Formation Problem....Pages 267-281
Rendezvous of Mobile Agents in Directed Graphs....Pages 282-296
Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids....Pages 297-311
Exclusive Perpetual Ring Exploration without Chirality....Pages 312-327
Drawing Maps with Advice....Pages 328-342
Network-Aware Distributed Algorithms: Challenges and Opportunities in Wireless Networks....Pages 343-343
Connectivity Problem in Wireless Networks....Pages 344-358
Trusted Computing for Fault-Prone Wireless Networks....Pages 359-373
Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony....Pages 374-388
Brief Announcement: Failure Detectors Encapsulate Fairness....Pages 389-391
Brief Announcement: Automated Support for the Design and Validation of Fault Tolerant Parameterized Systems - A Case Study....Pages 392-394
Brief Announcement: On Reversible and Irreversible Conversions....Pages 395-397
Brief Announcement: A Decentralized Algorithm for Distributed Trigger Counting....Pages 398-400
Brief Announcement: Flash-Log – A High Throughput Log....Pages 401-403
Brief Announcement: New Bounds for Partially Synchronous Set Agreement....Pages 404-405
It’s on Me! The Benefit of Altruism in BAR Environments....Pages 406-420
Beyond Lamport’s Happened-Before : On the Role of Time Bounds in Synchronous Systems....Pages 421-436
On the Power of Non-spoofing Adversaries....Pages 437-449
Implementing Fault-Tolerant Services Using State Machines: Beyond Replication....Pages 450-464
Low Communication Self-stabilization through Randomization....Pages 465-479
Fast Self-stabilizing Minimum Spanning Tree Construction....Pages 480-494
The Impact of Topology on Byzantine Containment in Stabilization....Pages 495-509
Minimum Dominating Set Approximation in Graphs of Bounded Arboricity....Pages 510-524
Brief Announcement: Sharing Memory in a Self-stabilizing Manner....Pages 525-527
Brief Announcement: Stabilizing Consensus with the Power of Two Choices....Pages 528-530
Back Matter....Pages -
