Stabilization, Safety, And Security Of Distributed Systems: 8th International Symposium, Sss 2006, Dallas, Tx, Usa, November 17-19, 2006, Proceedings (lecture Notes In Computer Science)

This symposium has been the main forum for presentation of research results in the area of self-\* for 17 years. It started as The Workshop on Self-Stabilizing Systems (WSS), and met in 1989 in Austin, 1995 in Las Vegas, 1997 in Santa Barbara, 1999 in Austin, and 2001 in Lisbon. It was then renamed The S- posium on Self-Stabilizing Systems (SSS), and has since met in 2003 in San Francisco, and in 2005 in Barcelona, Spain. This year,we extended the scope of the symposium to cover all safety and - curity related aspects of self-\* systems. The title of the symposium was changed to the International Symposium on Stabilization, Safety, and Security of D- tributed Systems (SSS) to re?ect this expansion. The decision by Mohamed Gouda, the General Chair, to expand the scope of the symposium was timely and successful. From 33 papers submitted for SSS 2005, the number of submissions increased to 155. Reviewing this surge of s- missions to select the ?nal set of papers for the symposium was a monumental taskfor the ProgramCommittee. The 61 ProgramCommittee membersdevoted countless hours reading and evaluating the papers. But even this e?ort was not enough; we recruited 143 external reviewers, whose work was also very subst- tial. Front Matter....Pages - Stabilization Enabling Technology....Pages 1-15 A General Characterization of Indulgence....Pages 16-34 Coverage, Connectivity, and Fault Tolerance Measures of Wireless Sensor Networks....Pages 35-49 A Case Study on Prototyping Power Management Protocols for Sensor Networks....Pages 50-64 Unconscious Eventual Consistency with Gossips....Pages 65-81 All k -Bounded Policies Are Equivalent for Self-stabilization....Pages 82-94 A 1-Strong Self-stabilizing Transformer....Pages 95-109 Optimal Message-Driven Implementation of Omega with Mute Processes....Pages 110-121 Incremental Synthesis of Fault-Tolerant Real-Time Programs....Pages 122-136 Toward a Time-Optimal Odd Phase Clock Unison in Trees....Pages 137-151 Recovery Oriented Programming....Pages 152-168 Evaluation of a Tracking Architecture in Wireless Sensor Networks....Pages 169-183 Self-protection for Distributed Component-Based Applications....Pages 184-198 From Self- to Snap- Stabilization....Pages 199-213 Self-stabilizing Philosophers with Generic Conflicts....Pages 214-230 Selfish Stabilization....Pages 231-243 Reliability and Availability Analysis of Self-stabilizing Systems....Pages 244-261 Circle Formation of Weak Mobile Robots....Pages 262-275 Self-stabilizing Device Drivers....Pages 276-289 Secure Communication for RFIDs Proactive Information Security Within Computational Security....Pages 290-303 Fault Masking in Tri-redundant Systems....Pages 304-313 Logarithmic Keying of Communication Networks....Pages 314-323 Safe Peer-to-Peer Self-downloading....Pages 324-334 Best Paper: Stabilizing Clock Synchronization for Wireless Sensor Networks....Pages 335-349 Self-stabilizing Byzantine Digital Clock Synchronization....Pages 350-362 Distributed Edge Coloration for Bipartite Networks....Pages 363-377 A Dependable Intrusion Detection Architecture Based on Agreement Services....Pages 378-394 Stabilizing Health Monitoring for Wireless Sensor Networks....Pages 395-410 A Byzantine-Fault Tolerant Self-stabilizing Protocol for Distributed Clock Synchronization Systems....Pages 411-427 A Memory Efficient Self-stabilizing Algorithm for Maximal k -Packing....Pages 428-439 Bounding the Impact of Unbounded Attacks in Stabilization....Pages 440-453 On Bootstrapping Topology Knowledge in Anonymous Networks....Pages 454-468 Self-adaptive Disk Arrays....Pages 469-483 Using Eventually Consistent Compasses to Gather Oblivious Mobile Robots with Limited Visibility....Pages 484-500 Self-stabilizing Asynchronous Phase Synchronization in General Graphs....Pages 501-515 Composition of Fault-Containing Protocols Based on Recovery Waiting Fault-Containing Composition Framework....Pages 516-532 Energy-Efficient and Non-interactive Self-certification in MANETs....Pages 533-547 Self-adaptive Worms and Countermeasures....Pages 548-562 Brief Announcement: Self-healing Algorithms for Reconfigurable Networks....Pages 563-565 Brief Announcement: Distributed Synthesis of Fault-Tolerance....Pages 566-567 Brief Announcement: Exploration and Mitigation of Deafness Problems in Directional Antennas Based Wireless Ad-Hoc Networks....Pages 568-569 Brief Announcement: A Synthetic Public Key Management Scheme for Large-Scale MANET....Pages 570-571 Brief Announcement: Termination Detection in an Asynchronous Distributed System with Crash-Recovery Failures....Pages 572-573 Brief Announcement: Self-stabilizing Spanning Tree Algorithm for Large Scale Systems....Pages 574-575 Brief Announcement: Chasing the Weakest System Model for Implementing $\it \Omega$ and Consensus....Pages 576-577 Brief Announcement: Wait-Free Dining for Eventual Weak Exclusion....Pages 578-579 Brief Announcement: An Efficient and Self-stabilizing Link Formation Algorithm....Pages 580-581 Brief Announcement: Analyzing the Interactions of Self-propagating Codes in Multi-hop Networks....Pages 582-583 Brief Announcement: Towards Modular Verification of Stabilisation in Self-adaptive Embedded Systems....Pages 584-585 Brief Announcement: An Adaptive Randomised Searching Protocol in Peer-to-Peer Systems Based on Probabilistic Weak Quorum System....Pages 586-587 Back Matter....Pages - This symposium has been the main forum for presentation of research results in the area of self-* for 17 years. It started as The Workshop on Self-Stabilizing Systems (WSS), and met in 1989 in Austin, 1995 in Las Vegas, 1997 in Santa Barbara, 1999 in Austin, and 2001 in Lisbon. It was then renamed The S- posium on Self-Stabilizing Systems (SSS), and has since met in 2003 in San Francisco, and in 2005 in Barcelona, Spain. This year, we extended the scope of the symposium to cover all safety and - curity related aspects of self-* systems. The title of the symposium was changed to the International Symposium on Stabilization, Safety, and Security of D- tributed Systems (SSS) to re?ect this expansion. The decision by Mohamed Gouda, the General Chair, to expand the scope of the symposium was timely and successful. From 33 papers submitted for SSS 2005, the number of submissions increased to 155. Reviewing this surge of s- missions to select the?nal set of papers for the symposium was a monumental taskfor the ProgramCommittee. The 61 ProgramCommittee membersdevoted countless hours reading and evaluating the papers. But even this e?ort was not enough; we recruited 143 external reviewers, whose work was also very subst- tial This book constitutes the refereed proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (formerly Symposium on Self-Stabilizing Systems), SSS 2006, held in Dallas, TX, USA in November 2006. The 36 revised full papers and 12 revised short papers presented together with the extended abstracts of 2 invited lectures were carefully reviewed and selected from 155 submissions. The papers address all aspects of self-stabilization, safety and security, recovery oriented systems and programing, from theoretical contributions, to reports of the actual experience of applying the principles of self-stabilization to static and dynamic systems Ajoy K. Datta, Maria Gradinariu (eds.). Includes Bibliographical References And Index.