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=1&rev2=2 -------------------------------------------------- = 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}} +
