A high-throughput, eventually consistent gossip protocol implementation. Designed to pass the Maelstrom distributed systems test suite with strict latency and validity guarantees.
This node implements a fan-out architecture optimized for high-latency, partition-prone networks.
- Temporal Batching: Implements a Nagle-like aggregation strategy. Messages are buffered and flushed via a 15ms ticker, reducing RPC overhead and network IOPS by ~90% compared to naive forwarding.
- Asynchronous Pipelining: Decouples message ingestion from propagation. Inbound broadcasts are immediately committed to local state (
sync.RWMutex), while outbound propagation is handled by dedicated, non-blocking neighbor workers. - Backpressure & Flow Control: Utilizes per-neighbor semaphores (buffered channels, cap=10) to limit inflight RPCs. This prevents head-of-line blocking and manages resource saturation during partition recovery.
- Reliability: Ensures at-least-once delivery via explicit RPC acknowledgments. Failed or timed-out batches are automatically re-queued for retry.
Performance was evaluated using a 25-node cluster arranged in a 4-ary tree topology, simulating widespread network latency.
Test Configuration:
- Nodes: 25
- Topology: Tree4
- Network Latency: 100ms (simulated)
- Throughput: 100 messages/sec
- Duration: 20s
Results:
| Metric | Result |
|---|---|
| Availability | 100% |
| Consistency | Strong Eventual |
| p50 Latency | 385ms |
| p99 Latency | 530ms |
| Net Overhead | ~13.3 msgs/op |
Build
go build -o node main.goReproduction Requires the Maelstrom binary.
./maelstrom test -w broadcast \
--bin ./node \
--node-count 25 \
--topology tree4 \
--time-limit 20 \
--rate 100 \
--latency 100