Optimal assignments of versions to processors in fault-tolerant computer systems

This paper addresses the problem of assigning n independently developed version of a program to n different computers to maximize system reliability. For any assignments, a component of the system is defined to be a version-computer pairing and a fault-tolerant system will consist of n such components. If system reliability is defined to be the probability of at least k working components, 1 ~ k ~ n, then the problem becomes an assignment problem for a k-out-of-n : G system. When k = 1; a linear assignment problem is obtained. For voting system, k must be at least 2 and, in this case the objective function is non-linear. This implies that linear assignment algorithms cannot be used to obtain the optimal assignment. However, we show the optimal assignment to be invariant for any integer k. Hence, solving the l-out-of-n : G system (linear AP) solves the general k-out-of-n:G system