Recoverable Consensus in Shared Memory
share
Herlihy's consensus hierarchy is one of the most widely cited results in distributed computing theory. It ranks the power of various synchronization primitives for solving consensus in a model where asynchronous processes communicate through shared memory and fail by halting. This paper revisits the consensus hierarchy in a model with crash-recovery failures, where the specification of consensus, called recoverable consensus in this paper, is weakened by allowing non-terminating executions when a process fails infinitely often. Two variations of this model are considered: independent failures, and simultaneous (i.e., system-wide) failures. Universal primitives such as Compare-And-Swap solve consensus easily in both models, and so the contributions of the paper focus on lower levels of the hierarchy. We make three contributions in that regard: (i) We prove that any primitive at level two of Herlihy's hierarchy remains at level two if simultaneous crash-recovery failures are introduced. This is accomplished by transforming (one instance of) any 2-process conventional consensus algorithm to a 2-process recoverable consensus algorithm. (ii) For any n > 1 and f > 0, we show how to use f+1 instances of any conventional n-process consensus algorithm and Θ(f + n) read/write registers to solve n-process recoverable consensus when crash-recovery failures are independent, assuming that every execution contains at most f such failures. (iii) Lastly, we prove for any f > 0 that any 2-process recoverable consensus algorithm that uses TAS and read/writer registers requires at least f+1 TAS objects, assuming that crash-recovery failures are independent and every execution contains at most f such failures per process (or at most 2f failures total).
READ FULL TEXT