hadoop-common-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Hadoop Wiki] Update of "ZooKeeper/PaxosRun" by FlavioJunqueira
Date Tue, 15 Dec 2009 18:34:45 GMT
Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Hadoop Wiki" for change notification.

The "ZooKeeper/PaxosRun" page has been changed by FlavioJunqueira.
http://wiki.apache.org/hadoop/ZooKeeper/PaxosRun?action=diff&rev1=7&rev2=8

--------------------------------------------------

  = Example: Paxos run =
  
- In this page, we show an example of a Paxos run that violates the primary order of messages.
The basic idea is that if we have three proposers over time and three acceptors, we can have
a situation in which a proposer proposes A and B, but only B is committed. For ZooKeeper,
operations are state changes, and such cases can lead to an inconsistent state. In this particular
example, the state change B depends upon A, but A was not committed.
+ ZooKeeper uses a protocol that we call Zab (ZooKeeper Atomic Broadcast). Even though Zab
follows the abstract description of Paxos by Butler Lampson, it does not match the description
of the Classic Paxos protocol by Lamport. In fact, in this page we show an example of a Paxos
run that violates the primary order of messages, which is a property that Zab satisfies. The
basic idea is that if we have three proposers over time and three acceptors, we can have a
situation in which a proposer proposes A and B, but only B is committed. For ZooKeeper, operations
are state changes, and such cases can lead to an inconsistent state. In this particular example,
the state change B depends upon A, but A was not committed.
  
  Note that we concentrate on instances 27, 28, and 29, for the sake of illustration. For
simplicity of presentation, we assume in each figure that the single proposer is the leader
for the corresponding part of the execution. We omit common optimizations like sending one
1a message for all instances or summarizing 1b messages. We also only show the values accepted
along with their ballots as part of the state of an acceptor.   
  

Mime
View raw message