Fault diagnosis in loop-connected systems

The paper considers fault diagnosis in a large system comprising a collection of small subsystems or units which can test one another for the existence of a faulty condition. If subsystem α is not faulty and tests subsystem β, a correct indication of the status of β is obtained; if α is faulty, the test outcome contains meaningless information. A particular form of interconnection is examined. For a system with n units u_o,u₁,...,u_{n - 1}, for each i unit u_i tests u_{i + 1},u_{i + 2},...,u_{i + A} (modulo n arithmetic being understood), where A is a preselected integer. If t is the maximum number of faulty units, we show that when t ≤ A, all faults are immediately diagnosable if n ≥ 2t + 1; we also show that when t ≥ A, at least A faults can be diagnosed if and only if n ≥ s(t - As) + t + A + 1, where s is the integer which maximizes the quadratic function f(x) = x(t - Ax) of the integer variable x.