Gossip Glomers - Distributed Systems Challenges

Special thanks to the Fly.io team and Kyle Kingsbury for creating this excellent series of distributed systems challenges. These challenges provide hands-on experience with fundamental concepts in distributed programming.

Challenges Overview

Challenge #1: Echo

A basic request/response application that serves as an introduction to the challenge framework.

Challenge #2: Unique ID Generation

Implementation of a globally-unique ID generation system. Solution uses a monotonically increasing counter where the final ID is generated by appending the node_id and counter value.

Challenge #3: Broadcast

Implementation of a broadcast system using gossip protocol for cluster-wide message propagation. Two approaches were explored:

1. Immediate Broadcast: Messages are broadcasted to all neighbors immediately upon receipt, with retries until successful delivery.
2. Periodic Batch Broadcast: Messages are collected and broadcasted periodically using a broadcast_many RPC call. While this approach is more bandwidth-efficient, it showed lower performance.

Challenge #4: Grow-Only Counter

Implementation of a grow-only counter using CRDT (Conflict-free Replicated Data Type). Two approaches were explored:

1. Stateful Service:
   • Each node maintains separate counters for all nodes in the network
   • On add request: node updates its counter and broadcasts the update
   • On broadcast receipt: node takes the max value between received and stored counter
   • On read request: node sums all counter values across nodes
2. Stateless Service using seq-kv:
   • Uses Maelstrom's seq-kv service to store counter values
   • Each node's counter is stored separately in seq-kv
   • On add request: node reads current value for node_id from seq-kv, adds the delta and writes back updated value to seq-kv
   • On read request: node read values for all node_ids from seq-kv, and sums all counter values

Challenge #5a: Kafka-Style Log

Implementation of a replicated log service similar to Kafka:

• Uses Maelstrom's lin-kv service for data storage
• Implements distributed locking for write operations
• Read operations proceed without locks for better performance

Challenge #6a: Totally-Available Transactions

Implementation of a transactional key-value store:

• Built on Maelstrom's lin-kv service
• Uses distributed locking for transaction integrity

Technical Implementation

• Built in Rust
• Uses serde for data serialization/deserialization
• Uses tokio for async runtime support
• Uses maelstrom client implemented from scratch