Implement a Sequence CRDT for Collaborative Text Editing - The Counter

                      TASK
                    

Implementation

A Sequence CRDT enables collaborative text editing where multiple users can type simultaneously without conflicts. The RGA (Replicated Growable Array) assigns each character a unique, ordered position identifier.

RGA design:

Each character has a unique ID: (lamport_timestamp, node_id)
Characters are ordered by their IDs — the document is the sorted sequence
Insert between positions P1 and P2: create a new ID between them
Delete: mark the character as a tombstone (keep the ID for ordering)

Concurrent inserts: if two users insert at the same position, the tiebreaker is the node ID. This ensures deterministic ordering across all replicas.

Request:  {"type": "seq_insert", "msg_id": 1, "position": 0, "char": "H"}
Response: {"type": "seq_insert_ok", "in_reply_to": 1, "id": "1-n1"}

Request:  {"type": "seq_read", "msg_id": 2}
Response: {"type": "seq_read_ok", "in_reply_to": 2, "text": "Hello", "length": 5}

Sample Test Cases

Insert and read charactersTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"seq_insert","msg_id":2,"position":0,"char":"H"}}
{"src":"c1","dest":"n1","body":{"type":"seq_insert","msg_id":3,"position":1,"char":"i"}}
{"src":"c1","dest":"n1","body":{"type":"seq_read","msg_id":4}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Delete marks character as tombstoneTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"seq_insert","msg_id":2,"position":0,"char":"A"}}
{"src":"c1","dest":"n1","body":{"type":"seq_insert","msg_id":3,"position":1,"char":"B"}}
{"src":"c1","dest":"n1","body":{"type":"seq_delete","msg_id":4,"position":0}}
{"src":"c1","dest":"n1","body":{"type":"seq_read","msg_id":5}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Hints

Hint 1▾

Use RGA (Replicated Growable Array): each character has a unique position ID

Hint 2▾

Position IDs are ordered and never change — new characters get IDs between neighbors

Hint 3▾

Delete marks a character as a tombstone (never physically removed)

Hint 4▾

Concurrent inserts at the same position are ordered by node ID (tiebreaker)

Hint 5▾

The final document is the sequence of non-tombstoned characters in position order

Resources

RGA: Replicated Growable Array

Roh et al. - Replicated abstract data types: Building blocks for collaborative applications

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

sequence CRDTRGAcollaborative editingposition identifiersconcurrent inserts

main.py

python