Handle Network Partition Healing and Resynchronization - The Gossiper

                      TASK
                    

Implementation

Handle the scenario where network partitions heal and previously isolated nodes reconnect. Implement anti-entropy mechanisms to synchronize message sets between nodes that were separated.

Sample Test Cases

Nodes sync after partition healsTimeout: 20000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2"]}}
{"src":"c0","dest":"n1","body":{"type":"topology","msg_id":2,"topology":{"n1":["n2"],"n2":["n1"]}}}
{"src":"c1","dest":"n1","body":{"type":"broadcast","msg_id":3,"message":10}}
{"src":"c1","dest":"n1","body":{"type":"broadcast","msg_id":4,"message":20}}
{"src":"c2","dest":"n1","body":{"type":"read","msg_id":5}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c0", "body": {"type": "topology_ok", "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "broadcast_ok", "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "n2", "body": {"type": "broadcast", "message": 10, "msg_id": 3}}
{"src": "n1", "dest": "c1", "body": {"type": "broadcast_ok", "in_reply_to": 4, "msg_id": 4}}
{"src": "n1", "dest": "n2", "body": {"type": "broadcast", "message": 20, "msg_id": 5}}
{"src": "n1", "dest": "c2", "body": {"type": "read_ok", "messages": [10, 20], "in_reply_to": 5, "msg_id": 6}}

Hints

Hint 1▾

Detect when partitions heal

Hint 2▾

Exchange message sets with reconnected nodes

Hint 3▾

Use Merkle trees for efficient sync

Hint 4▾

Reply with broadcast_ok before forwarding to neighbors to ensure deterministic output ordering

Resources

Anti-Entropy Protocols

Research on anti-entropy and synchronization

                      OVERVIEW
                    

Theoretical Hub

Anti-Entropy

Anti-entropy protocols periodically compare state between nodes and resolve differences. When partitions heal, nodes must reconcile their message sets to ensure eventual consistency.

Key Concepts

network partitionsresynchronizationanti-entropy

main.py

python