CAP vs. PACELC Theorem in Distributed Systems
Understand how the CAP and PACELC theorems help system designers navigate trade-offs in distributed systems. Learn to balance consistency, availability, latency, and fault tolerance to build more reliable and scalable architectures.
When designing systems that span multiple servers or data centers, how do we ensure they remain reliable and performant?
This question is fundamental to System Design. Building these systems means constantly managing trade-offs. We need to manage communication across multiple nodes, handle inevitable network failures, and maintain data consistency, all while delivering a fast and seamless user experience.
Frameworks like the CAP and PACELC theorems provide a mental model for navigating these complexities.
They do not give us the answers, but they help us ask the right questions about the trade-offs we must make. We’ll discuss both of these frameworks in detail in this lesson. Let’s start by understanding the inherent trade-offs in distributed systems.
Balancing trade-offs in distributed systems
Building distributed systems involves orchestrating multiple computers to work together as a cohesive unit.
This approach is essential for achieving scalability and high availability, but it introduces significant challenges. Servers can crash, and network links between them can fail, creating communication breakdowns known as partitions.
In these moments of uncertainty, a system must make difficult choices to maintain its integrity.
Achieving a perfect balance between reliability, performance, and data correctness is impossible. Every architectural decision involves a trade-off. Do we prioritize making the system always available, even if it means some users might see slightly stale data?
Or do we enforce strict data consistency, even if it slows down the system or makes it temporarily unavailable during a network issue?
Theoretical frameworks are valuable for this reason. They provide a language and structure for discussing system behavior under different conditions. For anyone starting in System Design, understanding these concepts is a critical step toward making informed architectural decisions that align with business goals and user expectations.
Visualizing a typical distributed system helps to understand the inherent tensions:
This visualization sets the stage for our first framework, the CAP theorem, which formalizes the trade-offs a system must make when those network links break.
Introduction to CAP theorem
The CAP theorem, first proposed by computer scientist Eric Brewer, is a fundamental principle in distributed System Design. The CAP Theorem states that in the event of a network partition, a distributed system can provide either consistency or availability, but not both simultaneously:
Consistency (C): This ensures all nodes return the same, most recent data. When a client writes a new piece of data and gets a successful acknowledgment, any subsequent read request from any other client will see that new data. For example, in a banking application where we transfer money, consistency (strong) ensures that once the transfer is confirmed, anyone viewing our balance, from any device, sees the updated amount instantly.
Availability (A): Every request receives a (non-error) response, without the guarantee that it contains the most recent write. An available system remains operational and responsive even if some of its nodes fail. For example, on an e-commerce platform, this means users can browse products and add items to their cart, even if the inventory count displayed is slightly outdated.
Educative byte: The CAP theorem is also known as Brewer’s theorem, as it was first presented as a conjecture in 2000. It was later formally proven by
The theorem’s crucial insight is that a network partition forces a choice. If the network splits, preventing two nodes from communicating, do we prioritize consistency or availability?
Choose consistency over availability (CP): To remain consistent, the system must refuse responses from partitions that cannot guarantee they have the most up-to-date information. This effectively makes that part of the system unavailable until the partition heals.
Choose availability over consistency (AP): To remain available, both sides of the partition continue to accept reads and writes. However, this means their data will diverge, leading to inconsistency until the partition is resolved and the data can be reconciled.
The CAP theorem illustrates a fundamental trade-off. We simply cannot build a system that is simultaneously consistent, available, and partition-tolerant, as illustrated below:
This model is powerful. Its main limitation is that it only describes what happens during a failure. The model does not address system behavior during normal operation.
Let’s look at a simple proof of the CAP theorem.
(From answer)
CAP theorem proof
Imagine a distributed system consisting of two nodes:
The distributed system acts as a replicated register, storing the value of variable x, which is initially set to 10. A network partition occurs, splitting Node A and Node B so they cannot communicate. A client successfully writes a new value of 15 to Node A and then immediately sends a read request to Node B.
Let’s examine what happens when different nodes process each request. During the partition, the system faces an impossible choice:
Option 1 (Sacrifice consistency): Node B can respond to the read request with its local value 10, maintaining availability but returning stale data. This violates consistency because the most recent write was 15, not 10.
Option 2 (Sacrifice availability): Node B can refuse to respond (or return an error) until it can confirm the latest value from Node A, maintaining consistency but violating availability since the request doesn’t receive a successful response.
The system cannot satisfy both requirements simultaneously during the partition. Node B cannot learn about the write operation on Node A because the network partition prevents any communication between them. This demonstrates that in the presence of a network partition, a distributed system must choose between consistency and availability; it cannot guarantee both.
While this proof demonstrates the CAP theorem’s fundamental constraint, its simplicity has led to widespread misconceptions about how it applies in practice.
Common misinterpretations of the CAP theorem
The simplicity of the CAP theorem is both its greatest strength and a source of significant confusion. Many engineers oversimplify it, leading to flawed design logic. Let’s clarify some of the most common myths.
Myth 1: We must pick two out of three. This is the most prevalent misunderstanding. Since partition tolerance is given in any distributed system, the choice is not among all three. The real decision is what to do when a partition occurs: do we favor consistency (CP) or availability (AP)? During normal operation, when there is no partition, systems can and do provide all three.
Myth 2: The choice is a one-time, static decision for the entire system. Real-world systems are far more nuanced. The trade-off can be made on a per-operation basis. For example, a write operation for a user’s password might require strong consistency, while loading their profile description might be an availability-first operation. Systems can be designed to dynamically shift their behavior.
Educative byte: A database like MongoDB allows developers to configure the desired level of consistency for each operation. We can specify whether a write must be acknowledged by a majority of replicas (prioritizing consistency) or just one (prioritizing speed and availability).
Myth 3: The theorem implies a binary choice. The trade-off is not an all-or-nothing decision. There is a spectrum between strong consistency and eventual consistency. Many systems operate in a middle ground, offering weaker consistency models that provide better performance and availability than strongly consistent systems. For example, a social media feed is eventually consistent; a new post will eventually appear for all followers, but not necessarily instantaneously.
The CAP theorem serves as a guide, not a rigid law that categorizes systems into two distinct boxes.
It provides a clear framework for decision-making during network partitions. However, these partitions are relatively rare events for most well-designed systems. The vast majority of the time, the system operates under normal conditions, with all nodes communicating successfully.
CAP is silent on the trade-offs that exist during these periods.
This is a significant omission because real-world performance is often defined by normal operating state behavior. Factors such as latency, or the speed at which a user receives a response, are critical to user experience but are not part of the CAP theorem.
For example, if we choose strong consistency, does that mean our system will be slower even when there are no network issues? The PACELC theorem addresses this gap.
PACELC theorem in distributed systems
The PACELC theorem, proposed by Daniel Abadi in 2012, extends the CAP theorem to provide a more complete picture of the trade-offs in distributed systems.
It offers a more nuanced framework by considering system behavior in both partitioned and normal states. PACELC acknowledges that a trade-off between consistency and latency is always present, even in the absence of network failures. The theorem’s logic can be broken down to see how it works in practice:
If partition (P): If a partition (P) occurs, the system must choose between availability (A) and consistency (C). This is the original CAP theorem trade-off. A network failure forces a hard choice between staying online with potentially stale data or going offline to preserve data integrity.
Else (E): In the absence of a partition, when the system is running normally, it must choose between latency (L) and consistency (C).
This Else part is the key extension. It recognizes that even without network failures, there is an inherent tension between the speed of an operation and the level of data consistency it guarantees.
Educative byte: Think of sending a critical message to a group of friends. We have two options. We can send it via a group text, which is fast (low latency), but we can’t be 100 percent sure everyone received it at the exact same moment (weaker consistency). Alternatively, we can call each person individually to confirm they received the message. This guarantees that everyone has the information (strong consistency), but it takes much longer (higher latency).
This trade-off is central to the architecture of many databases. The following flowchart can help visualize the decision-making process described by the PACELC theorem:
Understanding both CAP and PACELC helps predict how a system will behave. This includes behavior during both crises and normal, everyday operations.
CAP and PACELC theory vs. practice
While CAP and PACELC are related, they answer different questions about a system’s design.
The CAP theorem is fundamentally about how a system responds to failure, forcing a choice between staying available or staying consistent during a network partition. In contrast, the PACELC theorem offers a more comprehensive view, encompassing all operational states and highlighting the persistent trade-off between latency and consistency.
Knowing both theorems allows us to more accurately predict a system’s real-world behavior. For example, the following well-known systems illustrate this point:
Amazon DynamoDB prioritizes availability and low latency. It is classified as a PA/EL system. It chooses Availability during a Partition and Latency during normal operation (Else). It achieves this by replicating data asynchronously, which often provides
eventual consistency A consistency model where, if no new updates are made to a given data item, all accesses to that item will eventually return the last updated value. Google Spanner, a globally distributed database, prioritizes strong consistency. It is a PC/EC system. It chooses Consistency during a Partition and Consistency during normal operation (Else). To achieve this, it uses atomic clocks and a protocol called Two-Phase Commit to ensure that all transactions are globally consistent. The trade-off is potentially higher latency for write operations.
ScyllaDB, a high-performance NoSQL database, also navigates these trade-offs, often being compared to systems like Cassandra and DynamoDB.
Azure Cosmos DB is unique because it doesn’t force a single choice. Instead, it offers developers five different, well-defined consistency levels. This allows architects to tune the trade-off between consistency, availability, and latency to precisely match their application’s requirements, effectively letting them choose their own spot on the PACELC spectrum.
These are more than theoretical labels.
They reflect fundamental architectural decisions that impact how a system is built, deployed, and operated. The choice between consistency, availability, and latency must be a conscious one, driven by the specific needs of our application.
These frameworks ultimately guide us toward building systems that are fit for their purpose, balancing technical constraints with business needs.
Test Your Knowledge!
For a real-time chat system, which theorem—CAP or PACELC—better reflects its design trade-offs, and how does the system manage both low latency and message consistency across regions?
If you’re not sure how to do this, click the “Want to know the correct answer?” button.
Conclusion
The CAP and PACELC theorems are essential frameworks for reasoning about the inherent trade-offs in distributed systems.
The choices we make depend entirely on our business priorities. A system processing financial transactions will have vastly different requirements than one serving social media content. As a system designer, our goal is to use these theorems as a guide to ask the right questions.
We should ask how a system behaves during partitions and during normal operation. This is more useful than asking if a system is simply CAP-compliant. In the next lesson, we’ll see how these trade-offs manifest through different types of failures in System Design.