Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

Gilbert, S., & Lynch, N. (2002). Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News, 33(2), 51-59.

Type

Journal article

Intellectual base

Primary research

Year

2002

Volume

33

Issue

2

Pages

51-59

DOI

10.1145/564585.564601

DOI registrant

Association for Computing Machinery

Link

https://doi.org/10.1145/564585.564601

Cited from

computer_science, economics_finance, mathematics, synthesized, systems_cybernetics

Cited by

15 citations across 15 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Axiomatic Incompatibility
  • In distributed systems, the CAP theorem rules out consistency, availability, and partition-tolerance jointly under partition, and FLP rules out deterministic asynchronous consensus tolerating even one crash.

    Supported in partVerified against the publisher's abstract

    Its own abstract proves the CAP impossibility — consistency, availability and partition tolerance cannot all three be achieved — but says nothing about the team-production clause or about FLP.

    “When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three.”

    Read by an automated reader; not a human review. How support was checked

• Consistency Model
  • They interact (partitions force consistency/availability trade-offs

    This sourceProves the CAP theorem: under network partition a system must trade consistency against availability.

    SupportedVerified against the publisher's abstract

    Gilbert and Lynch state that consistency, availability and partition tolerance are the three properties commonly desired of distributed web services and that "It is impossible to achieve all three". Where partitions must be tolerated, consistency and availability cannot both be preserved, which is the interaction the sentence names.

    “When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three.”

    Read by an automated reader; not a human review. How support was checked

• Inconsistent Shared Model
  • The uncoupled inference channel is now literal: the replication link between A and B is severed, so each continues to apply writes and update its own internally consistent model with no way to compare against the other.

    This sourceFormal proof of the CAP theorem; the consistency/availability menu (CP refuse writes vs AP accept divergence and reconcile) is the set of pre-declared responses to split-brain divergence under partition.

    Supported in partVerified against the publisher's abstract

    The CAP impossibility abstract backs only the general partition trade-off, not the claim's specifics that a severed replication link leaves each side applying writes to its own unreconciled model.

    “When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three.”

    Read by an automated reader; not a human review. How support was checked

• Trade-offs
  • - Computer science and information systems

    Supported in partVerified against the publisher's abstract

    Abstract states a proof that consistency, availability and partition tolerance cannot all be had in distributed web services: a computer-science trade-off.

    “there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three.”

    Read by an automated reader; not a human review. How support was checked

• Trilemma
  • The three named desirables are Consistency (every read returns the most recent write), availability (every request receives a non-error response), and partition tolerance (the system continues operating despite dropped messages between nodes).

    This sourceFormal proof of the CAP theorem — consistency, availability, and partition tolerance cannot all be guaranteed in an asynchronous network.

    Supported in partVerified against the publisher's abstract

    The abstract names consistency, availability, and partition tolerance as the three commonly desired properties, but does not state the parenthetical definitions the claim gives.

    “When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance.”

    Read by an automated reader; not a human review. How support was checked

Domain-specific

• CAP Theorem
  • The CAP theorem, conjectured by Brewer in 2000 and proved by Gilbert and Lynch in 2002

    SupportedVerified against the source

    Read by an automated reader; not a human review. How support was checked

• CAP Theorem (and variants)
  • The CAP theorem (Brewer 2000; Gilbert and Lynch 2002) establishes that a distributed data store cannot simultaneously guarantee Consistency (linearisable reads), Availability (every non-failing node responds to every request), and Partition tolerance (continued operation when inter-node messages are lost or delayed) — and because partitions are an environmental fact of real networks, the operative trade-off is: during a partition, sacrifice consistency or sacrifice availability

    This sourceThe paper proving that a distributed web service cannot simultaneously guarantee consistency, availability and partition tolerance. The 2002 proof of Brewer's conjecture on which the article's worked two-node scenario is modelled.

    Supported in partVerified against the publisher's abstract

    “When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three. In this note, we prove this conjecture in the asynchronous network model”

    Read by an automated reader; not a human review. How support was checked

• Distributed Data Store
  • Gilbert and Lynch show that an asynchronous read/write service cannot guarantee atomic consistency, availability, and tolerance of arbitrary message loss simultaneously.
• Iron triangle of health care
  • That structure really recurs — in the CAP theorem of distributed systems (consistency, availability, partition tolerance), the Mundell-Fleming impossible trinity in international macroeconomics (fixed exchange rate, free capital flow, independent monetary policy), and the project-management triangle (scope, time, cost) — but the frontier-shifting exception does not carry across them uniformly: a productivity or technology gain can move the project triangle's frontier outward, whereas the CAP theorem is a proved impossibility that no technology gain relaxes

    This sourceGilbert and Lynch's proof that consistency, availability and partition tolerance cannot all be guaranteed together, though any two can.

    Supported in partVerified against the source

    Read by an automated reader; not a human review. How support was checked

Mechanisms

• Central Registry
  • Under a network partition the registry faces the consistency-versus-availability choice directly

    This sourceProves that a distributed service cannot guarantee both consistency and availability in the presence of network partitions.

• Coherence-Utility Tradeoff Test
  • It is the general form of the CAP-style

    This sourceShows that an asynchronous service subject to message loss cannot guarantee both atomic consistency and availability.

• Distributed Service Model
  • The unavoidable tension is that a distributed data store cannot be simultaneously consistent and available when the network partitions — you must choose which to sacrifice under a split, and pretending you won't have to is the classic error.
• Federated Registry Synchronization
  • This is the CAP trade in the flesh — under a partition you get availability or consistency, not both, so a federation that stays available will sometimes serve divergent answers.

    This sourceProves that a partitioned asynchronous service cannot guarantee both availability and atomic consistency, so remaining available permits divergent answers.

• Impossibility-Theorem Instantiation Review
  • … during partitions, or (rarely legitimate) assume partitions cannot occur — plus a recheck trigger: if the "always available under partition" requirement is later dropped, or the system is scoped to a single failure domain where partitions don't arise, CAP no longer bites and this verdict must be reopened.

    This sourceProves that atomic consistency, availability, and partition tolerance cannot all be guaranteed, and identifies the exits: weaken consistency, weaken availability during failures, or rely on the absence of partitions.

• Linearizable Read/Write Protocol
  • Its cost is exactly its guarantee: under a network partition it cannot be both available and linearizable, so the minority side must stop serving.

    This sourceUnder a network partition, an atomic or linearizable service cannot also guarantee a response to every request.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 8 of 15 citations: 2 supported, 6 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:5298f3b70ae1 · see in the full table