共识机制

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

共识机制

编辑

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

问题描述

编辑

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

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

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

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

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

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

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

计算的模型

编辑

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

共识机制

具有直接或可转移认证的通信通道

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

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

内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/193142/

(1)
词条目录
  1. 共识机制
  2. 问题描述
  3. 计算的模型
  4. 具有直接或可转移认证的通信通道

轻触这里

关闭目录

目录