NONADAPTIVE FAULT-TOLERANT FILE TRANSMISSION IN ROTATOR GRAPHS

Authors
HAMADA Y BAO F MEI AH IGARASHI Y
Citation
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
Journal title
IEICE transactions on fundamentals of electronics, communications and computer science → ACNP
ISSN journal
09168508
Volume
E79A
Issue
4
Year of publication
1996
Pages
477 - 482
Database
ISI
SICI code
0916-8508(1996)E79A:4<477:NFFTIR>2.0.ZU;2-H
Abstract
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.