Technical Reports
HPL-2011-6
Click here for full text:
Analyzing Consistency Properties for Fun and Profit
Golab, Wojciech; Li, Xiaozhou; Shah, Mehul A.
HP Laboratories
HPL-2011-6
Keyword(s): data consistency, algorightms, key-value stores
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.
26 Pages
Additional Publication Information: To be published and presented at PODC 2011, San Jose, June 6-8, 2011.
External Posting Date: June 6, 2011 [Fulltext]. Approved for External Publication
Internal Posting Date: June 6, 2011 [Fulltext]