PBFT N=3f+1 threshold的理解 [转]

The resiliency of our algorithm is optimal: 3f + 1 is the minimum number of replicas that allow an asynchronous system to provide the safety and liveness properties when up to f replicas are faulty (see [2] for a proof). This many replicas are needed because it must be possible to proceed after communicating with n - f replicas, since f replicas might be faulty and not responding. However, it is possible that the f replicas that did not respond are not faulty and, therefore, f of those that responded might be faulty. Even so, there must still be enough responses that those from non-faulty replicas outnumber those from faulty ones, i.e., n - 2f > f. Thereforen n > 3f.

对于原文的理解：假设作恶节点数量为f（注意：作恶节点可能不发送任何消息，也可能发送错误消息），那么为了保证一致性达成，系统内节点数量必须大于3。为什么呢？原文的意思是：因为我们知道有f个作恶节点，所以我们必须在n-f个状态复制机的沟通内，就要做出决定（为什么呢？因为我们在设计异步通信算法的时候，我们不知道那f个节点是恶意节点还是故障节点，这f个节点可以不发送消息，也可以发送错误的消息，所以在设计阈值的时候，我们要保证必须在n-f个状态复制机的沟通内，就要做出决定，因为如果阈值设置为需要n-f+1个消息，那么如果这f个作恶节点全部不回应，那这个系统根本无法运作下去）。

在n-f个状态复制机的沟通内，就要做出决定。而且我们无法预测这f个作恶节点做了什么（错误消息/不发送），所以我们并不知道，这n-f个里面有几个是作恶节点，我们必须保证正常的节点大于作恶节点数。所以有 n-f-f > f，从而得出了n > 3f。