Exercise 17: reduce number of messages (Paxos)

[dag7dev]

Exercise 17: How many messages are used in Paxos if no message is lost and in the best case? Is it possible to reduce the number of messages without losing tolerance to failures and without changing the number of proposers, acceptors, and learners?

[susannacifani]

The solution on Drive seems right to me:

Basic Paxos requires 4 communication rounds. It is possible to reduce the communication rounds (keeping the above requirements) to 3 if we run multiple instances of Paxos with a coordinator. This translates to $3n + n \cdot l$, where $n$ is the number of acceptors and $l$ is the number of learners in a round.

[simonesestito]

I can't understand this solution.
We already have $3n + nl$ messages in the standard way:

• a proposer sends prepare to all acceptors (n)
• all acceptors reply with a promise each (n)
• the proposer sends accept (n)
• all acceptors send their learn to all learners (l•n)

Total is the same. What's the difference?

[susannacifani]

I can't understand this solution. We already have 3n+nl messages in the standard way:

• a proposer sends prepare to all acceptors (n)
• all acceptors reply with a promise each (n)
• the proposer sends accept (n)
• all acceptors send their learn to all learners (l•n)

Total is the same. What's the difference?

It's not about total. The question says you shouldn't change the number of proposers, acceptors, and learners, so we should have $3n + nl$ anyway. The thing that change is the number of rounds: in basic paxos we have 4 rounds, but we can reduce to 3 rounds (if we run multiple instances of Paxos with a coordinator). So the difference is the number of rounds in the solution on Drive

[palmaaaa]

Well but the question is about the number of messages and not about the number of rounds, so the answer should be no? Unless we consider internal instances of paxos to not consider the prepare since the coordinator does it for each instance anywas, so they're left to do actually $2n+n \cdot l$ for each instance.

[susannacifani]

Well but the question is about the number of messages and not about the number of rounds, so the answer should be no? Unless we consider internal instances of paxos to not consider the prepare since the coordinator does it for each instance anywas, so they're left to do actually $2n+n \cdot l$ for each instance.

I thought that less number of rounds you have, less number of messages you have. Anyway we can't change $3n + nl$, because it's in the question: we can't change the number of proposers, acceptors, and learners.
I found somewhere that basic Paxos requires 4 communication rounds, but it's possible to reduce the communication rounds (keeping the above requirements) to 3 if we run multiple instances of Paxos with coordinator: and this is called Multi-Paxos.
Maybe I didn't get the question, but I think it's about Paxos and Multi-Paxos

[rotiroti]

The first part of the exercise doesn't require any formula but only a counter of the messages exchanged in each phase.

In a single Paxos instance with no message loss and in the best-case scenario, we have:

• 1 message exchanged from the proposer (P) to the acceptor (A)
• 1 response message exchanged from the acceptor (A) to the proposer (P)
• 1 message exchanged from the proposer (P) to the acceptor (A)
• 1 message exchanged from the acceptor (A) to the learner (L)

So, the total number of messages exchanged is equal to 4.

By extending this to $n$ acceptors and $l$ learners we can approximate the Total number $\approx 3n + (l \cdot n)$.