> For the complete documentation index, see [llms.txt](https://dongzeli95s-organization.gitbook.io/swe-interview-handbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dongzeli95s-organization.gitbook.io/swe-interview-handbook/system-design/deep-dive/collaborative-concurrency-control.md).

# 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.

<figure><img src="https://3949881291-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FcZwx4sqIBsQr7kP4dTuJ%2Fuploads%2FpAuDlomIKO3GXNDWARRi%2FScreenshot%202024-02-22%20at%208.48.33%20AM.png?alt=media&amp;token=7eeadbce-15c5-478d-a651-0e77ad0e2bba" alt=""><figcaption></figcaption></figure>

## CRDT

* Operation based

<figure><img src="https://3949881291-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FcZwx4sqIBsQr7kP4dTuJ%2Fuploads%2FPvK36CWfp8HRhvVjHoKH%2FScreenshot%202024-02-22%20at%208.54.18%20AM.png?alt=media&amp;token=6ff38e9b-97e8-4a9d-b2f3-ae5f5638b5f8" alt=""><figcaption></figcaption></figure>

<figure><img src="https://3949881291-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FcZwx4sqIBsQr7kP4dTuJ%2Fuploads%2Fo4v4wevFBxQQX0qBS3Hw%2FScreenshot%202024-02-22%20at%2011.22.12%20AM.png?alt=media&amp;token=83ea66a3-b920-4afd-b469-e6d699d968e8" alt=""><figcaption></figcaption></figure>

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

<figure><img src="https://3949881291-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FcZwx4sqIBsQr7kP4dTuJ%2Fuploads%2FGBIXkq9aXHs8ZxOk6VPr%2FScreenshot%202024-02-22%20at%209.02.59%20AM.png?alt=media&amp;token=72eef5a5-5a42-4844-8c24-0fb0057358b4" alt=""><figcaption></figcaption></figure>

Merge operator must satisfy:

<figure><img src="https://3949881291-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FcZwx4sqIBsQr7kP4dTuJ%2Fuploads%2F9ySrwNUg1NWoQMuNj9LV%2FScreenshot%202024-02-22%20at%209.05.38%20AM.png?alt=media&amp;token=60c50694-54a7-47bb-b659-edece78886f1" alt=""><figcaption></figcaption></figure>

Best effort broadcast

### State based vs operation based:

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

## OT

<figure><img src="https://3949881291-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FcZwx4sqIBsQr7kP4dTuJ%2Fuploads%2Foq0RPzJW6avOr80jwdS7%2FScreenshot%202024-02-22%20at%2011.18.53%20AM.png?alt=media&amp;token=ecffc593-df51-4bc3-ae55-ae8bc3d760e2" alt=""><figcaption></figcaption></figure>

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.