On failure detectors and type boosters

Abstract. The power of an object type T can be measured as the maximum number n of processes that can solve consensus using only objects of T and registers. This number, denoted cons(T), is called the consensus power of T. This paper addresses the question of the weakest failure detector to solve consensus among a number k> n of processes that communicate using shared objects of a type T with consensus power n. In other words, we seek for a failure detector that is sufficient and necessary to “boost ” the consensus power of a type T from n to k. It was shown in [21] that a certain failure detector, denoted Ωn, is sufficient to boost the power of a type T from n to k, and it was conjectured that Ωn was also necessary. In this paper, we prove this conjecture for one-shot deterministic types. We show that, for any one-shot deterministic type T with cons(T) ≤ n, Ωn is necessary to boost the power of T from n to any k> n. Our result generalizes, in a precise sense, the result of the weakest failure detector to solve consensus in asynchronous message-passing systems [6]. As a corollary of our result, we show that Ωn is the weakest failure detector to boost the resilience of a system of (n − 1)-resilient objects of any types and wait-free registers with respect to the consensus problem.