在阶段 1a 中，提议者是否在向接受者的提议中包含其打算选择的值？
在阶段 2a 之前，提议者不需要发送它打算选择的值。另请参阅我对先前问题的回答。
在阶段 1b 中，acceptor 应该返回它之前接受的值（如果有的话）。价值的生命周期是多少？IOW，什么时候被认为被接受，什么时候被覆盖/丢弃？
从我对另一个不同问题的回答来看，“接受者应该接受所有值，除非它承诺不接受它。” 也就是说，它应该接受任何一个round-id 大于或等于它发送的最后一个响应中的round-id 的值。
它必须接受任何其他值的原因是提议者可能会发现（作为阶段 1 的结果）应该或已经选择了不同的值；然后它将这个值广播给所有的接受者。当有多个提议者和/或在网络分区期间，可能会发生这种差异。
更新以回答评论。
当接受者接受一个值时，它会保留该值，直到它接受另一个值。（与此一起它存储值的轮次）。
在阶段 1b，Acceptor总是发送它的值，允许 Proposer 整理出实际选择的值是什么。它永远不会忘记它的当前值。曾经。
在收到接受者的承诺后，提议者对系统有一个很好的了解。（注意：它不一定是完整的或最新的视图。）
由于与不同的提议者发生争执，不同的接受者可能接受了不同的值。因此，提议者选择具有最高轮次 id 的值并将该值发送给所有接受者。这就是为什么接受者的值被允许改变的原因。
评论中的担忧是这会破坏 Paxos。不是这样。
但是，在我进入示例之前，让我强调一下，使用命名阶段和消息而不是 1a、1b、2a、2b 来考虑 Paxos 要容易得多。我通常将阶段命名为准备阶段和接受阶段。消息 1a 为 Prepare，1b 为 Promise，2a 为 Accept，2b 为 Accepted。
现在，让我们举一个人们经常给出的假设示例，他们认为这会破坏 Paxos。假设我们有三个 Acceptor A1、A2 和 A3。A1 和 A2 在第 1 轮中都接受了值 ABC，而 A3 在第 2 轮中选择了 XYZ（即来自不同的提议者）。我们可以看到 A1 和 A2 占多数，而 ABC 已被“选中”。
继续这个假设的例子，提议者发送 Prepare(3) 并接收来自 A2 和 A3 的回复，即 Promise(ABC @ 1) 和 Promise(XYZ @ 2)。Proposer 看到 XYZ 的轮次最高，并在接受阶段将其发送，覆盖其他主机上的 ABC。还有中提琴，Paxos 坏了，对吧？
不，问题在于启动状态，这是不可能的。让我告诉你为什么。
首先，一些命题，它们是 Paxos 正确运行的关键：
命题 A：对于 A1 和 A2 的值为 ABC @ 1，建议者必须发送 Accept(ABC @ 1)，这意味着它必须收到大多数 Promise 以响应发送 Prepare(1)。
命题 B：对于 A3 的值为 XYZ @ 2，建议者必须发送 Accept(XYZ @ 2)，这意味着它必须收到大多数 Promises 以响应发送 Prepare(2)。
现在证明：
案例 1：A1 和 A2 已经有值 ABC @ 1。根据命题 B，对于 A3 的值 XYZ @ 2 ，它必须从接受者那里收到大多数 Promise。由于值 ABC 在大多数接受者上，因此其中至少有一个必须发送 Promise(ABC @ 1)。1 是最高的轮 id，提议者必须选择值 ABC 并发送 Accept(ABC @ 2)。但它没有，它发送了 Accept(XYZ @ 2)。一个矛盾。
案例 2：A3 已经有值 XYZ @ 2。（请记住，第 2 轮可以在第 1 轮之前：轮 id 仅按每个提议者单调递增。）根据命题 A，对于 A1 和 A2 的值 ABC @ 1，a提议者必须从接受者那里收到过半数的承诺。同样，根据命题 B，要让 A3 也拥有它，必须已经收到了大多数 Promise。这意味着在集合 {A1, A2} 中必须至少有一个接受者承诺了两次。
情况 2a：acceptor 先发送 Promise(1)，然后发送 Promise(2)。那么当它收到Accept(ABC@1)消息时，它肯定拒绝了它，因为它已经承诺不接受早于2的值。但它没有拒绝它，因为它有值ABC@1。矛盾。
情况 2b：acceptor 先发送 Promise(2)。然后，当它收到消息 Prepare(1) 时，它肯定拒绝了它，因为它已经承诺进行更高的一轮。但它显然没有，因为根据命题 A，它发送了 Promise(1)。一个矛盾。
哇！
我希望这能够帮到你。
更新 2：这是 Paxos 的伪 python 实现
from itertools import count
from concurrent import futures
class Acceptor():
def __init__(self):
self.acceptedValue = None
self.acceptedRound = None
self.promisedRound = None
def onPrepare(self, message):
if self.promisedRound > message.round:
send(message.source, new Nack())
self.promisedRound = message.round
response = new Promise(round=self.acceptedRound, value=self.acceptedValue)
send(message.source, response)
def onAccept(self, message):
if self.promisedRound > message.round:
send(message.source, new Nack())
self.acceptedValue = message.value
self.acceptedRound = message.round
send(message.source, new Accepted())
class Proposer():
def __init__(self, selfId, quorum):
self.quorum = quorum
self.id = selfId
# get a unique starting round,
# assumes acceptors and proposers are on same hosts
self.initialRound = sorted(quorum).index(selfId)
def propose(self, value):
"Propose a value to be chosen; returns actual value chosen"
# round is always unique to a proposer
# count(start, step) returns an infinite sequence
for round in count(self.initialRound, len(self.quorum))
promises = self.prepare(round)
if not promises: continue
# interpret the prepare phase results, may be None
selectedValue = max(promises, key=lambda p: p.round or -1)
accepted = self.accept(round, selectedValue or value)
if accepted: return value
def prepare(self, round):
"Drive the Prepare phase. returns the promises from the acceptors or None"
message = new Prepare(round, source=self.id)
responses = []
for acceptor in self.quorum:
responses.append(send(acceptor, message)))
# wait for the results
promises = []
for response in futures.as_completed(responses):
if response.exception(): continue # message died
message = response.result()
if not isinstance(message, Promise):
# A nack message; abort the round. We may have got a majority,
# but this speeds up the case when we didn't.
return None
promises.append(message)
if (len(promises) > len(self.quorum) / 2:
return promises
# No majority of responses
return None
def accept(self, round, value):
"Drive the Accept phase. returns True iff the value was accepted"
message = new Accept(round, value)
responses = []
for acceptor in self.quorum:
responses.append(send(acceptor, message)
# wait for the results
accepts = 0
for response in futures.as_completed(responses):
if response.exception(): continue # message died
message = response.result()
if not isinstance(message, Accepted):
# A nack message; abort the round. We may have got a majority,
# but this speeds up the case when we didn't.
return False
accepts = accepts + 1
if accepts > len(self.quorum) / 2:
return True
# No majority of responses
return False
更新 3回答评论中的更多问题。
...如果它与上一轮发送的提议者相同，我们希望提议者忽略它（否则我们最终会陷入死循环，对吗？）
（我假设“忽略”该值意味着提前退出循环。）
首先，请注意当提议者收到来自大多数接受者的确认已选择一个值时，循环结束。因此，如果提议者发现自己正在执行后续的准备阶段，您可以确定它正在与另一个提议者竞争，或者发生了一些网络分区。其次，请注意即使只有一个接受者接受了一个值，准备阶段也会返回一个值（这意味着该值可能未被多数人接受。）
如果准备阶段产生的值与上一轮中看到的值相同，则出于多种原因，无论如何它都应该继续接受阶段。
- 如果提议者提前退出循环，则可能是其他提议者失败了。这可能导致不选择任何值。
- 如果它提前退出循环，那么其他提议者也是合理的，遵循相同的算法也退出了循环；再次导致可能没有选择任何值。
- 如果碰巧实际选择了该值，则可能并非所有节点都收到了该值（由于网络分区）或具有不同的值（由于与其他提议者的争斗）。那么，为了持久性，将值推送到节点是很好的。
另一方面，当两个或多个提议者之间发生争用并且运气不佳时，Paxos 可能会进入无限循环。（这对于任何共识算法都是正确的，并且在实际发现任何共识算法之前已被 Liskov 等人证明。）所以理论说，但在实际系统中很容易绕过：在随后的每一轮中，暂停一个随机量时间让其他提议者有机会赢得比赛。当然，无限循环仍然是可能的，但它不太可能在宇宙的整个生命周期中发生。
你有任何参考来支持这个论点吗？
我讲的主要是我自己的学习和经验。我所在的团队负责开发和维护一个以 Paxos 为核心的系统。我也对该主题进行了广泛的研究。
这里有一些关于这个主题的好论文：
更新 4回答问题中的更新。
通常在 paxos 工作流中，acceptor 应该总是手头有一个以前接受的值。并且在回答准备请求时，它将在承诺响应中发回该值。并且提议者需要检查该值是否与上一轮提议的自己的值相同。如果不是，则提议者继续发送带有接受者返回值的接受请求。
好的，到此为止。但是提议者不需要在轮次之间保持状态。我们很快就会找出原因。
如果它是[相同的值]，那么提议者继续发送带有它打算在当前轮中发送的值的接受请求。
如果接受器返回任何值，则必须在接受阶段使用具有最高 round-id 的值。如果接受者没有返回任何值，则可以使用任何值：我的逻辑表明这将是客户端传递给提议者的值。
将此与Paxos Made Simple（第 6 页）进行比较：
...其中 v 是响应中编号最高的提案的值，或者如果响应报告没有提案，则为任何值。
（术语在论文之间切换有点困难。这里 Lamport 使用术语numbered proposals，在其他地方他使用术语round-id。有一个和相同的。）
假设提议者运行准备阶段并在接受者中看到此状态。
A1 A2 A3
promise: 3 ? 4
value@round: x@3 ? y@4
实际状态在哪里
A1 A2 A3
promise: 3 4 4
value@round: x@3 y@4 y@4
现在，假设它以 y 值运行了上一轮。如果此时允许选择任何值，则可以强制此状态：
A1 A2 A3
value@round: z@5 z@5 z@5
这会覆盖选择的值，违反共识的一致性属性（即，最多可以选择一个值。）。
如果你想要这种行为，你不能按原样使用共识协议。您可以使用ABD之类的协议或其他基于轮数的寄存器。或者您可以将 Paxos 视为在状态机中选择转换。换句话说，每次你想改变一个变量时，你都会运行一个新的 Paxos 算法来选择转换。这就是我的系统所做的（我敢说最实用的 Paxos 系统）。
请注意，ABD 和基于循环的寄存器的行为类似于 Paxos，但更简单一些，因为它们不必保证上述一致性属性（一旦选择，总是选择）。但是基于 Paxos 的状态机允许对变量进行 CAS 操作。