Optimal Reactive k-Stabilization:
the case of Mutual Exclusion
EXTENDED ABSTRACT
Jooeroy Beauquier Christophe Genolini Shay Kutten
Abstract
Recently, it was suggested by multiple researchers that the smaller is the number of faults to hit a
network, the faster should a network protocol recover. This goal proved hard, however, so such protocols have
been suggested only for relatively easier (and less typical) cases, such as non-reactive tasks, or the case
where a node can detect that it is faulty. We present solutions for the reactive problem that is often used
as a benchmark for such protocols: the problem of token passing. We treat the realistic case, where no bound
is known on the time a node can hold the token (a node holds the token as long as the node has not completed
some external task). We study the scenario where up to k (for a given k) faults hit nodes in a reactive
asynchronous distributed system by corrupting their state undetectably. The exact number of faults, the
specific faulty nodes, and the time the faults hit are not known.
We present several algorithms that stabilize into a legitimate cono/guration (in which exactly one
node has a token) in time that depends only on k, and not on n (the number of nodes). We present our
solutions in stages, by o/rst presenting a basic protocol that stabilizes in O(power(k,2)) time and uses
only a
constant number of (logarithmic size) variables per node. For this first protocol it is required that k is
smaller than sqrt(n) - 2, that is, the first protocol k-stabilizes, but does not self-stabilize. In terms of
the number of individual nodes' steps the stabilization takes O(kn) steps, and it is shown that any
1-stabilizing algorithm (that is, when k = 1) must use at least n - 3 steps.
The other algorithms are built on the basic one: one stabilizes in O(power(k,2)) time and is
self-stabilizing (so k can be larger than sqrt(n) - 2), another enhanced version stabilizes in O(k) time
(and is time optimal) but the space it uses is larger by a multi plicative factor of k.