Distributed Computing: 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings

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 -