On the minimal synchronism needed for distributed consensus

TLDR

Reaching agreement is a fundamental primitive in distributed computing, but real systems require consensus protocols that tolerate a limited number of failures. The paper extends prior work by identifying key system parameters, such as synchrony conditions, and examining how their variation affects fault tolerance. The authors use proofs to expose heuristic principles that explain why consensus is possible in some models but not in others. They confirm that in a fully asynchronous model, even one failure cannot be tolerated, and that adjusting synchrony conditions changes the maximum number of tolerable faults. Citation: Fischer et al.

Abstract

Reaching agreement is a primitive of distributed computing. Whereas this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: A system is viable only if it permits the existence of consensus protocols tolerant to some number of failures. Fischer et al. have shown that in a completely asynchronous model, even one failure cannot be tolerated. In this paper their work is extended: Several critical system parameters, including various synchrony conditions, are identified and how varying these affects the number of faults that can be tolerated is examined. The proofs expose general heuristic principles that explain why consensus is possible in certain models but not possible in others.