Optimal Consecutive-2-Out-of-n Systems

A consecutive-2-out-of-n cycle (line) is a system of n items ordered into a cycle (line) such that the system fails if and only if two consecutive items both fail. A double-loop ring network for computers is such a cyclic system when the computers are also connected by a second loop which skips every other computer in the cycle (if n is even, there are two half loops). Suppose that item I i works with probability P i and that the items have been indexed so that P 1 ≤ P 2 ≤ ⋯ ≤ P n . Suppose further that any permutation of the n items constitutes a system. It has been conjectured that the cyclic system [Formula: see text] minimizes the probability of failure over all such arrangements and that the line system L n * = I 1 I n I 3 I n−2 … I n−3 I 4 I n−1 I 2 minimizes the probability of failure over all arrangements of the items into a line (the line conjecture follows from the cycle conjecture by setting P n = 1). In this paper we prove the cycle conjecture.