Perfect Failure Detection in the Partitioned Synchronous Distributed System Model

Abstract—In this paper we show that it is possible to implement a perfect failure detector P (one that detects all faulty processes if and only if those processes failed) in a non-synchronous distributed system. To realize that, we introduce the partitioned synchronous system (Spa) that is weaker than the conventional synchronous system. From some properties we introduce (such as strong partitioned synchrony) that must be valid in Spa and a trivially implementable Timeliness oracle, we show how to imple-ment P in Spa. Moreover, we show that even if strong partitioned synchrony is not valid, we are still able to take advantage of the existing synchronous partitions for improving the robustness of applications, by introducing a partially perfect failure detector named xP. We also discuss how applications can benefit from these failure detectors and present some related experimental data. The necessary properties and algorithms for implementing P and xP are presented in the paper, as well as the related correctness proofs. I