Universal adaptive self-stabilizing traversal scheme: random walk and reloading wave

DOI10.1016/J.JPDC.2012.10.006MaRDI QIDQ362562zbMATH OpenOpenAlexFDO

Authors Thibault Bernard, Alain Bui, Devan Sohier

Publication date 22 August 2013

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3561, http://www.sciencedirect.com/science/article/pii/S0743731512002560

zbMATH Keywords

random walkdistributed algorithmsfault-toleranceself-stabilizationtoken circulationuniversal traversal scheme

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Distributed systems (68M14) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: In this paper, we investigate random walk based token circulation in dynamic environments subject to failures. We describe hypotheses on the dynamic environment that allow random walks to meet the important property that the token visits any node infinitely often. The randomness of this scheme allows it to work on any topology, and require no adaptation after a topological change, which is a desirable property for applications to dynamic systems. For random walks to be a traversal scheme and to answer the concurrence problem, one needs to guarantee that exactly one token circulates in the system. In the presence of transient failures, configurations with multiple tokens or with no token can occur. The meeting property of random walks solves the cases with multiple tokens. The reloading wave mechanism we propose, together with timeouts, allows to detect and solve cases with no token. This traversal scheme is self-stabilizing, and universal, meaning that it needs no assumption on the system topology. We describe conditions on the dynamicity (with a local detection criterion) under which the algorithm is tolerant to dynamic reconfigurations. We conclude by a study on the time between two visits of the token to a node, which we use to tune the parameters of the reloading wave mechanism according to some system characteristics.

Recommendations

• Distributed computation in dynamic networks via random walks
• Self-stabilizing depth-first token circulation on networks
• Randomization adaptive self-stabilization
• Principles of Distributed Systems
• scientific article; zbMATH DE number 1304100

Cited in

(1)

• Distributed computation in dynamic networks via random walks

This page was built for publication: Universal adaptive self-stabilizing traversal scheme: random walk and reloading wave

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q362562)