Strong Consistency

Linearizability is the strongest and most intuitive form of strong consistency. It guarantees that operations appear to take effect instantaneously at a single point in time between their invocation and response. This creates an illusion of a single, up-to-date copy of the data.

• Real-time Ordering: If operation A completes before operation B begins, then A must appear to have taken effect before B for all observers.
• Single-System Equivalence: The system behaves as if it were a single, non-replicated machine.
• Example: A distributed key-value store like etcd or ZooKeeper provides linearizable reads and writes, ensuring that a client who writes a new value will immediately see it on a subsequent read, and all other clients will see the same updated value.

Achieving strong consistency requires synchronization and coordination between replicas for every write operation. This prevents concurrent, conflicting updates from creating divergent states.

• Coordination Protocols: Systems use protocols like Two-Phase Commit (2PC) or consensus algorithms like Raft and Paxos to ensure all replicas agree on the order and outcome of writes before acknowledging success to the client.
• Global Ordering: All operations must be serialized into a single, globally agreed-upon sequence.
• Performance Trade-off: This coordination introduces latency, as writes must wait for agreement across the network before completing. The CAP Theorem formalizes this trade-off, stating that during a network partition, a strongly consistent system must choose Consistency over Availability.

A fundamental property of strong consistency is the read-after-write guarantee (also called read-your-writes consistency). After a client successfully completes a write, any subsequent read—by the same or a different client—must reflect that update.

• Client-Session Guarantee: This holds true regardless of which node in the system the read request is routed to.
• Contrast with Eventual Consistency: In an eventually consistent system, a read immediately after a write might return a stale value until the update propagates asynchronously.
• Critical for User Experience: This guarantee is essential for applications like banking (seeing an updated balance after a deposit) or collaborative editing (seeing a colleague's change immediately).

Strong consistency enforces strict serialization of all operations (reads and writes). The system must produce an execution history that is equivalent to one where operations were executed one at a time, in some total order, while respecting real-time constraints.

• Serializable Isolation: In database terms, this is analogous to the highest isolation level, Serializable, which prevents phenomena like dirty reads, non-repeatable reads, and phantom reads.
• Consensus-Based Logs: Systems often use a replicated Write-Ahead Log (WAL) or a state machine replication approach, where a consensus algorithm ensures all replicas apply the same log of commands in the identical order.
• Example: Google Spanner uses synchronized atomic clocks and the Paxos consensus algorithm to provide globally serializable transactions across worldwide data centers.

The primary engineering trade-off for strong consistency is increased latency and potentially reduced availability. The requirement for immediate coordination and global agreement inherently slows down operations.

• Network Round-Trips: A write may require multiple network round-trips to achieve consensus among a quorum of replicas before it can be confirmed.
• Partition Intolerance: Per the CAP Theorem, if a network partition occurs, a strongly consistent system cannot accept writes on both sides of the partition without risking inconsistency. It must often choose to become unavailable for writes on one side to preserve consistency.
• Use Case Decision: This makes strong consistency ideal for systems where data correctness is paramount (e.g., financial ledgers, configuration stores) but less suitable for highly latency-sensitive, partition-tolerant applications (e.g., global social media feeds).

Strong consistency is most reliably implemented using distributed consensus algorithms. These algorithms allow a group of nodes to agree on a single value or sequence of values, even if some nodes fail.

• Leader-Based Coordination: Algorithms like Raft and Multi-Paxos elect a leader that sequences client requests into a log. Followers replicate the log, ensuring all apply the same commands in the same order.
• Byzantine Fault Tolerance (BFT): For environments with malicious actors, BFT consensus protocols (e.g., Practical Byzantine Fault Tolerance) are used to maintain consistency despite arbitrary ("Byzantine") failures.
• Atomic Broadcast: This communication primitive, which guarantees all correct processes deliver the same messages in the same total order, is the underlying mechanism for implementing strongly consistent state machine replication.

The strongest single-object consistency model, often considered the gold standard for strong consistency. It guarantees that operations appear to take effect instantaneously at a single point in time between their invocation and response, preserving the real-time ordering of all operations across the system. This means if one operation completes before another begins, the system must reflect that order to all observers. It is the model most intuitive for programmers but imposes significant performance costs due to required coordination.

A weak consistency model that guarantees if no new updates are made to a given data item, all accesses will eventually return the last updated value. It does not specify when convergence will happen. This model prioritizes availability and partition tolerance (as per the CAP Theorem) over immediate consistency, making it suitable for systems where temporary staleness is acceptable, such as social media feeds or DNS. It is the conceptual opposite of strong consistency.

A fundamental trade-off principle stating that a distributed data store can provide at most two of three guarantees simultaneously:

• Consistency (C): Every read receives the most recent write (strong consistency).
• Availability (A): Every request receives a non-error response.
• Partition Tolerance (P): The system continues operating despite network failures that split the nodes. The theorem forces architects to choose which guarantees to prioritize. Strong consistency systems typically choose CP (Consistency & Partition Tolerance), potentially sacrificing availability during a network partition.

A distributed algorithm that enables a group of processes or agents to agree on a single data value or sequence of actions despite the possibility of failures. They are the foundational mechanism for implementing strong consistency in replicated systems. Key examples include:

• Paxos: The seminal, complex protocol for achieving consensus.
• Raft: A more understandable algorithm designed for managing a replicated log. These algorithms ensure all correct replicas execute the same commands in the same order, a prerequisite for State Machine Replication.

A technique for ensuring consistency in replicated systems by requiring a defined subset of replicas to participate in operations. For a system with N replicas, a write quorum (W) and a read quorum (R) are defined. Consistency is maintained if W + R > N. This ensures that every read operation intersects with at least one node that has seen the latest write. It is a practical method to implement strong consistency without requiring all nodes to respond for every operation, improving availability.

A distributed atomic commitment protocol that ensures all participants in a transaction either all commit or all abort. It is a blocking protocol used to achieve strong consistency (atomicity) across multiple databases or services:

1. Prepare Phase: A coordinator asks all participants if they can commit.
2. Commit Phase: If all vote 'yes', the coordinator instructs them to commit; if any vote 'no', it instructs an abort. While it provides strong guarantees, it is a blocking protocol and suffers from coordinator failure, leading to alternatives like the Saga Pattern for long-running transactions.