Paxos made simple -- two details

I'm missing two details from Paxos made easy

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

• 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.

• 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?

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.

StackExchange Computer Science Q#77112, answer score: 2