A fault-tolerant token passing algorithm on tree networks

Author

Alari, Gianluigi ; Beauquier, Joffroy ; Datta, Ajoy K. ; Johnen, Colette ; Thiagarajan, Visalakshi

Author_Institution

Univ. Catholique de Louvain, Belgium

fYear

1998

fDate

16-18 Feb 1998

Firstpage

44

Lastpage

50

Abstract

We present a self stabilizing token passing algorithm for a tree network. The algorithm is based on the 4 state mutual exclusion algorithm of E.W. Dijkstra (1974) and works under the distributed daemon model of execution. Although our algorithm relies upon an underlying tree network topology, it is not less general than the protocol by S. Huang and N. Chen (1993) since a spanning tree of a network can be obtained by a number of self stabilizing algorithms (A. Arora and M. Gouda, 1993; N. Chen et al., 1991; S. Huang and N. Chen, 1992; S. Sur and P.K. Srimani, 1992). Token passing on a spanning tree thus places no restriction on the topology of the underlying distributed system

Keywords

distributed algorithms; fault tolerant computing; protocols; self-adjusting systems; tree data structures; trees (mathematics); 4 state mutual exclusion algorithm; distributed daemon model; fault tolerant token passing algorithm; self stabilizing algorithms; self stabilizing token passing algorithm; spanning tree; tree network topology; underlying distributed system; Fault tolerance; Network topology; Protocols; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Performance, Computing and Communications, 1998. IPCCC '98., IEEE International

Conference_Location

Tempe/Phoenix, AZ

ISSN

1097-2641

Print_ISBN

0-7803-4468-5

Type

conf

DOI

10.1109/PCCC.1998.659897

Filename

659897