共识协议述评

一致性问题是多智能体系统中的一个基本问题，它需要一组进程(或多个智能体)可靠、及时地就单个数据值达成一致。虽然在分布式计算的背景下进行了广泛的讨论，但它并不是该领域的专有，在我们的社会中也存在着各种情况，如民主选举、立法过程、陪审团审判程序等等。

它是通过使用协商一致的协议来解决的，该协议规范了进程(代理)之间的交互方式。这看起来可能是多余的，但要解决共识问题，首先所有进程都同意遵循相同的共识协议。

这些过程中的一些可能会失败或在其他方面不可靠(例如在利益冲突的情况下)，因此共识协议必须是容错的或有弹性的。这些流程必须以某种方式提出它们的候选值，相互沟通，并决定一个一致的值。

在这篇文章中，我回顾了四个主要的共识协议，它们是在我实施的基础上解决共识问题的，即：

在开始之前，让我们回顾一下共识协议的三个关键属性，并快速查看一下本讨论的相关术语。

如果所有正确的过程都提出了相同的值“v”，那么任何正确的过程都必须决定“v”。

这些要求相当直截了当。“终止”证明协议对停机故障具有弹性。“协议”阻止任何两个正确的过程决定不同的价值，这将破坏共识。最后，“完整性”实际上是灵活的，可能会根据应用程序的要求而变化，它确保协议以预期的和不偏不倚的方式运行。

这些术语在本文中使用，也在提供的支持源代码中使用。

管理流程行为的官方规则集(“算法”)，用于解决共识问题。

属于一个更大的群体的个体代理人，集体对达成共识感兴趣。流程可以是“正确的”，意味着它们严格遵守协议，不会出现故障；也可以是“错误的”，意味着我们不能一直依赖它们遵循协议。

在协商一致的协议下流程之间定义良好的一轮交互。根据基础协议的不同，达成共识需要一个或多个意向。

流程角色。此角色下的流程有权提出价值建议。所有正确的过程都同意的任何价值都必须起源于提议人。

流程角色。此角色下的流程有权决定一个值。所有正确流程同意的任何值都必须由至少一个决定者投票表决。

负责持久化决定的值并实现协议的特定数据约束的应用程序或子系统。

负责检测节点故障或崩溃的应用程序或子系统。

协议的特定阈值需要至少一半的可用选票，如果考虑到错误的进程，则需要更多。

协议的特定阈值，确保达到采取行动的最低参与者(或投票数)。

有了这些定义，让我们继续执行和审查每项协商一致的议定书。

我的主要目标是在代码中实现这四个协议，以便能够在受控环境中运行和评估它们。我还对尝试找出它们之间的结构相似性很感兴趣，这些相似性可以提取到一个公共的基础结构中，从而促进代码重用。

我的第一次编码迭代的结果显示在下面的简化类图中：

Procotol类有一个进程集合，这些进程将根据达成共识的协议规则彼此交互。协议的每次执行都通过Execute方法创建一个新实例(不要与面向对象编程中“实例”的传统含义混淆)。

Instance类表示可能导致共识的流程之间的一轮交互，如Consensus和Value属性所示。它负责管理执行建议者和/或决策者角色的流程之间的交互，提供消息传递(Send)和检索(WaitMessage和WaitQuorum)的方法。

Process类负责实现建议者和/或决策者角色。行为是在实例启动之前在bind方法中定义的，因为还有一些协议要求进程根据当前实例扮演不同的角色。

Process.Propose虚拟方法在该实例中的所有Proposer进程的实例执行开始时调用，以启动通信，并具有以下默认实现：

它首先基于底层的建议器逻辑(例如随机布尔建议器)生成一个建议书，然后对照归档程序验证所生成的值是否通过自定义应用程序需求，最后将其广播到所有兄弟流程。

绑定到Instance.WaitQuorum事件的进程将等待采取操作所需的协议特定消息量(针对每种消息类型)。具体数量是在派生实例类时在每个协议实现中定义的。

所有四个共识协议都是使用此基础结构实现的，如以下各节所示。我不会执行广泛的代码分析，而是将重点放在介绍我的实现的每个理论算法和关键点上。

