Séminaire REGALRSS

In Search of Lost Time

Intervenant(s) : Josef Widder (Vienna University of Technology, Autriche)
The talk establishes a formal understanding of the paradox between two of the best-known results regarding fault-tolerant consensus. Dwork, Lynch, and Stockmeyer (1988) and Lamport (1998) 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 (1996) show that a failure detector that, from some time on, provides "good information" forever is necessary. We show that this paradox is due to the "two layered" structure of the failure detector model, and discuss consequences of this modelling on comparison relations for failure detectors. T