Stabilization, Safety, and Security of Distributed Systems

1. Front Matter

   PDF

2. Keynote Talks

   1. Keynote: Primitives for Physical Trust

      • Anish Arora

      Pages 1-1

   2. Keynote: Trustworthy Services and the Biological Analogy

      • Michael Reiter

      Pages 2-2

   3. Keynote: Distributed Algorithms and VLSI

      • Ulrich Schmid

      Pages 3-3

3. MAC Layer Protocols

   1. A Distributed and Deterministic TDMA Algorithm for Write-All-With-Collision Model

      • Mahesh Arumugam

      Pages 4-18

   2. Distance-2 Self-stabilizing Algorithm for a b-Coloring of Graphs

      • Lyes Dekar, Hamamache Kheddouci

      Pages 19-31

4. Wireless Networks I

   1. Duty Cycle Stabilization in Semi-mobile Wireless Networks

      • Jing Li, Anish Arora

      Pages 32-46

   2. DISH: Distributed Self-Healing

      • Di Ma, Gene Tsudik

      Pages 47-62

   3. Universe Detectors for Sybil Defense in Ad Hoc Wireless Networks

      • Adnan Vora, Mikhail Nesterenko, Sébastien Tixeuil, Sylvie Delaët

      Pages 63-78

5. Stabilizing Algorithms I

   1. Self-stabilizing Numerical Iterative Computation

      • Ezra N. Hoch, Danny Bickson, Danny Dolev

      Pages 79-93

   2. A Self-stabilizing \(\frac{2}{3}\)-Approximation Algorithm for the Maximum Matching Problem

      • Fredrik Manne, Morten Mjelde, Laurence Pilard, Sébastien Tixeuil

      Pages 94-108

   3. Self-Stabilizing Leader Election in Optimal Space

      • Ajoy K. Datta, Lawrence L. Larmore, Priyanka Vemula

      Pages 109-123

6. Stabilizing Algorithms II

   1. Tiara: A Self-stabilizing Deterministic Skip List

      • Thomas Clouser, Mikhail Nesterenko, Christian Scheideler

      Pages 124-140

   2. Local Synchronization on Oriented Rings

      • Doina Bein, Ajoy K. Datta, Chitwan K. Gupta, Lawrence L. Larmore

      Pages 141-155

   3. Stabilization of Max-Min Fair Networks without Per-flow State

      • Jorge A. Cobb, Mohamed G. Gouda

      Pages 156-172

7. Wireless Networks II

   1. Convergence Time Analysis of Self-stabilizing Algorithms in Wireless Sensor Networks with Unreliable Links

      • Hirotsugu Kakugawa, Toshimitsu Masuzawa

      Pages 173-187

   2. Self-stabilizing Mobile Robot Formations with Virtual Nodes

      • Seth Gilbert, Nancy Lynch, Sayan Mitra, Tina Nolte

      Pages 188-202

   3. An Application of Specification-Based Design of Self-stabilization to Tracking in Wireless Sensor Networks

      • Murat Demirbas, Anish Arora

      Pages 203-217

8. Security and System Models

   1. Our Brothers’ Keepers: Secure Routing with High Performance

      • Alex Brodsky, Scott Lindenberg

      Pages 218-232

   2. Pharewell to Phishing

      • Taehwan Choi, Sooel Son, Mohamed G. Gouda, Jorge A. Cobb

      Pages 233-245

This volume contains the proceedings of the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), held November 21–23, 2008 in Detroit, Michigan USA. SSS started as the Workshop on Self-Stabilizing Systems (WSS), which was ?rst held at Austin in 1989. From the second WSS in Las Vegas in 1995, the - rum was held biennially, at Santa Barbara(1997),Austin (1999), Lisbon (2001), San Francisco (2003) and Barcelona (2005). The title of the forum changed to the Symposium on Self-Stabilizing Systems (SSS) in 2003. Since 2005, SSS was run annually, and in 2006 (Dallas) the scope of the conference was extended to cover all safety and security-related aspects of self-* systems. This extension followed the demand for self-stabilization in various areas of distributed c- puting including peer-to-peer networks, wireless sensor networks, mobile ad-hoc networks, robotic networks. To re?ect this change, the name of the symposium changed to the International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). This year we received 43 submissions from 13 countries. Most submissions were from the USA and France. Each submission was carefully reviewed by three to six Program Committee members with the help of external reviewers. For the ?rst time a rebuttal phase allowed the authors to react to the reviews beforethediscussionofthepaperswithintheProgramCommittee. Outofthe43 submissions,17excellentpaperswereselectedforpresentationatthesymposium, whichcorrespondsto anacceptancerateof40%. Itcanbenotedthatthehighest acceptance rate was for papers with keywordssensor networks (86%),MANETs (67%),andsecurityof sensorandmobile networksprotocols (67%).

• Peer
• adaptive systems
• algorithms
• distributed algorithms
• distributed systems
• fault-tolerance
• graphs
• network topologies
• overlays
• peer authentication
• peer-to-peer networks
• probabilistic self-stabilization
• program transformation
• secure routing
• self-assembling systems
• algorithm analysis and problem complexity

• Department of Computer Science and Engineering, Michigan State University, East Lansing, USA

  Sandeep Kulkarni

• École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland

  André Schiper

Policies and ethics