A knowledge-theoretic analysis of uniform distributed coordination and failure detectors
Joseph Yehuda Halpern, Aleta M. Ricciardi · 1999
It is shown that if there is no bound on the number of faulty processes, then in a precise sense, in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained if and only if a system has perfect failure detectors.This result is generalized to the case where there is a bound t on the number of faulty processes.It is shown that a certain type of generalized failure detector is necessary and sufficient for achieving UDC in a context with at most t faulty processes.Reasoning about processes' knowledge as to which other processes are faulty plays a key role in the analysis.