TASK
Implementation
Implement a gossip protocol where each node randomly selects neighbors to share information with. This provides robustness against node failures while keeping message overhead reasonable.
Sample Test Cases
Random gossip spreads message to all nodesTimeout: 15000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c0","dest":"n1","body":{"type":"topology","msg_id":2,"topology":{"n1":[]}}}
{"src":"c1","dest":"n1","body":{"type":"broadcast","msg_id":3,"message":99}}
{"src":"c1","dest":"n1","body":{"type":"read","msg_id":4}}
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":"c1","body":{"type":"read_ok","in_reply_to":4,"msg_id":3,"messages":[99]}}
Hints
Hint 1▾
Randomly select a subset of neighbors
Hint 2▾
Retry periodically for reliability
Hint 3▾
Balance between speed and overhead
OVERVIEW
Theoretical Hub
Gossip Protocols
Gossip, or epidemic, protocols spread information like a disease. Each infected node randomly selects peers to infect. This provides probabilistic guarantees of delivery with tunable overhead.
Key Concepts
gossip protocolrandom selectionprobabilistic broadcast
main.py
python
1
2
3
4
5
6
7
#!/usr/bin/env python3
import sys
import json
import random
# TODO: Implement gossip with random neighbor selection