Minimal System Conditions to Implement Unreliable Failure Detectors

In this paper we explore the minimal system requirements to implement unreliable failure detectors. We first consider systems formed by lossy asynchronous and eventually timely links. On these systems we define two properties, the weak property and the strong property, depending on whether all correct processes can be reached with links that are not lossy asynchronous from one or from all correct processes, respectively. We present necessary conditions based on these properties. We show that there is no algorithm that implements diamS, Omega, nor S (resp. diamP nor P) if we allow one single failure in a system that, when all processes are correct, does not satisfy the weak (resp. strong) property. Then, we propose an algorithm that implements diamP if the strong property is satisfied, and diamS (and Omega with an additional assumption) if only the weak property is satisfied. For systems formed by synchronous and lossy asynchronous links only, we propose another algorithm that implements detector class P₄ if the strong property is satisfied, and implements a new detector class S¹ (and Omega with an additional assumption) if only the weak property is satisfied