2009 | OriginalPaper | Buchkapitel
Abortable Fork-Linearizable Storage
verfasst von : Matthias Majuntke, Dan Dobre, Marco Serafini, Neeraj Suri
Erschienen in: Principles of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.