PaxosLease question

README.md

An e-mail I sent to the authors of the PaxosLease paper back in the day. One of them replied explaining how in their actual implementation of the protocol (http://github.com/scalien/keyspace/tree/master/src/Framework/PaxosLease) they added phase separation/tracking (bool preparing and bool proposing), which would indeed solve the issue with the protocol outlined in the paper as explained in the e-mail.

message.md

From:	Nicolas Trangez <ikke@>
To:	mtrencseni@, agazso@, hreinhardt@
Subject:	PaxosLease question
Date:	Thu, 29 Jul 2010 17:34:04 +0200

Hi all,

I've been reading your PaxosLease paper with great interest some days ago, and decided to implement the algorithm in Haskell (as a little exercise). The implementation [1] isn't done at all, but while working on it and thinking about it, something came to mind which looks like a potential issue in your PaxosLease system, although I could be (most likely ;-)) completely wrong, so maybe you could help to get my head

Here's the idea (based on the pseudocode used in the paper):

Assume S1, S2, S3, S4 and S5 are processors. We assume S1 is the processor which wants to acquire a lease.

At time 1, S1 broadcasts a prepare request to S1-5 (Proposer::Propose). Assume this request arrives at S1-4, but not (yet) at S5.

At time 2, S1-4 set the highestPromised value in their state, and send a prepare response to S1 (Acceptor::OnPrepareRequest).

At time 3 S1 received 4 prepare responses, which is a majority: numOpen will be 4 >= majority, a timeout timer is started, and a propose request is broadcasted (Proposer::OnPrepareResponse). Assume this propose request only arrives at S2 and S3.

At time 4 S2 and S3 send a propose response to S1 (Acceptor::OnProposeRequest), which now has numAccepted 2 (Proposer::OnProposeResponse), which is less than the majority.

At time 5, the prepare request of time 1 finally arrives at S5. S5 responds with a prepare response to S1 (Acceptor::OnPrepareRequest).

At time 6, S1 receives this prepare response from S5. It's numOpen value is now 5, which is >= majority, so it broadcasts a propose request (Proposer::OnPrepareResponse) (still for the same ballot as this whole round!). Let's assume this broadcast only arrives at S2 and S3 (again).

At time 7, S2 and S3 send a propose response to S1 (since the ballot number of the propose request from time 6 is still equal to their highestPromised value) (Acceptor::OnProposeRequest).

At time 8, S1 receives the propose responses from S2 and S3. numAccepted is now 4, which is >= majority, so it assumes it's the lease owner (Proposer::OnProposeResponse).

So, in the end, even though numAccepted == 4, only S2 and S3 ever sent a ProposeResponse, so an actual majority was never reached.

If this is an issue, I think this can be fixed by simply using '==' instead of '<' in Proposer::OnPrepareResponse and Proposer::OnProposeResponse.

Am I missing something important here? If so, please tell me where I'm going wrong :-)

Thanks a lot!

Nicolas

[1] http://github.com/NicolasT/Paxos