Introducing new analytic results, we minimize the cost of point-to-point fault tolerant avionics architectures. Refining the graph model of Hayes [1976], we formulate the worst-case feasibility of configuration as: What (f+l)-connected n-vertex graphs with fewest edges minimize the maximum radius or diameter of subgraphs (i.e., quorums) induced by deleting up to f of the n vertices? We solve this problem by proving: (i) K-cubes (cubes based on cliques) can tolerate a greater proportion of faults than can traditional C-cubes (cubes based on cycles); (ii) quorums formed from K-cubes have a diameter that is asymptotically equal to the Moore bound, while under no conditions of scaling can the Moore bound be attained by C-cubes whose radix exceeds 4. Thus, for fault tolerance logarithmic in n, K-cubes are optimal, whereas C-cubes are suboptimal. Our exposition also corrects and generalizes a mistaken claim by Armstrong and Gray [1981] concerning binary cubes.
Graph-theoretic fault tolerance for spacecraft bus avionics
2000 IEEE Aerospace Conference. Proceedings (Cat. No.00TH8484) ; 5 ; 283-294 vol.5
2000-01-01
1652348 byte
Conference paper
Electronic Resource
English
Graph-Theoretic Fault Tolerance for Spacecraft Bus Avionics
British Library Conference Proceedings | 2000
|IEEE | 2000
X-38 Spacecraft Fault-Tolerant Avionics System
NTIS | 2003
|The X-38 Spacecraft Fault-Tolerant Avionics System
NTRS | 2003
|NTIS | 1971