共识机制

分布式计算和多代理系统中的一个基本问题是，在存在一些故障进程的情况下，实现系统的整体可靠性。这往往需要协调进程来达成共识，或者就计算过程中需要的一些数据值达成一致。共识的应用实例包括同意以何种顺序向数据库提交哪些事务、状态机复制和原子广播。现实世界中经常需要共识的应用包括云计算、时钟同步、PageRank、意见形成、智能电网、状态估计、无人机（以及一般的多个机器人/代理）的控制、负载平衡、xxx等。

共识问题要求一些进程（或代理）之间就单个数据值达成协议。一些进程（代理）可能会失败或在其他方面不可靠，所以共识协议必须是容错的或有弹性的。这些进程必须以某种方式提出他们的候选值，相互沟通，并就单一的共识值达成一致。

共识问题是多Agent系统控制中的一个基本问题。产生共识的一种方法是让所有进程（代理）就一个多数值达成一致。在这种情况下，多数值要求至少有一个超过一半的可用票数（每个进程都有一票）。然而，一个或多个有问题的进程可能会歪曲结果，从而可能无法达成共识或不正确地达成共识。

解决共识问题的协议被设计用来处理数量有限的有缺陷的进程。这些协议必须满足一些要求才能发挥作用。例如，一个微不足道的协议可以让所有进程输出二进制值1。这是不有用的，因此要求被修改为输出必须在某种程度上取决于输入。也就是说，一个共识协议的输出值必须是某个进程的输入值。另一个要求是，一个进程只能决定一次输出值，而且这个决定是不可撤销的。如果一个进程没有经历过失败，那么它在执行过程中被称为正确的。一个可以容忍停止失败的共识协议必须满足以下特性。

终止最终，每个正确的进程都会决定一些值。完整性如果所有正确的进程都提出了相同的值v {displaystyle v}，那么任何正确的进程都必须决定v {displaystyle v}。协议每个正确的进程必须同意相同的值。

根据应用情况，完整性定义的变体可能是合适的。例如，一个较弱的完整性类型是决策值必须等于某个正确流程提出的值--不一定是所有的流程。在文献中还有一个被称为有效性的条件，它指的是一个进程发送的消息必须被传递的属性。

一个能够正确保证n个进程之间达成共识的协议，其中最多只有t个进程失败，这个协议被称为t-resilient。

在评估共识协议的性能时，有两个感兴趣的因素是运行时间和消息复杂性。运行时间用大O表示，即消息交换的轮数，是一些输入参数（通常是进程的数量和/或输入域的大小）的函数。消息复杂度是指协议产生的消息流量的数量。其他因素可能包括内存的使用和消息的大小。

不同的计算模型可以定义一个共识问题。一些模型可以处理全连接图，而另一些模型可以处理环和树。在一些模型中，允许消息认证，而在其他模型中，进程是完全匿名的。共享内存模型，其中进程通过访问共享内存中的对象进行通信，也是一个重要的研究领域。

在大多数通信协议模型中，参与者通过认证的通道进行通信。这意味着消息不是匿名的，接收者知道他们收到的每条消息的来源。有些模型假设了一种更强的、可转移的认证形式，即每条消息都由发送者签名，这样接收者不仅知道每条消息的直接来源，还知道最初创建该消息的参与者。这种更强的认证类型是由数字签名实现的，当这种更强的认证形式可用时，协议可以容忍更多的故障。

这两种不同的认证模式通常被称为口头交流和书面交流模式。在口头交流模式中，信息的直接来源是已知的，而在更强的书面交流模式中，每一步接收者不仅了解信息的直接来源。