An Interactive Intro to CRDTs

This article serves as an accessible, interactive introduction to Conflict-free Replicated Data Types (CRDTs), aiming to clarify a topic often obscured by academic language. It guides the reader through the fundamental principles of CRDTs before demonstrating how to construct and compose them into more complex data structures, culminating in a preview of a collaborative pixel art editor.

• What are CRDTs? CRDTs (Conflict-free Replicated Data Types) are data structures that allow multiple users to update their own state independently and asynchronously. They guarantee eventual consistency, meaning all peers will eventually converge on the same state without requiring a central server.
• Types of CRDTs: The article distinguishes between state-based CRDTs (which transmit full states for merging) and operation-based CRDTs (which transmit user actions). It focuses exclusively on state-based CRDTs.
• CRDT Interface and Properties: A CRDT is defined by a value, a state (metadata for syncing), and a merge function. This merge function must be Commutative, Associative, and Idempotent (CAI) to ensure consistent convergence.
• Last Write Wins (LWW) Register: The first primitive CRDT introduced, an LWW Register holds a single value and resolves conflicts using timestamps and peer IDs, ensuring the most recent write prevails. Interactive examples demonstrate its behavior.
• Last Write Wins (LWW) Map: Building on LWW Registers, the LWW Map demonstrates composition, allowing multiple key-value pairs to be managed. Each key in the map is, in fact, an LWW Register itself.
• Tombstones and Monotonicity: Deleting entries in an LWW Map doesn't remove them completely but rather sets their value to null. These 'tombstones' are crucial for maintaining merge properties and illustrating that CRDTs are monotonically increasing data structures—they only ever add information.