Date Added: May 2011
The authors examine the limits of consistency in fault-tolerant distributed storage systems. In particular, they identify fundamental tradeoffs among properties of consistency, availability, and convergence, and the authors close the gap between what is known to be impossible (i.e. CAP) and known systems that are highly-available but that provide weaker consistency such as causal. Specifically, in the asynchronous model with omission-failures and unreliable networks, the authors show the following tight bound: no consistency stronger than Real Time Causal Consistency (RTC) can be provided in an always-available, one-way convergent system and RTC can be provided in an always-available, one-way convergent system.