Martin Kleppmann
2015 · arXiv
The CAP Theorem is a frequently cited impossibility result in distributed systems, especially among NoSQL distributed databases. In this paper we survey some of the confusion about the meaning of CAP, including inconsistencies and ambiguities in its definitions, and we highlight some problems in its formalization. CAP is often interpreted as proof that eventually consistent databases have better availability properties than strongly consistent databases; although there is some truth in this, we show that more careful reasoning is required. These problems cast doubt on the utility of CAP as a tool for reasoning about trade-offs in practical systems. As alternative to CAP, we propose a "delay-sensitivity" framework, which analyzes the sensitivity of operation latency to network delay, and which may help practitioners reason about the trade-offs between consistency guarantees and tolerance of network faults.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
6 selected excerpts · 6 total mentions
Martin Kleppmann's "A Critique of the CAP Theorem" lays this all out very nicely and goes further, providing a better conceptual framework for discussing the tradeoffs: https://arxiv.org/abs/1509.05393 One of the best papers I've come across in the last few years.
> I don't think you realise how simple and fundamental the CAP theorem is May I recommend reading "A Critique of the CAP Theorum - Martin Kleppmann", available as a PDF here https://arxiv.org/abs/1509.05393 As that paper points out, your definition of CAP theorem is simplified and incomplete to the point of being wrong, as many are. As it also point out, CAP theorem doesn't really account for eventual consistency well. I would argue that a chat protocol is a good place to perform eventual consistency, and those tradeoffs work well. During network partitions, have both sides of the partition continue to accept messages. Have the client mark messages with random unique IDs,…
and have each server mark messages with a server timestamp. The well-defined merge operation is now to sort by server-time and dedupe by message ID, such that if a message is sent to two servers it only displays once. This doesn't work for IRC traditionally, since messages do not have unique IDs, and so no merge operation can deduplicate them, and servers do not store messages during netsplits (or at any time really), so they cannot be re-sent. However, a similar system exists for other chat systems. matrix is a federated system of multiple servers, and when partitions occur, each server will still accept new messages, and later those messages will be made available to other servers and merged in at the appropriate time. I think that CAP theorem's results are less interesting if you consider application-level resolutions to network issues (i.e. eventual consistency), and as I believe the paper also implies trotting it out constantly when talking about practical systems gets old fast.
Two things. 1. The notion of "high availability" wasn't used much before "web scale" applications. 2. As others have said, the CAP theorem is kind of tautological and does more to confuse about what's possible than to clarify. For example, the CAP theorem implies that even eventual consistency is impossible in the case of partitions. If partitions can be of infinite length then no kind of consistency is possible; if partitions are finite, then all kinds of consistency are possible (with "availability" meaning very high latency, though). In short, the CAP theorem itself doesn't contribute much information to the analysis of distribution problems. I recommend reading this nice overview of the issues with CAP: http://arxiv.org/abs/1509.05393
For the interested reader you can see a paper talking about this by Martin Kleppmann https://arxiv.org/abs/1509.05393 - the author of DDIA.
Related: A Critique of CAP Theorem by Martin Kleppman https://arxiv.org/abs/1509.05393 TL;DR: terms in CAP are not adequately defined and he proposes a delay-sensitive framework.
Concerning his claims about CAP and that their cluster is neither C nor A, because of P, while Percona claims it is CA, some days ago a paper was linked here "A Critique of the CAP Theorem" - http://arxiv.org/abs/1509.05393 which I found very englighting about the P in CAP.
More from the same topics.
William P. Thurston
In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.
Tim Kraska, Alex Beutel, Ed H. Chi +2
Indexes are models: a B-Tree-Index can be seen as a model to map a key to the position of a record within a sorted array, a Hash-Index as a model to map a key to a position of a record within an unsorted array, and a BitMap-Index as a model to indicate if a data record exists or not.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan +11
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.
Eric Chisolm
This is an introduction to geometric algebra, an alternative to traditional vector algebra that expands on it in two ways: 1.