Nonadaptive Fault-Tolerant File Transmission in Rotator Graphs

Yukihiro HAMADA
Feng BAO
Aohan MEI
Yoshihide IGARASHI

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A    No.4    pp.477-482
Publication Date: 1996/04/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
connectivity,  fault-tolerance,  file transmission,  information dispersal algorithm,  rotator graphs,  

Full Text: PDF>>
Buy this Article

A directed graph G = (V,E) is called the n-rotator graph if V = {a1a2・・・an|a1a2・・・an is a permutation of 1,2,・・・,n} and E = {(a1a2・・・an,b1b2・・・bn)| for some 2 i n, b1b2・・・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 length < 2n, connecting the two nodes. We propose a nonadaptive fault-tolerant file transmission algorithm which uses these disjoint paths. Then the probabilistic analysis of its reliability is given.