Self-stabilizing Universal Algorithms
Paolo Boldi, Sebastiano Vigna · McGill-Queen's University Press eBooks · 1997
We prove the existence of a “universal” self-stabilizing algorithm, i.e., an algorithm which allows to stabilize a distributed system to a desired behaviour (as long as an algorithm stabilizing to that behaviour exists). Previous proposals required drastic increases in asymmetry and knowledge in order to work, while our algorithm does not use any additional knowledge, and does not require more symmetry-breaking conditions than available; thus, it is also stabilizing with respect to changes in the topology and in the identifiers assigned to each processor. We prove a tight quiescence time n + Δ for a synchronous network of n processors and diameter Δ. The algorithm can be made finite state with a negligible multiplicative loss. If the activation is asynchronous, we propose an algorithm with O (Δ n 2 ) quiescence time. Our results are true for a wide variety of sharedmemory models, including unidirectional, wireless and uniform networks.