Many of today's Internet services rely on geo-distributed data stores, which
replicate data in different geographical locations. This improves user
experience by allowing accesses to the closest site and ensures
disaster-tolerance. However, geo-distribution also makes it more challenging to
keep the data consistent. The classical approach is to make replication
transparent to clients by providing strong consistency models, such as
linearizability [1]} or
serializability [2]}. The downside is that this approach requires
synchronization between data centers in the critical path. This significantly
increases latency [3]} and makes the system unavailable during network
partitionings [4]}. Thus, even though several commercial geo-distributed
systems follow this approach [5]}, [6]}, [7]}, [8]}, [9]},
the associated cost has prevented it from being adopted more widely.
