Computing Reliability Intervals for k-Resilient Protocols

K-resilient protocols are used in some parallel and distributed system applications for increased availability of resources. A protocol running on an n site system is k resilient if it could tolerate up to k failures and operate correctly. The reliability of such a protocol is defined as the probability that no more than k sites have failed. Such a ft-resilient protocol is beneficial only when its reliability is greater than the reliability of a protocol running on a system with a single site. We consider K-resilient protocols and develop a general technique for approximately computing the time until which these protocols have higher reliability than protocols running on single site systems. We call this time the reliability interval. Our general techniques for computing the reliability interval can be used irrespective of the type of failure distribution (with respect to time) of the sites of the system. We use experimental results to validate our technique.