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₁ ≤ P₂ ≤ ⋯ ≤ P_n. Suppose further that any permutation of the n items constitutes a system. It has been conjectured that the cyclic system

minimizes the probability of failure over all such arrangements and that the line system L_n* = I₁I_nI₃I_n−2 … I_n−3I₄I_n−1I₂ 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.