Minimal system conditions to implement unreliable failure detectors

Abstract:

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 ◇S, Ω, nor S (resp. ◇P 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 OV if the Strong Property is satisfied, and ◇S (and Ω 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 P4 if the Strong Property is satisfied, and implements a new detector class S' (and Ω with an additional assumption) if only the Weak Property is satisfied. © 2006 IEEE.

Año de publicación:

2006

Keywords:

Fuente:

scopus