Revisit CAP Theorem in Blockchain
I came across some articles 1 and lectures 2 that use the CAP theorem to explain the blockchain. I don’t think it is a good idea. The CAP theorem is a very specific theorem that is proved in a very specific context. It is not a general theorem that can be applied to any distributed system.
The CAP theorem came from this paper. The theorem is proved in a very restricted context, where a distributed read-write register is used for the model. The Consistency, Availability, and Partition Tolerance are the three precisely defined properties (unlike today’s vague definitions in the blockchain world).
- Consistency: It doesn’t mean that all replicas converge to the same state (I’ve seen a lot of people use this definition). It means linearizability, that all operations appear to have executed atomically in some order.
Under this consistency guarantee, there must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time.
- Availability: It means all requests to a non-failing node must return a response (without any time bound guarantee).
For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response.
- Partition Tolerance: It means you’re communicating over an asynchronous network, where messages can be delayed arbitrarily. Don’t be misled by the name.
In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another. When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost.
Blockchain is definitely a distributed system but not a distributed read-write register. The CAP theorem is not applicable to the blockchain given the assumptions and model doesn’t hold for the blockchain. If you use a mathematical theorem to explain something, you should make sure that the assumptions and model hold for the thing you’re explaining.
Please don’t use the CAP theorem to explain the blockchain, as it will cause more confusion than clarity.
[1] CAP Theorem in Blockchain https://www.geeksforgeeks.org/cap-theorem-in-blockchain/
[2] Peer-to-Peer Systems and Security at Technical University of Munich https://www.net.in.tum.de/teaching/ss24/p2p.html (I took this lecture at TUM but unfortunately the slides are not public and I can’t find any other references)