algorithm - 为什么使用接下来的两个命令来填补 paxos 事件之间的空白是合法的？

Question

Paxos 算法(http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf)中有一点我不明白。这是关于如何处理差距的问题，论文描述了以下两种方式:

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. 接受客户请求的下两个命令
2. 特殊的“no-op”命令

已经提到了第二个选项Why is it legit to use no-op to fill gaps between paxos events .

我的问题是关于第一个问题。在我看来，采取接下来的两个命令将违反一致性，因为稍后发生的实例可能具有较小的序列号。那为什么它仍然是合法的呢？

Answer 1

由于所有客户端都看到相同的一致结果，因此不存在违反一致性的情况。所以不存在违反算法不变量的情况。

如果您考虑所有命令都来自单个客户端的场景，那么与客户端发送值的顺序相比，这将是重新排序。如果单个客户端是多线程的，并且如果它流式传输多个并发请求，则重新排序可能是无害的(或无害，取决于应用程序语义)。如果您认为领导者使用 noop，那么它实际上只是丢弃一些消息，这些消息可能对客户端无害，这取决于它流式传输的值的顺序。这取决于应用程序。

如果您考虑所有值都来自不同客户端的情况，那么情况就自然得多。在不利条件下，会发生一些重新排序。然而，在正常运行下不会发生这种情况。重新排序看起来就像一些值“比正常情况下花费更长的时间”被领导者修复，而其他客户发布的后来值“运行得更快”。