2009 | OriginalPaper | Buchkapitel
On the Efficiency of Atomic Multi-reader, Multi-writer Distributed Memory
verfasst von : Burkhard Englert, Chryssis Georgiou, Peter M. Musial, Nicolas Nicolaou, Alexander A. Shvartsman
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
This paper considers quorum-replicated, multi-writer, multi-reader (MWMR) implementations of survivable atomic registers in a distributed message-passing system with processors prone to failures. Previous implementations in such settings invariably required two rounds of communication between readers/writers and replica owners. Hence the question arises whether it is possible to have single round read and/or write operations in this setting.
We thus devise an algorithm, called
Sfw
, that exploits a new technique called
server side ordering
(
SSO
), which –unlike previous approaches– places partial responsibility for the ordering of write operations on the replica owners (the servers). With SSO,
fast
write operations are introduced for the very first time in the MWMR setting. We prove that our algorithm preserves atomicity in all permissible executions. While algorithm SFW shows that in principle fast writes are possible, we also show that under certain conditions the MWMR model imposes inherent limitations on any quorum-based fast write implementation of a
safe read/write register
and potentially even restricts the number of writer participants in the system. In this case our algorithm achieves near optimal efficiency.