dc.contributor.author | Georgiou, Chryssis | en |
dc.contributor.author | Nicolaou, Nicolas C. | en |
dc.contributor.author | Shvartsman, A. A. | en |
dc.creator | Georgiou, Chryssis | en |
dc.creator | Nicolaou, Nicolas C. | en |
dc.creator | Shvartsman, A. A. | en |
dc.date.accessioned | 2019-11-13T10:40:11Z | |
dc.date.available | 2019-11-13T10:40:11Z | |
dc.date.issued | 2008 | |
dc.identifier.isbn | 978-1-59593-989-0 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53998 | |
dc.description.abstract | Atomic (linearizable) read/write memory is a fundamental abstractions in distributed computing. Following a seminal implementation of atomic memory of Attiya et al.[6], a folklore belief developed that in messaging-passing atomic memory implementations "reads must write." However, work by Dutta et al.[4] established that if the number of readers R is constrained with respect to the number of replicas S and the maximum number of crash-failures t so that R < S/t - 2, then single communication round-trip reads are possible. Such an implementation given in [4] is called fast. Subsequently, Georgiou et al.[3] relaxed the constraint in [4], and proposed semifast implementations with unbounded number of readers, where under realistic conditions most reads need only a single communication round-trip to complete. Their approach groups collections of readers into virtual nodes. Semifast behavior of their algorithm is preserved as long as the number of virtual nodes V is constrained by V < S/t - 2. Quorum systems are well-known mathematical tools that provide means for achieving coordination between processors in distributed systems. Given that the approach of Attiya et al.[6]is readily generalized from majorities to quorums (e.g., [5, 2]), and that the algorithms in [4] and[3] rely on intersections in specific sets of responding servers, one may ask: Can we characterize the conditions enabling fast implementations in a general quorumbased framework? This is what we establish in this work. | en |
dc.source | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing | en |
dc.source | 27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-57549086455&partnerID=40&md5=8dac1585af69092e4a04b2825557d900 | |
dc.subject | Distributed systems | en |
dc.subject | Aluminum | en |
dc.subject | Atoms | en |
dc.subject | Atomic physics | en |
dc.subject | Mathematical tools | en |
dc.subject | Shared memories | en |
dc.subject | Distributed Computing | en |
dc.subject | Atomic memories | en |
dc.subject | Communication rounds | en |
dc.subject | Quorum systems | en |
dc.subject | Fast implementations | en |
dc.subject | Virtual nodes | en |
dc.subject | Realistic conditions | en |
dc.title | Brief announcement: On the robustness of (semi)fast quorum-based implementations of atomic shared memory | en |
dc.type | info:eu-repo/semantics/conferenceObject | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Conference Object | en |
dc.description.notes | <p>Sponsors: ACM SIGACT | en |
dc.description.notes | ACM SIGOPS | en |
dc.description.notes | Conference code: 74476</p> | en |
dc.contributor.orcid | Georgiou, Chryssis [0000-0003-4360-0260] | |
dc.gnosis.orcid | 0000-0003-4360-0260 | |