Linearizability

If each individual object in a system is linearizable, then the system as a whole is linearizable when operations are composed. This locality property is a major advantage for system design, as it allows reasoning about complex systems by analyzing their components independently.

• Design Benefit: You can build a linearizable register, queue, or map and then combine them into a larger service without needing global coordination for every composite operation.
• Non-Composable Models: Other models, like Sequential Consistency, do not generally compose. A system of sequentially consistent objects is not necessarily itself sequentially consistent.

Linearizability strictly orders non-commuting operations. Two operations commute if executing them in either order produces the same final state and returns the same responses. Linearizability imposes a total order where the real-time sequence is respected.

• Example - Read/Write: A read and a write to the same variable do not commute. Their order is fixed by real-time.
• Example - Write/Write: Two writes to the same variable do not commute. The later write (in real-time) must be the one whose value persists.
• Contrast: Some weaker models only require a partial order or only order conflicting operations.

The strong guarantees of linearizability come with inherent performance costs, primarily due to the need for coordination to establish the real-time order and atomic points.

• High Latency: Operations often require communication with a majority of replicas (e.g., via a consensus protocol like Raft or Paxos) or a central leader to establish order, increasing response time.
• CAP Theorem Trade-off: Under a network partition (P), a linearizable (CP) system must choose Consistency over Availability, potentially becoming unavailable for writes to prevent divergent histories.
• Use Case: Essential for systems like leader election, distributed locks, and primary financial ledgers where correctness trumps maximum speed.

Proving a system is linearizable is complex. Key methods include:

• Linearization Point Argument: The most common proof technique, where you explicitly identify the atomic instant for each operation in a history.
• Refinement Mapping: Demonstrating that the concurrent implementation refines an abstract, atomic specification.
• Model Checking: Using tools like TLA+ or Ivy to exhaustively check state spaces of protocol implementations.
• Linearizability Checking: Tools like Lincheck for Java or Porcupine can test histories from actual runs, searching for a valid linearization order. A failed check proves non-linearizability.

A fundamental trade-off in distributed systems design, stating that a networked shared-data system can provide only two of three guarantees simultaneously:

• Consistency (C): Every read receives the most recent write (linearizability).
• Availability (A): Every request receives a (non-error) response.
• Partition Tolerance (P): The system continues operating despite arbitrary message loss.

Linearizability is the strongest form of the 'C' in CAP. The theorem implies that during a network partition, a system must choose between maintaining linearizable consistency (CP) or remaining fully available (AP).

A fundamental technique for building fault-tolerant services. The core idea is to replicate a deterministic service across multiple machines (replicas). If all replicas start in the same state and apply the same sequence of commands in the same order, they will produce identical outputs and states.

• Enabling Technology: Linearizable systems are often implemented using SMR.
• Mechanism: Requires an atomic broadcast protocol to ensure all replicas agree on the total order of commands, which is exactly the guarantee needed for linearizable execution.

A communication primitive that guarantees two properties: Total Order (all correct processes deliver the same set of messages in the same order) and Agreement (if a correct process delivers a message, all correct processes eventually deliver it).

• Equivalence to Consensus: Solving Atomic Broadcast is equivalent to solving Consensus.
• Relation to Linearizability: It is the core communication layer used to implement linearizable services via State Machine Replication. The total order of messages defines the linearization order of operations.

A weak consistency model that stands in contrast to linearizability. It guarantees that if no new updates are made to a data item, eventually all reads to that item will return the last updated value. Temporary inconsistencies, stale reads, and divergent states are allowed during normal operation.

• Trade-off: Sacrifices strong consistency for higher availability and lower latency, as popularized by many globally distributed databases (AP systems under CAP).
• Use Case: Ideal for applications where immediate consistency is not critical, such as social media feeds or collaborative document editing.