hesela.devCAP theorem
The CAP theorem rules out guaranteeing both linearizable read/write behavior and completion of every read/write request received by a non-failing node when communication may remain partitioned.
Formal scope: Gilbert and Lynch consider a read/write object in an asynchronous network that can lose arbitrarily many messages. Availability requires eventual operation completion, without a fixed response-time bound; consistency means linearizability, not a general claim about database constraints. [1]
Interpretation: The result depends on the service specification. A constant-returning service requiring no coordination is outside this read/write impossibility. A reachable majority serving requests does not establish completion for clients at every non-failing component. [2]
Design: Choosing two letters is not a complete storage contract. Brewer recommends explicit partition behavior and recovery planning; choices can differ by operation or data. Neither the theorem nor an availability label establishes crash durability. [3]
Operational boundary: A response-time budget can trigger partition handling on a slow but connected network. Nodes need not make this decision simultaneously; a timeout is not proof of physical disconnection. [3]
Relations
- related
- Network partition, Linearizability, Storage availability, Quorum intersection, Data durability, CALM theorem, Invariant confluence
Citations
- Gilbert and Lynch. Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (2002), sections 2.1-2.3 and 3.1.
- Seth Gilbert and Nancy A. Lynch. Perspectives on the CAP Theorem (2012), section 2.
- Eric Brewer. CAP Twelve Years Later: How the Rules Have Changed. Computer, February 2012, pp. 23-25.
Further reading
Sources & caveats
- Primary-source synthesis of the formal read/write model and its design implications; not a cluster experiment or product classification.