Chandra-Toueg共识算法由Tushar Deepak Chandra和Sam Toueg于1996年首次发表，并引入了故障检测器的概念作为解决共识问题的手段。该算法假设由f表示的多个故障进程小于n/2(即小于简单多数)。

在每种情况下，一个进程充当决策者(轮换协调器)，所有其他进程充当提出者。在每个实例中执行的操作为1：

协调器等待从至少一半的进程(包括其自身)接收消息。然后，它在发送的值中选择具有最新时间戳的值作为其首选项。

每个进程等待(1)从协调器接收(r，首选项)，或(2)等待其故障检测器将协调器标识为崩溃。在第一种情况下，它将自己的首选项设置为协调器的首选项，并使用ack(R)进行响应。

任何第一次收到Decision(首选项)的进程都会将Decision(首选项)传递给所有进程，然后决定优先项并终止。

让我们来看一下代码。下面的代码片断定义了建议书流程行为：

Private void BindAsProposer(实例r){WaitQuorum(r，MessageType.。选择，msgs=>；{var m=msgs。Single()；SendTo(m.。Source，r，MessageType。好的，M。Value)；})；WaitQuorum(r，MessageType.。决定，msgs=>；{var v=msgs。单个()。值；终止(r，v)；})；}。

例如，启动计划的提倡者传播他们的价值观。然后，他们等待法定人数从建议池中选择一个值。由于该协议每轮只定义一个决定者，所以当决定者过程广播他的选择时，满足该法定人数。一旦接收到该选择，提议节点将确认该选择并等待决策者的决定，然后决定相同的值并终止执行。

