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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Graph-theoretic fault tolerance for spacecraft bus avionics


    Contributors:


    Publication date :

    2000-01-01


    Size :

    1652348 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Graph-Theoretic Fault Tolerance for Spacecraft Bus Avionics

    LaForge, L. E. / Korver, K. F. / Institute of Electrical and Electronics Engineers | British Library Conference Proceedings | 2000



    X-38 Spacecraft Fault-Tolerant Avionics System

    C. Kouba / D. Buscher / J. Busa | NTIS | 2003


    The X-38 Spacecraft Fault-Tolerant Avionics System

    Kouba,Coy / Buscher, Deborah / Busa, Joseph | NTRS | 2003