PACELC theorem

In theoretical computer science, the PACELC theorem is an extension to the CAP theorem. It states that in case of network partitioning (P) in a distributed computer system, one has to choose between availability (A) and consistency (C) (as per the CAP theorem), 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).

Overview

PACELC builds on the CAP theorem. Both theorems describe how distributed databases have limitations and tradeoffs regarding consistency, availability, and partition tolerance. PACELC however goes further and states that a trade-off also exists, this time between latency and consistency, even in absence of partitions, thus providing a more complete portray of the potential consistency tradeoffs for distributed systems.

A high availability requirement implies that the system must replicate data. As soon as a distributed system replicates data, a tradeoff between consistency and latency arises.

The PACELC theorem was first described by Daniel J. Abadi from Yale University in 2010 in a blog post, which he later formalised in a paper in 2012. The purpose of PACELC is to address his thesis that "Ignoring the consistency/latency tradeoff 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."

Database PACELC ratings

Database PACELC ratings are from

• The default versions of Dynamo, Cassandra, and Riak are PA/EL systems: if a partition occurs, they give up consistency for availability, and under normal operation they give up consistency for lower latency.
• Fully ACID systems such as VoltDB/H-Store and Megastore are PC/EC: they refuse to give up consistency, and will pay the availability and latency costs to achieve it. BigTable and related systems such as HBase are also PC/EC.
• MongoDB can be classified as a PA/EC system. In the baseline case, the system guarantees reads and writes to be consistent.
• PNUTS is a PC/EL system.

DDBS	P+A	P+C	E+L	E+C
Dynamo	Yes		Yes
Cassandra	Yes		Yes
Riak	Yes		Yes
VoltDB/H-Store		Yes		Yes
Megastore		Yes		Yes
MongoDB	Yes			Yes
PNUTS		Yes	Yes

See also

• CAP theorem
• Consistency model
• Fallacies of Distributed Computing
• Paxos (computer science)
• Project management triangle
• Raft (computer science)
• Trilemma

External links

• "Consistency Tradeoffs in Modern Distributed Database System Design", by Daniel J. Abadi, Yale University Original paper that formalized PACELC
• "Problems with CAP, and Yahoo’s little known NoSQL system", by Daniel J. Abadi, Yale University. Original blog post that first described PACELC