Observations on Time-Adaptive Self-Stabilization.

T Herman, University of Iowa Department of Computer Science Technical Report TR 97-07:

Postscript Document and DVI file .


Abstract

Kutten and Patt-Shamir have proposed a method for fast recovery of the output of a non-reactive, distributed protocol: if f<n/2 processors are corrupted from a legitimate global state, then the method recovers the output in O(f) time. The proposed method leaves open the cases f=n/2 or f>n/2. This note presents a technique to resolve these open cases, again recovering the output in O(f) time. The result is therefore self-stabilizing and time-adaptive.