Generalized irreducibility of consensus and the equivalence of t-resilient and wait-free implementations of consensus

Abstract

We study the consensus problem, which requires multiple processes with different input values to agree on one of these values, in the context of asynchronous shared memory systems. Prior research focussed either on t-resilient solutions of this problem (which must be correct even if up to t processes crash) or on wait-free solutions (which must be correct despite the crash of any number of processes). In this paper, we show that these two forms of solvability are closely related. Specifically, for all n > t ≥ 2 and all sets S of shared object types (that include simple read/write registers), there is a t-resilient solution to n-process consensus using objects of types in S if and only if there is a wait-free solution to (t + 1)-process consensus using objects of types in S. Our proof of this equivalence uses another result derived in this paper, which is of independent interest. Roughly speaking, this result states that a wait-free solution to (n -1)-process consensus is never necessary in designing a wait-free solution to n-process consensus, regardless of the types of objects available. More precisely, for all n ≥ 2 and all sets S of shared object types (that include simple read/write registers), if there is a wait-free solution to n-process consensus that uses a wait-free solution to (n - 1)-process consensus and objects of types in S, then there is a wait-free solution to n-process consensus that uses only objects of types in S. © 2004 Society for Industrial and Applied Mathematics.