Self-Stabilizing Systems

Self-stabilizationisanestablishedprincipleofmoderndistributedsystemdesign. Theadvantagesofsystemsthatself-recoverfromtransientfailures,temporary- curity attacks,and spontaneousrecon?gurationareobvious.Lessobviousis how the ambitious goal of recovering from the most general case of a transient fault, namelythatofanarbitraryinitialstate,canleadtoasimplersystemdesignthan dealing with particular cases of failures. In the area of mathematical probl- solving, Po lya gave the term the inventors paradox to such situations, where generalizing the problem may simplify the solution. The dramatic growthof d- tributed systems, peer-to-peer distribution networks, and large grid computing environments confronts designers with serious di?culties of complexity and has motivated the call for systems that self-recover, self-tune, and self-manage. The principlesofself-stabilizationcanbeusefulfor thesegoalsofautonomoussystem behavior. The Symposium on Self-Stabilizing Systems (SSS) is the main forum for - search in the area of self-stabilization. Previous Workshops on Self-Stabilizing Systems (WSS) were held in 1989, 1995, 1997, 1999, and 2001. The previous Symposium on Self-Stabilizing Systems (SSS) took place in 2003. Thirty-three papersweresubmitted toSSS2005byauthorsfromEurope(16),NorthAmerica (8), Asia (4), and elsewhere (5). From the submissions, the program committee selected 15 for inclusion in these proceedings. In addition to the presentation of these papers, the symposium event included a poster session with brief pres- tations of recent work on self-stabilization.

Inhalt
Snap-Stabilizing Optimal Binary Search Tree.- Synchronous vs. Asynchronous Unison.- A Snap-Stabilizing DFS with a Lower Space Requirement.- Self-stabilization of Byzantine Protocols.- Self-stabilization with r-Operators Revisited.- Self-stabilization Preserving Compiler.- Self-stabilizing Mobile Node Location Management and Message Routing.- Memory Management for Self-stabilizing Operating Systems.- Code Stabilization.- Stabilizing Certificate Dispersal.- On the Possibility and the Impossibility of Message-Driven Self-stabilizing Failure Detection.- Approximation of Self-stabilizing Vertex Cover Less Than 2.- Self-stabilization in Spite of Frequent Changes of Networks: Case Study of Mutual Exclusion on Dynamic Rings.- Towards Automatic Convergence Verification of Self-stabilizing Algorithms.- About the Self-stabilization of a Virtual Topology for Self-organization in Ad Hoc Networks.