分布式选举共识协调机制拜占庭将军问题算法简介

程序员潇然

针对于分布式系统的资源互斥访问，有一类算法是集中式的管理，通过一个协调管理节点进行一些资源的分配管理。

其实不光是互斥资源，一个分布式系统或者集群中，也还有很多的事务需要进行管理。

那么这个管理者到底如何选择呢？

本文主要介绍一下分布式选举相关的机制与算法。

拜占庭将军

The Byzantine Generals Problem

https://dl.acm.org/doi/10.1145/357172.357176

1. Introduction: 介绍了拜占庭将军问题；
2. Impossibility Results：通过反证法证明了, 三将军问题对于口信消息是无解的；
3. A solution with oral message： 介绍了口信消息型拜占庭将军问题的解决方案；
4. A solution with signed message： 介绍了签名消息型拜占庭将军问题的解决方案；
5. Missing communication paths：讲述了在通信消失情况下的拜占庭将军问题；
6. Reliable systems：讲述了如何通过拜占庭将军问题构建可靠的系统；
7. Conclution：总结

问题描述

在敌人城市周边，驻扎了几队拜占庭军队，每一支队伍都有各自的将军，将军之间可以通过信使进行联系。

通过对敌军的观察，他们必须决定共同的行动计划。

然而，有的将军可能是叛徒，将会试图阻止忠诚的将军达成一致，将军们必须想办法保证：

A 所有忠诚的将军能够达成一致的行动计划;

不管叛徒怎么做，只要忠诚的将军按照算法进行即可，而且希望不仅仅是达成一致，而且是合理的一个计划。

B 少数的叛徒不能导致忠诚的将军们达成一个错误的计划；

这两点可以认为是一致性和正确性。

类比到分布式计算机系统节点上：

两军问题

其实在拜占庭将军问题之前就已经有类似的讨论：

Some constraints and tradeoffs in the design of network communications 1975

E. A. Akkoyunlu,K. Ekanadham,R. V. Huber

https://dl.acm.org/doi/10.1145/800213.806523

文中首次提出了计算机领域的两 军问题及其无解性证明，著名的数据库专家、图领奖得主JimGray正式将该问题命名为”两军问题”。

两军问题表明，在不可靠的通信链路上试图通过通信达成一致共识是不可能的，这被认为是计算机通信研究中第一个被证明无解的问题。

两军问题对计算机通信研究产生了重要的影响，时至今日最重要的TCP/IP 协议中的 “三次握手” 过程即是为解决两军问题不存在理论解而诞生的简单易行、成本可控的 “工程解”。

简单说就是没有绝对的一致性，但是可以在牺牲某些东西，承受部分可以接受的代价的前提下，达到可以接受的“一致共识”。

两军问题的重点在于不可靠通信链路上通过通信达成一致；

拜占庭将军问题重点在于叛将问题，也就是有节点故障或者恶意攻击的情况下，多节点达成一致共识。

FLP不可能原理

在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法。

Impossibility of distributed consensus with one faulty process 1985

https://dl.acm.org/doi/10.1145/3149.214121

作者是: Michael J. Fischer Nancy A. Lynch Michael S. Paterson

所以被称为FLP。

问题分析

针对这种场景，最一般的解决思路就是：

设N位将军，每位将军观察敌情，作出决定后，都将结果"广播"给其余所有的将军，这样所有将军都能获得同样的N份(包括自己)结果，只要取多数，那么每个人都能根据所有人的意见得出一个一致性的共识结论，而且是正确的。

但是如果有人是叛徒，剩下两方一方认为进攻，一方认为撤退，叛徒给另外的人发送不一致的消息，比如：

那么其他两个忠诚的将军都认为已经达成了一致，但是其实是错误的。

论文中以三个将军为例，反证法证明了在三个将军的情况下，没有办法解决，并且推导出一般结论：

如果有m个叛徒，那么将军总数少于3m+1时问题无解。

根据两军问题以及FLP不可能原理可以得出结论：

因为拜占庭将军问题中，存在叛徒，也就是允许节点失效(即使只有一个)，不存在一个可以解决一致性问题的确定性共识算法。

