how is multipaxos different from basic paxos? How does ordering work in multipaxos? Can someone explain multi-paxos along with the diagram
Tried out going through videos and research papers but cannot understand the exact difference and concept of multi paxos
Basic paxos allows a set of nodes to agree on a value. After the consensus is reached, the value will never changes. The fact that the value will never change is a serious limitation where paxos can be applied. Strictly speaking, when a consensus is reached, then each acceptor will have a tuple [N, V], where N is identifier number and V is the value agreed on.
In most practical tasks, consensus needs to be reached on and on. For example, we could use paxos for transaction management in a bank. So for every transaction will require a new consensus. Single paxos clearly won't work as it can't change consensus value at all.
So if one has several cases where a consensus is needed, one of options would be to just run paxos several times, independently for each case. This will lead to two problems: a) ordering of events and b) optimizations.
Independent rounds of paxos won't help with ordering. Since every paxos instance agrees independently on [N, V], there is nothing there to decide which of those events happened first. N is paxos's identifier number won't help as it varies for each instance.
This is where multipaxos comes in - if there is a stream of values to agree on and there is a stable proposer, then we can do two things - add ordering and optimize the flow.
Optimization comes from the fact that the leader is more or less stable. It knows the last successful identifier number N and knows that its proposals will be accepted with high probability (till another leader emerges). This observation removes several messages in the protocol, the leader can keep sending Accepts without Prepare - big optimization.
Order is managed in multipaxos by adding another counter I, which is get incremented by the leader for every new value. So when there is a consensus, it is reached on tuple of [I, N, V] (instead of single paxos with [N, V]).
To clarify: I is the value for events ordering, it is incremented by the leader every time when a value is agreed on. This implies that the leader is a learner as well (doesn't have to be, but this is a common approach).
Eventually, multipaxos is about optimizing consensus on a stream of values.
p.s. as for a diagram, wikipedia has a good one, putting the link instead of copying that over: https://en.wikipedia.org/wiki/Paxos_(computer_science)#Multi-Paxos_when_roles_are_collapsed