An Illustrated Proof of the CAP Theorem
The CAP Theorem is a fundamental theorem in distributed systems that states any distributed system can have at most two of the following three properties.
This guide will summarize Gilbert and Lynch's specification and proof of the CAP Theorem with pictures!
The CAP theorem states that a distributed system cannot simultaneously be consistent, available, and partition tolerant. Sounds simple enough, but what does it mean to be consistent? available? partition tolerant? Heck, what exactly do you even mean by a distributed system?
In this section, we'll introduce a simple distributed system and explain what it means for that system to be available, consistent, and partition tolerant. For a formal description of the system and the three properties, please refer to Gilbert and Lynch's paper.
Let's consider a very simple distributed system. Our system is composed of two servers, $G_1$ and $G_2$. Both of these servers are keeping track of the same variable, $v$, whose value is initially $v_0$. $G_1$ and $G_2$ can communicate with each other and can also communicate with external clients. Here's what our system looks like.
