How to cope with faulty processors in a completely connected network of communicating processors (Q1060840)

Computer systems consisting of a completely connected network of communicating processors should work reliable in spite of a number of malfunctioning processors that give conflicting information to different members of the system. It is necessary that all wellfunctioning processors agree on the message sent by any transmitting processor, regardless of the behaviour of the malfunctioning processors. Moreover, it is required that whenever the transmitter is wellfunctioning, the agreement reached should be equal to the message actually sent by the transmitter. In this paper it is shown by a mathematical proof that this is possible if and only if the number of malfunctioning processors is less than one-third of the total number of processors in the network. In cases where this requirement is fulfilled, we give a clear algorithm to reach agreement.