Skip to main content

A paper a day keeps the doctor away: Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

Sixteen year ago, Eric Brewer introduced what is now known as the CAP theorem, which states that for a web service it is impossible to guarantee consistency, availability, and partition tolerance.  The conjecture was based on Brewer's experiences at Inktomi--a search engine company he cofounded, and was published without proof.  Gilbert and Lynch presented one in their paper: "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services."

The paper is a good theoretical read, and the proofs the authors present are very tractable. They first begin by  formalizing the concepts of consistency (the authors use atomic in the paper), availability, and partition tolerance. For a consistent service, there is a total order on all operations such that each operation looks as if it were completed at a single instant. For availability, every request received by a non-failing node in the system must result in a response. Finally for partition tolerance the network is  allowed to lose arbitrarily many messages sent from one node to another.

The authors use these definitions to present their first impossibility result:

"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). "

They prove the assertion by contradiction. The proof uses  two nodes/partitions in the system $A$ and $B$, where all the messages between $A$ and $B$ are lost. The proof assumes two operations $\alpha$ and $\beta$ that execute separately on $A$ and $B$, and are ordered such that $\beta$ occurs after $\alpha$ has ended.  $\alpha$ executes a write on partition $A$, $\beta$ executes a read from partition $B$ with all messages between $A$ and $B$ lost. Each operation on its own returns consistent results, while combined together as a new operation $\alpha+\beta$, return inconsistent data, proving the theorem.

The authors extend the result through a similar method of argument to all types of executions, since nodes $A$ and $B$ can't tell if the messages between them are lost in an asynchronous network (without the concept of clocks or time). The authors provide some example systems for asynchronous networks that provide two of the three guarantees (C,A, and P).

For partially synchronous systems, where every node has a clock, and all clocks increase at the same rate, but are not synchronized, the authors present another impossibility result:

"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 is similar to the original impossibility result, with execution $\beta$ sufficiently delayed for the messages not to reach partition $B$.

The authors close by providing a weaker consistency condition that allows stale data to be returned when there are partitions through the use of a centralized node, and the formal requirements it places on the quality of the stale data returned .



Comments

Popular posts from this blog

Kindle Paperwhite

I have always been allergic to buying specialized electronic devices that do only one thing, such as the Kindle, the iPod, and fitness trackers. Why buy these when technology evolves so fast that a multi-purpose device such as the phone or a smart watch can eventually do the same thing, but with the convenience of updates that fix bugs and add functionality? So, I was shocked when this weekend I made an impulse buy and got the newest Kindle Paperwhite—a special purpose device for reading eBooks. I was walking past the Amazon store in the mall and saw that the newest Kindle Paperwhites were marked down by $40 for the holidays. The device looked good in the display, so I went in to look at it closely. The Paperwhite is small and light, with a 6” screen that is backlit and waterproof.   The text was crisp and readable, and in the ambient light, it felt like I am reading a printed book. I was sold and bought it on the spot. At home I have struggled to put it down. The bo...

A paper a day keeps the dr away: Dapper a Large-Scale Distributed Systems Tracing Infrastructure

Modern Internet scale applications are a challenge to monitor and diagnose. The applications are usually comprised of complex distributed systems that are built by multiple teams, sometimes using different languages and technologies. When one component fails or misbehaves, it becomes a nightmare to figure out what went wrong and where. Monitoring and tracing systems aim to make that problem a bit more tractable, and Dapper, a system by Google for large scale distributed systems tracing is one such system. The paper starts by setting the context for Dapper through the use of a real service: "universal search". In universal search, the user types in a query that gets federated to multiple search backends such as web search, image search, local search, video search, news search, as well as advertising systems to display ads. The results are then combined and presented back to the user. Thousands of machines could be involved in returning that result, and any poor p...

A paper a day keeps the doctor away: MillWheel: Fault-Tolerant Stream Processing at Internet Scale

The recent data explosion, and the increase in appetite for fast results spurred a lot of interest in low-latency data processing systems. One such system is MillWheel, presented in the paper " MillWheel: Fault-Tolerant Stream Processing at Internet Scale ", which is widely used at Google. In MillWheel, the users specify a directed computation graph that describe what they would like to do, and write application code that runs on each individual node in the graph. The system takes care of managing the flow of data within the graph, persisting the state of the computation, and handling any failures that occur, relieving the users from that burden. MillWheel exposes an API for record processing, that handles each record in an idempotent fashion, with an exactly once delivery semantics. The system checkpoints progress with a fine granularity, removing the need to buffer data between external senders. The authors describe the system using the Zeitgeist produ...