We have arrived in the so-called Big Data era with data volumes growing exponentially. This requires effective data management systems with extreme scalability in size as well as speed, often coined "Internet scalability." David Patterson (Communications, Oct. 2004) referred to an old network saying: "Bandwidth problems can be cured with money. Latency problems are harder because the speed of light is fixed—you can't bribe God." Therefore, reducing latency in a global application scenario requires distributing (that is, storing and/or replicating) data worldwide. Unfortunately, building efficient and reliable distributed data management systems remains an inherently difficult task.
With the emergence of (geographically) distributed data management in cloud infrastructures, the key value (KV) systems were promoted as NoSQL systems. To achieve maximum availability and performance, these KV stores sacrificed the "holy grail" of database consistency and relied on relaxed consistency models, such as eventual consistency. This was a consequence of Eric Brewer's so-called CAP observation (aka Theorem)1 stating that only two of the three desiderata of distributed systems could possibly be satisfied at the same time: Consistency, where every read operation receives the most recent committed write; availability which nowadays typically strives for the so-called many nines up-time (meaning, say, 99.99999% up-time); and, partition tolerance, which demands the system must remain operational even under severe network malfunctions.