CODEWITHSUNDEEP
consistencyeventual-consistencyassociativitycommutativitycrdt
Malaski
Malaski

Reputation: 1

Why only commutativity is sufficient for op-based CRDTs and not also associativity?

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.

Upvotes: 0

Views: 62

Answers (1)

lefalaf
lefalaf

Reputation: 141

CRDT operations are defined in terms of how they act on a state. Strictly speaking, it does not make sense to multiply the operations themselves, except via the trivial definition "OpA.OpB is the composed function that acts on a state as: first apply OpA, then apply OpB".

In algebraic terms, CRDT operations are more like a group action than a group's binary operation.

So when you say that Site A receives the ops in order Op1.Op3.Op2, we need to know how to apply the ops to the state, one at a time, in this order. The easiest interpretation would be:

  • OpA: Sets state to 5 -> it's 5
  • OpB: Sets state to 10 -> it's 10
  • OpC: Sets state to 20 -> it's 20

which will of course differ from the other sites' results. To instead implement your desired arbitration rules, the state would need to track which ops have been applied already, so that it knows to do something different when the next op arrives. If you write out an explicit state & ops in this form, you should find that the ops no longer commute.

Upvotes: 0

Related Questions