| A self-stabilizing distributed system guarantees spontaneous recovery from an arbitrary bad configuration that may be reached by a failure or a perturbation in the system. Due to the inherent non-determinism in distributed systems, the time required to stabilize may not have any connection with the severity of the failure. This is undesirable, and counter-intuitive.; In this thesis, we introduce controlled recovery as a solution for the problem in self-stabilizing systems. In controlled recovery, certain constraints are satisfied during the stabilization, among which we are particularly interested in time and space constraints, such as, requiring the recovery time to be faster when the number of faulty processes is fewer. In this thesis, we explore a few techniques of controlled recovery to address the non-proportional stabilization time problem in stabilizing systems.; The concept of single-fault-containment is further explored. A priority scheduler that provides a higher level prioritized semantics is proposed and implemented. Priority scheduler can be used to design fault-containing self-stabilizing systems as well as reason about their correctness proofs at a higher level that converts a generic non-reactive self-stabilizing algorithm into a single-fault-containing self-stabilizing one.; Subsequently, we extend the concept of single-fault-containment to K-fault-containment. A K-faulty state is one that a state that can be obtained from a legitimate state by corrupting K or fewer processes. A K-fault-containing self-stabilizing system is able to recover in O(K) time from a K-faulty state. We demonstrate the construction of such a K-fault-containing self-stabilizing system. K-fault-containment reaches a tradeoff between single-fault-containment and the more aggressive time-adaptive stabilization.; Finally, we address the general case of fault-scalable systems, where the stabilization time is a monotonically increasing function of the number of faulty processes in the system. We demonstrate a space-efficient protocol for self-stabilization that exhibits certain level of fault-scalability on a linear topology. |
