A lower bound on the reliability of an n-dimensional hypercube

Author

Bulka, Dov ; Dugan, Joanne Bechta

Author_Institution

Dept. of Comput. Sci., Duke Univ., Durham, NC, USA

fYear

1990

fDate

9-12 Oct 1990

Firstpage

44

Lastpage

53

Abstract

A recursive algorithm for computing a lower bound on the all-terminal reliability of an n-dimensional hypercube is presented. The recursive step decomposes an n-dimensional hypercube into lower dimension hypercubes that are linked together. As an illustration of the effectiveness and power of this method, a lower bound is computed on the all-terminal reliability of the 16-dimensional hypercube (Connection Machine architecture) whose links number 2¹⁹. The notation and assumptions are defined, and background information on bounding the reliability polynomial is provided. Methods for tightening these bounds for the analysis of the hypercube architecture are discussed

Keywords

fault tolerant computing; hypercube networks; parallel architectures; 16-dimensional hypercube; Connection Machine architecture; all-terminal reliability; lower bound; n-dimensional hypercube; recursive algorithm; reliability polynomial; Computer architecture; Computer networks; Computer science; Failure analysis; Hypercubes; Information analysis; Multiprocessing systems; Multiprocessor interconnection networks; Power system reliability; Telecommunication network reliability;

fLanguage

English

Publisher

ieee

Conference_Titel

Reliable Distributed Systems, 1990. Proceedings., Ninth Symposium on

Conference_Location

Huntsville, AL

Print_ISBN

0-8186-2081-1

Type

conf

DOI

10.1109/RELDIS.1990.93950

Filename

93950