Efficient linearizable write operations using bounded global time uncertainty
2013 (English)In: Proceedings - 2013 IEEE 12th International Symposium on Parallel and Distributed Computing, ISPDC 2013, IEEE , 2013, 59-66 p.Conference paper (Refereed)
Distributed key-value stores employed in data centers treat each key-value pair as a shared memory register. For fault-tolerance and performance, each key-value pair is replicated. Various models exist for the consistency of data amongst the replicas. While atomic consistency, also known as linearizability, provides the strongest form of consistency for read and write operations, various key-value stores, such as Cassandra, and Dynamo, offer only eventual consistency instead. One main motivation for such a decision is performance degradation when guaranteeing atomic consistency. In this paper, we use time with known bounded uncertainty to improve the performance of write operations, while maintaining atomic consistency. We show how to use the concept of commit wait in a shared memory register to perform a write operation in one phase (message round trip), instead of two. We evaluate the solution experimentally by comparing it to ABD, a well-known algorithm for achieving atomic consistency in an asynchronous network, which uses two phases for write operations. We also compare our protocol to an eventually consistent register. Our experiments show an improved throughput, and lower write latency, compared to the ABD algorithm.
Place, publisher, year, edition, pages
IEEE , 2013. 59-66 p.
Atomic consistency, bounded time uncertainty, eventual consistency, linearizability
IdentifiersURN: urn:nbn:se:kth:diva-143141DOI: 10.1109/ISPDC.2013.17ScopusID: 2-s2.0-84892706679ISBN: 978-076955018-3OAI: oai:DiVA.org:kth-143141DiVA: diva2:706109
2013 IEEE 12th International Symposium on Parallel and Distributed Computing, ISPDC 2013; Bucharest; Romania; 27 June 2013 through 30 June 2013
QC 201403192014-03-192014-03-172014-03-19Bibliographically approved