因为拜占庭将军问题中，信使也可能被抓出现问题，也就是不可靠的通信链路上试图通过通信达成一致共识是不可能的。

所以，理论上不存在绝对的解法，但是可以通过容忍某些方面的牺牲，或者说是设法达成某种条件为前提，进而解决拜占庭将军问题。

口信消息型解决方案(ORAL MESSAGES)

针对“如果有m个叛徒，那么将军总数少于3m+1时，问题无解。”

那么，人数大于等于 3m+1之后可以解决，这个本身也是一个额外的限制条件。

增加一个将军，以及一定的条件，将问题解决，这就是口信型解决方案。

下面介绍下当将军总数为n，m为叛徒个数，当n>=3m+1时的解决方法。

口信消息要求：

A1. Every message that is sent is delivered correctly. A2. The receiver of a message knows who sent it. A3. The absence of a message can be detected.

命令的内容不会被破坏，都可以正确发送，无论来自叛徒或者忠将 命令的来源一定可以判断 如果有将军不发命令, 可以被感知

这就要求：

不管是忠将还是叛徒，他们发送的消息都能够正确到达，不会中途变化（被篡改）；

收到消息的人能够溯源，到底是谁发送的消息；

如果没发送消息，可以知道是谁没发送；

通过A1和A2 可以保障叛徒不可以干涉两个将军之间的通讯，通过A1 可以保障叛徒不能改变干涉他们已经发送的消息（因为他们发什么就会被收到什么），通过A2 可以保证他们不能通过发布虚假的消息来混淆他们的通信（你就是你，不能冒充别人）。

A3 可以防止那些想要通过不发消息想要阻止决策的叛徒。

而且，要求每个将军都可以给其他将军直接发送消息。

将第一个发起请求（命令）的人称之为将军，其他的称之为为副官。

鉴于如果将军是叛徒，那么他可能不发送任何命令，所以所有的副官还必须约定一个默认的行为，此处约定如 果没有收到消息，那么就执行 RETREAT

算法实现的目的

所有的忠诚的将军将会采取最终一致的行动，一起行动或者一起撤退；

所有忠诚的副官必须执行他的命令；

ORAL MESSAGES algorithms 定义为 OM(m)，m是非负整数，用来解决 m个叛徒的问题。

将军将命令发送到 n-1个副官那里。

下面的描述中，我们将使用 获得一个值，而不是 服从命令来更方便直观的描述这个事情。

i表示副官序号，对于任意 i，vi代表副官从指挥官收到的值

定义一个函数 majority，majority(v1,v2,...,vn)中出现次数超过半数的值为 v时，返回 v否则返回 RETREAT

OM(0)的算法：

1. 将军将他的命令发给所有的（n-1）副官
2. 所有的副官使用接收到的值 Vi，如果没有接收到值，使用RETREAT

算法 OM(m)，m>0

1. 将军将他的命令发给所有的（n-1）副官
2. 每个副官接收到的值 记为Vi，如果没有接收到值，使用RETREAT, 然后每一个副官i，扮演算法OM(m-1)中的指挥官，向其他n-1个副官发送值
3. 对于任意i以及任意的j != i，用vj代表副官i在步骤2中从副官j收到的值，如果没有收到就用默认值RETREAT。副官i采用函数majority(v1,v2……vn-1)的值

简单说就是每一个副官在每一轮中都将收到的消息转发给其他副官，并质疑收到的其他副官转发的值，通过在下一轮的问询中来裁决本轮收到的其他副官的值。

重复这个过程直到OM(0)轮确定后反推到第一轮的其他副官的值。

是一个递归的过程。

假设 m = 1, n = 4，也就是叛徒一个，总共 4个将军。

先计算 OM(1)

将军将他的命令发给所有的 4-1=3个副官。

副官1、副官2、副官3将他们收到的值作为记为v;

然后他们分别作为副官进行 OM(0)，接收到其他人发送的消息，叛徒随便发送记为 x，而忠诚的副官1和副官2 肯定是发送 v，因为忠诚的副官将会遵守将军的命令，所以最终的序列：

副官1：vvx

副官2：vvx

副官3：vvv

副官i采用 majority(v1,v2……vn-1)的值

