Conflict-free Replicated Data Types (CRDT) vs Paxos or Raft

When is it a good idea to use something like CRDT instead of paxos or raft?

This is a very important question — and one that I spend a lot of time with myself!

The way I describe the distinction is:

• Whereas PAXOS/RAFT implement a Distributed State Machine
• CRDT/OT implement just Distributed State itself

So PAXOS/RAFT implement more than CRDT/OT, but in a monolithic way. CRDT and OT enable a layered architecture, where you can build a machine on top of a distributed state abstraction!

Specifically, PAXOS and RAFT provide a consistent linear sequence of state transitions through a state machine. You can specify arbitrary state transition functions using turing-complete code, including arbitrary validator functions to determine when a mutation to the state is valid or invalid. This gives you transactions, which is cool, if you like transactions. However, the cost is requiring a leader that everyone follows, and state transitions are not valid until the leader confirms them, which means that all other peers have to wait 1 round trip of latency before knowing if their mutations are included or not, and whenever the leader goes down (or the network partitions), all peers have to wait 2-ish round trips for a new leader election before anyone can edit again. (I don't believe PAXOS/RAFT allow editing when offline—someone check me on this.)

On the other hand, CRDT and OT implement just distributed state, without forcing everyone onto a single linear line of time, and without any machinery to decide which state transitions are valid. CRDT/OT does not itself provide for validation or transaction semantics. But it is a very efficient and robust way to implement the distributed state part. There is no leader. There's no latency to know if mutations are included by default. You can work offline just as well as online!

But using a CRDT means that validation gets built in a different layer. I think this is a better architecture, as you can cleanly separate validation from mutation. But generalized validation algorithms/models that work on top of CRDTs are still a topic of research. I do a lot of this research in the braid.org group, myself, and I break down validation approaches into three categories:

1. Static Consensus Rules: The best validators are ones that every peer can compute independently of all others. For instance, if all mutations are signed by a private key on the peer initiating the mutation, and the validator just needs to check that this peer has the authority to mutate, then all peers can verify that the mutation was signed by the peer with authority if they obey the same cryptographic consensus rule for signing. These validators require zero round trips over the network, which is great. If you can express all your validators this way, you can have a fully distributed system.
2. Authoritative Peers that Validate: However, if your system is a hybrid of distributed peers plus an authority, like a database, that needs to sign off on a transaction, then you will require waves of acknowledgements to propagate back from that authority after each mutation so that the network knows that the authority has approved of it. You will often need two waves of acknowledgements, or "two-phase commit", so that all peers know both that the authority has approved the mutation, and that all other peers have received the approval acknowledgement. This gives you the same network requirements and performance as PAXOS/RAFT.
3. Merging + Validators requires Mining: Now, consider the case where you have static validation rules (in point 1) on data that can also merge together (via the CRDT rules) in interesting ways. For instance, suppose you have a distributed ledger that holds a bank-account balance of $3. If two peers with authority over that account simultaneously debit $2, then all peers can validate that each $2 debit is valid independently. But when those debits merge together, they add up to a $2 + $2 = $4 debit, which takes the bank account balance negative, and is no longer valid. Thus, the debits can be valid individually, but not when merged together, and the network now needs a mechanism for all peers to agree on which of the k of N individually-valid mutations should be allowed. You'll note that this is the double-spend problem. If you want to solve it in a distributed way, where no authority is in charge, and nobody can game the system to "arbitrarily" choose k transactions that are to its advantages, the only known solution is mining and mining-like things, such as Proof-of-Work, Proof-of-Stake, and the Avalanche protocol.

More information on this can be found in my talk at Braid Meeting-17 on "Validation, Merging, and Tie-Breakers", and my presentation on "Transactions on CRDT/OT" in Meeting-79.