拜占庭将军问题(Byzantine failures),是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息
丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的
,或不存在本问题。
故事是这样的,拜占庭帝国想要进攻一个强大的敌人,为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国,但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因,这10支军队不能集合在一起单点突破,必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算,除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周,依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是,他们不确定他们中是否有叛徒,叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下,“忠诚”的拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商,达成正确的一致,从而赢取战斗?这就是著名的拜占庭将军问题。
一群将军想要实现某一个目标(一致进攻或者一致撤退),但是单独行动行不通,必须合作, 达成共识;由于叛徒的存在,将军们不知道应该如何达到一致。注意,这里“一致性”才是拜占庭将军问题探讨的内容。
将军问题
拜占庭将军问题是一个协议问题,拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的,并且将军中存在叛徒。叛徒可以任意行动以达到以下目标:欺骗某些将军采取进攻行动;促成一个不是所有将军都同意的决定,如当将军们不希望进攻时促成进攻行动;或者迷惑某些将军,使他们无法做出决定。如果叛徒达到了这些目的之一,则任何攻击行动的结果都是注定要失败的,只有完全达成一致的努力才能获得胜利。
拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或断开以及遭到恶意攻击,计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效,并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征,t表示算法可以应付的错误进程数。很多经典算法问题只有在n ≥ 3t+1时才有解,如拜占庭将军问题,其中n是系统中进程的总数。
失效
所谓拜占庭失效指一方向另一方发送消息,另一方没有收到,或者收到了错误的信息的情形。
在容错的分布式计算中,拜占庭失效可以是分布式系统中算法执行过程中的任意一个错误。这些错误被统称为“崩溃失效”和“发送与遗漏式失效”。当拜占庭失效发生时,系统可能会做出任何不可预料的反应。
这些任意的失效可以粗略地分成以下几类:
进行算法的另一步时失效,即崩溃失效;
无法正确执行算法的一个步骤;
执行了任意一个非算法指定的步骤
各个步骤由各进程执行,算法就是由这些进程执行的。一个错误的进程是在某个点出现了上述情况的进程。没有出现错误的进程是正确的进程。
解决算法
拜占庭问题的最初描述是:n 个将军被分隔在不同的地方,忠诚的将军希望通过某种协议达成某个命令的一致(比如一起进攻或者一起后退)。但其中一些背叛的将军会通过发送错误的消息阻挠忠诚的将军达成命令上的一致。Lamport 证明了在将军总数大于3m ,背叛者为m 或者更少时,忠诚的将军可以达成命令上的一致。
为了保证上面的需求,必须满足下面两个条件:
1. 每两个忠诚的将军必须收到相同的值 v(i)(v(i)是第i 个将军的命令)
2. 如果第i 个将军是忠诚的,那么他发送的命令和每个忠诚将军收到的v(i)相同
为了简化以上模型,我们使用一个将军发送命令给多个副官的形式来证明,发送命令的将军称为发令者,接收命令的将军为副官,那么上面的两个条件可以表述为:
IC1. 所有忠诚的副官遵守相同的命令
IC2. 如果发出命令的将军是忠诚的,那么所有忠诚的副官遵守司令(发出命令的将军)的命令
特别提示:发送命令的每次只有一个将军,将其命令发送给n-1 个副官。m 代表叛国者的个数,因为将军总数为n,所以副官总数为n-1 个。IC2 中副官遵守实际上是指忠诚的将军能够正确收到忠诚将军的命令消息。
相关推荐
拜占庭将军问题是分布式计算领域中的一个经典问题,它抽象地描述了在一个可能存在故障节点的分布式系统中,如何达成一致性的问题。该问题源自于一个古代战争的比喻:拜占庭军队的将军们必须通过不完全可靠的信使来...
拜占庭将军问题,源自古代拜占庭帝国的军事通讯难题,是分布式计算领域中的一个经典问题。在该问题中,一群将军分布在敌人的包围中,他们必须通过不完全可靠的信使来协调进攻或撤退的决定。由于存在叛徒(即故障节点...
【拜占庭将军问题】是分布式系统中一个重要的理论模型,由Leslie Lamport, Robert Shostak,和Marshall Pease在1982年提出。这个问题旨在探讨在不可靠的通信环境下,如何确保一组分散的将军(代表分布式系统的节点)...
拜占庭将军问题的核心在于如何在不可靠的网络环境中,尤其是在存在恶意节点(叛徒)的情况下,确保系统的一致性和正确性。在拜占庭将军问题的场景中,将军们需要达成一种共识,即决定何时进攻或撤退,而这个共识必须...
经过翻译和校对的拜占庭将军问题。
此程序用来模拟工作量证明链如何解决拜占庭将军问题,使用Objective-C语言,需要使用Xcode开发工具运行并执行演示,演示结果打印在Xcode控制台。 压缩包解压密码:liangjingcheng
拜占庭问题 拜占庭问题最早由 Leslie Lamport 等学者于 1982 年在论文《The Byzantine Generals Problem》中正式...拜占庭问题即讨论在此情况下,如何让忠诚的将军们能达成行动的一致。 拜占庭问题(Byzantine Probl
拜占庭将军问题(Byzantine failures),是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠...
该资源摘要信息对区块链技术的发展历史进行了详细的解读,包括共识简史、拜占庭将军问题、分布式系统、共识算法、拜占庭将军问题的理论证明、分布式系统与拜占庭将军问题、Paxos 共识算法等知识点。
拜占庭将军问题是分布式计算中的经典问题对系统针对任意对抗性故障的恢复能力进行建模。 现有的该问题的解决方案往往非常复杂,其中许多采用某种形式的递归。 本文提出了一种解决该问题的新算法。 一个非常简单的...
### 拜占庭将军问题解析 #### 一、引言与背景介绍 拜占庭将军问题是由Leslie Lamport、Robert Shostak和Marshall Pease在SRI International共同研究提出的一个理论模型。该问题主要探讨了在分布式计算系统中如何...
### 拜占庭将军问题解析 #### 一、引言与背景 拜占庭将军问题(The Byzantine Generals Problem)是计算机科学领域中一个经典的分布式系统问题,由Leslie Lamport、Robert Shostak和Marshall Pease在1982年提出。...
### 拜占庭将军问题解析 #### 一、引言与背景 拜占庭将军问题(The Byzantine Generals Problem)是由Leslie Lamport、Robert Shostak和Marshall Pease三位计算机科学家在1982年提出的一个理论模型。这一问题主要...
TrInc(Trust in tiny Incumbent)是针对这一问题提出的一种解决方案,它强调在大规模分布式系统中引入小型可信硬件,以应对拜占庭将军问题和equivocation(矛盾性)问题。这篇论文的作者包括John R. Douceur、Jacob...