How does Basic Paxos proposer know when to increment roundId / proposal number

Question

Looking at the screenshot from this video, around 27:20

https://www.youtube.com/watch?v=JEpsBg0AO6o

When server S5 sends out the prepare RPC, it uses the roundId (proposal number) 4 and server number 5 (hence 4.5) as well as value "Y".

But how does it know 4 is the the roundId to use? Earlier, S1 used up roundId 3, but there's no way for S5 to know about that, as there hasn't been communication between S5 and anybody else at the time S5 chose 4 as roundId.

Answer 1

In theory, there is no need to know what is the latest number as every proposer will keep increasing the round number until it gets it right.

In your example S5 knows nothing, so it will start with smallest number and then keep going up.

In practical application, when a proposer proposes a number, and if the proposal is declined by an acceptor, the declined message will contain the largest round number seen so far by that acceptor; this will help the proposer to retry with a larger round number (instead of increasing their current number one by one).

-- Edit: Max posted a link with an answer claiming (at of now) that N has to be unique per proposer

Let me explain why there is no global uniqueness requirement by an example.

Let's say we have a system with two proposers and three accepters(and few learners):

1. Both proposers sent PREPARE(1) - same number - to all acceptors.
2. Based on paxos rules, only one of proposers will get the majority of PROMISE messages - this is based on the rule that acceptor promises if PREPARE has number strongly greater than any other previously seen by the acceptor.
3. Now we are in a state where one proposer has two (or three) PROMISES for N=1 and the other proposer has one (or zero) PROMISE with N = 1.
4. Only first proposer may issue ACCEPT(1, V) as it got majority. The other proposer does not have the majority of PROMISES and has to retry with a larger N.
5. After the other proposer retries, it will use N larger than any other it saw before - hence it will try with N=2
6. From now on, it's all works the same way - proposer PREPARES and if get majority of PROMISE for its N, then the proposer issues ACCEPT(N, VALUE_ACCORDING_TO_PROTOCOL)

The key understanding for paxos is there is no way to have two ACCEPT(N, V) messages being sent where same N will have different V, hence there is no issue that two proposer use the same N.

As for initiating every node with some unique ID - that's ok; will it improve the performance - it's a big question and I haven't see a formal proof for that yet.