2005 | OriginalPaper | Chapter
Topological Adaptability for the Distributed Token Circulation Paradigm in Faulty Environment
Authors : Thibault Bernard, Alain Bui, Olivier Flauzac
Published in: Parallel and Distributed Processing and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper, we combine random walks and self-stabilization to design a single token circulation algorithm. Random walks have proved their efficiency in dynamic networks and are perfectly adapted to frequent network topological changes. Self-stabilization is the most general technique to design an algorithm that tolerates transient failures. Taking account that the token circulates continually according to a random walk scheme, designing a self-stabilizing algorithm implies to solve two situations (1) no token in the system and (2) several tokens in the system. The former is generally solved by a time-out mechanism, upon timeout a new token is created. In this paper, we focus on this problem. Just state that one may choose a sufficiently long time-out period is not possible in our case: the system could never stabilize. Indeed, a random walk based token eventually cover the network but only the
expected
time to cover the network can be captured. Therefore, we introduce a mechanism “the reloaded wave propagation” to prevent unnecessary token creation and preserve self-stabilization properties.