2008 | OriginalPaper | Buchkapitel
On the Robustness of (Semi) Fast Quorum-Based Implementations of Atomic Shared Memory
verfasst von : Chryssis Georgiou, Nicolas C. Nicolaou, Alexander A. Shvartsman
Erschienen in: Distributed Computing
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 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.