Note that C,A, and P mean very specific things in this context.

  • C: linearizability among all servers’ requests, as if exeuting on a single node. If B starts after A, then B can’t see the state before A
    • This definition is different from the C in ACID
    • Snapshot and MVCC are by design non-linearizable
  • A: every request to ANY NON-FAILED node must return a response if it is successful or failure
    • Node failure is outside the scope of CAP!
    • Returning failure still gives A
  • P: network is allowed to lose any messages from one node to another.
    • Note this does not mean packet loss - in the proof they use a TCP-ish protocol already. However, from a node’s perspective you can not distinguish between a failed node and partitioned node
    • Retrying communication indefinitely is in essence choosing C over A.
  • Trivial CP system: ignore all requests, return “no result” => Not being available at all is enough to be CP
  • Trivial AP system: return v0 to all requests
  • It is possible for a system to be none of CP, AP, or CA! Most systems don’t need atomic consistency or perfect availability during P anyway.

PACELC

Network partitions(P) are too likely to happen, so CA is useless in practice, but else(E), even when P is not happening, the system should ideally have the perfect CA, i.e., the trade-off between C and latency(L).

If a system chooses to provide C over A in the presence of P, it can:

  • refuse to respond to some requests, e.g., don’t write in two phase commit
  • shutdown entirely
  • Only r/w if the data’s master node is inside the partitioned component

Case studies

  • Paxos
    • AP? no when the link to the leader is cut. Note AP protocols in general need conflict resolution
    • CA? because it is async model, so liveness can not be guaranteed
  • 2PC
    • CP? not consistent
    • AP? not available, because we can not do any multi-node action
    • Not even CA in this sense
      • What if master failed? the view is not consistent!
      • When master failed and prepared, all slaves are locked
      • A common CA solution is the full strict quorum control
  • Master-slave replication
    • Not A - when client is partitioned from the leader, but not follower
  • Cassandra
    • Not A - when client is partitioned from the leader, but not follower during quorum read