In paper Zab: High-performance broadcast for primary-backup systems, the figure 1 shows that Paxos could violate primary order of requests. I understand the result will be like that if each proposer proposes values as the paper suggests; What I don't understand is why Proposer 2, 3 would propose a value different from Proposer 1. What could cause that? Are proposers only collect all information from phase1 or is there Client retransmit because proposer 1 failed? Could anyone give a complete picture of it?
Two other questions:
- What need to be modified to let Multi-Paxos replication system support primary order?
- Does plain Multi-Paxos support linearizability of client requests?