Exercise 20: You are an optimization freak (fast paxos)

[dag7dev]

Exercise 20: You are an optimization freak. You realize that, in some cases, it is not necessary that the proposer collects $n-f'$ (the Fast Paxos quorum) promises to take a decision. Which is the minimum quorum and under what hypothesis this minimum quorum is enough to take a decision?

[susannacifani]

I think the solution on Drive is correct:

[simonesestito]

But when is it correct? For every round or only the first one?

Also, could someone try to rephrase it? It's pretty strange to understand at a first glance 🤔

[lor3ny]

I've solved the exercise using the following reasoning (inspired by the drive solution), but i'm not sure if it is correct.

We can split fast paxos execution in two macro phases:

1. Prepare-promise
2. Accept any-Accept

Phase 1 is handled only by the coordinator, so it works like a basic paxos because it doesn't allow other participant to request promises by the acceptors. That means the coordinator, in this phase, can follow the basic paxos quorum, so $\text{Max } f: n = 2f +1$.

Fast paxos, after the phase 1, send an "accept any" message. That message allows the acceptor to select and vote for the first accept message received by any proposer. This makes the proposers in Phase 2 concurrent, invalidating the basic paxos quorum rule. Therefore, we need $\frac{2}{3}$ quorum.

In summary: 1-phase (quorum $> \frac{1}{2}$) + 2-phase (quorum $> \frac{2}{3}$)

[simonesestito]

But are we allowed, in Fast Paxos, to send an Accept-Any message if and only if it's the first round?

I mean: if, because of concurrency between multiple acceptors, no value is chosen and another round must be done, is the coordinator able to send another Accept-Any message?
Is only $\frac{1}{2}$ quorum enough in this situation?