  We present a framework for concurrency control and availability in
multi-datacenter datastores. While we consider Google's Megastore as our
motivating example, we define general abstractions for key components, making
our solution extensible to any system that satisfies the abstraction
properties. We first develop and analyze a transaction management and
replication protocol based on a straightforward implementation of the Paxos
algorithm. Our investigation reveals that this protocol acts as a concurrency
prevention mechanism rather than a concurrency control mechanism. We then
propose an enhanced protocol called Paxos with Combination and Promotion
(Paxos-CP) that provides true transaction concurrency while requiring the same
per instance message complexity as the basic Paxos protocol. Finally, we
compare the performance of Paxos and Paxos-CP in a multi-datacenter
experimental study, and we demonstrate that Paxos-CP results in significantly
fewer aborted transactions than basic Paxos.
