Unanimity in an unknown and unreliable environment

Abstract

Can unanimity be achieved in an unknown and unreliable distributed system? We analyze two extreme models of networks: one in which all the routes of communication are known, and the other in which not even the topology of the network is known. We prove that independently of the model, unanimity is achievable if and only if the number of faulty processors in the system is 1. less than one half of the connectivity of the system's network, and 2. less than one third of the total number of processors. In cases where unanimity is achievable, an algorithm to obtain it is given.