Subtracks & Tasks
The Lost Update Problem
Implement Basic Counter with Lost Update Problem
Implement a basic grow-only counter that handles add and read operations. Multiple nodes share counter state, but your initial implementation will los...
Integrate Sequentially Consistent Key-Value Store
Use Maelstrom's built-in seq-kv service to store your counter value. This provides sequential consistency but introduces new challenges around availab...
Implement Compare-And-Swap (CAS) Operation
Implement your counter using Compare-And-Swap (CAS) operations. CAS atomically updates a value only if it matches an expected value, preventing lost u...
Build Grow-Only Counter (G-Counter) CRDT
Implement a G-Counter CRDT where each node maintains its own counter. The total is the sum of all per-node counters. Merging is done by taking the max...
Handle Concurrent Increments Across Multiple Nodes
Test your G-Counter under heavy concurrent load. Multiple nodes will simultaneously increment and the final value must equal the sum of all increments...
G-Counter and PN-Counter
Implement a G-Counter (Grow-Only CRDT)
A G-Counter (Grow-only Counter) is the simplest CRDT. Each node maintains a vector of N integers, one per node. A node only increments its own slot, a...
Prove G-Counter CRDT Properties
A CRDT merge function must satisfy three properties to guarantee convergence: commutativity, associativity, and idempotency. Proving these for the G-C...
Implement a PN-Counter for Increment and Decrement
A G-Counter only grows. To support decrements, the PN-Counter uses two G-Counters: P (positive) for increments and N (negative) for decrements. **Dat...
Gossip PN-Counter Across a Cluster
To replicate the PN-Counter across a cluster, each node periodically gossips its full state to random peers. This is an anti-entropy protocol that gua...
Pass the Maelstrom G-Counter Workload
The Maelstrom g-counter workload is the definitive correctness test for your CRDT counter implementation. It runs your nodes in a simulated distribute...
More CRDTs
Implement an OR-Set (Observed-Remove Set)
The OR-Set (Observed-Remove Set) solves the concurrent add/remove problem. Each element is tagged with a unique identifier, and remove only removes ta...
Implement a Multi-Value Register (MV-Register)
A Multi-Value Register (MV-Register) handles concurrent writes by keeping ALL concurrent values as siblings. The client resolves conflicts on read. *...
Implement a Sequence CRDT for Collaborative Text Editing
A Sequence CRDT enables collaborative text editing where multiple users can type simultaneously without conflicts. The RGA (Replicated Growable Array)...
Analyze CRDT Tradeoffs vs. OCC and Locking
CRDTs provide coordination-free eventual consistency, but come with tradeoffs. Comparing CRDTs with OCC (Optimistic Concurrency Control) and locking r...
Build a Distributed Shopping Cart with CRDTs
A distributed shopping cart demonstrates CRDTs solving a real-world problem. Using an OR-Set, items can be added and removed from the cart across part...
Interview Prep
Common interview questions for Backend / Distributed Systems Engineer roles that map directly to what you build in this track. Click any question to reveal the model answer.
Questions are representative of real interview patterns. Model answers are starting points — adapt them with your own experience and the specific context of the interview.
Common Mistakes
The top 5 mistakes builders make in this track — and exactly how to fix them. Click any mistake to see the root cause and the correct approach.
Comparison Mode
Side-by-side comparisons of the approaches, algorithms, and trade-offs you encounter in this track. Expand any comparison to see a detailed breakdown.
Concepts Covered
Prerequisites
It is recommended to complete the previous tracks before starting this one. Concepts build progressively throughout the curriculum.
Rabbit Holes
For when you want to go deeper. Curated papers, posts, and talks beyond what this track covers.
CRDTs: Consistency without Concurrency Control
Shapiro et al., 2011. The paper that formalized CRDTs (Conflict-free Replicated Data Types). G-Counters and PN-Counters are Section 3. This is the theoretical foundation for why your counter works without coordination.
A Comprehensive Study of CRDTs
A longer survey of the CRDT landscape with proofs of convergence. Useful when you want to understand what data structures besides counters can be made eventually consistent without coordination.
Strong Eventual Consistency and CRDTs (Talk by Marc Shapiro)
Shapiro explaining the intuition behind CRDTs in a way that the papers don't. If the math in the paper is dense, start here.
Riak's CRDT Documentation
How Riak exposed CRDTs as first-class types to application developers. The API design decisions here are worth studying even if you never use Riak.