DISC 2008
September 22-24, 2008, Arcachon, France.
22nd International Symposium on Distributed Computing

Accepted papers

Regular papers

  • A Self-stabilizing algorithm with tight bounds for mutual exclusion on a ring
    Viacheslav Chernoy, Mordechai Shalom and Shmuel Zaks

  • Computing lightweight spanning subgraphs locally
    Iyad Kanj, Ljubomir Perkovic and Ge Xia

  • Ping Pong in Dangerous Graphs
    Paola Flocchini, David Ilcinkas and Nicola Santoro

  • A Limit to the Power of Multiple Nucleation in Self-Assembly
    Aaron Sterling

  • r3: Resilient Random Regular Graphs
    Stanko Dimitrov, P Krishnan, Colin Mallows, Jean Meloche and Shalini Yajnik

  • Broadcasting in UDG Radio Networks with Missing and Inaccurate Information
    Emanuele Guido Fusco and Andrzej Pelc

  • Local Maps: New Insights into Mobile Agent Algorithms
    Bilel Derbel

  • Leveraging Linial's Locality Limit
    Christoph Lenzen and Roger Wattenhofer

  • Local Terminations and Distributed Computabillity in Anonymous Networks
    Jeremie Chalopin, Emmanuel Godard and Metivier Yves

  • Deterministic rendezvous in trees with little memory
    Pierre Fraigniaud and Andrzej Pelc

  • Fast distributed approximations in planar graphs
    Andrzej Czygrinow, Michal Hanckowiak and Wojciech Wawrzyniak

  • Bosco: One-Step Byzantine Asynchronous Consensus
    Yee Jiun Song and Robbert van Renesse

  • No Double Discount: Condition-based Simultaneity Yields Limited Gain
    Yoram Moses and Michel Raynal

  • Using Bounded Model Checking to Verify Consensus Algorithms
    Tatsuhiro Tsuchiya and Andre Schiper

  • Efficient broadcasting in known geometric radio networks with non-uniform ranges
    Leszek Gasieniec, Dariusz Kowalski, Andrzej Lingas and Martin Wahlen

  • The Weakest Failure Detector for Message Passing Set-Agreement
    Carole Delporte, Hugues Fauconnier, Rachid Guerraoui and Andreas Tielmann

  • Matrix Signatures: From MACs to Digital Signatures in Distributed Systems
    Amitanand Aiyer, Lorenzo Alvisi, Rida Bazzi and Allen Clement

  • On Radio Broadcasting in Random Geometric Graphs
    Robert Elsaesser, Leszek Gasieniec and Thomas Sauerwald

  • The Synchronization Power of Coalesced Memory Accesses
    Phuong Ha, Philippas Tsigas and Otto Anshus

  • Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics
    Michael Dinitz

  • How to solve consensus in the smallest window of synchrony
    Dan Alistarh, Seth Gilbert, Rachid Guerraoui and Corentin Travers

  • Constant-space Localized Byzantine Consensus
    Danny Dolev and Ezra N. Hoch

  • Permissiveness in Transactional Memories
    Rachid Guerraoui, Thomas Henzinger and Vasu Singh

  • Optimistic Erasure Coded Distributed Storage
    Partha Dutta, Rachid Guerraoui and Ron Levy

  • Optimizing Threshold Protocols in Adversarial Structures
    Maurice Herlihy, Flavio Junqueira, Keith Marzullo and Lucia Draque Penso

  • Continuous Consensus with Failures and Recoveries
    Yoram Moses and Tal Mizrahi

  • Theoretical Bound and Practical Analysis of Minimum Connected Dominating Set in Ad Hoc and Sensor Networks
    Alireza Vahdatpour, Foad Dabiri, Maryam Moazeni and Majid Sarrafzadeh

  • Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion
    Robert Danek and Wojciech Golab

  • Dynamic Routing and Location Services in Metrics of Low Doubling Dimension
    Goran Konjevod, Andrea Richa and Donglin Xia

  • The Mailbox Problem
    Marcos Aguilera, Eli Gafni and Leslie Lamport

  • Hopscotch Hashing
    Moran Tzafrir, Nir Shavit and Maurice Herlihy

  • On the Robustness of (Semi)Fast Quorum-Based Implementations of Atomic Shared Memory
    Chryssis Georgiou, Nicolas Nicolaou and Alexander Shvartsman

  • On the emulation of finite-buffered OQ switches using Combined Input-Output Queuing
    Mahmoud Elhaddad and Rami Melhem

Brief announcements

  • Easy Consensus Algorithms for the Crash-Recovery Model
    Felix Freiling, Christian Lambertz and Mila Majster-Cederbaum

  • A distributed algorithm for computing and updating the process number of a forest
    David Coudert, Florian Huc and Dorian Mazauric

  • On the Solvability of Anonymous Partial Grids Exploration
    Roberto Baldoni, François Bonnet, Alessia Milani and Michel Raynal

  • Local-Spin Algorithms for Abortable Mutual Exclusion and Related Problems
    Hyonho Lee and Robert Danek

  • Corruption Resistant Local Codes
    Shlomi Dolev and Nir Tzachar

  • Reliable Broadcast Tolerating Byzantine Faults in a Message-Bounded Radio Network
    Guang Tan, Marin Bertier and Anne-Marie Kermarrec

  • The Dynamics of Probabilistic Population Protocols
    Ioannis Chatzigiannakis and Paul Spirakis

  • Eventual Leader Election in the Infinite Arrival Message-passing System Model
    Sara Tucci-Piergiovanni and roberto Baldoni

  • Data failures
    Simona Orzan and Mohammad Torabi Dashti

  • An Early-stopping Protocol for Computing Aggregate Functions in Sensor Networks
    Antonio Fernandez, Miguel Mosteiro and Christopher Thraves

  • Evaluating the quality of a network topology through random walks
    Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola and Gilles Tredan


Pôle RésCom