3
$\begingroup$

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?
Improve this question
$\endgroup$
1
  • 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, 2017 at 19:45

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

  1. What exactly is the reason for rule P1?

P1 satisfies liveness property only in cases without failure or message loss. That is what the paper says:

In the absence of failure or message loss, we want a value to be chosen even if only one value is proposed by a single proposer.

Unlike P2 which guarantees the crucial safety property, P1 did not guarantees liveness property in general cases.

  1. What does "P1a subsumes P1" mean?

In context of P1, there's no concept of "A promise never again to accept a proposal numbered less than n" in prepare request. In other words, in context of P1a, a proposal could be either acceptable or not acceptable, but in context of P1, all proposal is acceptable. In context of P1a, P1 could be rewritten as:

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

and P1a indicates:

An acceptor must accept all acceptable proposal that is receives

which means P1a is stronger and subsumes P1.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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