Fault-tolerant file transmission by information dispersal algorithm in rotator graphs

Author

Hamada, Yukihiro ; Bao, Feng ; Mei, Aohaa ; Igarashi, Yoshihide

Author_Institution

Dept. of Comput. Sci., Gunma Univ., Japan

fYear

1996

fDate

27-30 May 1996

Firstpage

19

Lastpage

25

Abstract

A directed graph G=(V, E) is called the n-rotator graph if V={a ₁a₂···a_n|a₁a₂···a_n is a permutation of 1, 2, ···, n} and E={(a₁a ₂···a_n, b₁b₂···b_n) I for some 2⩽i⩽n, b ₁b₂···b_n=a₂···a_ia₁a_i+1···a_n}. We show that for any pair of distinct nodes in the n-rotator graph, we can construct n-1 disjoint paths, each with length less than 2n, connecting the two nodes. By using these disjoint paths and information dispersal algorithm (IDA) by M.O. Rabin (1989), we design a file transmission scheme and analyse its reliability

Keywords

computer network reliability; directed graphs; fault tolerant computing; multiprocessor interconnection networks; directed graph; disjoint paths; distinct nodes; fault-tolerant file transmission; file transmission scheme; information dispersal algorithm; n-1 disjoint paths; reliability; rotator graphs; Algorithm design and analysis; Clocks; Complexity theory; Computer science; Fault tolerance; Information analysis; Joining processes; Network topology; Synchronization; Telecommunication network reliability;

fLanguage

English

Publisher

ieee

Conference_Titel

Distributed Computing Systems, 1996., Proceedings of the 16th International Conference on

Print_ISBN

0-8186-7399-0

Type

conf

DOI

10.1109/ICDCS.1996.507897

Filename

507897