Show simple item record

dc.contributor.authorGeorgiou, Chryssisen
dc.contributor.authorNicolaou, Nicolas C.en
dc.contributor.authorShvartsman, A. A.en
dc.creatorGeorgiou, Chryssisen
dc.creatorNicolaou, Nicolas C.en
dc.creatorShvartsman, A. A.en
dc.description.abstractThis 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. © 2008 Springer-Verlag Berlin Heidelberg.en
dc.source22nd International Symposium on Distributed Computing, DISC 2008en
dc.subjectQuality assuranceen
dc.subjectFault toleranceen
dc.subjectMessage passingen
dc.subjectAtomic physicsen
dc.subjectShared memoriesen
dc.subjectWrite operationsen
dc.subjectQuorum systemsen
dc.subjectFast readsen
dc.subjectRead operationsen
dc.subjectRealistic conditionsen
dc.subjectAtomic registersen
dc.subjectNetwork Simulatorsen
dc.subjectTime stampsen
dc.titleOn the robustness of (semi) fast quorum-based implementations of atomic shared memoryen
dc.description.volume5218 LNCSen
dc.description.endingpage304 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Sponsors: CNRSen
dc.description.notesConference code: 74262en
dc.description.notesCited By :7</p>en
dc.source.abbreviationLect. Notes Comput. Sci.en
dc.contributor.orcidGeorgiou, Chryssis [0000-0003-4360-0260]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record