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 Neiger (Proceedings of the 14th annual ACM symposium on principles of distributed computing (PODC), pp. 100–109, 1995) 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 first 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 n+1. Then we go a step further and show that Ω_n is also the weakest to boost the power of (n+1)-ported one-shot deterministic types 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 (Chandra et al. in J ACM 43(4):685–722, 1996). As a corollary, we show that Ω_t is the weakest failure detector to boost the resilience level of a distributed shared memory system, i.e., to solve consensus among n>t processes using (t−1)-resilient objects of consensus power t. |