拜占庭算法

概述

拜占庭算法是一种用于解决分布式系统中由于各个节点的不可靠性和网络的不稳定性从而导致节点间可能存在的信任问题的算法，它可以保证在一定条件下，即使有部分节点出现故障(不发送消息)或者作恶(只发送相反的消息)的情况下，仍然可以让各个节点之间达成一致的共识。

问题描述

针对拜占庭问题，如果叛徒的数量大于或等于1/3，拜占庭问题不可解。

假设只有3个人，A、B、C，三人中如果其中一个是叛徒。当A发出进攻命令时，B如果是叛徒，他可能告诉C，他收到的是“撤退”的命令。这时C收到一个“进攻”，一个“撤退“，于是C被信息迷惑，而无所适从。

如果A是叛徒。他告诉B“进攻”，告诉C“撤退”。当C告诉B，他收到“撤退”命令时，B由于收到了司令“进攻”的命令，而无法与C保持一致。

解决方案

• 拜占庭算法：可以解决一个分布式系统中，除了存在故障节点，还存在作恶节点的情况。拜占庭解决方案里又包括两类

  • 口头消息型方案
  • 书面协议型方案(加上了签名机制)

• 非拜占庭算法：只能用来解决分布式系统中存在故障节点的情况，这个场景中可能会丢失消息、或者消息重复，但是不会出现错误消息的情况。

  • 非拜占庭算法中常见的算法有CFT算法、Paxos算法、Raft算法、ZAB协议等

拜占庭容错算法

拜占庭容错算法是由拜占庭将军问题衍生出来的共识算法。拜占庭容错共识算法有3种版本

• 实用拜占庭容错（PBFT，Practical Byzantine Fault Tolerance）
• 联邦拜占庭协议（FBA，Federated Byzantine Agreement）
• 授权拜占庭容错算法（dBFT，Delegated Byzantine Fault Tolerance）

PBFT算法链接

https://www.cnblogs.com/zmk-c/p/14535734.html

https://blog.csdn.net/u011703187/article/details/121876111

上面这两个链接里讲的PBFT中，都没有提到f的值应该怎么确定。自己思考的是因为需要满足3f+1<=n，这样是不是可以默认将f设置为(n-1)/3的值呢。