Self-Stabilizing Algorithms in DAG Structured Networks

Sajal K. Das (1) , Ajoy Datta (2) , Sébastien Tixeuil (3)

1 CSE - Department of Computer Science and Engineering [Texas A&M University]
2 Department of Computer Science [Las Vegas]
3 LRI - Laboratoire de Recherche en Informatique

This paper describes a parameterized protocol applicable to directed acyclic graph (DAG) topologies. The function parameter of the protocol is instantiated twice to design two specific protocols: (i) the topological sorting of the successor list at every node, and (ii) a shortest path routing table construction. Both protocols are self-stabilizing and thus they are resilient to transient failures and guarantee system recovery in a finite time linear in the network diameter. From the fact that a DAG topology can be imposed on a more general topology through graph labeling protocols, the solutions presented in this paper are expected to be quite useful for a large class of distributed systems, where an optimal routing along with the robustness and fault tolerance are key factors. Read More: http://www.worldscientific.com/doi/abs/10.1142/S0129626499000529

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Informatique ubiquitaire; Réseaux et télécommunications [cs.NI]

Sajal K. Das, Ajoy Datta, Sébastien Tixeuil. Self-Stabilizing Algorithms in DAG Structured Networks. Parallel Processing Letters, 1999, 9 (4), pp.563-574. ⟨10.1142/S0129626499000529⟩. ⟨hal-00930899⟩