Table of Contents
The 2010 Edsger W. Dijkstra Prize in Distributed Computing 1
Invited Lecture I Consensus (Session la)
The Power of Abstraction (Invited Lecture Abstract) Barbara Liskov 3
Fast Asynchronous Consensus with Optimal Resilience Ittai Abraham Marcos K. Aguilera Dahlia Malkhi 4
Transactions (Session lb)
Transactions as the Foundation of a Memory Consistency Model Luke Dalessandro Michael L. Scott Michael F. Spear 20
The Cost of Privatization Hagit Attiya Eshcar Hillel 35
A Scalable Lock-Free Universal Construction with Best Effort Transactional Hardware Francois Carouge Michael Spear 50
Window-Based Greedy Contention Management for Transactional Memory Gokarna Sharma Brett Estrade Costas Busch 64
Shared Memory Services and Concurrency (Session 1c)
Scalable Flat-Combining Based Synchronous Queues Danny Hendler Itai Incze Nir Shavit Moran Tzafrir 79
Fast Randomized Test-and-Set and Renaming Dan Alistarh Hagit Attiya Seth Gilbert Andrei Giurgiu Rachid Guerraoui 94
Concurrent Computing and Shellable Complexes Maurice Herlihy Sergio Rajsbaum 109
Brief Announcements I (Session 1d)
Hybrid Time-Based Transactional Memory Pascal Felber Christof Fetzer Patrick Marlier Martin Nowack Torvald Riegel 124
Quasi-Linearizability: Relaxed Consistency for Improved Concurrency Yehuda Afek Guy Korland Eitan Yanovsky 127
Fast Local-Spin Abortable Mutual Exclusion with Bounded Space Hyonho Lee 130
Wireless Networks (Session 1e)
What Is the Use of Collision Detection (in Wireless Networks)? Johannes Schneider Roger Wattenhofer 133
Deploying Wireless Networks with Beeps Alejandro Cornejo Fabian Kuhn 148
Distributed Contention Resolution in Wireless Networks Thomas Kesselheim Berthold Vöcking 163
A Jamming-Resistant MAC Protocol for Multi-Hop Wireless Networks Andrea Richa Christian Scheideler Stefan Schmid Jin Zhang 179
Brief Announcements II (Session 1f)
Simple Gradecast Based Algorithms Michael Ben-Or Danny Dolev Ezra N. Hoch 194
Decentralized Network Bandwidth Prediction Sukhyun Song Pete Keleher Bobby Bhattacharjee Alan Sussman 198
Synchronous Las Vegas URMT Iff Asynchronous Monte Carlo URMT Abhinav Mehta Shashank Agrawal Kannan Srinathan 201
Invited Lecture II Best Student Paper (Session 2a)
Foundations of Speculative Distributed Computing (Invited Lecture Extended Abstract) Rachid Guerraoui 204
Anonymous Asynchronous Systems: The Case of Failure Detectors François Bonnet Michel Raynal 206
Consensus and Leader Election (Session 2b)
The Computational Structure of Progress Conditions Gadi Taubenfeld 221
Scalable Quantum Consensus for Crash Failures Bogdan S. Chlebus Dariusz R. Kowalski Michal Strojnowski 236
How Much Memory Is Needed for Leader Election Emanuele G. Fusco Andrzej Pelc 251
Leader Election Problem versus Pattern Formation Problem Yoann Dieudonné Franck Petit Vincent Villain 267
Mobile Agents (Session 2c)
Rendezvous of Mobile Agents in Directed Graphs Jérémie Chalopin Shantanu Das Peter Widmayer 282
Almost Optimal Asynchronous Rendezvous in Infinite Multidimensional Grids Evangelos Bampas Jurek Czyzowicz Leszek Gasieniec David Ilcinkas Arnaud Labourel 297
Exclusive Perpetual Ring Exploration without Chirality Lélia Blin Alessia Milani Maria Potop-Butucaru Sébastien Tixeuil 312
Drawing Maps with Advice Dariusz Dereniowski Andrzej Pelc 328
Invited Lecture III Wireless Networks (Session 3a)
Network-Aware Distributed Algorithms: Challenges and Opportunities in Wireless Networks (Invited Lecture Summary) Nitin Vaidya 343
Connectivity Problem in Wireless Networks Dariusz R. Kowalski Mariusz A. Rokicki 344
Computing in Wireless and Mobile Networks (Session 3b)
Trusted Computing for Fault-Prone Wireless Networks Seth Gilbert Dariusz R. Kowalski 359
Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony Antonio Fernández Anta Alessia Milani Miguel A. Mosteiro Shmuel Zaks 374
Brief Announcements III (Session 3c)
Failure Detectors Encapsulate Fairness Scott M. Pike Srikanth Sastry Jennifer L. Welch 389
Automated Support for the Design and Validation of Fault Tolerant Parameterized Systems - A Case Study Francesco Alberti Silvio Ghilardi Elena Pagani Silvio Ranise Gian Paolo Rossi 392
On Reversible and Irreversible Conversions Mitre C. Dourado Lucia Draque Penso Dieter Rautenbach Jayme L. Szwarcfiter 395
A Decentralized Algorithm for Distributed Trigger Counting Venkatesan T. Chakaravarthy Anamitra R. Choudhury Vijay K. Garg Yogish Sabharwal 398
Flash-Log - A High Throughput Log Mahesh Balakrishnan Philip A. Bernstein Dahlia Malkhi Vijayan Prabhakaran Colin Reid 401
New Bounds for Partially Synchronous Set Agreement Dan Alistarh Seth Gilbert Rachid Guerraoui Corentin Travers 404
Modeling Issues and Adversity (Session 3d)
It's on Me! The Benefit of Altruism in BAR Environments Edmund L. Wong Joshua B. Leners Lorenzo Alvisi 406
Beyond Lamport's Happened-Before: On the Role of Time Bounds in Synchronous Systems Ido Ben-Zvi Yoram Moses 421
On the Power of Non-spoofing Adversaries H.B. Acharya Mohamed Gouda 437
Implementing Fault-Tolerant Services Using State Machines: Beyond Replication Vijay K. Garg 450
Self-stabilizing and Graph Algortihms (Session 3e)
Low Communication Self-stabilization through Randomization Shay Kutten Dmitry Zinenko 465
Fast Self-stabilizing Minimum Spanning Tree Construction: Using Compact Nearest Common Ancestor Labeling Scheme Lélia Blin Shlomi Dolev Maria Gradinariu Potop-Butucaru Stephane Rovedakis 480
The Impact of Topology on Byzantine Containment in Stabilization Swan Dubois Toshimitsu Masuzawa Sébastien Tixeuil 495
Minimum Dominating Set Approximation in Graphs of Bounded Arboricity Christoph Lenzen Roger Wattenhofer 510
Brief Announcements IV (Session 3f)
Sharing Memory in a Self-stabilizing Manner Noga Alon Hagit Attiya Shlomi Dolev Swan Dubois Maria Gradinariu Sébastien Tixeuil 525
Stabilizing Consensus with the Power of Two Choices Benjamin Doerr Leslie Ann Goldberg Lorenz Minder Thomas Sauerwald Christian Scheideler 528
Author Index 531
