“自由选择的另一个优势：完全异步协议协议”的解释

Question

任何人都可以，请澄清“ Completely Asynchronous Agreement Protocol”中的第3步（见下文）：

处理P：初始值xp。

• 步骤0：设置r := 1。
• [步骤1：将消息(1, r, xp)发送到所有进程。
• 步骤2：等待直到收到N - t类型的(1, r, x)消息。如果多个N/2消息具有相同的值v，则将消息(2, r, v, D)发送到所有进程。否则将消息(2, r, ?)发送到所有进程。
• 步骤3：等待直到N - t类型的(2, r)消息到达。
  • （（a）如果有一个D消息(2, r, v, D)，则设置xp := v。
  • （b）如果D消息多于t，则确定v。
  • [（c）否则分别设置xp = 1或0的概率为1/2。
• [步骤4：设置r := r + 1并转到步骤1。

我理解此协议如下。

第一步，每个节点将其状态通知其他每个节点。

在第二步，每个节点决定是否具有“看到的”足够信息来确定该值，换句话说，它等待多数。如果多数具有相同的值，它将开始广播此信息，例如“我看到多数认为v”。否则，它发送的消息表明它没有下定决心。

[最后，在第三步中，我们检查是否有超过t个“决定性”消息（如果不会传递t节点的消息，则至少会有一个“决定性”消息）。但是我不明白为什么仅在收到确切的一个 D消息时才设置xp := v。接收到两个D消息属于3c，在这种情况下，我们将为v分配随机值。为什么？

为什么我们不能像这样描述第三步：

• （（a）如果D消息为零，则分别以1/2的概率设置xp = 1或0。
• （b）如果D消息多于t，则确定v。
• [（c）其他集xp := v。

Answer 1

您链接的论文介绍了Ben-Or共识算法。它提供了两种版本，一种用于简单的概率共识，另一种用于拜占庭协议。您提供的伪代码复制了前者。

注意步骤3（a）的含义可能会引起误解：

If there is one D-message (2, r, v, D) then set xp := v

它的意思不是“完全一个”，而是“至少一个”。这可以从1998 algorithm's correctness proof中推断出，其中第三步略有改写：

wait for messages of the form (P, k, ∗) from n − f processes {“∗” can be 0, 1 or ?}
if received at least f + 1 (P, k, v) with the same v != ? then decide(v)
if at least one (P, k, v) with v != ? then x ← v else x ← 0 or 1 randomly {query r.n.g.}