HackerPapers

arXiv:1509.05393cs.DC

A Critique of the CAP Theorem

Martin Kleppmann

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.DCDistributed, Parallel, and Cluster Computing cs.DBDatabases

On Hacker News

Linked by 7 identifiable commenters in 7 comments across 7 threads, from Sep 2015 to Sep 2026. Found in 2 HN submissions from Sep 2015 to Jun 2017. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments7 threads

  1. Distributed Systems Classics (2017) 1 comment

    • A Critique of the CAP theorem by Martin Kleppmann. https://arxiv.org/abs/1509.05393 Basically naive CAP theorem assumes "no latency (delay) allowed", in which case, yeah, sure, the quorum must agree or you are writing to a split-brain quorum somehow. But what if delay…

      NortySpockView on HNParent context

  2. An illustrated proof of the CAP theorem (2018) 1 comment

    • 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.

      tajdView on HNParent context

  3. CAP twelve years later: How the "rules" have changed (2012) 1 comment

    • 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.

      sethammonsView on HNParent context

  4. Why is IRC distributed across multiple servers? 1 comment

    • > 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…

      TheDongView on HNParent context

  5. The Limits of the CAP Theorem 1 comment

    • 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.

      thraxilView on HNParent context

  6. The CAP FAQ 1 comment

    • 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…

      pronView on HNParent context

  7. Call Me Maybe: Percona XtraDB Cluster 1 comment

    • 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.

      _CodemonkeyismView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.