【论文笔记】Reaching agreement in the presence of faults (EIG)

这篇论文讨论了分布式系统中处理节点故障以达成一致的问题，提出了交互一致性（interactive consistency）的概念，并设计了指数信息收集（EIG）算法来解决拜占庭将军问题的前身。论文首先定义了问题：在一个由n个节点组成的系统中，最多有m个节点故障，节点之间只能通过消息传递通信，消息的传递时延可以忽略，接收方可以识别消息的发送方。非故障节点需要通过算法达成共识。
论文通过引入交互一致性概念，描述了算法如何通过多轮消息传递计算一致性向量（ICV），使得所有非故障节点的向量值一致。当n≥3m+1时，算法可以有效达成共识。具体来说，单点故障（m=1）需要两轮消息传递，而多点故障（m≥2）则需要m+1轮，算法复杂度呈指数级增长。
当n<3m+1时，由于故障节点可能伪造或拒绝消息，无法达成共识。论文还提出了一种带认证的算法，通过在消息中加入签名机制，防止故障节点伪造消息，从而在n<3m+1的情况下实现共识。
总结而言，这篇论文为分布式系统中的容错性共识问题提供了理论基础和算法解决方案，提出了交互一致性概念，并通过EIG算法展示了如何在一定条件下实现拜占庭问题的解决。

文章目录

• 1 问题定义

• 2 交互一致性

• 3 单点故障

• • m=1 n=4

• 4 多点故障（n>=3m+1）

• • 计算过程
  • m=2 n=7

• 5 n<3m+1不能达成协定

• 6 带认证的算法

• 7 总结

于1980年发表的这篇论文，是基于1982年著名拜占庭将军问题的早期研究。作者Leslie Lamport曾荣获2013图灵奖，其论文分别被引用5000+和2000+次。该论文所提出的算法现被称为EIG算法（EIG全称指数信息收集），其命名原因在于消息数量与节点数量呈指数关系。

The paper titled "Achieving Agreement in the Presence of Faults" was authored by M. PEASE, R. SHOSTAK, and L. LAMPORT and published in 1980.
The seminal work "Addressing the Byzantine General Problem" was co-authored by Leslie Lamport, Robert Shostak, and Marshall Pease and appeared in 1982.

1 问题定义

一个分布式处理系统包含多个处理单元，要确保系统的可靠性，必须具备容错能力，使其能够在部分处理单元出现故障的情况下正常运行。而本算法针对的问题是与一些相互独立的处理单元相关联，其中可能存在故障的单元，各处理单元之间仅通过双方的消息传递进行通信。

问题定义 如下：

由n个独立节点构成的集合中，故障节点的数量最多为m。
节点之间的通信仅限于双方共享的信息，不存在第三方干扰或信道故障的情况，因此消息能够可靠地传递给接收方，并且接收方能够准确识别消息的发送方。
每个非故障节点都持有独特的私有值（private value），用于与其他节点进行通信。
在正常运行状态下，非故障节点始终以诚信的方式进行通信，而故障节点可能会谎报信息（传递错误消息）。

算法设计目标 ：

推断出的某非故障节点值应当是该节点的私有值。所有非故障节点推断出的故障节点的值必须保持一致。

目标本质上是使非故障节点达成共识

2 交互一致性

为了介绍算法，该论文定义了一个叫做交互一致性的概念，以阐述其特性。交互一致性具体定义如下：

由n个独立节点构成的集合中，假设故障节点数量最多为m。在节点之间的通信中，仅允许双方参与，且传输过程中的时延可以忽略不计。接收方能够确定消息的发送方。假设节点p拥有一个私有值Vp（例如基于时钟值或传感器读数），问题可具体表述为：对于给定的正整数m和n，是否存在一种基于消息传递机制的算法，使得每个非故障节点p能够计算出一个值向量，其中每个元素对应于集合中的一个节点。

• 每个非故障节点推导出一个完全一致的向量
• 在向量中，指定某个非故障节点的元素值对应于该节点的私有值

请注意，该算法无需确定哪些节点是故障的，其核心在于确保所有非故障节点计算出的向量值保持一致。

算法对于n>=3m+1可解，其中n为节点总数，m为故障节点数

计算出的向量称为一致性向量(interactive consistency vector，ICV)

由于每个非故障节点可以根据应用需求对向量进行平均或滤波运算函数，对同一向量采用相同的运算方式，从而达成共识。

3 单点故障

首先我们从满足该条件的最简单的例子m=1，n=4开始介绍。

整个处理流程由两部分构成，信息的交互以及基于交互结果的交互一致性向量计算。在单点故障情况下，信息交互需经历两个阶段。在第一阶段，节点之间交换各自的私有值；在第二阶段，节点基于第一阶段获得的结果进行交互。

在整个过程中故障节点可能“说谎”，即传递错误的信息 ，或拒绝发送信息 。

消息的交换

• Round1：节点交换各自私有值
• Round2：交换第一轮得到的值

ICV向量计算

• 投票

当消息交换完成之后，非故障节点p在其对应的向量位置记录了私有值Vp。对于另外三个节点q的值，则根据接收的三个q的值来确定。其中，一个q的值来自第一轮交换，另外两个q的值来自第二轮交换。如果这三个值中至少有两个是相同的，则采用该相同的数值；如果三个值都不相同，则采用默认值NIL。

m=1 n=4