所以副官1、副官2、副官3 分别是 v=majority(vvx) v=majority(vvx) v=majority(vvv)

由此可以确定，大家都认为将军的命令是v，达成一致。

上一次递归中确认了将军的命令 v，进行 OM(0)，按照算法要求，他们都接收到对方的命令即可

最终形成了序列

将军： (v)

副官1： (v,v,w)

副官2： (v,v,w)

副官3： (v,v,w)

按照 majority的定义，所以最终结果是一致的都是 v，而且执行了将军的命令 v

简单说在每一次的确认中，大家都确认了上一个发消息的人的消息值是多少。

经过多次递归，就可以决断出来所有人的值，根据得到的所有人的值，就可以判断出来最终的决策。

换一个图再次梳理下:

说明

每个人都会把自己收到的消息发送给比人，告诉别人他收到了是什么，别人收到了他发的之后，就记为Vi=v

换言之，每个人都知道别人收到的消息都是什么

比如V2知道V1、V3、V4、V5、V6他们都收到的什么，因为忠诚的将军会遵守命令，只有叛徒才可能说谎，而且叛徒的数量少，所以经过majority方法计算后，所有忠诚的将军，都将一致的执行第一位将军的命令。

前面的分析有一个前提，这个前提就是第一个发出请求指令的将军，必须是忠诚的，只有这样，所有的忠诚的将军才能够一致的执行将军的命令。

否则如下面两个示例，第一个图中，叛徒将军给了三个忠诚的副官不同的命令，每个人接收到的最终都是(x,y,z)

第二个图中，将军给其中两个发送x，另外一个发送y，那么:

副官1:(x,y,x)，副官2:(y,x,x)，副官3:(x,x,y)，虽然majority都是x，但是没啥意义

在扩展下，如果 m = 2, n = 7，也就是叛徒 2个，总共 7个将军。

下表中，对角线表示各自收到的将军发送的值

对于交叉点，且 i不等于 j，表示左侧竖着一列，告诉横着一行，他收到的将军的值。

副官1~副官4，忠诚副官，所以他告诉所有人他收到的将军的都是v，也就是前面四行都是v

副官5、副官6 叛徒，所以他们胡说八道，随便说

但是通过每一列的分析，对于副官1来说,将军的值，副官2、3、4都告诉他，他们收到的是v，他自己收到的也是v，所以majority就是v；

以此类推，副官2、3、4也都认为将军的值是v，由于副官5、6是叛徒，他们实际的值不确定。

所以，他们最终也是达成一致，也都是遵从将军的命令执行。

签名消息型解决方案

口信型消息中，通过增加忠诚将军的数量，来保障个别叛徒的错误消息左右不了全局。

即使你说谎，我相信大多数人的说法，所以说谎无用。

那么，如果能保证叛徒无法说谎，也就是如果能够验证叛徒是否说谎，就不需要增加额外的将军数量。

这就是签名消息型解决方案

口信消息要求：

A1. Every message that is sent is delivered correctly. A2. The receiver of a message knows who sent it. A3. The absence of a message can be detected.

增加一个A4

A4. (a) A loyal general's signature cannot be forged, and any alteration of the contents of his signed messages can be detected. (b) Anyone can verify the authenticity of a general's signature.

一个忠诚将军的签名不可被伪造，任何伪造都可以被发现；

任何人都有鉴别消息是否伪造的能力；

对叛徒的签名没有任何要求，而且，我们允许另一个叛徒伪造他的签名，从而允许叛徒勾结。

也就是忠诚的将军不可被伪造，叛徒的签名可以被伪造，也就是叛徒勾结。

这样的前提条件下，就不在要求不小于3m+1了，只要求不小于m+2（m为叛徒数量）

叛徒个数为m，只要总数大于等于m+2 即可 也就是假设将军总数为n n>=m+2，m<=n-2 也就是最多可以容忍n-2个叛徒，再多就不可以了

比如1个叛徒的情况下，总数3个将军有解。

比如总数为4，只能容忍最多2个叛徒。

In our algorithm, the commander sends a signed order to each of his lieutenants. Each lieutenant then adds his signature to that order and sends it to the other lieutenants, who add their signatures and send it to others, and so on.

