Conflict-Free Replicated Data Types (CRDTs)

The guarantee that all replicas of a CRDT will converge to the same state once all operations have been propagated and applied, regardless of the order they were received. This is the primary design goal, enabling high availability and partition tolerance.

• No Coordination Required: Replicas can operate independently, accepting local updates even when disconnected from the network.
• Convergence is Deterministic: The merge function ensures that any two replicas, given the same set of operations, will arrive at an identical final state.
• Example: In a collaborative document, two users adding different words offline will see both words appear once their devices sync, with the final document being identical for both.

The mathematical property where the order of operation application does not affect the final outcome. For CRDTs, this means that concurrent updates can be applied in any order on different replicas and will still converge to the same correct state.

• Core to Conflict Resolution: This property eliminates the 'conflict' in conflict-free replication. If operations commute, there is no conflict to resolve.
• Applies to State-Based CRDTs: The merge function for state-based CRDTs (CvRDTs) must be commutative, associative, and idempotent.
• Example: Incrementing a counter twice (inc() and inc()) commutes; the final count is 2 regardless of which inc was applied first on a remote replica.

The property where applying the same operation multiple times has the same effect as applying it once. This is critical for operation-based CRDTs (CmRDTs) to handle duplicate message delivery in unreliable networks safely.

• Safe Retransmission: Network protocols can retry messages without causing state corruption, as duplicate operations are harmless.
• Combined with Commutativity: Idempotency and commutativity together form the basis for safe, unordered broadcast of operations.
• Example: Setting a flag to true is idempotent; receiving the "set to true" message one time or one hundred times results in the flag being true.

The property where the grouping of operations does not affect the result. For state-based CRDTs, the merge function must be associative: merge(a, merge(b, c)) must equal merge(merge(a, b), c). This ensures convergence is independent of the merge sequence or network topology.

• Enables Partial Merges: Replicas can merge intermediate states from other replicas in any sequence, and the final global state remains consistent.
• Foundation for Gossip Protocols: Associativity allows state to be propagated through a network via peer-to-peer gossip, as merges can happen in any pairwise order.
• Example: In a G-Counter (grow-only counter), the merge function takes the element-wise maximum of two vector states. The max operation is associative.

The formal mathematical structure that underpins state-based CRDTs (CvRDTs). A join-semilattice is a partially ordered set where every pair of elements has a least upper bound (LUB). The CRDT state must be part of such a lattice, and the merge function must compute this LUB.

• Partial Order: Defines a 'happened-before' relationship between states (e.g., one counter vector is less than or equal to another if all its entries are ≤).
• Merge as LUB: Merging two states finds the smallest state that is greater than or equal to both inputs, ensuring progress and consistency.
• Example: A G-Set (grow-only set) forms a lattice where the partial order is subset inclusion (⊆). The merge of two G-Sets is their union (∪), which is the LUB in this lattice.

A messaging guarantee often required by operation-based CRDTs (CmRDTs). It ensures that if operation A causally happened before operation B, then every replica will apply A before B. This preserves logical dependencies without requiring strong consistency or total order broadcast.

• Preserves Intent: Prevents anomalies where an operation that depends on a prior state is applied out of order.
• Weaker than Total Order: Does not require ordering for concurrent, independent operations, maintaining high performance.
• Implementation: Typically achieved using Version Vectors or Dot Contexts to track causal history and buffer operations until their dependencies are satisfied.

A consistency model for distributed systems where, if no new updates are made to a given data item, all replicas will eventually converge to the same value. This model prioritizes high availability and partition tolerance over immediate consistency, making it the ideal target guarantee for CRDTs. It is a core tenet of the CAP theorem.

• Key Trade-off: Accepts temporary state divergence for uninterrupted operation.
• Example: A collaborative document editor (like Google Docs) uses CRDTs to achieve eventual consistency, allowing users to type simultaneously even with network lag.

A fundamental method for implementing a fault-tolerant service by replicating a deterministic state machine across multiple servers. Unlike CRDTs, which allow concurrent, uncoordinated updates, this approach requires all replicas to process the exact same sequence of commands in the same total order to guarantee strong consistency. It is the basis for systems like Apache ZooKeeper and etcd.

• Core Mechanism: Uses a consensus protocol (e.g., Raft, Paxos) to agree on the command log.
• Contrast with CRDTs: Provides strong consistency but requires coordination, which can impact availability during network partitions.

An alternative concurrency control algorithm used in real-time collaborative editing. OT transforms editing operations (like insert or delete) against concurrent operations so they can be applied in any order while preserving user intent. It was pioneered by systems like Google Wave.

• Key Challenge: Requires a central server or complex logic to define transformation rules for all possible operation pairs.
• Comparison to CRDTs: CRDTs are often considered simpler for decentralized systems because they are commutative by design and do not require a central authority or transformation logic for convergence.

A peer-to-peer communication protocol used for efficient and robust information dissemination in decentralized clusters. Nodes periodically exchange state with a few randomly selected peers, causing updates to "epidemically" spread through the network. This is the typical communication layer for propagating CRDT updates.

• Properties: Highly scalable, fault-tolerant, and supports eventual consistency.
• Use Case: Apache Cassandra uses gossip protocols for cluster membership and metadata propagation, forming the transport layer for its CRDT implementations.

CRDTs are broadly categorized by their convergence strategy:

• Operation-based CRDTs (CmRDTs): Require reliable, exactly-once delivery of commutative operations. The state is identical if all replicas apply the same set of operations, regardless of order. Simpler state, more complex messaging guarantees.
• State-based CRDTs (CvRDTs): Replicas periodically exchange their full state via a merge function that is commutative, associative, and idempotent. Simpler messaging (at-least-once), can have larger payloads.
• Pure CRDTs: Converge based on the mathematical properties of the state itself (e.g., monotonic semilattices).

The property of a distributed system that can reach correct consensus even when some components fail arbitrarily (i.e., behave maliciously). This is a stricter fault model than the crash-fault tolerance (CFT) assumed by standard CRDTs and consensus algorithms like Raft.

• CRDT Context: Standard CRDTs are not Byzantine-resistant; a malicious node sending invalid operations can corrupt the shared state.
• Advanced Research: Byzantine CRDTs are an area of study, combining CRDT merge semantics with cryptographic verification (e.g., digital signatures) to tolerate a limited number of Byzantine nodes.