Abstract | ||
---|---|---|
Motivated by the increasing popularity of eventually consistent key-value stores as a commercial service, we address two important problems related to the consistency properties in a history of operations on a read/write register (i.e., the start time, finish time, argument, and response of every operation). First, we consider how to detect a consistency violation as soon as one happens. To this end, we formulate a specification for online verification algorithms, and we present such algorithms for several well-known consistency properties. Second, we consider how to quantify the severity of the violations, if a history is found to contain consistency violations. We investigate two quantities: one is the staleness of the reads, and the other is the commonality of violations. For staleness, we further consider time-based staleness and operation-count-based staleness. We present efficient algorithms that compute these quantities. We believe that addressing these problems helps both key-value store providers and users adopt data consistency as an important aspect of key-value store offerings. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1145/1993806.1993834 | PODC |
Keywords | Field | DocType |
key-value store offering,consistency violation,consistency property,consistent key-value store,time-based staleness,analyzing consistency property,important aspect,key-value store provider,operation-count-based staleness,well-known consistency property,data consistency,profitability,key value store,consistency,atomicity | Atomicity,Eventual consistency,Computer science,Popularity,Theoretical computer science,Associative array,Consistency model,Database,Data consistency,Distributed computing | Conference |
Citations | PageRank | References |
28 | 1.17 | 20 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Wojciech Golab | 1 | 210 | 17.22 |
Xiaozhou Li | 2 | 164 | 8.55 |
Mehul A. Shah | 3 | 3547 | 317.66 |