Replicated data types
Authors:
Open Access
- 8 January 2014
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 49 (1) , 271-284
Abstract
Geographically distributed systems often rely on replicated eventually consistent data stores to achieve availability and performance. To resolve conflicting updates at different replicas, researchers and practitioners have proposed specialized consistency protocols, called replicated data types, that implement objects such as registers, counters, sets or lists. Reasoning about replicated data types has however not been on par with comparable work on abstract data types and concurrent data types, lacking specifications, correctness proofs, and optimality results. To fill in this gap, we propose a framework for specifying replicated data types using relations over events and verifying their implementations using replication-aware simulations. We apply it to 7 existing implementations of 4 data types with nontrivial conflict-resolution strategies and optimizations (last-writer-wins register, counter, multi-value register and observed-remove set). We also present a novel technique for obtaining lower bounds on the worst-case space overhead of data type implementations and use it to prove optimality of 4 implementations. Finally, we show how to specify consistency of replicated stores with multiple objects axiomatically, in analogy to prior work on weak memory models. Overall, our work provides foundational reasoning tools to support research on replicated eventually consistent stores.Keywords
This publication has 26 references indexed in Scilit:
- Eventually Consistent Transactions2012
- Cloud Types for Eventual ConsistencyLecture Notes in Computer Science, 2012
- Brief Announcement: Semantics of Eventually Consistent Replicated SetsLecture Notes in Computer Science, 2012
- Transactional storage for geo-replicated systems2011
- Replicated abstract data types: Building blocks for collaborative applicationsJournal of Parallel and Distributed Computing, 2011
- Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web servicesACM SIGACT News, 2002
- Eventually-serializable data services1996
- Shared memory consistency models: a tutorialComputer, 1996
- Concerning the size of logical clocks in distributed systemsInformation Processing Letters, 1991
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978