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:
In other words any system must pick two and give up on the third.
For more information see the CAP theorem Wikipedia article.
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.
3 Phase Commit (3PC) gives up on partition tolerence. If the network partitions 3PC can give inconsistent states!
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.