A related problem is anti-entropy, synchronizing replica sets across nodes, for which Merkle Trees are useful: http://en.wikipedia.org/wiki/Merkle_signature_scheme

Why not use the bitcoin protocol, longest block chain wins, missing transactions are just replayed. Use difficulty settings to tweak the transaction latency. It even solves the split brain issue, which ever brain has the longest block chain wins when the network is unified.

That provides the same functionality of just using vector clocks, at ludicrously higher cost and complexity (and only addresses half the problem that Alex is discussing).

A big problem is that arbitrary DB writes after split brain (aka network partition) situations are much harder to 'unify' than bitcoin transactions. Check out the Dynamo paper (or Riak docs like: http://blog.basho.com/2010/01/29/why-vector-clocks-are-easy/) for details.

In some cases (e.g., shopping carts) conflict resolution is as easy as it is in bitcoin - but in most common applications it's far more difficult, if not impossible.

That's sorta how CouchDB does it's default conflict resolution. In a conflict, by default CouchDB picks the revision with the longest edit chain.

Couch doesn't throw out the other conflicts, it hangs on to them so applications can make their own decisions about resolution.

In a word, the cap.

A good review, thanks!