This means that a lieutenant must effectively receive one signed message, make several copies of it, and sign and send those copies.

It does not matter how these copies are obtained; a single message might be photocopied, or else each message might consist of a stack of identical messages which are signed and distributed as required.

算法定义一个函数 choice，函数的入参是一个命令的集合，返回一个单独的值 Our algorithm assumes a function choice which is applied to a set of orders to obtain a single one. 函数的要求如下：

1. If the set V consists of the single element v, thenchoice(V) = v.
2. choice(∅) =RETREAT, where ∅ is the empty set.

Note that one possible definition is to let choice(V) be the median element of V--assuming that there is an ordering of the elements.

论文中这话的意思就是，如果假设这是一个有序集合（按照某种方式排过序），可以去集合中间的那个值。

算法使用 x:i表示值x被将军i签名;

所以 v:j:i表示值 v 被将军 j签名然后值 v:j被将军 i签名

设将军0 是指挥官，也就是第一个发出命令的人

在这个算法中每个副官 i维持了一个 Vi的集合，保存了到目前为止他收到的所有的命令值(如果指挥官是忠诚的,那么这个集合将永远不会超过一个元素)

Vi表示的是他收到的命令值的集合,而不是他收到的消息集合(x:i中 x是命令 x:i是消息)。因为不断在的签名发送，所以同样的命令值会有很多不同的消息。

对于m个叛徒的签名消息定义算法SM(m)

初始时，Vi = ∅（空集），选取一位将军为指挥官，发送消息（v:0）给所有副官

由上图算法过程可以确定：

对于左侧的循环，任意副官i，第一次收到消息初始化集合，然后他就再发一次，此后条件不满足，就不会继续发消息；

对于右侧的循环，如果v已经在集合中了，不会继续发送，只有v不在集合中，并且接收到的消息被签名的个数k<m 时继续，而k从0开始，当k刚好等于m-1时，还在继续循环，再多发一次之后k=m，不继续循环，所以总共接收到的消息的个数是m+1（v :0 :j1 : -.. :jk 消息是k+1个），也就是即使v不在集合中，当收到m+1次消息就结束，m是叛徒的个数，只要每个人收到比叛徒m个数多一个次的消息即可

3个将军，其中1个叛徒为例

左侧执行一次之后就不再循环，右侧循环直接就不满足，所以行为如下图所示

如果将军是叛徒，如下图所示，但是鉴于：

一个忠诚将军的签名不可被伪造，任何伪造都可以被发现；

任何人都有鉴别消息是否伪造的能力；

那么副官1 和副官2 都会知道叛徒是将军，因为签名不能造假，也可以被识破，那就只能是将军发出了不同的命令。

拜占庭错误与非拜占庭错误

拜占庭将军问题描述的是最困难的，也是最复杂的一种分布式故障场景。

除了存在故障行为，还存在恶意行为的一个场景。

但是实际上可以针对某些方面弱化问题，进而达成“解决拜占庭问题”。

比如，对于一个分布式系统的各个节点，他们可能部署在自己的机房内，那么每个节点就可以假设他们都没有叛徒，可以发生故障，但是不会主动作恶。

定义

一般地，把出现故障( crash 或 fail-stop，即不响应)但不会伪造信息的情况称为“非拜占庭错误”( non-byzantine fault)或“故障错误”( Crash Fault);

伪造信息恶意响应的情况称为“拜占庭错误”( Byzantine Fault)，对应节点为拜占庭节点。

非拜占庭错误

而在计算机分布式系统中，最常用的是非拜占庭容错算法，即故障容错算法（Crash Fault Tolerance，CFT）。

CFT 解决的是分布式的系统中存在故障，但不存在恶意节点的场景下的共识问题。

常见的算法有 Paxos 算法、Raft 算法、ZAB 协议。

拜占庭错误

在存在恶意节点行为的场景中（比如在数字货币的区块链技术中），必须使用拜占庭容错算法（Byzantine Fault Tolerance，BFT）。除了口信和签名，常用的拜占庭容错算法还有：PBFT 算法，PoW 算法。

转载务必注明出处：程序员潇然，疯狂的字节X，https://crazybytex.com/thread-239-1-1.html