分布式与一致性协议之拜占庭将军问题(一)

拜占庭将军问题

概述

拜占庭将军问题其实是借拜占庭将军故事展现了分布式共识问题,探讨和论证了解决的办法。实际上,拜占庭将军问题是分布式领域最复杂的一个容错模型,一旦搞懂了它,久能掌握分布式共识问题的解决思路,还能更深刻地理解常用的共识算法,这样在设计分布式系统的时候,就能根据场景特点,更好地选择或者设计合适的算法

什么是拜占庭将军问题?

以战国时期六国抗秦的故事为主线串联

苏秦的困境

战国时期,齐、楚、燕、赵、魏、秦七雄并立,后来秦国的势力不断强大,成为东方六国的共同威胁。于是这六个国家决定联合起来,全力抗秦,以免被秦国各个击破。一天,苏秦作为合纵长,挂六国相应,带着六国的军队叩关函谷,驻军在秦国边境,为围攻秦国做准备。但是,因为各国军队分别驻扎在秦国边境的不同地方,所以军队之间只能通过信使互相联系,这时,苏秦面临一个很严峻的
问题:如何同意作战计划?

万一一些诸侯国暗通秦国,发送误导性的作战信息,怎么办?如果心事被敌人截杀,甚至被间谍替换了,又该怎么办?这些都会导致自己的作战计划被扰乱,出现有的诸侯国在进攻,有的诸侯国在撤退的情况,这时,秦国一定会趁机出兵,把它们逐一击破。

所以,如果达成公式,指定统一的作战计划呢?
这个问题其实是拜占庭将军问题的一个简化表述,也即一个典型的公式难题:如果在可能有误导信息的情况下,采用合适的通信机制,让多个将军达成公式,制订一致的作战计划呢?

二忠一叛难题

为了便于理解和层层深入,先假设只有3个国家要攻打秦国,这3个国家的三位将军,分别叫齐、楚、燕。同时因为很强大,所以只有3个国家半数以上的将军都参与进攻,才能击败敌人(假设),且在这个期间,将军们彼此之间需要通过信使传递消息,待协商一致之后,才能在同一是按点发动进攻。

例子
  • 举个例子。这3位将军各自一脸严肃地决定明天是进攻还是撤退,并让信使传递消息,按照"少数服从多数"的原则投票决定,两个人意见一致就可以了:
    1.齐根据侦察情况决定撤退
    2.楚和燕根据侦察信息,决定进攻

可是,问题来了:一旦有人暗通秦国,就会出现作战计划不一致的情况。比如齐向楚、燕分别发送"撤退"的消息,燕向齐和楚发送"进攻"的消息。撤退:进攻 = 1:1,无论楚投进攻还是撤退,都会成为2:1,这时候还是会形成一个一致的作战方案。

但是,楚这个叛将在暗中配合秦国,让信使向齐发送了"撤退",向燕发送了"进攻",那么:
1.燕看到的是,撤退:进攻=1:2
2.齐看到的是,撤退:进攻=2:1
如图所示,按照少数服从多数的原则,燕单独进攻秦军,最后的结果当然是燕寡不敌众,被秦军打败了。在这里可以看到,叛将通过发送误导信息,非常轻松地干扰了齐和燕的作战计划,导致两位终程将军被秦军逐一击破。这也是常说的二忠一叛难题
在这里插入图片描述
在这里插入图片描述

口信消息。该如何处理呢?

先来说第一个解决办法。首先,3位将军都分拨一部分军队,由苏秦率领,苏秦参与作战计划讨论并执行作战指令。这样,3位将军的作战讨论就变为了4位将军的作战计划,这能够增加讨论中忠诚将军的数量。然后,4位将军约定了,如果没有受到命令,就执行预设的命令,比如
“撤退”。除此之外,它们还约定一些流程来发送作战信息、执行作战指令,比如,进行两轮作战信息协商。为什么要进行两轮协商呢?后面再解释。

  • 第一轮:
    1.先发送作战信息的将军作为指挥官,其他将军作为副官
    2.指挥官将他的作战信息发送给每位副官
    3.每位副官将从指挥官处收到的作战信息作为他的作战指令;如果没有收到作战信息,则把默认的"撤退"作为
    作战指令
  • 第二轮:
    1.除了第一轮的指挥官外,剩余的3位将军将分别作为指挥官,向另外两位将军发送作战信息。
    2.然后,这3位将军按照少数服从多数的原则,执行收到的作战指令

