Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - Eventually linearizable shared objects
AU - Serafini, M.
AU - Dobre, D.
AU - Majuntke, M.
AU - Bokor, P.
AU - Suri, Neeraj
PY - 2010/7/25
Y1 - 2010/7/25
N2 - Linearizability is the strongest known consistency property of shared objects. In asynchronous message passing systems, Linearizability can be achieved with ◇S and a majority of correct processes. In this paper we introduce the notion of Eventual Linearizability, the strongest known consistency property that can be attained with ◇S and any number of crashes. We show that linearizable shared object implementations can be augmented to support weak operations, which need to be linearized only eventually. Unlike strong operations that require to be always linearized, weak operations terminate in worst case runs. However, there is a tradeoff between ensuring termination of weak and strong operations when processes have only access to ◇S. If weak operations terminate in the worst case, then we show that strong operations terminate only in the absence of concurrent weak operations. Finally, we show that an implementation based on ◇P exists that guarantees termination of all operations. Copyright 2010 ACM.
AB - Linearizability is the strongest known consistency property of shared objects. In asynchronous message passing systems, Linearizability can be achieved with ◇S and a majority of correct processes. In this paper we introduce the notion of Eventual Linearizability, the strongest known consistency property that can be attained with ◇S and any number of crashes. We show that linearizable shared object implementations can be augmented to support weak operations, which need to be linearized only eventually. Unlike strong operations that require to be always linearized, weak operations terminate in worst case runs. However, there is a tradeoff between ensuring termination of weak and strong operations when processes have only access to ◇S. If weak operations terminate in the worst case, then we show that strong operations terminate only in the absence of concurrent weak operations. Finally, we show that an implementation based on ◇P exists that guarantees termination of all operations. Copyright 2010 ACM.
KW - Availability
KW - Eventual linearizability
KW - Graceful degradation
KW - Consistency property
KW - Linearizability
KW - Message passing systems
KW - Shared objects
KW - Worst case
KW - Degradation
KW - Message passing
KW - Linearization
U2 - 10.1145/1835698.1835723
DO - 10.1145/1835698.1835723
M3 - Conference contribution/Paper
SN - 9781605588889
SP - 95
EP - 104
BT - PODC '10 Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing
PB - ACM
ER -