TASK
Implementation
What fanout K guarantees that all N nodes receive a message with probability >= 0.99? The theory says that after R rounds of gossip with fanout K, the probability that a specific node has NOT received the message is approximately (1 - K/N)^R.
Your task is to:
- Implement the probability calculation: P(miss) = (1 - K/(N-1))^R
- Find minimum K for a given N and target probability
- Simulate gossip rounds to verify empirically
Implement a calc_fanout handler:
Request: {"type": "calc_fanout", "msg_id": 1, "nodes": 25, "target_prob": 0.99, "rounds": 5}
Response: {"type": "calc_fanout_ok", "in_reply_to": 1, "min_fanout": 3, "miss_prob": 0.003}And a simulate_gossip handler that runs a Monte Carlo simulation:
Request: {"type": "simulate_gossip", "msg_id": 2, "nodes": 25, "fanout": 2, "rounds": 10, "trials": 100}
Response: {"type": "simulate_gossip_ok", "in_reply_to": 2, "delivery_rate": 0.98, "avg_rounds_to_all": 4.7}Sample Test Cases
Calculate fanout for small clusterTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"calc_fanout","msg_id":2,"nodes":5,"target_prob":0.99,"rounds":5}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Simulate gossip returns delivery rateTimeout: 10000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"simulate_gossip","msg_id":2,"nodes":10,"fanout":3,"rounds":5,"trials":50}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
Probability of a node NOT receiving a message in one round: (1 - K/N)^R where R is rounds
Hint 2▾
For 99% delivery across N nodes, solve for K given the number of gossip rounds
Hint 3▾
More rounds = lower K needed, but more latency
Hint 4▾
Log(N) rounds with fanout K=2 typically suffices for high probability delivery
Hint 5▾
Implement a simulation to verify the theoretical formula empirically
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
probabilitygossip reliabilityfanout analysisconvergence
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python3
import sys
import json
import random
import math
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 calc_min_fanout(self, n, target_prob, rounds):
# TODO: Find minimum K where P(all receive) >= target_prob
pass
def simulate(self, n, fanout, rounds, trials):
# TODO: Monte Carlo simulation of gossip
pass
def main():
node = Node()
random.seed(42)
for line in sys.stdin:
line = line.strip()
if not line:
continue
message = json.loads(line)
body = message["body"]