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

Workshops plannings

GRAAL program (here)
DYNAMO program (here)
FRACAS&MALISSE program (here)

Program of DISC

Program of DISC [booklet.pdf]

Sunday, September 21 - 1st floor, Palais des Congrès

18:00 - 20:00 Welcoming Reception. A registration desk will operate from 18:00 to 20:00.

Monday, September 22 - salle des Ambassadeurs, Palais des Congrès

8:00 - 8:50 Registration

8:55 Welcome address

9:00 Invited talk by David Harel

Title: In Silico Biology, or On Comprehensive and Realistic Modeling

Abstract: The talk shows the way software and systems engineering, especially of reactive systems, can be applied beneficially to the life sciences. We will discuss the idea of comprehensive and realistic computerized modeling of biological systems. In comprehensive modeling the main purpose is to understand an entire system in detail, utilizing in the modeling effort all that is known about the system, and to use that understanding to analyze and predict behavior in silico. In realistic modeling the main issue is to model the behavior of actual elements, making possible totally interactive and modifiable realistic executions and simulations that reveal emergent properties. I will address the motivation for such modeling and the philosophy underlying the techniques for carrying it out, as well as the crucial question of when such models are to be deemed valid, or complete. The examples I will present will be from among the biological modeling efforts my group has been involved in: T cell development in the thymus, lymph node behavior, organogenesis of the pancreas, fate determination in the reproductive system of C. elegans , and a generic cell model. I will also discuss a long-term "grand challenge" --- to model a full multi-cellular organism.

10:00 Coffee break

10:20 - 12:25
Session 1: Consensus - Session chair: Philippas Tsigas

  • 10:20
    How to Solve Consensus in the Smallest Window of Synchrony
    Dan Alistarh, Seth Gilbert, Rachid Guerraoui and Corentin Travers

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

  • 11:10
    Continuous Consensus with Failures and Recoveries
    Tal Mizrahi and Yoram Moses

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

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

12:30 - 14:00 Lunch

14:00 - 16:05
Session 2: Network and graph algorithms - Session chair: Dariusz Kowalski

  • 14:00
    Fast Distributed Approximations in Planar Graphs
    Andrzej Czygrinow, Michal Hanckowiak and Wojciech Wawrzyniak

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

  • 14:50
    r^3: Resilient Random Regular Graphs
    Stanko Dimitrov, P Krishnan, Colin Mallows, Jean Meloche and Shalini Yajnik

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

  • 15:40
    Computing Lightweight Spanning Subgraphs Locally
    Iyad Kanj, Ljubomir Perkovic and Ge Xia

16:05 - 16:25 Coffee break

16:25 - 18:30
Session 3: Fault tolerance and distributed data - Session chair: Shay Kutten

  • 16:25
    A Self-stabilizing Algorithm with Tight Bounds for Mutual Exclusion on a Ring
    Viacheslav Chernoy, Mordechai Shalom and Shmuel Zaks

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

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

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

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

18:40 Business meeting

Tuesday, September 23 - salle des Ambassadeurs, Palais des Congrès

9:00 Invited talk by Alexander A. Shvartsman

Title: Distributed Cooperation and Adversity: Complexity Trade-Offs

Abstract: The problem of cooperatively performing a collection of tasks in a decentralized setting where the computing medium is subject to undesirable perturbations is one of the fundamental problems in distributed computing, with applications encompassing such important areas as Internet supercomputing, parallel simulation, and multi-agent collaboration. The perturbations in the computing medium are typically due to processor and software failures (benign or malicious), communication breakdowns, and unpredictable delays. Such perturbations become even more prominent when an application needs to harness massive amounts of available computational resources. To develop efficient solutions for computation problems based on distributed cooperation, it is important to understand efficiency trade-offs characterizing the ability of p processors to cooperate on t tasks in key models of computation in the presence of adversity. In this talk we survey historical and recent results for distributed cooperation roughly grouped along the following topics: (i) fundamental failure-sensitive bounds for distributed cooperation problems for synchronous crash-prone processors, (ii) upper and lower bounds on distributed cooperation in shared-memory models, (iii) bounds on distributed work in message-passing models and on redundant work for processors that may experience prolonged absence of communication.

