TASK
Implementation
CRDTs provide coordination-free eventual consistency, but come with tradeoffs. Comparing CRDTs with OCC (Optimistic Concurrency Control) and locking reveals when each approach is appropriate.
CRDT advantages:
- Always available (no coordination required)
- Works under network partitions (AP in CAP)
- Automatic conflict resolution (no human intervention)
CRDT disadvantages:
- Storage overhead: tombstones, vector clocks, tags accumulate
- Merge complexity: custom merge functions for each data type
- Weaker consistency: only eventual (not linearizable)
Comparison table:
| Aspect | CRDT | OCC | Locking |
|---|---|---|---|
| Consistency | Eventual | Linearizable | Linearizable |
| Availability | Always | Abort on conflict | Block on contention |
| Coordination | None | Validation phase | Lock acquisition |
| Storage | High (metadata) | Low | Low |
| Latency | Low (local) | Low (optimistic) | Variable (wait) |
Request: {"type": "tradeoff_analysis", "msg_id": 1, "use_case": "shopping_cart", "partition_rate": 0.1, "conflict_rate": 0.3}
Response: {"type": "tradeoff_analysis_ok", "in_reply_to": 1, "recommendation": "CRDT", "reasoning": "High partition rate favors always-available CRDT over blocking approaches"}Sample Test Cases
High partition rate recommends CRDTTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"tradeoff_analysis","msg_id":2,"use_case":"counter","partition_rate":0.5,"conflict_rate":0.1}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Low conflict rate recommends OCCTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"tradeoff_analysis","msg_id":2,"use_case":"banking","partition_rate":0.01,"conflict_rate":0.05}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
CRDTs: no coordination, but tombstones and metadata increase storage cost
Hint 2▾
Locking: strong consistency, but lock contention limits scalability
Hint 3▾
OCC (Optimistic Concurrency Control): good for low-conflict workloads, aborts on conflict
Hint 4▾
CRDTs shine under partition: they remain available without coordination
Hint 5▾
Build a comparison for 3 use cases: counter, shopping cart, document editing
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
CRDT tradeoffsstorage overheadmerge complexityOCC comparisoncoordination-free
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python3
import sys
import json
def main():
# Your implementation here
for line in sys.stdin:
msg = json.loads(line)
print(json.dumps(msg), flush=True)
if __name__ == "__main__":
main()