为了更直观地理解苏秦地整个解决方案,接下来将演示作战信息的协商过程。会分别以忠将和叛将先发送作战信息为例来完整地演示叛将对作战计划干扰破坏的可能性

  • 首先是3位忠将先发送作战信息的情况。
    为了演示方便,假设苏秦先发起作战信息,作战指令是"进攻"。那么在第一轮作战信息协商中,苏秦向齐、楚、燕发送作战指令"进攻",如图所示
    在这里插入图片描述
  • 在第二轮作战信息协商中,齐、楚、燕分别作为指挥官,向另外两位将军发送作战信息"进攻",因为楚已经叛变了,所以,为了干扰作战计划,它会发送"撤退"作战指令,如图所示在这里插入图片描述
  • 最终,齐和燕收到的作战信息都是"进攻、进攻、撤退",按照烧出服从多数的原则,齐、燕和苏秦一起执行作战指令"进攻",实现了作战计划的一致性,保证了作战的胜利。那么如果是叛将楚先发送作战信息,干扰作战计划,结果是否会有所不同?在第一轮作战信息协商中,楚向苏秦发送指令"进攻",向齐、燕发送作战指令"撤退",如图所示
    在这里插入图片描述
  • 然后在第二轮作战信息协商中,苏秦、齐、燕分别作为指挥官,向另外两位将军发送作战信息,如图所示最终,苏秦、齐和燕收到的作战信息都是"撤退、撤退、进攻",按照少数服从多数的原则,苏秦、齐和燕执行作战指令"撤退",实现了作战计划的一致性。也就是说,无论叛将楚如何捣乱,苏秦、齐、和燕都会执行一致的作战计划,从而保证作战的胜利。
    在这里插入图片描述
  • 这个解决办法其实是在兰伯特在论文"The Byzantine Generals Problem"中提到的口信问题型拜占庭问题之解(A Solution with Oral Message):如果叛将认数位m,将军任务不能少于3m+1,那么拜占庭将军问题就能解决了,不过,作者在论文中没有讲清除一些细节:

这个算法有个前提,也就是叛将认数m,或者说能容忍的叛将数m是已知晓的。在这个算法中,叛将数m决定了递归循环的次数(也就是说,叛将数m决定了将军们要在多少轮作战信息协商),既m+1轮(例如这里只有楚是叛将,所以进行了两轮),从另一个角度理解:n位将军,最多能容忍(n-1)/3位叛将

该算法虽然能解决拜占庭将军问题,但它有一个限制,如果叛将认数为m,那么将军总人数必须不小于3m+1.在二忠一叛欸度问题中,在存在1位叛将的情况下,必须增加1位将军,将3位将军的协商共识转换位4位将军的协商共识,这样才能实现忠诚将军的一致性作战计划,那么,有没有什么办法可以在不增加将军认数的情况下之解解决二忠一叛的难题呢?

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/565330.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

NTLM认证

文章目录 1.概念(1) 本地认证(2) SAM(3) NTLM Hash(4) NTLM 和 NTLM Hash(5) NTLM v2 1.概念 (1) 本地认证 Windows不存储用户的明文密码,它会将用户的明文密码经过加密后存储在 SAM (Security Account Manager Database,安全账号管理数据库)中。 (2)…

Marching Cubes算法

Marching Cubes算法 1. 简介2. 算法原理的理解2.1 如何找到面经过的这些小块(六面体)?2.2 找到后,如何又进一步的找到面与这些小块(六面体)的交点;2.3 这些交点按照怎么的拓扑连接关系连接,是怎么操作的? 3. 总结4. 参…

【链表】Leetcode 两数相加

题目讲解 2. 两数相加 算法讲解 我们这里设置一个头结点,然后遍历两个链表,使用一个flag记录相加的结果和进位,如果两个链表没有走到最后或者进位不等于0,我们就继续遍历处理进位;如果当前的链表都遍历完成了&#x…

基于springboot实现的摄影跟拍预定管理系统

开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7(一定要5.7版本) 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven…

【系统分析师】多媒体技术与知识产权标准化

文章目录 一、多媒体技术1、音频2、图像3、媒体的分类4、有损压缩和无损压缩5、多媒体标准 二、知识产权标准化1、保护范围和对象2、保护期限3、知识产权人确定4、侵权判定5、标准化 一、多媒体技术 1、音频 # 声音文件格式 .wav .mp3 .ra .mid .snd .au .aif .voc2、图像 # 彩…

一招下载transformers真不用网上那些教程(我试了1*mol多次才知道)

pip很多是2 然而!!!!!!!!!!!!!!!!!!!!…

ASP.NET大文件分片上传

ASP.NET大文件分片上传,C#上传大型视频文件到服务器,解决方案,用C# 实现断点续传 (HTTP),ASP.NET实现文件夹的上传和下载,.NET使用WEBUPLOADER做大文件的分块和断点续传,ASP.NET实现文件上传和下载,完美解决…

