TY - GEN
T1 - On the robustness of (semi) fast quorum-based implementations of atomic shared memory
AU - Georgiou, Chryssis
AU - Nicolaou, Nicolas C.
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 - 2008
Y1 - 2008
N2 - This paper studies a trade-off between fault-tolerance and latency in implementations of atomic read/write objects in message-passing systems. In particular, considering fast or semifast quorum-based implementations, that is, implementations where all or respectively most read and write operations complete in a single communication round-trip, it is shown that such implementations are not robust due to the fact that they necessarily require a quorum system with a common intersection between its quorums. To trade speed for fault-tolerance, the notion of weak-semifast implementations is introduced. Here more than a single complete slow (two round-trip) read operation is allowed for each write operation (semifast implementations allow only one such slow read). A quorum-based algorithm is given next and it is formally shown that it constitutes a weak-semifast implementation of atomic registers. The algorithm uses the notion of Quorum Views to facilitate the characterization of all possible object timestamp distributions that a read operation may witness during its first communication round-trip. Noteworthy is that the algorithm allows fast read operations even if they are concurrent with other read and write operations. Finally, experimental results were gathered by simulating the algorithm using the NS-2 network simulator. The results show that under realistic conditions, less than 13% of read operations are slow, thus the overwhelming majority of operations take a single communication round-trip.
AB - This paper studies a trade-off between fault-tolerance and latency in implementations of atomic read/write objects in message-passing systems. In particular, considering fast or semifast quorum-based implementations, that is, implementations where all or respectively most read and write operations complete in a single communication round-trip, it is shown that such implementations are not robust due to the fact that they necessarily require a quorum system with a common intersection between its quorums. To trade speed for fault-tolerance, the notion of weak-semifast implementations is introduced. Here more than a single complete slow (two round-trip) read operation is allowed for each write operation (semifast implementations allow only one such slow read). A quorum-based algorithm is given next and it is formally shown that it constitutes a weak-semifast implementation of atomic registers. The algorithm uses the notion of Quorum Views to facilitate the characterization of all possible object timestamp distributions that a read operation may witness during its first communication round-trip. Noteworthy is that the algorithm allows fast read operations even if they are concurrent with other read and write operations. Finally, experimental results were gathered by simulating the algorithm using the NS-2 network simulator. The results show that under realistic conditions, less than 13% of read operations are slow, thus the overwhelming majority of operations take a single communication round-trip.
UR - http://www.scopus.com/inward/record.url?scp=56549114156&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=56549114156&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-87779-0_20
DO - 10.1007/978-3-540-87779-0_20
M3 - Conference contribution
AN - SCOPUS:56549114156
SN - 3540877789
SN - 9783540877783
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 289
EP - 304
BT - Distributed Computing - 22nd International Symposium, DISC 2008, Proceedings
T2 - 22nd International Symposium on Distributed Computing, DISC 2008
Y2 - 22 September 2008 through 24 September 2008
ER -