Mailing-List: contact common-commits-help@hadoop.apache.org; run by ezmlm
Precedence: bulk
Reply-To: common-dev@hadoop.apache.org
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
From: Apache Wiki <wikidiffs@apache.org>
To: Apache Wiki <wikidiffs@apache.org>
Date: Sat, 05 Dec 2009 14:14:36 -0000
Message-ID: <20091205141436.3880.76849@eos.apache.org>
Subject: 
 =?utf-8?q?=5BHadoop_Wiki=5D_Update_of_=22ZooKeeper/PaxosRun=22_by_FlavioJ?=
 =?utf-8?q?unqueira?=

Dear Wiki user,

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

The "ZooKeeper/PaxosRun" page has been changed by FlavioJunqueira.
http://wiki.apache.org/hadoop/ZooKeeper/PaxosRun?action=3Ddiff&rev1=3D1&rev=
2=3D2

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

  =3D Example of Paxos run =3D
  =

- In this page, we show an example of a Paxos run that violates our expecte=
d 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 propo=
ses A and B, but only B is committed. For ZooKeeper, operations are state c=
hanges, and such cases can lead to inconsistent state. In this particular e=
xample, the state change B represents depends upon A, but A was not committ=
ed. =

  =

+ '''Notation''': For the following figures, we use '''''bold italics''''' =
to represent the state of an acceptor, and regular font to represent messag=
es.
+ =

+ '''Figure 1''': Proposer 1 finishes phase 1, and proposes A and B for ins=
tances 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 consequ=
ently 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 acc=
ept C, B, and D. These three values are anchored for instances 1, 2, and 3,=
 respectively. =

+ =

+ {{attachment:proposer-3.png}}
+=20