A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and Failure Detectors
<|reference_start|>A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and Failure Detectors: It is shown that, in a precise sense, if there is no bound on the number of faulty processes 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.<|reference_end|>
@article{halpern2004a,
    title={A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and
  Failure Detectors},
    author={Joseph Y. Halpern and Aleta Ricciardi},
    journal={arXiv preprint arXiv:cs/0402012},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0402012},
    primaryClass={cs.DC}
}