Asynchronous and Fully Self-stabilizing Time-Adaptive Majority Consensus
Janna Burman,Ted Herman,Shay Kutten and Boaz Patt-Shamir
Abstract:
We study the scenario where a batch of transient faults hits an asynchronous distributed
system by corrupting the state of some f nodes. We concentrate on the basic majority
consensus problem, where nodes are required to agree on a common output value which is the
input value of the majority of them. We give a fully self-stabilizing adaptive algorithm,
i.e., the output value stabilizes in O(f) time at all nodes, for any unknown f. Moreover,
a state stabilization occurs in time proportional to the (unknown) diameter of the network.
Both upper bounds match known lower bounds to within a constant factor. Previous results
(stated for a slightly less general problem called “persistent bit”) assumed the synchronous
network model, and that f