CAP Theorem in Distributed Systems for Blockchain Development
4 min read
Blockchains are a type of distributed systems. For any distributed system, the Cap Theorem is a fundamental. The CAP Theorem was developed by Eric Brewer where CAP comes in as an abbreviation for Consistency, Availability and Partition Tolerance. How does it work and what's its application in blockchain development? Let's first dive into a blockchain consensus backdrop.
Distributed systems thrive in two components. One is 'nodes' - say computer machines and 'message passing' whose aim is to show that info can be shared between machines. We need distributed systems since a single system is bound to fail due to malware attacks and other faults. We therefore need to protect our data via distributed systems. We also need to bear in mind that a distributed system should work in concurrency but that too cannot always be guaranteed especially with the Nakamoto based consensus.
According to Leslie B. Lamport, an American computer scientist best known for his works in distributed systems, a working distributed system is based on its safety and liveness respectively. Safety for things that will not take place and liveness for things that will take place. You quickly notice that getting closer to safety means moving further away from liveness and the vice versa is true. For a distributed system to come to an agreement, it needs to arrive at a consensus. Thus the term consensus algorithms which thrives on three requirements, validity, agreement and termination.
CAP theory or Brewer's theory as it is known is based on Consistency, Availability and partition Tolerance as previously noted. Consistency means that every read operation will result in getting the latest record. All the information is guaranteed to be up to date. A lack of consistency means that no response is thus given. Consistency can be said to be based on safety as earlier put.
Availability is a property that indicates a distributed system will always be available. One or more nodes of such a system might turn off for a reason or more, however, the system will still be accessible through other nodes. This is then based on liveness.
Partition Tolerance represents the ability of the system to be partitioned. Thus it means that every node can work independently from the other ones. Partition Tolerance tends to lie more on the safety component, though arriving at the safety consensus in Partition Tolerance is a bit complicated.
In a distributed system, the processes can only be based on two of the three CAP theorem properties. These are to be, one of CA, CP or AP at a go. The CAP theorem is faulty too in the sense that it is ambiguous in real world instances. CAP does not cover the delays in response time thus terming it as available while at the same time, partly available nodes are still termed as available.
Therefore, the PACELC theorem came up as a build up of the CAP theorem faults thus making it more applicable in todays distributed systems. PACELC is attributed to the efforts of Daniel Abadi. As he states in his thesis, "Ignoring the consistency/latency trade-off of replicated systems is a major oversight [in CAP], as it is present at all times during system operation, whereas CAP is only relevant in the arguably rare case of a network partition." PACELC works as in the case of network partitioning (P) in a distributed computer system, one needs to choose between availability (A) and consistency (C) (as in CAP), but else (E), even when the system is running normally in the absence of partitions, one has to choose between latency (L) and consistency (C).
Bitcoin is one of the great successes of distributed systems. Even in such a case, the CAP theorem is always violated where Consistency is always given up to favor Availability and Partition Tolerance. To achieve eventual consistency, mining is applied through the famous proof of work (PoW) which means more and more blocks are needed in he chain.
With the explained case scenarios, fails still happen and are described under the Byzantine General's problem. This then leaves us with the dilemma if not a trilemma of whether consensus is fully attainable in blockchain. Byzantine nodes choose to act maliciously, sending corrupted information, despite being fully functional. However, under a set of favorable conditions, consensus algorithms are always arrived at by the nodes.
All this brings us into working with trust without trust, underlying the fundamentals of distributed systems and distributed consensus. Consensus algorithms arrived at via continual mining of Bitcoin, used as an example are then able to bring transactions at a point of trust by the users. But trust without trust!