Home > Research > Publications & Outputs > Eventually linearizable shared objects

Links

Text available via DOI:

View graph of relations

Eventually linearizable shared objects

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Published

Standard

Eventually linearizable shared objects. / Serafini, M.; Dobre, D.; Majuntke, M. et al.
PODC '10 Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. ACM, 2010. p. 95-104.

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Harvard

Serafini, M, Dobre, D, Majuntke, M, Bokor, P & Suri, N 2010, Eventually linearizable shared objects. in PODC '10 Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. ACM, pp. 95-104. https://doi.org/10.1145/1835698.1835723

APA

Serafini, M., Dobre, D., Majuntke, M., Bokor, P., & Suri, N. (2010). Eventually linearizable shared objects. In PODC '10 Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (pp. 95-104). ACM. https://doi.org/10.1145/1835698.1835723

Vancouver

Serafini M, Dobre D, Majuntke M, Bokor P, Suri N. Eventually linearizable shared objects. In PODC '10 Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. ACM. 2010. p. 95-104 doi: 10.1145/1835698.1835723

Author

Serafini, M. ; Dobre, D. ; Majuntke, M. et al. / Eventually linearizable shared objects. PODC '10 Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. ACM, 2010. pp. 95-104

Bibtex

@inproceedings{54cb90a494214e6ca3dcddf863b4119f,
title = "Eventually linearizable shared objects",
abstract = "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.",
keywords = "Availability, Eventual linearizability, Graceful degradation, Consistency property, Linearizability, Message passing systems, Shared objects, Worst case, Degradation, Message passing, Linearization",
author = "M. Serafini and D. Dobre and M. Majuntke and P. Bokor and Neeraj Suri",
year = "2010",
month = jul,
day = "25",
doi = "10.1145/1835698.1835723",
language = "English",
isbn = "9781605588889",
pages = "95--104",
booktitle = "PODC '10 Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing",
publisher = "ACM",

}

RIS

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 -