Optimal reactive k-stabilization: The case of mutual exclusion

作     者：Beauquier, Joffroy Genolini, Christophe Kutten, Shay 

出 版 物：《Proceedings of the Annual ACM Symposium on Principles of Distributed Computing》 (Proc Annu ACM Symp Princ Distrib Comput)

年 卷 期：1999年

页      面：209-218页

核心收录：

主　　题：Distributed computer systems 

摘      要：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 configuration (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 first presenting a basic protocol that stabilizes in O(k2) 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 √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(k2) time and is self-stabilizing (so k can be larger than √n-2), another enhanced version stabilizes in O(k) time (and is time optimal) but the space it uses is larger by a multiplicative factor of k.