dc.contributor.author | Georgiou, Chryssis | en |
dc.contributor.author | Nicolaou, Nicolas C. | en |
dc.contributor.author | Russell, A. C. | en |
dc.contributor.author | Shvartsman, A. A. | en |
dc.creator | Georgiou, Chryssis | en |
dc.creator | Nicolaou, Nicolas C. | en |
dc.creator | Russell, A. 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 | 2011 | |
dc.identifier.isbn | 978-0-7695-4489-2 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53996 | |
dc.description.abstract | This work explores implementations of multi-writer/multi-reader (MWMR) atomic registers in asynchronous, crash-prone, message-passing systems with the focus on low latency and computational feasibility. The efficiency of atomic read/write register implementations is traditionally measured in terms of the latency of read and write operations. To reduce operation latency researchers focused on the communication costs, expressed as the number of communication round-trips (or rounds), often ignoring the computation costs. In this paper we consider efficiency of a register implementation in terms of both communication and computation costs. As of this writing, algorithm SFW is the sole known MWMR algorithm that allows single round read and write operations. The algorithm uses collections of intersecting sets (quorums), and to enable single round operations, SFW relies on the evaluation of certain predicates. We formulate a new combinatorial problem that captures the computational burden of evaluating the predicates in algorithm SFW and we show that it is NP-Complete. To make the evaluation of the predicates feasible, we present a polynomial log-approximation algorithm for this problem and we show how to use it with algorithm SFW. Then we present a new algorithm, called CWFR, that allows fast operations independently of the underlying quorum system construction. The algorithm implements two-round writes and allows reads to complete in a single round. We conclude with experimental evaluations of our algorithms obtained from simulations in NS2. © 2011 IEEE. | en |
dc.source | Proceedings - 2011 IEEE International Symposium on Network Computing and Applications, NCA 2011 | en |
dc.source | 10th IEEE International Symposium on Network Computing and Applications, NCA 2011 | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-80054981913&doi=10.1109%2fNCA.2011.18&partnerID=40&md5=53e7434202f1b0cc9bbbe994c6e58672 | |
dc.subject | Computational efficiency | en |
dc.subject | Wireless sensor networks | en |
dc.subject | Computational complexity | en |
dc.subject | Message passing | en |
dc.subject | Approximation algorithms | en |
dc.subject | Polynomial approximation | en |
dc.subject | NP Complete | en |
dc.subject | Atoms | en |
dc.subject | Low latency | en |
dc.subject | Computational burden | en |
dc.subject | Communication cost | en |
dc.subject | Experimental evaluation | en |
dc.subject | Message passing systems | en |
dc.subject | Atomic register | en |
dc.subject | Read/Write registers | en |
dc.subject | Write operations | en |
dc.subject | Computation costs | en |
dc.subject | Atomic memories | en |
dc.subject | Atomic memory | en |
dc.subject | Combinatorial problem | en |
dc.subject | Computational feasibility | en |
dc.subject | Fast operation | en |
dc.subject | MWMR registers | en |
dc.subject | NP-Complete | en |
dc.subject | Quorum systems | en |
dc.title | Towards feasible implementations of low-latency multi-writer atomic registers | en |
dc.type | info:eu-repo/semantics/conferenceObject | |
dc.identifier.doi | 10.1109/NCA.2011.18 | |
dc.description.startingpage | 75 | |
dc.description.endingpage | 82 | |
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: Technical Committee on Distributed Processing | en |
dc.description.notes | IEEE Computer Society | en |
dc.description.notes | Akamai | en |
dc.description.notes | Irianc | en |
dc.description.notes | Conference code: 87009 | en |
dc.description.notes | Cited By :3</p> | en |
dc.contributor.orcid | Georgiou, Chryssis [0000-0003-4360-0260] | |
dc.gnosis.orcid | 0000-0003-4360-0260 | |