INDBS Noter

Tags:conceptdatabasecapcaptheoremdistributedsystems Status:🟩

CAP Theorem

Summary

The CAP Theorem states that in a distributed system, only two out of three guarantees—Consistency, Availability, and Partition Tolerance—can be provided at any time. During a network partition, the system must choose between consistency and availability. The PACELC Theorem extends this idea, adding that in normal operations (without partitions), a system must choose between Latency and Consistency. Together, these theorems highlight the trade-offs distributed systems must manage to balance speed, reliability, and data consistency.

Details

The CAP Theorem states that a distributed system can provide only two out of three guarantees at any given time: consistency, availability, and partition tolerance. In the face of a network partition, a system must choose between maintaining consistency or availability. It cannot achieve all three simultaneously. In the real world you find a balance between consistency and availability, and its not directly one over the other. A network partition occurs when communication is lost between nodes in a distributed system, causing them to operate independently.

  • C = Consistency

    • Every read operation returns the most recent write, meaning all nodes in the system have the same data at any point in time.

  • A = Availability

    • The system guarantees that a valid response is returned for every request, even if some nodes are unavailable (i.e., it doesn’t fail completely).

  • P = Partition Tolerance

    • The system continues to function, even in the presence of network partitions (i.e., when communication between nodes is lost).

Pacelc formulation

The PACELC theorem is an extension of the CAP theorem that addresses trade-offs in distributed systems beyond just partition tolerance:

  • P: In a partitioned network (when there’s a network failure), a system must choose between Availability and Consistency (like the CAP theorem).
  • E: In normal (non-partitioned) operation, the system must choose between Latency (how quickly responses are returned) and Consistency (ensuring all nodes are in sync).

Graph View

Backlinks