Why is it legit to take the next two commands to fill gaps between paxos events?

Question

There is a point in Paxos algorithm (http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf) that I do not understand. It's about how to deal with the gaps, the paper describe two ways as below:

The leader, as well as any other server that learns all the commands the leader knows, can now execute commands 1–135. However, it can’t execute commands 138–140, which it also knows, because commands 136 and 137 have yet to be chosen. The leader could take the next two commands requested by clients to be commands 136 and 137. Instead, we let it fill the gap immediately by proposing, as commands 136 and 137, a special “no- op” command that leaves the state unchanged. (It does this by executing phase 2 of instances 136 and 137 of the consensus algorithm.) Once these no-op commands have been chosen, commands 138–140 can be executed.

1. take the next two commands requested by clients
2. special “no- op” command

The second option has been mentioned Why is it legit to use no-op to fill gaps between paxos events.

And My question is about the first one. In my opinion, take the next two commands will violate the consistency, since the instance happened later may be have a smaller sequence number. So why it is still legit?

Answer 1

Since all clients see the same consistent outcome there isn't a violation of consistency. So there isn't a violation of the algorithms invariants.

If you consider the scenario where all the commands come from a single client then it would be a reordering compared to the order the client sent the values. If a single client is multi-threaded and if it streams multiple concurrent requests the reordering may be harmless (or not, depending on the application semantics). If you consider that the leader uses noops then it effectively just drops some messages which may not be harmless to a client that depends on the ordering of values it streams. It depends on the application.

If you consider the scenario where all the values come from different clients then the situation is far more natural. Under averse conditions some reordering occurs. Yet under normal running that doesn't happen. The reordering it just looks like some values "took longer than normal" to be fixed by a leader while later values issued by other clients "ran faster".

Answer 2

the first option and the second option is the same.

such as in this example, the client want write 4 commands,

a = 1  
b = 2  
c = 3  
d = 4  

in the first option, the result may be

a = 1  
e = 5  
f = 6  
d = 4  

And in the second option, the result is

a = 1  
noop  
noop  
d = 4  

so, both of the results are illegal. There is no difference between lost data and violate the order in this problem.

Then as @simbo1905 said, multi-Paxos don't promise the FIFO order.

if 136, 137, and 138 have order relation, such as they are sent by one TCP connection, and the client sends these three commands with a pipeline. It is the client's responsibility that makes these operations in FIFO order. If the client has many outgoing commands and the client want FIFO client order, the client needs to retry the command from the first failure command.

The other scenario is that they are sent by different connections. Since the are send by different connection, the server can't promise the FIFO client order. The 136, 137 operations are failed, any scenario is acceptable, these two operations can be successful or can be failed. If the client wants to know the result, the client should retry the operation.

In both scenarios, it is the client the responsibility to promise the order, not the server.

So I think you misunderstanding the meaning of consistency, consistency has no relation with order. It is about safety and liveness