Eventual Consistency

Eventual consistency is a liveness property. Eventually consistent trade-offs are chosen to offer higher availability and/or performance (in CAP terminology AP biased trade-offs not CP) by sacrificing consistency guarantees. Strong consistency (linearizability, serializability, sequential, etc) can require coordination which reduces availability because it is not tolerant to failures and can reject operations for periods of time. To achieve high availability some systems allow writes and reads to happen on any side of a partition. The challenge is what to do with conflicting changes when the system heals.

Casual history

Convergence requires metadata. One example is storing casual history with a vector clock or a dotted version vector logical clock. This comes at a cost. Some systems choose to provide weaker correctness and avoid recording and merging casual history by reducing metadata and providing LWW (last write wins) guarantees using timestamps.

There has been a lot of research and innovations around causality and how to make storing the casual history more efficient and how to prune history that is unneccessary after convergence using distributed garbage collection.

References

Amazon Dynamo
Convergent replicated data types
Logical clocks
Vector clocks
Dotted version vectors
Distributed garbage collection