Y. Hamada et al., NONADAPTIVE FAULT-TOLERANT FILE TRANSMISSION IN ROTATOR GRAPHS, IEICE transactions on fundamentals of electronics, communications and computer science, E79A(4), 1996, pp. 477-482
Citations number
6
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
A directed graph G = (V, E) is called the n-rotator graph if V = {a(1)
a(2) ... a(n)\a(1)a(2) ... a(n) is a permutation of 1, 2,..., n} and E
= {(a(1)a(2) ... a(n), b(1)b(2) ... b(n)) \ for some 2 less than or e
qual to i less than or equal to n, b(1)b(2) b(n) = a(2) ... a(i)a(1)a(
i+1)... a(n)}. We show that for any pair of distinct nodes in the n-ro
tator 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 prob
abilistic analysis of its reliability is given.