Memory adaptive and fast self-stabilizing protocols

Efthymios Anagnostou, Ran El-Yaniv and Vassos Hadzilacos

We present a token diffusion scheme that forms the basis of efficient self-stabilising protocols for a variety of problems including unique naming, network topology, and token management. For the model where processors' initial knowledge about the network is restricted to their neighbours, we introduce the concept of memory-adaptive protocols. In these, once the system stabilises, the size of the memory used by each processor is a function of the actual network size --- even though the system may have been started in a state where each processor ``thinks'' that it is embedded in a network much larger (or smaller) than the actual one. For this model, we develop memory-adaptive self-stabilising protocols for the problems mentioned above that stabilise in time almost linear in the number of processors. For the model where processors also know an upper bound $D$ on the diameter of the network, we develop bounded-memory self-stabilising protocols for the same problems that stabilise in $O(D)$ time. All our protocols are based on the token diffusion scheme, and are uniform, in the sense that processors with the same number of neighbours execute the same program.