Unanimity in an unknown and unreliable environment
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is proved that independently of the model, unanimity is achievable if and only if the number of faulty processors in the system is less than less than one half of the connectivity of the system's network.
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.