algorithm - 拜占庭将军问题不可解性的模拟证明如何正确？

在兰波特关于拜占庭将军问题的论文中（pdf）：

在N = 3 个将军和M = 1 个叛徒（第 384、385 页）的普通情况下，有一个无法解决的证明。这很容易理解。

论文接着给出了一个模拟证明（第 386 页）：

......没有少于3M + 1个将军的解决方案可以应付m个叛徒。

证明是矛盾的，他们说如果 3M+1 个将军和 M 个叛徒是可以解决的，那么 3 个将军和 1 个叛徒的琐碎情况也是如此。但既然三将一奸是无解的，我们就得出了一个矛盾。

这只是没有意义或成立。我的理由：

论文表明，3名将军和1名叛徒的小事，不使用仿真是无法解决的。
因此，声称如果3M+1将军和M个叛徒是可解的，那么琐碎的情况可以是可解的，并且由于琐碎的情况是不可解的，具有 M 个叛徒的 3M+1 将军是不可解的，只是由于第 1 点不成立.

看来这只是一个无效的循环引用。

有人可以指出我在这里缺少什么吗？谢谢！

标签： algorithmcomputer-sciencedistributed-computingdistributed-systemconsensus

我在这里没有看到循环引用。

声称对于所有 M，不可能有一种算法可以解决 3M 将军和 M 叛徒的 BGP。（请注意，这不是针对“一些 M”，而是针对“所有 M”——否则 3 一般 1 叛徒情况立即暗示该定理。）

证明是矛盾的。假设对于一些 M - 任何给定的 M - 我们可以使用算法 A 解决 3M 将军和 M 叛徒的 BGP。然后我们可以设计一个可以解决 3/1 情况的算法 B，让每个将军模拟 M 个将军，并且然后将算法 A 作为子程序运行。

这是一个矛盾，因为我们知道——独立地——不存在解决 3/1 情况的算法 B，从而得出证明。