下文通过数学公式进行详细说明：假设P1、P2、P4为正常节点，而P3为故障节点。P1、P2、P3、P4的私有值分别为{1,2,3,4}。P3在第一轮向P1、P2、P4发送了私有值3、Z、Y。以P1接收到的消息为例，P1接收到来自P2的消息向量为{1,2,Z,4}，即P2在第一轮向P3发送的P2私有值为2，在第二轮转交给P1的P2私有值为Z及P4私有值为4。同理，P1接收到P3的消息向量为{1,B,3,4}，接收到P4的消息向量为{1,2,Y,4}。经过两轮消息传递后，统计P2、P3、P4的消息向量在相同单元位置出现次数超过两次的值，设为ICV元素值，若无则设为NIL。由此可得，P1的ICV为{1,2,NIL,4}。

按照上述方法进行推导，类推可得剩余两个非故障节点P2和P4的ICV分别为{1,2,NIL,4}，由此可知所有非故障节点的ICV值相同，最终达成共识。若集合{3,Z,Y}中存在两个或更多元素具有相同值，则将该非NIL元素设为v，这样可以推导出最终P1、P2和P4的ICV必定相等，其值为{1,2,v,4}。

4 多点故障（n>=3m+1）

• 对于单点故障 -> 需要2轮信息交换
• 对于m点故障 -> 需要m+1轮信息交换

在第一阶段，私有值进行轮换；随后，每一轮将接收的值进行传递。整个过程呈指数增长，因此也被命名为指数信息收集算法（EIG）。

设P为节点集合 , V为值的集合

当k≥1时，k-level scenario对应于从一个非空字符串集合{p1,p2,p3,…pn}，其中每个字符串属于集合P且长度不超过k+1，到目标空间V的对应关系。例如：对于一个k-level scenario σ和一个字符串w=p1p2…pn，σ(ω)的值是pn所传达的信息，即pn通过告诉pn-1，直到pn通过pn-1告诉pn-2，依此类推，直到pn通过pn-1告诉pn-2。

在给定的k水平场景σ下，字符串ω=p1p2p3⋯pn满足2≤n≤k+1，其中，σ(ω)定义为，p_n的私有值通过p_{n-1}、p_{n-2}等直到p_2的传递，最终传递给p_1。

对于单个字符的字符串σ(p)表示p的私有值。一个k水平的场景代表了通过k次信息交互的结果。所有非故障节点q，任意节点p以及字符串w，均满足关系式σ(pqω)=σ(qω)。

计算过程

节点p接收的信息以以p开头的字符串限定，记为σ_p。对于任意非负整数m，满足n≥3m+1的条件时，基于σ_p的计算过程如下：

如果P中的元素数量达到或超过(n+m)/2的子集Q存在，且对于所有长度不超过m的字符串w（这些字符串由Q中的元素组成），都有σ_p(pωq)=v，则p记录该值。否则，算法将m-1和n-1代入进行递归调用。此时，P将被替换为P-{q}，而σ_p(pωq)将被替换为σ_p(pω)。对于每个长度不超过m的字符串w，如果在由n-1个元素组成的向量中至少有(n+m)/2个元素的值相同，则p记录该值；否则，p记录NIL值。

m=2 n=7

以m=2、n=7为例，阐述多故障节点下的信息传递机制。如图所示，图中包含7个节点，其中节点4和6为故障节点，其余为正常节点。在初始信息传递阶段，各节点依次发送自身所掌握的私有数据。值得注意的是，节点4和6在这一阶段发送了被篡改的私有数据。

以节点1为例，列举所有满足条件的σ_p (pωq)情况，并进行判断。由此，节点1的向量确定为{V1,V2,V3,NIL,V5,NIL,V7}。对于非故障节点，其向量同样为{V1,V2,V3,NIL,V5,NIL,V7}，这表明各节点间达到了交互一致性，达成了最终的协定。

5 n<3m+1不能达成协定

以下是以m=1，n=3为例说明当n<3m+1时无法达成共识。如图所示，节点3为故障节点，节点1和2为正常节点。观察节点1和2的向量，各元素均无明确多数值，例如节点1向量的第二个元素包含一个B和一个V2，没有元素占据绝对优势，因此无法达成共识。

6 带认证的算法

在n<3m+1的情况下，无法达成协议的原因归因于故障节点可能拒绝转发，或者生成自其他节点传入的值。

通过认证机制，可以确保故障节点尽管可能在传递自己私有值时发送失败或拒绝发送，但不会错误转发来自其他节点的值。

采用认证机制，就是在消息中添加数字签名，该数字签名仅由发送方生成。接收方可以通过验证器来验证发送方的身份以及消息内容的完整性。公钥和私钥通过结合对消息进行哈希处理，可以确保消息来源的可信度。

在m=1，n=3的情况下，当采用带有认证的算法时，节点3无法模仿节点1和节点2所接收的值。因此可以观察到，节点1的两个向量在第二个元素上均为V2，而节点2的两个向量在第一个元素上均为V1。最终，两个节点所获得的向量保持一致，且非故障节点的元素仅包含节点的私有值，这符合交互一致性要求，从而实现了协定的达成。

7 总结

这篇论文是拜占庭问题起源性研究的重要文献，对拜占庭问题进行了概述。阐述了交互一致性的概念，用于定义协定问题，这一概念对于分布式容错系统的设计具有重要意义。此外，提出了EIG算法，用于解决拜占庭协定问题。

在该问题中，故障节点不仅具备伪造私有值的能力，还能够接收其他节点发送的数据。当故障节点数量少于总节点数的三分之一时，该算法能够有效帮助非故障节点达成一致。当故障节点数量超过总节点数三分之一时，节点将无法达成一致。

当采用带有认证机制的方案时，在该协定条件下，故障节点可生成私有值，但无法伪造来自其他节点的数据。非故障节点可在该协定条件下达成协议。