The CAP theorem (also known as Brewer’s theorem) is one of the key concepts in distributed systems. It was proposed by Eric Brewer in 2000 and formally proven in 2002 by Seth Gilbert and Nancy Lynch. The theorem describes the limitations inherent to the design of distributed systems, especially regarding three essential properties: Consistency (C), Availability (A) and Partition Tolerance (P).
According to the theorem, in a distributed system it is impossible to guarantee the following three properties simultaneously:
Consistency: All nodes in the system hold the same data at the same time. In other words, after a write operation, every subsequent read returns the most recent value.
Availability: The system is always available to respond to requests, even if some nodes are down or failing.
Partition Tolerance: The system keeps operating even when communication failures or network partitions prevent some nodes from exchanging information.
According to the theorem, a distributed system can satisfy at most two of these properties at once, but never all three (at the same time).
What does each property of the theorem represent?
- Consistency
Consistency guarantees that every node in the system has a uniform view of the data. For example, in a distributed database, if one client updates a record, every other client must see that update immediately.
- Availability
Availability ensures the system responds to every request, even if some nodes are unavailable. This means the system must be resilient to failures and always provide a valid response.
- Partition Tolerance
Partition tolerance is the system’s ability to keep working correctly even when communication between some nodes is interrupted. In distributed systems, network partitions are inevitable, especially in large, complex networks.
Possible choices
- Consistency + Availability (CA): The system is consistent and available, but does not tolerate partitions. This is only feasible on reliable networks, where partitions are extremely rare.
- Consistency + Partition Tolerance (CP): The system is consistent and tolerates partitions, but may sacrifice availability. This means that, during a partition, some requests may go unanswered.
- Availability + Partition Tolerance (AP): The system is available and tolerates partitions, but may sacrifice consistency. This is common in systems that prioritize user experience, such as social networks and distributed caches.
Applications of the CAP theorem
CA systems: Centralized databases or systems on reliable local networks.
CP systems: Distributed databases such as HBase and MongoDB in strong consistency mode.
AP systems: Systems such as Cassandra and DynamoDB, which prioritize high availability and fault tolerance.
The CAP theorem is an essential tool for understanding the trade-offs in distributed system design. It reminds us that there is no perfect solution and that the choices depend on the specific needs of each application. By understanding the theorem’s implications, software engineers can make better-informed decisions when designing scalable, resilient and efficient systems.