TY - GEN
T1 - On the efficiency of atomic multi-reader, multi-writer distributed memory
AU - Englert, Burkhard
AU - Georgiou, Chryssis
AU - Musial, Peter M.
AU - Nicolaou, Nicolas
AU - Shvartsman, Alexander A.
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=73049084212&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=73049084212&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-10877-8_20
DO - 10.1007/978-3-642-10877-8_20
M3 - Conference contribution
AN - SCOPUS:73049084212
SN - 3642108768
SN - 9783642108761
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 240
EP - 254
BT - Principles of Distributed Systems - 13th International Conference, OPODIS 2009, Proceedings
T2 - 13th International Conference on Principles of Distributed Systems, OPODIS 2009
Y2 - 15 December 2009 through 18 December 2009
ER -