# 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

## Consistency

• 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

## Availability

• 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

• proof by contradiction. Assume a system can be CAP

• begin by partitioning our system.

• with a partition, the data is inconsistent