Easily rendering token-ring algorithms of distributed and parallel applications fault tolerant

Luciana Arantes (1) , Julien Sopena (1)

1 Regal - Large-Scale Distributed Systems and Applications

We propose in this paper a new algorithm that, when called by existing token ring-based algorithms of parallel and distributed applications, easily renders the token tolerant to losses in presence of node crashes. At most k consecutive node crashes are tolerated in the ring. Our algorithm scales very well since a node monitors the liveness of at most k other nodes and neither a global election algorithm nor broadcast primitives are used to regenerate a new token. It is thus very effective in terms of latency cost. Finally, a study of the probability of having at most k consecutive node crashes in the presence of f failures and a discussion of how to extend our algorithm to other logical topologies are also presented.

Mots clés: distributed algorithm; fault tolerance; token-based; scalability

Domaines: Autre [cs.OH]

Luciana Arantes, Julien Sopena. Easily rendering token-ring algorithms of distributed and parallel applications fault tolerant. [Research Report] RR-8359, INRIA. 2013, pp.23. ⟨hal-00859863⟩