CAP Theorem

In theoretical computer science, the CAP theorem states that it is impossible for a distributed data store (such as a blockchain network) to simultaneously provide more than two out of the three guarantees: Consistency, Availability & Partition tolerance.

CAP Theorem – the parts

  • C: Consistency – At any given time, all nodes in the network have exactly the same (most recent) value.
  • A: Availability – Every request to the network receives a response, though without any guarantee that returned data is the most recent.
  • P: Partition tolerance – The network continues to operate, even if an arbitrary number of nodes are failing.
CAP Theorem - The PartsCAP Theorem - The Parts
CAP Theorem - The Parts

CAP Theorem – applied

Due to the nature of distributed data stores (such as blockchain), Partition tolerance is a given fact; there will always be failing/unreachable nodes in the network (not least because of the unstable nature of the internet). CAP Theorem states that one has to choose between C (Consistency) or A (Availability) when in the presence of P (Partition):

Availability over Consistency (A + P)

Every request to the network receives a response, even if the network cannot guarantee it is up to date due to network partitioning (failing nodes).

Choosing Availability over Consistency for a world-wide distributed system will make it highly available, but its data will be out of date for 99.99% of the time. Furthermore, no-one will be able to guarantee that the data returned is in fact the most recent.

CAP Theorem - Availability over ConsistencyCAP Theorem - Availability over Consistency
CAP Theorem - Availability over Consistency

Consistency over Availability (C + P)

The system will return an error or a time-out if particular information cannot be guaranteed to be up to date due to network partitioning (failing nodes).

Choosing Consistency over Availability for a world-wide distributed system will make it highly accurate, but it will most likely be unavailable for 99.99% of the time.

CAP Theorem - Consistency over AvailabilityCAP Theorem - Consistency over Availability
CAP Theorem - Consistency over Availability

Examples

Regular database systems

‘Regular’ databases (or; non-distributed, centralized databases) can use both Consistency + Availability, as they don’t have to worry about partition tolerance (they have no components/nodes in danger of failing, they can only fail as a whole). Note that Availability goes out the door the minute you connect to the database over the internet.

Blockchain

As blockchain networks (such as Bitcoin) are distributed systems, they have to deal with Partition tolerance. Out of the two options that remain, they choose Availability over Consistency. If, for example, Bitcoin would instead choose consistency, it would mean that in the event of a connectivity problem, or any failing node/component (which happens all the time), you wouldn’t be able to use/send/receive Bitcoin. Blockchain networks in general use other means of becoming eventually consistent over time: through mining & blocks.

Paul Kernfeld does a great job explaining how Bitcoin deals with CAP Theorem, right here.

Overview

CAP Theorem - overviewCAP Theorem - overview
CAP Theorem - overview