Pass Linearizable KV with Network Partitions - The Consensus

                      TASK
                    

Implementation

The ultimate test: pass a linearizable key-value workload with 5 nodes under network partitions. This combines everything: leader election, log replication, commitment, snapshots, and partition handling.

Your system must:

Continue serving reads and writes when a majority is available
Reject requests when only a minority partition is reachable
Recover correctly after partition heals
Maintain linearizability throughout

Request:  {"type": "partition_test", "msg_id": 1, "cluster_size": 5, "operations": 100, "partition_after_op": 30, "heal_after_op": 70}
Response: {"type": "partition_test_ok", "in_reply_to": 1, "total_ops": 100, "ops_during_partition": 40, "ops_succeeded": 85, "ops_rejected": 15, "linearizable": true}

Request:  {"type": "verify_linearizability", "msg_id": 2, "history": [...]}
Response: {"type": "verify_linearizability_ok", "in_reply_to": 2, "linearizable": true, "violations": []}

Sample Test Cases

Partition test maintains linearizabilityTimeout: 10000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3","n4","n5"]}}
{"src":"c1","dest":"n1","body":{"type":"partition_test","msg_id":2,"cluster_size":5,"operations":20,"partition_after_op":5,"heal_after_op":15}}

Expected Output

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

Writes rejected in minority partitionTimeout: 10000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3","n4","n5"]}}
{"src":"c1","dest":"n1","body":{"type":"partition_test","msg_id":2,"cluster_size":5,"operations":10,"partition_after_op":2,"heal_after_op":8}}

Expected Output

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

Hints

Hint 1▾

Network partitions split the cluster into minority and majority groups

Hint 2▾

The minority partition must stop serving writes (no quorum)

Hint 3▾

The majority partition elects a new leader and continues serving

Hint 4▾

After partition heals, the minority nodes must sync up via log replication

Hint 5▾

Linearizability means every read returns the most recent committed write

Resources

Maelstrom - Linearizable KV Workload

Maelstrom lin-kv workload specification for testing linearizability

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

linearizabilitynetwork partitionMaelstromend-to-end correctness

main.py

python