CAP

Basic Concept

• CAP theorem states that, it is impossible to build an implementation of read-write storage in an asynchronous network that satisfies all three factors of consistency, availability and partition tolerance at the same point in time, in case of a distributed system

  • Consistency - every read gets most recent write or an error… the question we ask here is will all executions of reads and writes seen by all nodes be atomic or linearizably consistent

    • Atomic or linearzable consistency

      • B:set(5), A:set(10), A:get() = 10, B:get() = 10
      • Atomic consistency ensures that external communication about the value of a register is respected. That is, if I read X and tell you about it, you can go to the register and read X for yourself. Therefore following situation depicts a case where though by the serial history shows as if the atomic consistency is assured, in reality it is not
        • What is not
          • B:set(5), B:get() = 5, A:set(10), A:get() = 10

  • Availability - every request receives a response, without the guarantee of it being the latest… the question we ask here is will a request made to the data store always eventually complete?

  • Partition Tolerance - the system continues to operate despite of network partitions (caused out of network failures)

  • Note

    • A read write storage is a register which supports following 2 operations
      • set(X) sets the value of the register to X
      • get() returns the last value set in the register
    • An asynchronous network is which has no bound on how long a message will take time to get delivered to the destination
    • Availability - a data store is called available if ALL requests return a response and not an error message
    • Partition - a partition is when a network fails to deliver messages to one or more nodes by completely loosing them

• In real world scenario, because network fails all the time, it is impossible to a distributed system which guarantees C & A

• CP - in a consistent and partition tolerant system, requests may get responses or an error (because of the partition effect)

• AP - in an available and partition tolerant system, requests may get stale data and writes may require some time to get across all nodes (and the nodes are said to become eventually consistent)

• History

  • Dr. Eric Brewer gave a keynote speech at the Principles of Distributed Computing conference in 2000 called ‘Towards Robust Distributed Systems’. In it he posed his ‘CAP Theorem’ - at the time unproven - which illustrated the tensions between being correct and being always available in distributed systems.
  • Two years later, Seth Gilbert and Professor Nancy Lynch - researchers in distributed systems at MIT - formalised and proved the conjecture in their paper “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services”

References

• Basic introduction
• CAP in plain english
• CAP FAQ