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 Sat, 05 Dec 2009 14:14:36 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.


  = Example of Paxos run =
- In this page, we show an example of a Paxos run that violates our expected order of messages.
+ 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 inconsistent state. In this particular
example, the state change B represents depends upon A, but A was not committed. 
+ '''Notation''': For the following figures, we use '''''bold italics''''' to represent the
state of an acceptor, and regular font to represent messages.
+ '''Figure 1''': Proposer 1 finishes phase 1, and proposes A and B for instances 1 and 2,
respectively. Proposer 1, however, fails before it can get acceptors 1 and 2 to accept A and
B, so only acceptor 1 has accepted A and B.
+ {{attachment:proposer-1.png}}
+ '''Figure 2''': Proposer 2 finishes phase 1, and proposes C for instance 1. Proposer 2 makes
acceptors 2 and 3 accept C and crashes. Value C consequently is anchored (using the terminology
of Lampson) for instance 1. 
+ {{attachment:proposer-2.png}}
+ '''Figure 3''': Proposer 3 finishes phase 1, and proposes C, B, and D for instances 1, 2,
and 3 respectively. Proposer 3 makes acceptors 1 and 3 accept C, B, and D. These three values
are anchored for instances 1, 2, and 3, respectively. 
+ {{attachment:proposer-3.png}}

View raw message