Time-adaptive self stabilization
Shay Kutten, Boaz Patt-Shamir · 1997
We study the scenario where a transient fault hit f of the n nodes of a distributed system by corrupting their state. We consider the basic persistent bit problem, where the system is required to maintain a 0/1 value in the face of transient failures by means of replication. We give an algorithm to recover the value quickly: the value of the bit is recovered at all nodes in O(f) time units for an unknown f ! n=2. Moreover, complete state quiescence occurs in O(diam) time units, where diam denotes the actual diameter of the network. This means that the value persists indefinitely so long as any f ! n=2 faults are followed by \\Omega\\Gamma diam) fault-free time units. We prove matching lower bounds on both the output stabilization time and the state quiescence time. Using our persistent bit algorithm, we present a general transformer which takes a distributed non-reactive non-stabilizing protocol P , and produces a self-stabilizing protocol P 0 which solves the problem P solv...