CAP Theorem
Multi-master replication is known to be difficult because of some negative results which have been
established in the literature, such as the CAP theorem [
]
which shows that it is impossible for a distributed database system to guarantee all three of the following:
- consistency
- availability
- partition tolerance
In other words any system must pick two and give up on the third.
2PC and Paxos
For example 2 Phase Commit (2PC) gives up on availability. If the coordinator and a cohort crash then other cohorts may block indefinitely while holding mutexes and they can't commit or abort.
Similarly under Paxos a site can be unavailable if a majority (over half of the nodes) can't communicate.
3PC
3 Phase Commit (3PC) gives up on partition tolerence. If the network partitions 3PC can give inconsistent states!
CEDA
CEDA addresses the limitations of the CAP theorem by giving up on strong consistency and allowing sites to temporarily diverge as operations are performed in different orders. This is sometimes called eventual consistency.