为什么确定为“异步”网络的拜占庭式容错的阈值？（它不能容忍甚至一个故障的节点）

Question

在以下答案（链接： https://bitcoin.stackexchange.com/a// 58908/41513 ），已经表明，对于异步拜占庭协议：

“我们不能容忍1/3或更多的节点是不诚实的，或者我们输了 无论是安全还是活力。“

对于此证明，已考虑以下条件/要求：

1. 我们的系统是异步。
2. 一些参与者可能是恶意的。
我们想要安全。
3. 我们想要活跃。

一个基本问题是：

考虑着名的众所周知的纸张标题：“具有一个故障过程的分布式共识不可能”（链接： https：//apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf ）< / p>

显示：

否完全异步共识协议可以容忍甚至是单个未经处理的过程死亡，

我们仍然可以假设网络是异步吗？正如在那种情况下，网络甚至无法容忍一个故障节点。

Answer 1

答案与跟踪在这些不同结果中进行的精确假设有关。简而言之，虽然这两个结果都假定了异步，“具有一个故障过程的分布式共识不可能”需要一种更强烈的活力和决定论，并使其不可能。

1。具有一个故障过程的分布式共识不可能是

这个精髓结果（Michael Fischer，Nance Lynch和Michael Paterson）是关于分布式共识，其中系统不仅仅是异步，还满足：

• 确定主义。共识算法不使用任何随机性。

• 在消息延迟下的活力。不仅可以任意延迟消息，但即使在存在这种持续延迟的情况下也必须保证生活。

让我们了解为什么Tehse属性太强大，并使分布式共识不可能。

考虑一个例子：爱丽丝，鲍勃和查理是朋友，想决定在哪里见面吃饭。其中一个人可能意外地变得令人惊讶（或者决定他们不再是朋友不再感兴趣），并停止响应邮件。在这种情况下，其他两个仍然可以决定一个地方见面。现在他们应该怎么做？

明显的方法是：

爱丽丝刚刚决定去哪里，并告诉鲍勃和查理。

但这不起作用，因为爱丽丝可能是那个令人畏缩的人。 因此解决这个问题，下一个最明显的方法可能是：

alice和bob告诉其他人去哪里。如果每个人都从爱丽丝听到，那么他们会去爱丽丝所说的;否则，他们会去鲍勃说的地方。

但这有一个新问题。假设你是查理。如果你从爱丽丝听到，你知道去哪里。如果你没有听到他们，你会等你听到。问题是当您听到鲍勃的消息时，而不是爱丽丝。因为有任意的消息延迟，你不能提交鲍勃说的地方：爱丽丝可能已经说过去哪里，你还没有收到它！ 所以你完全被困，如果它碰巧爱丽丝已经消失了，你将继续等待。

这里的问题是我们无法中止交易;没办法说，“好的，这不起作用，已经太久了，我没有收到延迟 - 让我们再试一次。”现实世界共识算法（最知名的PaxoS）有可能由于网络延迟而失败的可能性，在这种情况下，他们刚刚重试，希望网络延迟更短。此外，可以通过使用通常是工作的随机协议来解决问题，并且仅使用小（或甚至零）概率来永远持续。

2。异步拜占庭式协议，其中少于节点的$ 1/3 $ 失败

比特码帖您链接在最终问题上界定，说只是“继续进步的能力”。事实上，上述结果表明，最强烈的形式是不可能的，因此我们必须放宽我们的要求/假设。

让我们考虑两个例子。在Miguel Castro和Barbara Liskov的“实用拜占庭容错”中，他们通过缺少的节点达到了少于三分之一的节点，假设消息延迟不断无限期地生长。作为作者状态：

我们保证活跃，即客户 最终会收到他们的请求的答复，最多提供 $ \ frac {n-1} {3} $ 副本是有缺陷和 $ delay（t）$ 才不是 生长速度超过 $ t $ 无限期......这是一个相当弱的同步 假设在任何真实系统中可能是真实的 提供的网络故障最终修复，但它 使我们能够规避[9]的不可能的结果。

这里[9]是上面讨论的不可能性结果。在我们的榜样的平原术语中，通过要求弱形的同步形式来避免上述问题：查理并不简单地继续等待，因为我们知道邮件延迟只能长期成长，而不是无限期。 （当然，实际算法变得更加复杂，但这部分是为什么是可能的概念思想。）

在Ran Canetti和Tal Rabin的“快速异步拜占庭与最佳弹性协议”中，他们使用随机性以少于 $ n / 3 $ 拜占庭式节点故障。从他们的论文中：

在此设置中，我们描述了 $（\ lceil \ frac {n} {3} \ rceil-1）$ -resilient拜占庭协议协议。和 压倒性概率所有非故障播放器都完成了执行

议定书。在某种程度上 事件所有非故障播放器已完成 执行协议，他们持续预期 时间。

此处 $（\ lceil \ frac {n} {3} {3} \ rceil-1）$ -resilient只意味着少于三分之一的节点是拜占庭。 注意带有压倒性概率的关键词。因此它们具有概率算法，具有许多可能的“运行”，而且大多数工作都是如此。请注意，上述不可能性结果意味着必须始终存在某些运行，其中不发生以内，即没有共识：

Fischer，Lynch和Paterson的【FLP]确定性协议的明确结果意味着到达BA的任何（随机）协议都必须具有不变的运行。