Collaborative Concurrency Control

Strong Eventual Consistency

1. Eventual delivery: every update made to one non-faulty replica is eventually processed by every non-faulty replica.

2. Convergence: any two replicas that have processed the same set of updates are in the same state.

CRDT

• Operation based

1. last write wins

2. Need arbitrary position arithemetic library.

3. Reliable broadcast ensures every operation is eventually delivered to every replica.

4. Applying operation is commutative: order of delivery doesn't matter.

• State based

Merge operator must satisfy:

Best effort broadcast

State based vs operation based:

State-based	Operation-based
	Can tolerate message loss/duplication
has smaller message payload to broadcast

OT

Initially the document has "BC"

1. User A inserts A at the beginning, the text becomes "ABC"

2. User B inserts D at the very end, the text becomes "BCD"

3. When then changes from user A get broadcast to userB, it works okay.

4. When the changes from user B: (insert, 2, "D") get broadcast to user A, it becomes "ABDC"

5. Operational transformation aim to transform the operation such that the operation will work correctly.