10:00 Coffee break

10:20 - 12:25
Session 4: Shared memory synchronization - Session chair: Michel Raynal

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

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

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

  • 11:35
    Hopscotch Hashing
    Maurice Herlihy, Nir Shavit and Moran Tzafrir

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

12:30 - 14:00 Lunch

14:00 - 15:28
Brief announcements session - Session chair: Chryssis Georgiou

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

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

  • 14:16
    A Distributed Algorithm for Computing and Updating the Process Number of a Forest
    David Coudert, Florian Huc and Dorian Mazauric

  • 14:24
    Corruption Resistant Local Codes
    Shlomi Dolev and Nir Tzachar

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

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

  • 14:48
    Evaluating the Quality of a Network Topology Through Random Walks
    Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola and Gilles Tredan

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

  • 15:04
    Data Failures
    Simona Orzan and Mohammad Torabi Dashti

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

  • 15:20
    Eventual Leader Election in the Infinite Arrival Message-passing System Model
    Sara Tucci-Piergiovanni and Roberto Baldoni

15:40 - 16:00 Coffee break

Wednesday, September 24 - salle des Ambassadeurs, Palais des Congrès

9:00 Invited talk by Phillip B. Gibbons

Title: Fun with Networks: Social, Sensor, and Shape Shifting

Abstract: Part of the "fun" in algorithmic research in networking arises from the emergence of important new network settings. These new settings bring new algorithmic problems to be formulated and studied. In this talk, we consider three such settings. First, we consider social networks and how they can be used in a novel way to defend against Sybil attacks in P2P distributed systems. In a Sybil attack, a malicious user creates a very large number of fake identities in order to out-vote the honest users in collaborative P2P tasks. Our protocols, SybilGuard and its follow-on SybilLimit, use randomized routes (a variant of random walks) on a social network topology in order to reject all but a limited number of votes by fake identities. Second, we consider wireless sensor networks and how to perform robust, in-network aggregation in an energy-efficient way. Our approach, Synopsis Diffusion, seeks to combine the energy-efficiency of tree-based aggregation with the robustness of gossip-based aggregation. This is accomplished through the use of order-and-duplicate-insensitive (ODI) synopses, which enable the efficient, robust use of the broadcast wireless medium. We present a theory of ODI synopses, as well as open problems. Finally, we look ahead to a new network setting arising from modular robotic ensembles of billions of submillimeter-sized modules, called catoms. Catoms dynamically form physical shapes by "rolling" across each other under software control. While we present a few initial results, devising an effective communication scheme for such networks remains an open problem.
This talk covers joint work with Casey Helfrich, Michael Kaminsky, Amit Manjhi, Todd Mowry, Suman Nath, Padmanabhan Pillai, Srinivasan Seshan, and Haifeng Yu.

10:00 Coffee break

10:20 - 12:25
Session 5: Radio Networks and message passing algorithms - Session chair: Seth Gilbert

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

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

  • 11:10
    Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges
    Leszek Gasieniec, Dariusz Kowalski, Andrzej Lingas and Martin Wahlen

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

  • 12:00
    Local Terminations and Distributed Computability in Anonymous Networks
    Jeremie Chalopin, Emmanuel Godard and Metivier Yves

12:30 - 14:00 Lunch

14:00 - 15:40
Session 6: Network algorithms and sensor networks - Session chair: Sebastien Tixeuil

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

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

  • 14:50
    On the Emulation of Finite-buffered OQ Switches using Combined Input-Output Queuing
    Mahmoud Elhaddad and Rami Melhem

  • 15:15
    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

15:40 - 16:00 Coffee break

16:00 - 17:40
Session 7: Mobile agents and failure detectors - Session chair: Amos Korman

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

  • 16:25
    Deterministic Rendezvous in Trees with Little Memory
    Pierre Fraigniaud and Andrzej Pelc

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

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


Pôle RésCom