Extra 4: CAP Theorem

  • A distributed system coan have at msot two out of the three properties
    • Consistency
    • Availability
    • Partition Tolerance
  • BigTable, MongoDB, and Redis are CP
    • Spanner is CP but highly available
  • Dynamo, Cassandra are AP
  • Amazon Aurora? Physalia in AWS EBS (Looks to be CP but highly available)?

  • servers \(G_1\), \(G_2\) and client with initial value \(v_0\)

  • write to any server. Only \(G_1\) is updated in this case


  • any read operation that begins after a write operation completes must return that value, or the result of a later writer operation

  • we write to \(G_1\) but read from \(G_2\) and get a different result

  • we write to \(G_1\) which replicates to \(G_2\) and sends an acknowledgement which \(G_1\) sends back to ghe client
    • now the client can read from \(G_2\) and get a consistent result


  • every request received by a non-failing node in the system must result in a response
    • server cannot ignore client's requests

Partition Tolerance

  • the network will be allowed to lose arbitarily many messages sent from one node to another


  • proof by contradiction. Assume a system can be CAP

  • begin by partitioning our system.

  • with a partition, the data is inconsistent