🧩Linearizability

NEW

A correctness condition ensuring each concurrent operation appears to occur atomically at some point between invocation and response.

DESCRIPTION

Linearizability provides a strong guarantee for concurrent objects: operations behave as if executed instantaneously and in a single global order consistent with real-time. It simplifies reasoning about correctness by allowing developers to think in terms of atomic operations. Many distributed systems expose linearizable reads and writes at high cost, while others relax guarantees for availability or performance. Understanding linearizability versus weaker models like sequential or eventual consistency guides system design choices. Formal proofs and testing frameworks help validate linearizable behavior.

ALTERNATIVE DEFINITIONS

Wikipedia

Linearizability is a correctness condition for concurrent objects which allows you to consider each operation as if it occurred instantaneously at some point between its invocation and its response.

Centers atomicity and real-time order for concurrent operations.

Source

Herlihy & Wing

Linearizability provides a formal notion of ‘atomic’ object behavior in concurrent systems, preserving real-time ordering of non-overlapping operations.

Introduces the original formalism linking atomicity and real-time order.

Source

Jepsen

Linearizability requires operations to appear in a single global order consistent with real time; it is stronger than sequential consistency.

Practical emphasis comparing to other models with testing guidance.

Source

RELATED TERMS

Consistency Model Atomicity Serializability Isolation (ACID) Distributed Systems CAP Theorem Quorum Lock-Free Algorithms

COMPETING TERMS

Sequential Consistency Eventual Consistency

KNOWLEDGE AREAS

Software Engineering Data Storage & Operations Data Engineering

TARGET AUDIENCE

Software Developer Data Engineer Cloud Architect Software Architect DevOps Engineer IT Auditor

EXTERNAL SOURCES

• Wikipedia - Linearizability
• The Art of Multiprocessor Programming - Foundational coverage of linearizability
• Jepsen - Consistency models guide
• Microsoft - Cosmos DB consistency levels

TOP QUESTIONS

Why is Linearizability useful in distributed systems?

It simplifies reasoning: operations appear atomic and ordered, reducing concurrency bugs and enabling strong invariants.

Category: Relevancy

How does Linearizability compare to Sequential Consistency?

Linearizability respects real-time order; sequential consistency does not require it. Linearizability is strictly stronger.

Category: Distinction

What are the costs of Linearizability?

Higher latency, reduced throughput, and more complex coordination. Systems may trade consistency for availability or performance.

Category: Risks

How do you test for Linearizability?

Use histories of operations and check if a valid linearization exists; tools like Jepsen model and test behaviors under faults.

Category: Testing

Where does Linearizability matter most?

Banking balances, inventory counts, and any state requiring strict correctness guarantees under concurrency.

Category: Example

Is Linearizability required for all operations?

No. Many read-mostly or analytics workloads accept weaker models to scale. Choose per use case.

Category: Opinion

How does CAP theorem relate to Linearizability?

Strong consistency like linearizability can conflict with availability during partitions; systems must choose tradeoffs.

Category: Requirements

What is a common misunderstanding of Linearizability?

Equating it with serializability. Linearizability is for single-operation atomicity; serializability is for transactions.

Category: Misunderstanding

What is a hot topic around Linearizability?

Efficient quorum and replication protocols that deliver near-linearizable behavior with better performance.

Category: Topic