fastgpt、dify功能分析比较

目录 前言 一、dify、fastgpt是什么? 二、同场pk 1.大模型接入 2.chat(最简应用) 3.发布应用 4.知识库 5.workflow 6.其他 三、一些point记录 总结 前言 现在都开始AI应用开发,何谓AI应用,起码要和AI大模型…

13-LINUX--消息队列

一.消息队列 1.消息队列:消息队列为一个进程向另一个进程发送一个数据块提供了条件,每个数据块会包含一个类型。 2.相关函数 1>.msgget(key_t key,int msgflg) : 创建消息队列 2>. msgsnd:把消息添加到消息队列 3>.msgrcv &#xf…

【iOS开发】(四)react Native第三方组件五个20240419-20

react native 外的 第三方组件 目录标题 react native 外的 第三方组件(一)与rn核心组件的使用步骤区别:(二)第三方组件概览1 WebView2 Picker3 Swiper4 AsyncStorage5 Geolocation6 Camera (三)详细学习1 WebViewCoco…

C语言 分支控制语句之 if

然后 我们来说 流程控制语句之 if 选择控制结构 是通过 分支语句来实现的 其中 包括 单分支选择语句通过 (if) 来实现 双分支语句通过 (if) 和 (else) 实现 多分支语句通过 (if) (else if) (else) 实现 对于单分支来讲 它控制的语句就是 要嘛做 要嘛不做 好比如 放假了 你是…

MySQL基础之单表操作(定义DDL,增删改DML,查DQL)

目录 一、概述1.1 什么是数据库1.2 连接MySQL1.3 数据模型1.4 SQL语句的分类1.5 数据类型 二、数据库设计-DDL2.1 数据库层面2.2 数据表层面创建表约束查询修改add,modify,change,drop,rename删除 三、数据库操作-DML3.1 添加数据insert3.2 修改数据update3.3 删除数据delete 四…

插值与重采样在AI去衣技术中的关键作用

在人工智能(AI)的众多应用中,去衣技术作为一种新兴的图像处理技术,逐渐引起了广泛关注。这项技术不仅涉及复杂的计算机视觉和深度学习算法,还需要对图像处理中的插值与重采样技术有深入的理解。本文将详细探讨插值与重…

霸气归来,AKG N9 Hybrid头戴式降噪耳机震撼发布!手边的“大耳”瞬间不香了?

自1947年Rudolf Grike博士和Ernst Pless先生在“音乐之都”维也纳创立AKG以来,品牌已经走过77载辉煌历程,其产品被广泛应用于全球各大巡回演出和录音棚中,为全球音乐爱好者和专业人士提供了无数优质的声音体验。 近日,AKG再度以王…

(一)Java EE企业级应用开发实战之Servlet教程——JDK安装

首先打开清华大学开源软件镜像站,清华大学开源镜像网站地址为: https://mirrors.tuna.tsinghua.edu.cn/ 打开该地址后的界面显示如下图所示 找到8版本对应的SDK安装包,我现在用的开发机器是Windows,所以我找的是Windows对应的版本…

手机文件怎么传给商家打印?

在数字化时代,手机已经成为我们生活和工作中不可或缺的工具。当需要将手机中的文件传给商家打印时,传统的打印店往往要求通过微信等社交软件传输文件,这种方式非常操作繁琐。那么,手机文件怎么传给商家打印呢?琢贝云打…

Kotlin语法快速入门-函数(4)

Kotlin语法快速入门-函数(4) 文章目录 Kotlin语法快速入门-函数(4)四、函数1、函数定义2、infix关键字3、参数省略4、函数类型参数5、多参数--vararg 四、函数 1、函数定义 fun 函数名(参数: 类型) :返回值类型{//函…

“EDM邮件营销”如何构建企业获客增长新赛道

在这个瞬息万变的数字时代,企业的营销策略不断进化,以求在激烈的市场竞争中脱颖而出。其中,“EDM(Electronic Direct Mail)邮件营销”作为一项经典且高效的营销手段,正借助先进的技术力量,重新焕…

网络常识!!!

网络常识!!! 一:网络的发展史二:关键的概念三:IP地址四:端口号二级目录二级目录二级目录二级目录三级目录 一:网络的发展史 从游戏方面发展历程进行理解: 从单机游戏-----游戏支持局域网对战-------游戏支持广域网对战-------移动端 (1)局域网对战:在同一个网吧里,不同的游戏…

stable diffusion本地部署@win10

一键无脑安装stable-diffusion-webui stable diffusion是当前非常出色的文生图模型,要优于以前gan文生图模型。现在有了stable-diffusion-webui软件,可以一键安装,大大简化了操作难度。本文档就是stable-diffusion-webui在windows 10上的安装…