Fast and Lean Self-Stabilizing Asynchronous Protocols

We consider asynchronous general topology dynamic networks of identical nameless nodes with worst-case transient faults. Starting from any faulty configuration, our protocols self-stabilize any computation in time polynomial in the (unknown) network diameter. This version sacrifices some diversity of tasks and efficiency for simplicity and clarity of details. Appendix gives more efficient procedures in less detail. >

Authors

• Gene Itkis
• Leonid A. Levin

Keywords

• Protocols
• Network topology
• Computer networks
• Counting circuits
• Clocks
• Distributed computing
• Polynomials
• Resists
• Nominations and elections
• Algorithms
• Transient Faults
• Specific Markers
• Legality
• Interval Length
• Head And Tail
• Constant Length
• Deadlock
• Substring
• Standard Intervals
• Cellular Automata
• Idle Time
• Spanning Tree
• Input Field
• Basic Cycle
• Tree Edges
• Leader Election
• Absence Of Nodes
• Back Edge