In the context of op-based CRDTs, it has been shown that a sufficient condition to ensure convergence (Strong Eventual Consistency) is that all operations commute. (assuming an underlying reliable causal broadcast channel)
However I don't understand why associativity is dropped here as it look likes an important property to have when multiple concurrent operations happen, even if they all commute pairwise.
Let's take an example:
Imagine an op-based register with 3 operations Op1,Op2 and Op3.
op1 is for example the operation set_the_register_to_5 op2 is the operation set_the_register_to_10 op3 is the operation set_the_register_to_20
This would be a pretty dummy register as only limited to 3 values but looks like it would be a valid op-based CRDT if we define the arbitration for concurrent events as such:
| Op1 | Op2 | Op3 | |
|---|---|---|---|
| Op1 | LWW | op1 wins | op3 wins |
| Op2 | op1 wins | LWW | op2 wins |
| Op3 | op3 wins | op2 wins | LWW |
Here LWW stands for the classic Last-Writer-Wins provided by something like a lamport clock along with an UUID to ensure uniqueness (ans thus total order)
So for each pair of operations, we defined a precedence so that all operations commute pairwise.
Now imagine that three sites A, B and C start from the same state and execute the operation op1, op2 and op3 respectively in a concurrent manner. Because they are executed concurrently, they can be received in arbitrary order at any Site. (i.e. the reliable causal channel will not order them)
For example each site receives operations in this order: Site A: Op1.Op3.Op2 Site B: Op2.Op1.Op3 Site C: Op3.Op2.Op1
For Site A, first applying Op1 leads to 5, the applying Op3 leads to 20 and finally applying Op2 ends up with value 10.
For all sites:
Site A would end up with state (i.e. the register value) equals 10 Site B: register is 20 Site C: register is 5
This obviously not converges because even if operations commute pairwise, the result on each site will be different if evaluated left-to-right or right-to-left. For example left-to-right on Site A: (Op1.Op3).Op2 = Op3.Op2 = Op2 right-to-left: Op1.(Op3.Op2) = Op1.Op2 = Op1
The underlying problem here is that the arbitration order is not a total order (it contains a cycle)
But still, all operations commute pairwise but eventual convergence is not reached.
So looks like to me associativity is also required but I'm definitely missing something here as it has been shown that commutativity was sufficient for op-based :)
Or maybe is it because it is a state-based approach disguised in an op-based, I don't now ?
If anyone can help, Thanks for reading me.