Toward a theory for self-stabilizing protocols
Nicholas Joseph Multari, Mohamed G. Gouda · 1989
Failure recovery is a major consideration in the design of any communication protocol. To date, the primary methodologies used to recover have been exception handling and redundancy. Also, correct operation of the protocol is dependent upon starting from a safe, initial Self-stabilization is a property that can guarantee failure recovery regardless of the initial state. A communication protocol is called self-stabilizing if and only if starting from any state, possibly unsafe, the protocol is guaranteed to converge to a safe state in finite time, i.e. within a finite number number of state transitions. Self-stabilization provides protocols with an unprecedented degree of tolerance to transient failures; it also simplifies their initialization procedures. In this dissertation, we outline the main characteristics of self-stabilizing protocols as well as characteristics that prevent a protocol from becoming self-stabilizing. A modular methodology to prove the self-stabilization property of a protocol is presented. Several commonly used protocols are shown not to be able to recover from certain failures. Specifically, unrecoverable errors can occur in a connection management protocol, a window protocol, and a worm or network reconfiguration protocol. A self-stabilization version of each is presented and proven correct. The changes made to the original protocols to incorporate the self-stabilization property were minor in nature and did not increase the complexity of the protocol. In fact, in the case of the connection management protocol, the self-stabilized version is less complex than the protocols currently used.