Stabilizing time-adaptive protocols

We study the scenario where a transient batch of faults hits a minority of the nodes in a distributed system by corrupting their slate. We concentrate on the basic persistent bit problem, where the system is required to maint ain a Oil value in the face of transient failures by means of replication. We give an algorithm to stabilize the value to a correct state quickly; tha t is, denoting the unknown number of faulty nodes by f, our algorithm recov ers the value of the bit at all nodes in Off) time units for any f < n/2, w here n is the number of all nodes. Moreover, complete state quiescence occu rs in O(diam) time units, where diam denotes the actual diameter of the net work. This means that the value persists indefinitely so long as any f < n/ 2 faults are followed by Omega(diam) fault-free time units. (Strict self-st abilization requires recovery for f greater than or equal to n/2 as well.) We prove matching lower bounds on both the output stabilization time and th e state quiescence time. Using our persistent bit algorithm, we present a t ransformer which takes a distributed non-reactive non-stabilizing protocol p, and produces a protocol p' which solves the problem p solves, with the a dditional property that if a batch of faults changes the state of f < n2 of the nodes, then the output is recovered in O(f) time units, and the state stabilizes in O(diam) time units. Our upper and lower bounds are all proved in the synchronous network model. (C) 1999 Elsevier Science B.V. All right s reserved.