Back to Search
Start Over
Self-Stabilizing Algorithms in Dag Structured Networks.
- Source :
-
Parallel Processing Letters . Dec99, Vol. 9 Issue 4, p563. 12p. - Publication Year :
- 1999
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ACYCLIC model
*TOPOLOGY
Subjects
Details
- Language :
- English
- ISSN :
- 01296264
- Volume :
- 9
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Parallel Processing Letters
- Publication Type :
- Academic Journal
- Accession number :
- 9624401
- Full Text :
- https://doi.org/10.1142/S0129626499000529