Implement Anti-Entropy with Digest Comparison - The Gossiper

                      TASK
                    

Implementation

Full state sync wastes bandwidth when nodes are mostly in sync. Anti-entropy optimizes this: first exchange compact digests. Only transfer full state if digests differ.

Implement digest-based anti-entropy:

digest handler returns a hash of the current message set
digest_sync handler compares digests and only transfers if different
Track bandwidth savings

Request:  {"type": "digest", "msg_id": 1}
Response: {"type": "digest_ok", "in_reply_to": 1, "digest": "abc123", "count": 5}

Request:  {"type": "digest_sync", "msg_id": 2, "remote_digest": "abc123", "remote_messages": null}
Response: {"type": "digest_sync_ok", "in_reply_to": 2, "match": true, "transferred": 0}

If digests differ, the remote sends its messages:

Request:  {"type": "digest_sync", "msg_id": 3, "remote_digest": "xyz789", "remote_messages": [1,2,3]}
Response: {"type": "digest_sync_ok", "in_reply_to": 3, "match": false, "transferred": 2, "local_messages": [1,2,3,4,5]}

Sample Test Cases

Digest of empty setTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"digest","msg_id":2}}

Expected Output

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

Digest sync with matching digestTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"broadcast","msg_id":2,"message":42}}
{"src":"c1","dest":"n1","body":{"type":"digest","msg_id":3}}

Expected Output

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

Hints

Hint 1▾

A digest is a compact summary of your state (e.g., sorted hash of all message IDs)

Hint 2▾

Compare digests first; only transfer full state if they differ

Hint 3▾

This saves bandwidth when nodes are mostly in sync

Hint 4▾

Use a simple hash of sorted message IDs as the digest

Hint 5▾

Track bytes saved by using digests vs full sync

Resources

Merkle Trees for Anti-Entropy

How Merkle trees enable efficient set reconciliation

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

anti-entropydigestset reconciliationbandwidth optimization

main.py

python

#!/usr/bin/env python3
import sys
import json
import hashlib
class Node:
    def __init__(self):
        self.node_id = None
        self.node_ids = []
        self.next_msg_id = 0
        self.messages = set()
    def send(self, dest, body):
        body["msg_id"] = self.next_msg_id
        self.next_msg_id += 1
        msg = {"src": self.node_id, "dest": dest, "body": body}
        print(json.dumps(msg), flush=True)
    def reply(self, request, body):
        body["in_reply_to"] = request["body"]["msg_id"]
        self.send(request["src"], body)
    def compute_digest(self):
        # TODO: Return a hash of sorted message IDs
        pass
def main():
    node = Node()
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        message = json.loads(line)
        body = message["body"]
        msg_type = body["type"]
        if msg_type == "init":
            node.node_id = body["node_id"]
            node.node_ids = body["node_ids"]
            node.reply(message, {"type": "init_ok"})
        elif msg_type == "broadcast":