- 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)?
![](https://i.imgur.com/gOdsOTh.png)
- servers \(G_1\), \(G_2\) and client with initial value \(v_0\)
![](https://i.imgur.com/VdDnFOe.png)
- write to any server. Only \(G_1\) is updated in this case
![](https://i.imgur.com/D2npy59.png)
- any read operation that begins after a write operation completes must return that value, or the result of a later writer operation
![](https://i.imgur.com/0mRXuDn.png)
- we write to \(G_1\) but read from \(G_2\) and get a different result
![](https://i.imgur.com/URIGrN7.png)
- 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
- the network will be allowed to lose arbitarily many messages sent from one node to another
![](https://i.imgur.com/8EJY8iZ.png)
- proof by contradiction. Assume a system can be CAP
![](https://i.imgur.com/G8V540m.png)
- begin by partitioning our system.
![](https://i.imgur.com/3kcEKeq.png)
![](https://i.imgur.com/0nDJgSk.png)
- with a partition, the data is inconsistent