Title :
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
Abstract :
A directed graph G=(V, E) is called the n-rotator graph if V={a 1a2···an|a1 a2···an is a permutation of 1, 2, ···, n} and E={(a1a 2···an, b1b2 ···bn) I for some 2⩽i⩽n, b 1b2···bn=a2 ···aia1ai+1 ···an}. 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;
Conference_Titel :
Distributed Computing Systems, 1996., Proceedings of the 16th International Conference on
Print_ISBN :
0-8186-7399-0
DOI :
10.1109/ICDCS.1996.507897
