Implement an OR-Set (Observed-Remove Set) - The Counter

Implementation

The OR-Set (Observed-Remove Set) solves the concurrent add/remove problem. Each element is tagged with a unique identifier, and remove only removes tags that have been observed.

Problem with naive sets: if node A adds "x" and node B concurrently removes "x", what happens? With a naive set, the result depends on message ordering — non-deterministic.

OR-Set solution:

add("x"): store ("x", tag_1) where tag_1 is a unique UUID
remove("x"): remove ALL currently visible pairs for "x": {("x", tag_1)}
If node A does add("x") concurrently with node B doing remove("x"): node A's add creates tag_2, which node B has never seen. After merge, ("x", tag_2) survives. Add wins.

Request:  {"type": "or_set_add", "msg_id": 1, "element": "apple"}
Response: {"type": "or_set_add_ok", "in_reply_to": 1, "tag": "uuid-001"}

Request:  {"type": "or_set_remove", "msg_id": 2, "element": "apple"}
Response: {"type": "or_set_remove_ok", "in_reply_to": 2, "tags_removed": ["uuid-001"]}

Request:  {"type": "or_set_read", "msg_id": 3}
Response: {"type": "or_set_read_ok", "in_reply_to": 3, "elements": ["banana", "cherry"]}

Sample Test Cases

Add and read elementTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"or_set_add","msg_id":2,"element":"apple"}}
{"src":"c1","dest":"n1","body":{"type":"or_set_read","msg_id":3}}

Expected Output

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

Remove deletes elementTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"or_set_add","msg_id":2,"element":"banana"}}
{"src":"c1","dest":"n1","body":{"type":"or_set_remove","msg_id":3,"element":"banana"}}
{"src":"c1","dest":"n1","body":{"type":"or_set_read","msg_id":4}}

Expected Output

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

Hints

Hint 1▾

Each element is stored with a unique tag (UUID) when added

Hint 2▾

add(e) creates a new entry: (element, unique_tag)

Hint 3▾

remove(e) removes all currently observed (element, tag) pairs for that element

Hint 4▾

Concurrent add + remove: the new add has a tag not yet observed by the remove, so it survives

Hint 5▾

Merge: union of all (element, tag) pairs from both replicas

Implementation

Sample Test Cases

Hints

Resources

Theoretical Hub

Key Concepts