拜占庭将军问题

✍ dations ◷ 2025-06-07 17:59:00 #分布式计算,计算机科学,理论计算机科学,计算理论,容错

拜占庭将军问题(Byzantine Generals Problem),是由莱斯利·兰波特在其同名论文中提出的分布式对等网络通信容错问题。

在分布式计算中,不同的计算机通过通讯交换信息达成共识而按照同一套协作策略行动。但有时候,系统中的成员计算机可能出错而发送错误的信息,用于传递信息的通讯网络也可能导致信息损坏,使得网络中不同的成员关于全体协作的策略得出不同结论,从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

莱斯利·兰波特在其论文中描述了如下问题:

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题,将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果,因此各位将军必须通过投票来达成一致策略,即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向,他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军,这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统的问题在于,将军中可能出现叛徒,他们不仅可能向较为糟糕的策略投票,还可能选择性地发送投票信息。假设有9位将军投票,其中1名叛徒。8名忠诚的将军中出现了4人投进攻,4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻,而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来,投票结果是5人投进攻,从而发起进攻;而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

由于将军之间需要通过信使通讯,叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下,也不能排除信使被敌人截杀,甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。

假使那些忠诚(或是没有出错)的将军仍然能通过多数决定来决定他们的战略,便称达到了拜占庭容错。在此,票都会有一个默认值,若消息(票)没有被收到,则使用此默认值来投票。

上述的故事映射到计算机系统里,将军便成了计算机,而信差就是通信系统。虽然上述的问题涉及了电子化的决策支持与信息安全,却没办法单纯的用密码学与数字签名来解决。因为电路错误仍可能影响整个加密过程,这不是密码学与数字签名算法在解决的问题。因此计算机就有可能将错误的结果提交去,亦可能导致错误的决策。

在1982年的论文中提过几个解决方案。方案中把问题往下拆解,认为在“拜占庭将军”的问题可以在“军官与士官的问题”里解决,以降低将军问题的发生。而所谓的“军官与士官的问题”,就是探讨军官与他的士官是否能忠实实行命令。

此外,1980年代还有其他用来达到拜占庭容错的架构被提出,如:FTMP、MMFCS与 SIFT。

1999年,卡斯托(Miguel Castro)与李斯克夫(Barbara Liskov)提出了实用拜占庭容错(PBFT)算法。该算法能提供高性能的运算,使得系统可以每秒处理成千的请求,比起旧式系统快了一些。

而在PBFT之后,许多用于拜占庭容错(BFT)的通信协议也被提出来改善其通信的强健性与效率。比如Q/U、HQ、Zyzzyva与ABsTRACTs...,用来提升效率。而Aardvark与RBFT是用来加强强健性。另外,Adapt则使用原有的BFT协议做调适,以强化其效率与强健性。BFT协议更可以借由加入可任务的单元,以减少发出副本的次数。比如:A2M-PBFT-EA与MinBFT。

在分布式对等网络中需要按照共同一致策略协作的成员计算机即为问题中的将军,而各成员计算机赖以进行通讯的网络链路即为信使。拜占庭将军问题描述的就是某些成员计算机或网络链路出现错误、甚至被蓄意破坏者控制的情况。

在点对点式数字货币系统比特币里,比特币网络的运作是平行的(parallel)。各节点与终端都运算著区块链来达成工作量证明(PoW)。工作量证明的链接是解决比特币系统中拜占庭问题的关键,避免有问题的节点(即前文提到的“反叛的将军”)破坏数字货币系统里交易帐的正确性,是对整个系统的运行状态有着重要的意义。

在一些飞行器(如波音777)的系统中也有使用拜占庭容错。而且由于是即时系统,容错的功能也要能尽快回复,比如即使系统中有错误发生,容错系统也只能做出一微秒以内的延迟。

一些航天飞机的飞行系统甚至将容错功能放到整个系统的设计之中。

拜占庭容错机制是将收到的消息(或是收到的消息的签名)转交到其他的接收者。这类机制都假设它们转交的消息都可能念有拜占庭问题。在高度安全要求的系统中,这些假设甚至要求证明错误能在一个合理的等级下被排除。当然,要证明这点,首先遇到的问题就是如何有效的找出所有可能的、应能被容错的错误。这时候会试着在系统中加入错误插入器。

相关

  • 高雄荣民总医院坐标:22°40′46″N 120°19′25″E / 22.67942°N 120.32368°E / 22.67942; 120.32368高雄荣民总医院,简称高雄荣总(英语:Kaohsiung Veterans General Hospital),位于中华民国高
  • 邝宇平邝宇平(1932年11月9日-),生于北京,籍贯广东台山,中国理论物理学家,兰州大学、清华大学教授。1955年毕业于北京大学物理系。2003年当选为中国科学院院士。
  • International Agency for Research on Cancer国际癌症研究机构(英语:International Agency for Research on Cancer,简称IARC)是世界卫生组织下属的一个跨政府机构,办公地点设在法国的里昂。该机构的主要任务是进行和促进对
  • 降伏文书《日本投降书》(英语:Japanese Instrument of Surrender; 日语:降伏文書/こうふくぶんしょ Kōfukubunsho)是大日本帝国于1945年9月2日在美国海军战列舰密苏里号上所签署之投降
  • 反质子反质子(英语:antiproton)是质子的反粒子,其质量及自旋与质子相同,但电荷及磁矩则与质子相反,带有与电子相同的负电荷。保罗·狄拉克在他的1933年诺贝尔物理学奖演讲中预言反质子的
  • 行唐县行唐县是中国河北省石家庄市所辖的一个县。战国赵惠文王八年,建南行唐城,城址位于今故郡村;西汉置南行唐县,属常山国,东汉、曹魏、西晋皆因之。北魏改名行唐,太和十四年于此设置唐
  • 拉格朗日力学拉格朗日力学(英语:Lagrangian mechanics)是分析力学中的一种,于1788年由约瑟夫·拉格朗日所创立。拉格朗日力学是对经典力学的一种的新的理论表述,着重于数学解析的方法,并运用最
  • 宾夕法尼亚大学诺贝尔奖得主列表诺贝尔奖由瑞典皇家科学院、瑞典学院、卡罗琳学院和挪威诺贝尔委员会每年颁发一次,分别授予在化学、物理学、文学、和平、生理学或医学和经济学领域作出杰出贡献的人士。除经
  • 地球战场《地球战场》(英语:)是美国科幻作家兼山达基教(科学教)创办人L·罗恩·贺伯特出版于1982年的一部科幻小说。贺柏特本人亦曾为亲自这部小说创作了一张名为“”的专辑,这张专辑在198
  • 查戈斯群岛查戈斯群岛(Chagos Archipelago),是印度洋中部的一个群岛,由7个环礁共60余岛组成,位于马尔代夫正南方约500公里处,为英属印度洋领地的主要组成部分。群岛总面积63.17平方公里,主岛