More on the power of random walks: Uniform self-stabilizing randomized algorithms

Abstract

We present a self-stabilizing randomized protocol for the Unique Naming problem. In the Unique Naming problem an anonymous system assigns unique names to all the processors in the system. Let G be the underlying interconnection network. If N is a known bound on the network size then our protocol uses O(C_GNlogN) bits and stabilizes within O(C_G) rounds where C_G is the cover time of G. The protocol is uniform, tolerates dynamic changes of the network topology, and works correctly under a very powerful adversary which at any stage has knowledge of a bounded number of future random choices of the processors and it can even bias all future random choices.

We then show that a small modification to our protocol provides a solution for another important problem; the Topology problem in which each node in an anonymous network computes an exact description of the network's topology. Moreover these two protocols yield uniform and bounded space solutions to many other important problems such as Leader Election, Spanning Tree, Mutual Exclusion (Token Management), etc.