22. DISC 2008: Arcachon, France

Regular Papers

• Marcos Kawazoe Aguilera, Eli Gafni, Leslie Lamport:
  The Mailbox Problem. 1-15
  
• Amitanand S. Aiyer, Lorenzo Alvisi, Rida A. Bazzi, Allen Clement:
  Matrix Signatures: From MACs to Digital Signatures in Distributed Systems. 16-31
  
• Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Corentin Travers:
  How to Solve Consensus in the Smallest Window of Synchrony. 32-46
  
• Jérémie Chalopin, Emmanuel Godard, Yves Métivier:
  Local Terminations and Distributed Computability in Anonymous Networks. 47-62
  
• Viacheslav Chernoy, Mordechai Shalom, Shmuel Zaks:
  A Self-stabilizing Algorithm with Tight Bounds for Mutual Exclusion on a Ring. 63-77
  
• Andrzej Czygrinow, Michal Hanckowiak, Wojciech Wawrzyniak:
  Fast Distributed Approximations in Planar Graphs. 78-92
  
• Robert Danek, Wojciech M. Golab:
  Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion. 93-108
  
• Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Andreas Tielmann:
  The Weakest Failure Detector for Message Passing Set-Agreement. 109-120
  
• Bilel Derbel:
  Local Maps: New Insights into Mobile Agent Algorithms. 121-136
  
• Stanko Dimitrov, P. Krishnan, Colin Mallows, Jean Meloche, Shalini Yajnik:
  r3: Resilient Random Regular Graphs. 137-151
  
• Michael Dinitz:
  Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics. 152-166
  
• Danny Dolev, Ezra N. Hoch:
  Constant-Space Localized Byzantine Consensus. 167-181
  
• Partha Dutta, Rachid Guerraoui, Ron R. Levy:
  Optimistic Erasure-Coded Distributed Storage. 182-196
  
• Mahmoud Elhaddad, Rami G. Melhem:
  On the Emulation of Finite-Buffered Output Queued Switches Using Combined Input-Output Queuing. 197-211
  
• Robert Elsässer, Leszek Gasieniec, Thomas Sauerwald:
  On Radio Broadcasting in Random Geometric Graphs. 212-226
  
• Paola Flocchini, David Ilcinkas, Nicola Santoro:
  Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens. 227-241
  
• Pierre Fraigniaud, Andrzej Pelc:
  Deterministic Rendezvous in Trees with Little Memory. 242-256
  
• Emanuele G. Fusco, Andrzej Pelc:
  Broadcasting in UDG Radio Networks with Missing and Inaccurate Information. 257-273
  
• Leszek Gasieniec, Dariusz R. Kowalski, Andrzej Lingas, Martin Wahlen:
  Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges. 274-288
  
• Chryssis Georgiou, Nicolas C. Nicolaou, Alexander A. Shvartsman:
  On the Robustness of (Semi) Fast Quorum-Based Implementations of Atomic Shared Memory. 289-304
  
• Rachid Guerraoui, Thomas A. Henzinger, Vasu Singh:
  Permissiveness in Transactional Memories. 305-319
  
• Phuong Hoai Ha, Philippas Tsigas, Otto J. Anshus:
  The Synchronization Power of Coalesced Memory Accesses. 320-334
  
• Maurice Herlihy, Flavio Paiva Junqueira, Keith Marzullo, Lucia Draque Penso:
  Optimizing Threshold Protocols in Adversarial Structures. 335-349
  
• Maurice Herlihy, Nir Shavit, Moran Tzafrir:
  Hopscotch Hashing. 350-364
  
• Iyad A. Kanj, Ljubomir Perkovic, Ge Xia:
  Computing Lightweight Spanners Locally. 365-378
  
• Goran Konjevod, Andréa W. Richa, Donglin Xia:
  Dynamic Routing and Location Services in Metrics of Low Doubling Dimension. 379-393
  
• Christoph Lenzen, Roger Wattenhofer:
  Leveraging Linial's Locality Limit. 394-407
  
• Tal Mizrahi, Yoram Moses:
  Continuous Consensus with Failures and Recoveries. 408-422
  
• Yoram Moses, Michel Raynal:
  No Double Discount: Condition-Based Simultaneity Yields Limited Gain. 423-437
  
• Yee Jiun Song, Robbert van Renesse:
  Bosco: One-Step Byzantine Asynchronous Consensus. 438-450
  
• Aaron D. Sterling:
  A Limit to the Power of Multiple Nucleation in Self-assembly. 451-465
  
• Tatsuhiro Tsuchiya, André Schiper:
  Using Bounded Model Checking to Verify Consensus Algorithms. 466-480
  
• Alireza Vahdatpour, Foad Dabiri, Maryam Moazeni, Majid Sarrafzadeh:
  Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks. 481-495
  

Brief Announcements

• Roberto Baldoni, François Bonnet, Alessia Milani, Michel Raynal:
  Brief Announcement: On the Solvability of Anonymous Partial Grids Exploration by Mobile Robots. 496-497
  
• Ioannis Chatzigiannakis, Paul G. Spirakis:
  The Dynamics of Probabilistic Population Protocols. 498-499
  
• David Coudert, Florian Huc, Dorian Mazauric:
  A Distributed Algorithm for Computing and Updating the Process Number of a Forest. 500-501
  
• Shlomi Dolev, Nir Tzachar:
  Brief Announcment: Corruption Resilient Fountain Codes. 502-503
  
• Antonio Fernández Anta, Miguel A. Mosteiro, Christopher Thraves:
  Brief Announcement: An Early-Stopping Protocol for Computing Aggregate Functions in Sensor Networks. 504-506
  
• Felix C. Freiling, Christian Lambertz, Mila E. Majster-Cederbaum:
  Easy Consensus Algorithms for the Crash-Recovery Model. 507-508
  
• Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan:
  Evaluating the Quality of a Network Topology through Random Walks. 509-511
  
• Robert Danek, Hyonho Lee:
  Brief Announcement: Local-Spin Algorithms for Abortable Mutual Exclusion and Related Problems. 512-513
  
• Simona Orzan, Muhammad Torabi Dashti:
  Data Failures. 514-515
  
• Marin Bertier, Anne-Marie Kermarrec, Guang Tan:
  Reliable Broadcast Tolerating Byzantine Faults in a Message-Bounded Radio Network. 516-517
  
• Sara Tucci Piergiovanni, Roberto Baldoni:
  Brief Announcement: Eventual Leader Election in the Infinite Arrival Message-Passing System Model. 518-519