I'm missing two details from Paxos made easy

P1. An acceptor must accept the first proposal that it receives.

  1. What exactly is the reason for rule P1? What if the rule P2 was different, i.e. Upon receiving a proposal: acceptor memorizes the proposal as most recent proposal; if acceptor is not waiting with a running countdown, a countdown of Xmsec is set up; upon a countdown timeout acceptor accepts the most recent proposal

I'm not proposing the above rule as better or more interesting -- rather I'm posing a question of which exactly requirement is fulfilled by following P1.

Observe that P1a subsumes P1.

  1. What does this mean? That P1a is more general? Fulfilling P1a fulfills P1? At least scenario mentioned in section 2.4 suggest P1a does not imply P1. What am I missing?
  • 1
    $\begingroup$ Regarding (1), there are seven properties that any consensus algorithm cannot fulfill all at the same time. One of them is asynchronicity, which is fulfilled by Paxos's algorithm. It means that you don't want to rely on timeouts. If you rely on timeouts, it doesn't add value to the algorithm in the worst case (when some other process was just lagging for a while and the timeout expires, you're facing the same problem as when you wouldn't have a timeout). $\endgroup$ – Albert Hendriks Jun 22 '17 at 19:45

What exactly is the reason for rule P1?

The paper says:

We use the customary asynchronous, non-Byzantine model...

In other words, it assumes that everything can take an arbitrarily long time to happen, but no messages are corrupted in transit and all agents obey the protocol.

What this means is that it would be perfectly fine to write the timeout-based rule as you describe, but it would be harder to describe and analyse and yet it would not satisfy any different properties from a protocol that has no timeouts: the asynchronous model already allows for arbitrary delays and message-reordering, so adding any further delays and message-reordering doesn't gain anything.

What does "P1a subsumes P1" mean?

It means it replaces P1. The sentence after P1 starts ...

But this requirement raises a problem.

... which means that P1 isn't the correct requirement. The correct requirement is in fact P1a.

| cite | improve this answer | |

Regarding your second question, it means $P1^a$ is stronger and therefore implies $P1$. Therefore it "includes", "absorbs", "subsumes" $P1$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.