  Limitations of CAP theorem imply that if availability is desired in the
presence of network partitions, one must sacrifice sequential consistency, a
consistency model that is more natural for system design. We focus on the
problem of what a designer should do if she has an algorithm that works
correctly with sequential consistency but is faced with an underlying key-value
store that provides a weaker (e.g., eventual or causal) consistency. We propose
a detect-rollback based approach: The designer identifies a correctness
predicate, say P , and continue to run the protocol, as our system monitors P .
If P is violated (because the underlying key-value store provides a weaker
consistency), the system rolls back and resumes the computation at a state
where P holds.
  We evaluate this approach in the Voldemort key-value store. Our experiments
with deployment of Voldemort on Amazon AWS shows that using eventual
consistency with monitoring can provide 20 - 40% increase in throughput when
compared with sequential consistency. We also show that the overhead of the
monitor itself is small (typically less than 8%) and the latency of detecting
violations is very low. For example, more than 99.9% violations are detected in
less than 1 second.
