Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

This paper introduces the conjecture made by Eric Brewer, which says "it would be impossible to achieve consistency, availability, and partition tolerance at the same time". The statement is quite sad because all the three properties are highly desired in distributed systems. The paper first defines each property, and I liked the section since those properties tend to be used somewhat differently depending on areas and contexts. Then the authors formally prove the conjecture on Asynchronous Networks (without clock) and Partially Synchronous Networks (with a clock for each node yet not globally synchronized) models.

Even though it is impossible to achieve the three properties for both models, this paper does not fall into theoretical nihilism. First, the authors show that it is fairly easy to achieve any two properties out of the three. Furthermore, the paper defines a weaker property, Delayed-t Consistency, and proves that it is possible to achieve availability and partition tolerance with the delayed-t consistency. The concept of delayed-t consistency is somewhat similar to "eventual consistency", but it is more formal in a sense that delayed-t consistency provides an explicit time bound.

I think that this paper gives very important implication for distributed system design: i) Availability and partition-tolerance are the things you should not give up easily. So what you can do is to have relatively weak consistency, and actually this is pretty much prevalent in many scalable distributed systems (and many services based on them). ii) It is impossible to design a completely scalable and consistent database on distributes systems. iii) Not all distributed services can go with weak consistency, and iv) weak consistency in any forms would add semantic complexity to the system.