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 – 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)
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.
Consistency over Availability (C + P)
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.
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.
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.
CAP Theorem was originally conceived by Eric Brewer.
Continued reading / sources
- Brewer’s CAP Theorem – The kool aid Amazon and Ebay have been drinking – Julian Browne
- Wikipedia – CAP Theorem
- The Road Ahead for Ethereum: Three Hard Problems – Muneeb Ali
- How Bitcoin Loses to the CAP Theorem – Paul Kernfeld
- What if a country loses connectivity to the rest of the world?
- You Can’t Sacrifice Partition Tolerance – Coda Hale
- Please stop calling databases CP or AP – Martin Kleppmann