On failure detectors and type boosters: (Extended abstract)

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_m^r(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 Ω_n (introduced in [18]) which outputs, at each process, a set of at most n processes so that, eventually, all correct processes detect the same set that includes at least one correct process. We prove that Ω_n is the weakest failure detector type booster for deterministic one-shot types. As an interesting corollary of our result, we show that Ω_t is the weakest failure detector to boost the resilience level of (t - 1)-resilient objects solving consensus.