私有void绑定协调程序(实例r){WaitQuorum(r，MessageType.。建议，msgs=>；{var v=PickMostRecentValue(msg.。其中(m=>；Archiver。CanCommit(m.。值)；广播(r，MessageType。SELECT，v)；})；WaitQuorum(r，MessageType.。Ack，msgs=>；{var v=PickMostRecentValue(Msgs)；Broadcast(r，MessageType.。决定，v)；终止(r，v)；})；}。

它首先等待法定人数的提案，也就是说，等待简单多数的提案提交他们的价值。然后，决策器挑选最新的消息值，可能用存档程序验证值，并将选定的值广播回所有进程。

在广播选定的值之后，决策器等待法定人数的提议人确认它，在这种情况下，它决定该值，并在终止之前将其决定广播给所有进程。

请注意，这种简化的实现没有考虑故障，即使Chandra-Toueg协议具有故障恢复能力。

BEN-OR是一个分散的共识协议，也就是说，它不将决策者角色分配给任何特定的过程。奇怪的是，算法的正确性证明是在其最初发表15年后才在一篇论文中提供的。

由于缺乏解决平局情况的决定者，Ben-or只能处理二进制值一致性(“真”或“假”)，而不能处理任意值一致性。即使到那时，它也使用随机化来收敛到共识。

该算法在实例内分阶段工作，并且在给定n>；2f的情况下，对于总共n个进程中的f个崩溃进程具有弹性。以下是实例中每个进程执行的操作：

循环：等待来自n个−f进程的(R，k，*)形式的消息(“∗”可以是0或1)。

等待来自n个∗f进程的(P，k，−)形式的消息(“∗”可以是0、1或？)。如果接收到的至少f+1(P，k，v)具有相同的v≠？然后。

它本质上是一个循环，在流程能够决定一个值时结束，否则它将继续进行，其中每个循环迭代都是一个由两个异步循环组成的新阶段。

在该算法中，每条消息都包含一个标记(R或P)、一个阶段号和一个0或1的值(对于标记为P的消息，它也可以是“？”)。标记为“R”的消息称为报告，标记为“P”的消息称为建议。

这个协议是最容易实现的，但是不要自欺欺人，实际上它的行为不是很容易分析的，这就是为什么花了这么长时间才得到正确性证明的原因。下面是我对ben-or进程行为的实现：

公共重写空绑定(实例r){WaitQuorum(r，MessageType.。建议，msgs=>；{var x=PickMostFrequentValue(msg.。其中(m=>；Archiver。CanCommit(m.。值)；var v=x。计数>；r。提名人。数/2？X。值：空；广播(r，MessageType.。SELECT，v)；})；WaitQuorum(r，MessageType.。SELECT，msgs=>；{var x=PickMostFrequentValue(msg.。其中(m=>；m.。Value！=NULL))；IF(x.。Count>；=f+1){Terminate(r，x.。价值)；提出者。Reset()；}Else{if(x.。计数&>；0)推荐人。设置(x。值)；否则为提出者。Reset()；}})；}

我已经将“R”标记替换为MessageType.Propose枚举值，并将“P”标记替换为MessageType.Select以便与存储库中的其他协议实现更一致。除此之外，它几乎是前面描述的算法的副本，实际的循环是以基于事件的方式实现的，即，作为进程之间循环消息传递的结果。

所以我才知道帕克索斯家族的协议和我一样老，是由莱斯利·兰波特在1989年(我出生的那年)首次提交的。它的名字源于希腊帕克索斯岛上使用的一种虚构的立法协商一致制度，兰波特在那里写道，议会必须发挥作用，“即使立法者不断进出议会会议厅”。

到目前为止，Paxos是最难用代码推理和实现的。在信息技术中，过程被分类为提出者、接受者和学习者(单个过程可能同时具有这三种角色)。其想法是，提出者试图通过收集大多数接受者的接受来认可(来自任意输入集的)建议的决策值，并且学习者观察到这种认可。协议是通过保证只有一个提案可以获得大多数接受者的投票来执行的，并且有效性取决于只允许提出输入值3。

提出者向所有接受者发送消息PREPARE(N)。(假设他们都会响应，只发送给大多数接受者就足够了。)。

每个接受者将N与其响应准备消息的编号最高的建议进行比较。如果n较大，则它用ack(n，v，nv)响应，其中v是它接受的编号最高的提案，nv是该提案的编号(如果没有这样的提案，则为⊥，0)。

发起人等待(可能永远)从大多数接受者接收ACK。如果任何ACK包含值，则它将v设置为它接收的最新(按照建议编号排序)值。然后，它将Accept(n，v)发送给所有接受者(或只是多数接受者)。

在接收到Accept(n，v)时，接受者接受v，除非它已经接收到针对某个n‘>；n的准备(n’)。如果大多数接受者接受给定建议的值，则该值成为协议的判定值。

现在，让我们从Proposer角色行为开始，看看代码实现：

受保护覆盖无效提议(实例r){proposalNumber=minNumber+1；Broadcast(r，MessageType.。Proposal，proposalNumber)；}private void BindAsProposer(实例r){WaitQuorum(r，MessageType.。Ack，msgs=>；{var v=PickHighestNumberedValue(Msgs)？价值？？提名人。GetProposal()；IF(Archiver.。CanCommit(V)){var x=new NumberedValue(v，proposalNumber)；Broadcast(r，MessageType.。SELECT，x)；}})；WaitMessage(r，MessageType.。Nack，msg=>；{if(msg.。值！=NULL){var n=(长)消息。值；IF(n&>；minNumber){minNumber=数学。Max(n，minNumber)；if(RandomExtensions.。试用(0.5))提议(R)；})；WaitQuorum(r，MessageType.。接受，msgs=>；{var m=msg.。选择(m=>；m.。值)。DISTINCT()；如果(m.。Count()==1){var x=m。Single()as NumberedValue；Terminate(r，x)；Broadcast(r，MessageType.。决定，x)；}})；}。

OBS：在这段代码中使用Math.Max似乎是多余的，但实际上它是用来解决争用条件的，而不是求助于互斥锁。

您可以看到，在本例中，Process.Propose方法被覆盖以实现Paxos协议提案编号逻辑，并且我使用MessageType.Propose枚举成员来表示“Prepare”消息。

在广播其提案编号之后，流程将等待MessageType.Ack或MessageType.Nack响应。如果它收到否定响应，这意味着它的建议书编号已过期，因此该流程将更新它并提交新的建议书(在我出于调试目的添加的随机间隔之后)。但是，如果它收到足够多的肯定响应以形成仲裁，该流程将广播一个MessageType.Select消息，该消息具有到目前为止看到的最高数值，如果它还没有看到它自己的首选值，则选择它自己的首选值。

最后，建议者将等待一定数量的一致MessageType.Accept消息，在这种情况下，它决定该值并终止。

在图片的另一边，我们有接受者，他们的行为代码如下所示：

Private void BindAsAccepter(实例r){WaitMessage(r，MessageType。建议，msg=>；{var n=(Long)msg.。值；IF(n&>；minNumber){minNumber=n；SendTo(msg.。Source，r，MessageType。确认，接受)；}否则{发送至(消息。Source，r，MessageType。Nack，minNumber)；}})；WaitMessage(r，MessageType.。选择，msg=>；{var x=msg.。NumberedValue形式的值；如果(x.。Number>；=minNumber&；&；Archiver。CanCommit(x.。值)){Accept=x；SendTo(消息。Source，r，MessageType。Accept，x)；}})；WaitMessage(r，MessageType.。决定，msg=>；{var x=msg.。数值为NumberedValue；Terminate(r，x)；})；}。

在接收到MessageType.Propose消息时，只要提案编号大于到目前为止看到的最高提案编号(MinNumber)，接受者就会“确认”，更新该编号，如果小于或等于，则“nack”。

然后，只要建议书编号大于或等于minNumber，它就等待MessageType.Select消息并接受它，在这种情况下，它更新其最后接受的值，并将MessageType.Accept消息发回给建议书。

最后，接受者只需等待MessageType.Decide决定其值并终止执行。

但是…。在我的实现中有一个陷阱，您注意到了吗？在目前的形式下，它是不完整的，进程不知道是否真的达成了共识！从实例的角度看，可以检查值是否有多数决定，但从过程的角度看，不是。这是因为我(还没有)实现学习者角色，该角色将负责将选择的值通知其他所有人。

在比特币白皮书中，中本聪提出了一种非常简单的拜占庭容错共识算法，也被称为中本聪共识。它基本上是一个随机的共识协议，它使用“工作证明”的概念来定义哪个过程有权合法地决定一个值。

这种工作操作的证明是不对称的，很难得出结论，但很容易验证。这是实现作为协议基础的功能性随机行为所必需的，否则进程将很难就建议值的有效性达成一致。

中本聪共识有自己的术语。与“价值”不同，流程寻求在数据“块”上达成共识。随着协议执行的推进，一组确定的数据块形成了一个“链”，每个新块都加强了前一个链块。传递块上的工作证明以使进程向网络建议该块的行为称为“挖掘”。

在每一轮r处，诚实的进程尝试在其观察到的最长链(r轮−1结束时)的顶部挖掘新块(其中平局可以任意断开)。这通常被称为最长链规则。

在每轮r处，诚实的进程确认一个块，如果它采用的最长链包含该块以及至少k个其他更高高度的块。这有时被称为k深度确认规则。

K深度确认规则的目的是将进程决定不确定/易失性数据块的机会减少到可以忽略的概率。

尽管Nakamoto共识协议形式简单，但它需要相当数量的代码来实现块挖掘和区块链管理逻辑。以下是我的实现顶层代码：

受保护的覆盖无效提议(实例r){ThreadManager。Start(()=>；{var b=MineBlock(R)；if(b！=null){ProcessBlock(r，b)；Broadcast(r，MessageType.。Propose，b)；}})；}public Override void bind(Instance R){WaitMessage(r，MessageType.。建议，msg=>；{var b=msg.。值为Block；ProcessBlock(r，b)；})；}Private void ProcessBlock(实例r，块b){if(b.。VerifyPoW()){var newChain=AddNewChain(B)；if(IsKDeep(NewChain)&；&；！IsTerminated(R)){Terminate(r，GetBlockAt(newChain，k))。值)；Committee Chain(NewChain)；}。

由于挖掘块是一项耗时的操作，因此它是在线程内执行的，与前面描述的其他协议不同，该建议。

.