23. DISC 2009: Elche, Spain

• Lorenzo Alvisi, Rachid Guerraoui, Prasad Jayanti, Idit Keidar, Shay Kutten, Jennifer L. Welch:
  The 2009 Edsger W. Dijkstra Prize in Distributed Computing. 1-2
  

Michel Raynal and Shmuel Zaks 60th Birthday Symposium

• Jean-Michel Hélary:
  Computing, Observing, Controlling, Checkpointing: Symbiosis Is Even Better Than Agreement! 3-4
  
• Achour Mostéfaoui:
  What Agreement Problems Owe Michel. 5
  
• Nicola Santoro:
  Shmuel Zaks - The Early Years: A Combinatorialist in Distributed Computing. 6
  
• Mordechai Shalom:
  Shmuel Zaks - The Mathematician, Computer Scientist and Personality. 7
  

Award Nominees

• Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Andreas Tielmann:
  The Disagreement Power of an Adversary. 8-21
  
• Yuval Emek, Amos Korman:
  New Bounds for the Controller Problem. 22-34
  
• Eli Gafni, Petr Kuznetsov:
  On Set Consensus Numbers. 35-47
  
• Fabian Kuhn, Nancy A. Lynch, Calvin C. Newport:
  The Abstract MAC Layer. 48-62
  
• Henrique Moniz, Nuno Ferreira Neves, Miguel Correia, Paulo Veríssimo:
  Randomization Can Be a Healer: Consensus with Dynamic Omission Failures. 63-77
  

Transactional Memory

• Yehuda Afek, Nir Shavit, Moran Tzafrir:
  Interrupting Snapshots and the Java^TM^{\mbox{\tiny TM}} Size() Method. 78-92
  
• Pascal Felber, Vincent Gramoli, Rachid Guerraoui:
  Elastic Transactions. 93-107
  
• Hagit Attiya, Alessia Milani:
  Brief Announcement: Transactional Scheduling for Read-Dominated Workloads. 108-110
  

Shared Memory

• Yehuda Afek, Eli Gafni, Opher Lieber:
  Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus. 111-126
  
• Panagiota Fatourou, Nikolaos D. Kallimanis:
  The RedBlue Adaptive Universal Constructions. 127-141
  
• Damien Imbs, Michel Raynal:
  Help When Needed, But No More: Efficient Read/Write Partial Snapshot. 142-156
  
• Gadi Taubenfeld:
  Contention-Sensitive Data Structures and Algorithms. 157-171
  
• Michiko Inoue, Tsuyoshi Suzuki, Hideo Fujiwara:
  Brief Announcement: Acceleration by Contention for Shared Memory Mutual Exclusion Algorithms. 172-173
  
• Ananda Basu, Borzoo Bonakdarpour, Marius Bozga, Joseph Sifakis:
  Brief Announcement: Incremental Component-Based Modeling, Verification, and Performance Evaluation of Distributed Reset. 174-175
  

Distributed and Local Graph Algorithms

• Bilel Derbel, Cyril Gavoille, David Peleg, Laurent Viennot:
  Local Computation of Nearly Additive Spanners. 176-190
  
• Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, Jara Uitto:
  A Local 2-Approximation Algorithm for the Vertex Cover Problem. 191-205
  
• Zvika Brakerski, Boaz Patt-Shamir:
  Distributed Discovery of Large Near-Cliques. 206-220
  
• Christos Koufogiannakis, Neal E. Young:
  Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality. 221-238
  
• Ioannis Chatzigiannakis, Othon Michail, Paul G. Spirakis:
  Brief Announcement: Decidable Graph Languages by Mediated Population Protocols. 239-240
  
• Rachid Guerraoui, Kévin Huguenin, Anne-Marie Kermarrec, Maxime Monod:
  Brief Announcement: Towards Secured Distributed Polling in Social Networks. 241-242
  

Modeling Issues

• Cyril Gavoille, Adrian Kosowski, Marcin Markiewicz:
  What Can Be Observed Locally? 243-257
  
• Sotiris Kentros, Aggelos Kiayias, Nicolas C. Nicolaou, Alexander A. Shvartsman:
  At-Most-Once Semantics in Asynchronous Shared Memory. 258-273
  
