On the Impossibility of Boosting Distributed Service Resilience

We show that no deterministic algorithm can solve consensus in the presence of t+1 process crash failures, in a system of n processes that communicate in a reliable way and synchronize their activities using any number of t-resilient services. These base services can range from any type of atomic objects shared by the processes (including consensus objects), to any class of non-atomic objects like failure detectors (including perfect ones), and broadcast primitives (including totally ordered one). The services are t-resilient in the sense that their liveness is guaranteed only if no more than t processes crash. Our boosting impossibility result applies also to the case where atomic object services can fail only because of failures of the processes connected to them. Interestingly, in this case, it is possible to boost the resilience level of the system solving problems easier than consensus. For example, we show that the k-set consensus problem is solvable for 2k-1 failures using consensus services that tolerate only 1 failure apiece.