In search of lost time

Dwork, Lynch, and Stockmeyer [3], and Lamport [4], showed that, in order to solve Consensus in a distributed system, it is sufficient that the system behaves well during a finite period of time. In sharp contrast, Chandra, Hadzilacos, and Toueg [6] proved that a failure detector that, from some time on, provides “good” information forever is necessary. We explain that this apparent paradox is due to the two-layered structure of the failure detector model. This structure also has impact on comparison relations between failure detectors. In particular, we make explicit why the classic relation is neither reflexive nor extends the natural history-wise inclusion. Our point is to help understanding existing models and to study how they model real distributed systems in an accurate way.