Infoscience

Report

# On Failure Detectors and Type Boosters

The power of a set S of object types can be measured as the maximum number n of processes that can solve consensus using only types in S and registers. This number, denoted by h^r_m (S), is called the consensus power of S. The use of failure detectors can however boost'' the consensus power of types. This paper addresses the weakest failure detector type booster question, which consists in determining the weakest failure detector D such that, for any set S of types with h_m^r(S)=n, h_m^r(S;D)=n+1. We consider the failure detector \Omega_n (introduced in (Neiger,1995)) which outputs, at each process, a set of at most n processes so that, eventually, all correct processes detect the same set of processes that includes at least one correct process. We prove that \Omega_n is the weakest failure detector type booster for deterministic one-shot types. As an interesting corollary of our result, we show that \Omega_f is the weakest failure detector to boost the power of (f-1)-resilient objects solving consensus.