basic question about the Paxos protocol

[Jan Hidders]

Most descriptions of the Paxos protocol I've seen say that the preparation message only contains the proposal number, and not already a proposed value. This puzzles me a little, since I think the following scenario then can happen:

Assume two proposers P1 and P2, and three acceptors A1, A2 and A3.

First, P1 sends prepare(2) to A1 and A2 (a majority) and receives from both a promise(-, -) message.

Then P2 sends a prepare(4) to A2 and A3 (another majority) and receives from both a promise(-,-) message. After all, no proposals have been accepted yet, although a promise has been made by A2.

Then P1 has gotten a positive response form a majority of acceptors, so it can start sending accept-request(2, v1) to A1 and A2, where v1 is the value preferred by P1. Similarly P2 can also send accept-request(4, v2) to A2 and A3.

Then I think the acceptor are doing the following:

A1 : sends accept(v1), since it did not promise to ignore proposals with number 2

A2 : sends accept(v2), but not accept(v1), since it promised to ignore proposals with number 2

A3 : sends accept(v2)

But hat means that both v1 and v2 are accepted! Exactly the thing that should not happen.

I could see how this could be prevented if in the prepare message already a value would have to be proposed, but I see many descriptions of the Paxos protocol, including the one by Lamport himself, that seem to imply that this is not necessary. What am I missing here?

Any help would be appreciated.

-- Jan Hidders

 

[Justin Sheehy]

The "v1" is not accepted by the protocol just because a single acceptor has sent an accept message. It requires a quorum.

So, in your example, only one proposal has been accepted by a quorum of acceptors. There is no problem.

Justin

--
You received this message because you are subscribed to the Google Groups "Distributed Systems" group.
To unsubscribe from this group and stop receiving emails from it, send an email to distsys-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to distsys-discuss@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/distsys-discuss/7e46d808-8999-437c-8ad1-bb103f42690e%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jan Hidders]

Thank you. Somehow it had escaped me that the decision is not final until a learner sees an accept form a majority of acceptors.

-- Jan Hidders

On Tuesday, 20 February 2018 20:17:45 UTC+1, Justin Sheehy wrote:

The "v1" is not accepted by the protocol just because a single acceptor has sent an accept message. It requires a quorum.

So, in your example, only one proposal has been accepted by a quorum of acceptors. There is no problem.

Justin

On Tue, Feb 20, 2018 at 12:04 PM, Jan Hidders <hid...@gmail.com> wrote:

Most descriptions of the Paxos protocol I've seen say that the preparation message only contains the proposal number, and not already a proposed value. This puzzles me a little, since I think the following scenario then can happen:

Assume two proposers P1 and P2, and three acceptors A1, A2 and A3.

First, P1 sends prepare(2) to A1 and A2 (a majority) and receives from both a promise(-, -) message.

Then P2 sends a prepare(4) to A2 and A3 (another majority) and receives from both a promise(-,-) message. After all, no proposals have been accepted yet, although a promise has been made by A2.

Then P1 has gotten a positive response form a majority of acceptors, so it can start sending accept-request(2, v1) to A1 and A2, where v1 is the value preferred by P1. Similarly P2 can also send accept-request(4, v2) to A2 and A3.

Then I think the acceptor are doing the following:

A1 : sends accept(v1), since it did not promise to ignore proposals with number 2

A2 : sends accept(v2), but not accept(v1), since it promised to ignore proposals with number 2

A3 : sends accept(v2)

But hat means that both v1 and v2 are accepted! Exactly the thing that should not happen.

I could see how this could be prevented if in the prepare message already a value would have to be proposed, but I see many descriptions of the Paxos protocol, including the one by Lamport himself, that seem to imply that this is not necessary. What am I missing here?

Any help would be appreciated.

-- Jan Hidders

 

--
You received this message because you are subscribed to the Google Groups "Distributed Systems" group.

To unsubscribe from this group and stop receiving emails from it, send an email to distsys-discu...@googlegroups.com.
To post to this group, send email to distsys...@googlegroups.com.

[Greg Young]

On a side note if you want to research varying behaviours as they run... Download eventstore and setup a 3 node cluster on localhost. The paxos implementation based on http://www.cs.cornell.edu/courses/cs7412/2011sp/paxos.pdf is run over http so you can run fiddler on the node and actually see the message flows easily for various scenarios.

Cheers,

Gre

To unsubscribe from this group and stop receiving emails from it, send an email to distsys-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to distsys-discuss@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/distsys-discuss/bb0b4d10-97e4-421a-94e2-ec0783066aaa%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Studying for the Turing test