Tune Gossip Parameters for Maelstrom Broadcast - The Gossiper

                      TASK
                    

Implementation

The Maelstrom broadcast workload requires messages-per-op < 30 under network partitions. Your task is to implement configurable gossip parameters and track message efficiency.

Implement a configure handler to set gossip parameters:

Request:  {"type": "configure", "msg_id": 1, "fanout": 3, "gossip_interval_ms": 200}
Response: {"type": "configure_ok", "in_reply_to": 1}

And a gossip_stats handler to report efficiency:

Request:  {"type": "gossip_stats", "msg_id": 2}
Response: {"type": "gossip_stats_ok", "in_reply_to": 2, 
           "broadcasts_received": 10, "gossip_messages_sent": 45,
           "messages_per_op": 4.5, "unique_messages": 10}

Sample Test Cases

Configure updates fanoutTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3"]}}
{"src":"c1","dest":"n1","body":{"type":"configure","msg_id":2,"fanout":3,"gossip_interval_ms":100}}

Expected Output

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

Stats with zero broadcastsTimeout: 5000ms

Input

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

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "gossip_stats_ok", "broadcasts_received": 0, "gossip_messages_sent": 0, "messages_per_op": 0, "unique_messages": 0, "in_reply_to": 2, "msg_id": 1}}

Hints

Hint 1▾

messages-per-op = total messages sent / total broadcast operations

Hint 2▾

Lower fanout = fewer messages but slower convergence

Hint 3▾

Higher gossip interval = fewer rounds but more latency

Hint 4▾

The sweet spot balances message overhead vs delivery reliability

Hint 5▾

Track both metrics and expose them via a stats endpoint

Resources

Fly.io Gossip Glomers - Broadcast

Fly.io distributed systems challenge for broadcast workloads

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

parameter tuningmessages-per-oplatency tradeoffgossip optimization

main.py

python

#!/usr/bin/env python3
import sys
import json
import random
class Node:
    def __init__(self):
        self.node_id = None
        self.node_ids = []
        self.next_msg_id = 0
        self.messages = set()
        self.fanout = 2
        self.gossip_interval_ms = 200
        self.broadcasts_received = 0
        self.gossip_messages_sent = 0
    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 gossip(self, value, exclude=None):
        peers = [n for n in self.node_ids if n != self.node_id and n != 
        exclude]
        targets = random.sample(peers, min(self.fanout, len(peers)))
        for t in targets:
            self.send(t, {"type": "gossip", "value": value})
            self.gossip_messages_sent += 1
def main():
    node = Node()
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue