A self-stabilizing shortest path algorithm in a DAG

Author

Bourgon, Brian ; Das, Sajal K. ; Datta, Arun Kumar ; Natarajan, Viruthagiri

Author_Institution

Dept. of Comput. Sci., Nevada Univ., Las Vegas, NV, USA

fYear

1995

fDate

28-31 Mar 1995

Firstpage

341

Lastpage

345

Abstract

This paper describes two protocols applicable to directed acrylic graph topologies. The first is a topological sorting of the successor list at each node, and the second is a shortest routing path protocol. Both of these protocols are resilient to transient failures in that they guarantee system recovery in a finite number of moves. This resiliency is obtained by using the notion of self-stabilization. This is a method by which convergence to the desired behavior is guaranteed. These algorithms have direct application in network routing

Keywords

computer network reliability; directed graphs; fault tolerant computing; parallel algorithms; protocols; reliability; system recovery; directed acrylic graph topologies; network routing; resiliency; self-stabilization; self-stabilizing shortest path algorithm; shortest routing path protocol; system recovery; topological sorting; transient failures; Computer crashes; Computer science; Distributed algorithms; Fault tolerant systems; Message passing; Network topology; Robustness; Routing protocols; Sorting; System recovery;

fLanguage

English

Publisher

ieee

Conference_Titel

Computers and Communications, 1995., Conference Proceedings of the 1995 IEEE Fourteenth Annual International Phoenix Conference on

Conference_Location

Scottsdale, AZ

Print_ISBN

0-7803-2492-7

Type

conf

DOI

10.1109/PCCC.1995.472471

Filename

472471