Home > Research > Publications & Outputs > Abortable fork-linearizable storage

Research

Associated organisational units

Links

Text available via DOI:

Keywords

View graph of relations

Abortable fork-linearizable storage

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter

Published

Standard

Abortable fork-linearizable storage. / Majuntke, M.; Dobre, D.; Serafini, M. et al.
Principles of Distributed Systems: 13th International Conference, OPODIS 2009, Nîmes, France, December 15-18, 2009. Proceedings. Vol. 5923 LNCS Springer, 2009. p. 255-269.

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter

Harvard

Majuntke, M, Dobre, D, Serafini, M & Suri, N 2009, Abortable fork-linearizable storage. in Principles of Distributed Systems: 13th International Conference, OPODIS 2009, Nîmes, France, December 15-18, 2009. Proceedings. vol. 5923 LNCS, Springer, pp. 255-269. https://doi.org/10.1007/978-3-642-10877-8_21

APA

Majuntke, M., Dobre, D., Serafini, M., & Suri, N. (2009). Abortable fork-linearizable storage. In Principles of Distributed Systems: 13th International Conference, OPODIS 2009, Nîmes, France, December 15-18, 2009. Proceedings (Vol. 5923 LNCS, pp. 255-269). Springer. https://doi.org/10.1007/978-3-642-10877-8_21

Vancouver

Majuntke M, Dobre D, Serafini M, Suri N. Abortable fork-linearizable storage. In Principles of Distributed Systems: 13th International Conference, OPODIS 2009, Nîmes, France, December 15-18, 2009. Proceedings. Vol. 5923 LNCS. Springer. 2009. p. 255-269 doi: 10.1007/978-3-642-10877-8_21

Author

Majuntke, M. ; Dobre, D. ; Serafini, M. et al. / Abortable fork-linearizable storage. Principles of Distributed Systems: 13th International Conference, OPODIS 2009, Nîmes, France, December 15-18, 2009. Proceedings. Vol. 5923 LNCS Springer, 2009. pp. 255-269

Bibtex

@inbook{7e4ea46a08fa463e83201fcf1326b1ff,
title = "Abortable fork-linearizable storage",
abstract = "We address the problem of emulating a shared read/write memory in a message passing system using a storage server prone to Byzantine failures. Although cryptography can be used to ensure confidentiality and integrity of the data, nothing can prevent a malicious server from returning obsolete data. Fork-linearizability [1] guarantees that if a malicious server hides an update of some client from another client, then these two clients will never see each others' updates again. Fork-linearizability is arguably the strongest consistency property attainable in the presence of a malicious server. Recent work [2] has shown that there is no fork-linearizable shared memory emulation that supports wait-free operations. On the positive side, it has been shown that lock-based emulations exist [1,2]. Lock-based protocols are fragile because they are blocking if clients may crash. In this paper we present for the first time lock-free emulations of fork-linearizable shared memory. We have developed two protocols, Linear and Concur. With a correct server, both protocols guarantee linearizability and that every operation successfully completes in the absence of step contention, while interfering operations terminate by aborting. The Concur algorithm additionally ensures that concurrent operations invoked on different registers complete successfully. {\textcopyright} 2009 Springer-Verlag.",
keywords = "Abortable objects, Fork-linearizability, Lock-freedom, Online collaboration, Shared memory, Byzantine failures, Concurrent operations, Consistency property, Linearizability, Lock-free, Message passing systems, Shared memories, Storage servers, Message passing",
author = "M. Majuntke and D. Dobre and M. Serafini and Neeraj Suri",
year = "2009",
doi = "10.1007/978-3-642-10877-8_21",
language = "English",
isbn = "3642108768 ",
volume = "5923 LNCS",
pages = "255--269",
booktitle = "Principles of Distributed Systems",
publisher = "Springer",

}

RIS

TY - CHAP

T1 - Abortable fork-linearizable storage

AU - Majuntke, M.

AU - Dobre, D.

AU - Serafini, M.

AU - Suri, Neeraj

PY - 2009

Y1 - 2009

N2 - We address the problem of emulating a shared read/write memory in a message passing system using a storage server prone to Byzantine failures. Although cryptography can be used to ensure confidentiality and integrity of the data, nothing can prevent a malicious server from returning obsolete data. Fork-linearizability [1] guarantees that if a malicious server hides an update of some client from another client, then these two clients will never see each others' updates again. Fork-linearizability is arguably the strongest consistency property attainable in the presence of a malicious server. Recent work [2] has shown that there is no fork-linearizable shared memory emulation that supports wait-free operations. On the positive side, it has been shown that lock-based emulations exist [1,2]. Lock-based protocols are fragile because they are blocking if clients may crash. In this paper we present for the first time lock-free emulations of fork-linearizable shared memory. We have developed two protocols, Linear and Concur. With a correct server, both protocols guarantee linearizability and that every operation successfully completes in the absence of step contention, while interfering operations terminate by aborting. The Concur algorithm additionally ensures that concurrent operations invoked on different registers complete successfully. © 2009 Springer-Verlag.

AB - We address the problem of emulating a shared read/write memory in a message passing system using a storage server prone to Byzantine failures. Although cryptography can be used to ensure confidentiality and integrity of the data, nothing can prevent a malicious server from returning obsolete data. Fork-linearizability [1] guarantees that if a malicious server hides an update of some client from another client, then these two clients will never see each others' updates again. Fork-linearizability is arguably the strongest consistency property attainable in the presence of a malicious server. Recent work [2] has shown that there is no fork-linearizable shared memory emulation that supports wait-free operations. On the positive side, it has been shown that lock-based emulations exist [1,2]. Lock-based protocols are fragile because they are blocking if clients may crash. In this paper we present for the first time lock-free emulations of fork-linearizable shared memory. We have developed two protocols, Linear and Concur. With a correct server, both protocols guarantee linearizability and that every operation successfully completes in the absence of step contention, while interfering operations terminate by aborting. The Concur algorithm additionally ensures that concurrent operations invoked on different registers complete successfully. © 2009 Springer-Verlag.

KW - Abortable objects

KW - Fork-linearizability

KW - Lock-freedom

KW - Online collaboration

KW - Shared memory

KW - Byzantine failures

KW - Concurrent operations

KW - Consistency property

KW - Linearizability

KW - Lock-free

KW - Message passing systems

KW - Shared memories

KW - Storage servers

KW - Message passing

U2 - 10.1007/978-3-642-10877-8_21

DO - 10.1007/978-3-642-10877-8_21

M3 - Chapter

SN - 3642108768

SN - 9783642108761

VL - 5923 LNCS

SP - 255

EP - 269

BT - Principles of Distributed Systems

PB - Springer

ER -