A realistic look at failure detectors

Abstract

This paper shows that, in an environment where we do not bound the number of faulty processes, the class P of perfect failure detectors is the weakest (among realistic failure detectors) to solve fundamental agreement problems like uniform consensus, atomic broadcast, and terminating reliable broadcast (also called Byzantine generals). Roughly speaking, in this environment, we collapse the Chandra-Toueg failure detector hierarchy, by showing that P ends up being the only class to solve those agreement problems. This contributes in explaining why most reliable distributed systems we know of do rely on some group membership service that precisely aims at emulating P. As an interesting side effect of our work, we show that, in our general environment, uniform consensus is strictly harder than consensus, and we revisit the view that uniform consensus and atomic broadcast are strictly weaker than terminating reliable broadcast.