2

请任何人澄清“完全异步协议协议”中的第 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) 如果有多个tD 消息，则决定v。
    • (c) 其他集合xp = 1或0每个集合的概率为 1/2。
  • 第 4 步：设置r := r + 1并转到第 1 步。

我对这个协议的理解如下。

在第一步中，每个节点都会通知其他每个节点其状态。

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

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

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

  • (a) 如果 D 消息为零，则以 1/2 的概率设置xp = 1或0每个。
  • (b) 如果有多个tD 消息，则决定v。
  • (c) 其他设置xp := v。
4

1 回答 1

0

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

请注意，步骤3 (a)的含义可能有点误导：

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

这并不意味着“完全一个”，而是“至少一个”。这可以从1998 年算法的正确性证明中推断出来，其中第三步稍作改写：

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.}
于 2020-06-09T02:11:04.787 回答