Paper Info
Title
Recoverable Consensus in Shared Memory.
Abstract
Herlihyu0027s consensus hierarchy 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 emph{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. Several results are proved in this model: (i) We prove that any primitive at level two of Herlihyu0027s 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 u003e 1$ and $f u003e 0$, we show how to use $f+1$ instances of any conventional $n$-process consensus algorithm and $Theta(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) Next, we prove for any $f u003e 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. (iv) Lastly, we generalize and strengthen (iii) by proving that any universal construction of $n$-process recoverable consensus from a type $T$ with consensus number $n$ and read/write registers requires at least $f+1$ base objects of type $T$ in executions with up to $f$ failures.
Year
Venue
Field
2018
arXiv: Distributed, Parallel, and Cluster Computing
Asynchronous communication,Consensus algorithm,Synchronization,Shared memory,Computer science,Theoretical computer science,Hierarchy,Distributed computing
DocType
Volume
Citations 
Journal
abs/1804.10597
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Wojciech Golab121017.22