Self-Stabilizing Systems: 6th International Symposium, SSS 2003, San Francisco, CA, USA, June 24-25, 2003, Proceedings (Lecture Notes in Computer Science (2704))

This Book Constitutes The Refereed Proceedings Of The 6th International Symposium On Self-stabilizing Systems, Sss 2003, Held In San Francisco, Ca, Usa, In June 2003. The 15 Revised Full Papers Presented Were Carefully Reviewed And Selected From 27 Submissions. The Papers Address Self-stabilization Issues For Various Types Of Systems And Software Including Communication Protocols, Sensor Networks, Biological Systems, And Directed Networks; Several New Algorithms Are Presented. A Pursuer-evader Game For Sensor Networks -- Collision-free Communication In Sensor Networks -- Self-stabilizing Pulse Synchronization Inspired By Biological Pacemaker Networks -- Self-stabilizing Algorithms For {k}-domination -- Self-stabilizing Group Communication In Directed Networks (extended Abstract) -- Lyapunov Analysis Of Neural Network Stability In An Adaptive Flight Control System -- Self-stabilizing Token Circulation On Uniform Trees By Using Edge-tokens -- Self-stabilizing Atomicity Refinement Allowing Neighborhood Concurrency -- A New Self-stabilizing ?-out-of-? Exclusion Algorithm On Rings -- A Framework Of Safe Stabilization -- A Method For Evaluating Efficiency Of Protocols On The Asynchronous Shared-state Model -- Time-efficient Self-stabilizing Algorithms Through Hierarchical Structures -- A Stabilizing Solution To The Stable Path Problem -- Route Preserving Stabilization -- An Improved Snap-stabilizing Pif Algorithm. Shing-tsaan Huang, Ted Herman (eds.). Lecture Notes in Computer Science Preface Organization Table of Contents A Pursuer-Evader Game for Sensor Networks Introduction The Problem An Evader-Centric Program Proof of Correctness Proof of Stabilization Performance Metrics A Pursuer-Centric Program Proof of Correctness Proof of Stabilization Performance Metrics A Hybrid Pursuer-Evader Program Proof of Correctness Proof of Stabilization Performance Metrics An Efficient Version of the Hybrid Program Performance Metrics Discussion and Related Work References Collision-Free Communication in Sensor Networks Introduction Model and Assumptions Collision-Free Diffusion Version 1: Communicate 1, Interfere 1 Version 2: Communicate x, Interfere x Version 3: Communicate 1, Interfere y Version 4: Communicate x, Interfere y Diffusion by an Arbitrary Sensor Observations about Our Algorithm Application to Time-Division Multiplexing (TDM) Simple TDM Algorithm Stabilization of TDM and Diffusion Extensions: Dealing with Failed/Sleeping Sensors and Arbitrary Topology Diffusion in Imperfect Grids or Grids with Failed Sensors/Links Diffusion to Other Graphs Related Work Conclusion and Future Work References Self-Stabilizing Pulse Synchronization Inspired by Biological Pacemaker Networks Introduction Assumptions, Definitions and Specifications of the Algorithm The ``Pulse Synchronization'' Algorithm Solving the ``Pulse Synchronization'' Problem Analysis of the Algorithm and Comparison to Related Algorithms Discussion References Appendix: The Summation Algorithm Self-Stabilizing Algorithms for {k}-Domination Introduction {k}-Domination Minimal {k}-Dominating Function Minimal {2}-Dominating Function Concluding Remarks References Self-Stabilizing Group Communication in Directed Networks Introduction The System Group Communication Specifications Group Communication Algorithms Token Algorithm: Tree Algorithm: Emulating a General Topology Resource Allocation Concluding Remarks References Lyapunov Analysis of Neural Network Stability in an Adaptive Flight Control System Introduction Background Limitations of Traditional Self-Stabilization Proof Techniques Overview Self-Stabilization Using Lyapunov Functions DCS Neural Network Competitive Hebb Rule (CHR) Kohonen-Like Rule (KLR) Growing the Network DCS Algorithm Self-Stabilization of DCS Network State Space of the DCS Network Mathematical Verification of Self-Stabilization Online Stability Monitoring Case Study Summary and Discussion References Self-Stabilizing Token Circulation on Uniform Trees by Using Edge-Tokens* Introduction The Self-Stabilizing Edge Token Algorithm The Token Circulation Algorithm The Correctness Proof and Analysis for the Token Circulation Algorithm Correctness Proof Complexity Analysis Concluding Remarks References Self-Stabilizing Atomicity Refinement Allowing Neighborhood Concurrency Introduction Preliminaries Local Resource Allocation Self-Stabilizing LRA Protocol Proof of Correctness Atomicity Transformation Conclusion References A New Self-Stabilizing k-out-of- l Exclusion Algorithm on Rings Introduction Preliminaries The k-out-of- l Exclusion Specification Non-self-stabilizing k-out-of- l Exclusion Protocol Self-Stabilizing k-out-of- l Exclusion Protocol Protocols Proof Outline Conclusion References A Framework of Safe Stabilization Introduction Preliminaries Strong and Weak Safety Safety Margin A First Step Relationship between Fault Models and Safe Stabilization Designing Algorithms for Safe Stabilization Performance Conclusion References A Method for Evaluating Efficiency of Protocols on the Asynchronous Shared-State Model Introduction Model Linear State-Transition Protocol Efficiency Evaluation of the LST Protocols Key Properties of the LST Protocols A Method for Evaluating Efficiency of the LST Protocols Application for Stabilizing Alternator Stabilizing Alternator Application of the Proposed Method Performance Analysis Conclusion References Time-Efficient Self-Stabilizing Algorithms through Hierarchical Structures Introduction A Toolbox of Self-Stabilizing Spanning Tree Algorithms System Assumptions Lower Bounds Two Basic Algorithms Summary Adding Structure for Constructing Efficient Self-Stabilizing Spanning-Tree Algorithms System Assumptions and Base Algorithm Interface Introducing Structure Deriving a Global Spanning Tree Examples Correctness of the Transformed Algorithm Analysis Discussion Conclusions References A Stabilizing Solution to the Stable Path Problem Introduction Notation Ordered Paths Stable Path Problem Monotonic Path Orderings Enforcing Monotonic Path Orderings Monotonic Paths Protocol Stabilization Correctness Proof Concluding Remarks References Route Preserving Stabilization Introduction Model The Route Preserving Self-Stabilizing Shortest Path Algorithm Problem to Be Solved Description Proof of Correctness Route Preserving Proof Self-Stabilization Proof The Generic Algorithm Conclusion References An Improved Snap-Stabilizing PIF Algorithm Introduction Preliminaries Algorithm Normal Behavior Error Correction Proof of Correctness Some Definitions Abnormal Processors Proof of Snap-Stabilisation Complexity Analysis Conclusion References Author Index