Self-stabilization with r-operators revisitedReport as inadecuate

Self-stabilization with r-operators revisited - Download this document for free, or read online. Document in PDF available to download.

1 LRI - Laboratoire de Recherche en Informatique 2 Heudiasyc - Heuristique et Diagnostic des Systèmes Complexes Compiègne 3 GRAND-LARGE - Global parallel and distributed computing LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d-Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623

Abstract : We present a generic distributed algorithm for solving silents tasks such as shortest path calculus, depth-first-search tree construction, best reliable transmitters, in directed networks where communication may be only unidirectional. Our solution is written for the asynchronous message passing communication model, and tolerates multiple kinds of failures transient and intermittent. First, our algorithm is self-stabilizing, so that it recovers correct behavior after finite time starting from an arbitrary global state caused by a transient fault. Second, it tolerates fair message loss, finite message duplication, and arbitrary message reordering, during both the stabilizing phase and the stabilized phase. This second property is most interesting since, in the context of unidirectional networks, there exist no self-stabilizing reliable data-link protocol. The correctness proof subsumes previous proofs for solutions in the simpler reliable shared memory communication model.

Keywords : r-operators self-stabilization message passing asynchronous distributed computing

Author: Sylvie Delaët - Bertrand Ducourthial - Sébastien Tixeuil -



Related documents