• Simon Doherty, Mark Moir:
  Nonblocking Algorithms and Backward Simulation. 274-288
  
• Péter Bokor, Marco Serafini, Neeraj Suri, Helmut Veith:
  Brief Announcement: Efficient Model Checking of Fault-Tolerant Distributed Protocols Using Symmetry Reduction. 289-290
  
• Swan Dubois, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil:
  Brief Announcement: Dynamic FTSS in Asynchronous Systems: The Case of Unison. 291-293
  

Game Theory

• Martin Hoefer, Siddharth Suri:
  Dynamics in Network Interaction Games. 294-308
  
• Ashraf Al Daoud, Sachin Agarwal, Tansu Alpcan:
  Brief Announcement: Cloud Computing Games: Pricing Services of Large Data Centers. 309-310
  

Failure Detectors

• Vibhor Bhatt, Prasad Jayanti:
  On the Existence of Weakest Failure Detectors for Mutual Exclusion and k-Exclusion. 311-325
  
• Srikanth Sastry, Scott M. Pike, Jennifer L. Welch:
  Crash-Quiescent Failure Detection. 326-340
  
• François Bonnet, Michel Raynal:
  The Price of Anonymity: Optimal Consensus Despite Asynchrony, Crash and Anonymity. 341-355
  
• Mikel Larrea, Cristian Martín:
  Brief Announcement: On Implementing Omega Efficiently in the Crash-Recovery Model. 356-357
  
• Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg:
  Brief Announcement: The Minimum Failure Detector for Non-Local Tasks in Message-Passing Systems. 358-359
  
• Martin Biely, Peter Robinson, Ulrich Schmid:
  Brief Announcement: Weak Synchrony Models and Failure Detectors for Message Passing (k-)Set Agreement. 360-361
  

From Theory to Practice

• Flavio Paiva Junqueira, Benjamin C. Reed:
  Brief Announcement Zab: A Practical Totally Ordered Broadcast Protocol. 362-363
  

Graph Algorithms and Routing

• Ittai Abraham, Dahlia Malkhi, David Ratajczak:
  Compact Multicast Routing. 364-378
  
• Wei Chen, Christian Sommer, Shang-Hua Teng, Yajun Wang:
  Compact Routing in Power-Law Graphs. 379-391
  
• Dahlia Malkhi, Siddhartha Sen, Kunal Talwar, Renato Fonseca F. Werneck, Udi Wieder:
  Virtual Ring Routing Trends. 392-406
  
• Lélia Blin, Maria Potop-Butucaru, Stephane Rovedakis, Sébastien Tixeuil:
  A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property. 407-422
  
• Evangelos Bampas, Leszek Gasieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing, Adrian Kosowski:
  Euler Tour Lock-In Problem in the Rotor-Router Model. 423-435
  

Consensus and Byzantine Agreement

• Yoram Moses:
  Optimum Simultaneous Consensus for General Omissions Is Equivalent to an NP Oracle. 436-448
  
• Matthias Fitzi, Jesper Buus Nielsen:
  On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement. 449-463
  
• Valerie King, Jared Saia:
  From Almost Everywhere to Everywhere: Byzantine Agreement with Õ(n^3/2) Bits. 464-478
  
• Fatemeh Borran, André Schiper:
  Brief Announcement: A Leader-free Byzantine Consensus Algorithm. 479-480
  

Radio Networks

• Erez Kantor, David Peleg:
  Efficient k-Shot Broadcasting in Radio Networks. 481-495
  
• Alejandro Cornejo, Fabian Kuhn, Ruy Ley-Wild, Nancy A. Lynch:
  Keeping Mobile Robot Swarms Connected. 496-511
  
• Jurek Czyzowicz, Leszek Gasieniec, Dariusz R. Kowalski, Andrzej Pelc:
  Consensus and Mutual Exclusion in a Multiple Access Channel. 512-526
  
• Roy Friedman, Alex Kogan:
  Brief Announcement: Efficient Utilization of Multiple Interfaces in Wireless Ad Hoc Networks. 527-528
  
• Nikolaos Fountoulakis, Anna Huber, Konstantinos Panagiotou:
  Brief Announcement: The Speed of Broadcasting in Random Networks - Density Does Not Matter. 529-530