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   Vol.E83-D   No.6   pp.1309-1313
Publication Date: 2000/06/25
Online ISSN: 
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)>>
Buy this Article

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.