For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Generalization of Consecutive k-out-of-n:G Systems
Min-Sheng LIN Ming-Sang CHANG Deng-Jyi CHEN
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/06/25
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Fault Tolerance
reliability, consecutive-k-out-of-n:G system, distributed computing system,
Full Text: PDF(167.2KB)>>
A generalized class of consecutive-k-out-of-n:G systems, referred to as Con/k*/n:G systems, is studied. A Con/k*/n:G system has n ordered components and is good if and only if ki good consecutive components that originate at component i are all good, where ki is a function of i. Theorem 1 gives an O(n) time equation to compute the reliability of a linear system and Theorem 2 gives an O(n2) time equation for a circular system. A distributed computing system with a linear (ring) topology is an example of such system. This application is very important, since for other classes of topologies, such as general graphs, planar graphs, series-parallel graphs, tree graphs, and star graphs, this problem has been proven to be NP-hard.