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 15:27:51 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=4&rev2=5

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

  = 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 inconsistent state. In this particular
example, the state change B represents depends upon A, but A was not committed. 
+ 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.
+ 
+ Note that we concentrate on instances 27, 28, and 29, for the sake of illustration. We have
omitted common optimizations like sending one 1a message for all instances or summarizing
1b messages.   
  
  '''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 both acceptors 1 and 2 to accept
A and B, and only acceptor 1 has accepted A and B.
+ '''Figure 1''': Proposer 1 finishes phase 1, and it has two values to propose: A and B.
It proposes A and B for instances 27 and 28, respectively. Proposer 1, however, fails before
it can get both acceptors 1 and 2 to accept A and B, and only acceptor 1 accepts 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. 
+ '''Figure 2''': Proposer 2 finishes phase 1, and it has one value to propose: C. It proposes
C for instance 27. 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. 
+ '''Figure 3''': Proposer 3 finishes phase 1, and it has one value to propose: D. Given the
values in messages 1b, it 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}}
  

Mime
View raw message