CAP Theorem and the Blockchain as the Database(chepurnoy.org)
chepurnoy.org
CAP Theorem and the Blockchain as the Database
http://chepurnoy.org/blog/2015/04/cap-theorem-and-the-blockchain-as-the-database/
1 comments
I guess it seems odd to say that it's CP if the system is in an inconsistent state during a partition. What I'm getting at is that as users of the system, we are not happy to accept work until we have evidence that the work is verified by multiple different nodes of the system. While one node might accept transactions, as clients, we ourselves only "accept" those transactions once we observe that the system as a whole is consistent. Since the system does not "do work" for us while there is a partition, I'm saying that it's more CP than AP.
Much of the interesting thing about AP and CP systems is their behavior during a partition.
With a CP system, when a partition happens, the system may have to stop accepting transactions. It becomes unavailable because it cannot provide consistency. For example, imagine something like Raft, where a message can only be committed to the log once it has been replicated to a majority of the cluster. When there is a partition that prevents the cluster from reaching a majority vote, messages cannot be added to the log.
With an AP system, nodes continue to accept transactions even when they cannot communicate with other nodes to guarantee consistency. When a partition occurs, for example splitting the cluster in halves, the state of the system on each side of the partition may diverge, losing consistency. You might eventually reach consistency if you have a way to reconcile the divergent state when the partition heals (see: CRDTs), but during the partition, it's possible that the overall state of the system will not be consistent across all nodes.
Here's a thought experiment to think about how the distributed ledger system works under a network partition. Imagine you run a bitcoin mining rig at home. You use it as part of the global distributed system of bitcoin miners. Your roommates are all bitcoin users, and you use bitcoins to settle payments between yourselves for various purposes. So one day, your home loses internet connectivity. Your bitcoin rig still works on your local LAN. Your roommate submits a payment to you, which your rig goes to work on, finding an acceptable nonce to prove out the block for the transaction. After several hours, you see that your rig has actually processed several other blocks following the original payment, but you are still cut off from the rest of the network... Now ask, are you satisfied that the payment made to you is permanently logged in the bitcoin ledger? What if your roommate had submitted other transactions to other nodes which were still connected to each other, perhaps via his cell phone or the coffee-shop wifi down the street? What is going to happen when your internet service comes back, and your mining rig can communicate with the rest of the system again? Odds are that the rest of the system has processed more blocks than yours in that time, that your rig has a short branch, which will be discarded by the system as a whole. Since the system was not in a consistent state during the partition, it looks like bitcoin is a CP system overall.
This is not to say that bitcoin is uninteresting! Lots of CP systems are built on the idea of cooperating nodes, which use the principle of majority voting or confirmation to provide consistency. Bitcoin is fascinating because it achieves consistency without requiring majority voting, while providing resilience to many kinds of attack by un-cooperative nodes.