Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services

I already am. told The CAP Theorem by Eric Brewer. Today I'm going to talk about whitepaper 2002 Seth Gilbert and Nancy Lynch, in which the hypothesis became a theorem. The hypothesis itself for proof sounds like this.

It is impossible for a web service to provide the following three guarantees: consistency, availability, partition-tolerance All these properties are desirable in real systems. But in order to prove this statement, it is necessary to first formalize all three properties.

1. Start with consistencywhere the authors go sideways atomic data objects linearized consistency (linearizable consistency)

Under this consistency guarantee, there must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time. Such cosistance guarantees are easier for users to perceive and it is easier for such a model to design a client application that will interact with such a distributed system.

2. The second characteristic is availabilitywhere, for continuous availability, each request that falls on a non-failing node of the system must receive its response. Thus, any algorithm for generating a service response must eventually end. (eventually terminate). Interestingly, this is a weak definition of availability, since there is no upper limit on response time – this allows for unbounded computation. But when viewed from a position of separation resistance, it can be seen as a strong definition of accessibility - even if network failures occur, every request must be completed.

3. To simulate partition-tolerance, the authors suggest that an arbitrary number of messages that are sent from one node to another can be lost in the network. So we can model any pattern of loss.

When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost. (And any pattern of message loss can be modeled as a temporary partition separating the communicating nodes at the exact instant the message is lost.)

The authors then proceed to the evidence. n

1. Let’s start with asynchronous systems first.

Theorem 1 It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: • Availability • Atomic consistency in all fair executions (including those in which messages are lost). This theorem is proved on the fingers by the opposite method. Imagine that such an algorithm exists. Next, imagine a system of two nodes G1 and G2. We have lost all communication between G1 and G2. Then you write in G1 and then read in G2. As a result, reading from G2 will not return the value that was written in G1. There is more formal evidence in the article itself.

2. In the real world, we do not use fully asynchronous systems, but partially synchronous ones. In them, nodes have their own clock, which allows you to measure time and use timeouts. But even in a more powerful setup, we get a similar result.

Theorem 2 It is impossible in the partially synchronous network model to implement a read/write data object that guarantees the following properties: • Availability • Atomic consistency in all executions (even those in which messages are lost). The proof here is similar to the previous one, like two drops of water:)

The rest of the white paper is devoted to Delayed-t consistency in partially synchronous systems, which we will not talk about here.

In the next post, let’s talk about the PACELC theorem.

#Software #Architecture #DistributedSystems #SystemDesign