湖南省房屋和城乡建设部网站,信息流推广的竞价机制是,做设计最好的参考网站,蓬莱网站建设公司报价分布式理论#xff1a;拜占庭将军问题 介绍拜占庭将军的故事将军的难题 解决方案口信消息型拜占庭问题之解流程总结 签名消息型拜占庭问题之解 总结 介绍
拜占庭将军问题是对分布式共识问题的一种情景化描述#xff0c;由兰伯特于1082首次发表《The Byzantine Generals Prob… 分布式理论拜占庭将军问题 介绍拜占庭将军的故事将军的难题 解决方案口信消息型拜占庭问题之解流程总结 签名消息型拜占庭问题之解 总结 介绍
拜占庭将军问题是对分布式共识问题的一种情景化描述由兰伯特于1082首次发表《The Byzantine Generals Problem》中提及它是分布式领域最复杂的一个容错模型 它描述了如何在存在恶意行为的情况下使分布式系统达成一致了解拜占庭问题对于掌握分布式共识问题具有深刻意义。
拜占庭将军的故事
拜占庭帝国的几只军队此时驻扎在敌人的城墙之外每个军队都有专门的将军来指挥但因为各只军队分别驻扎在敌城的不同地方将军之间只能通过信使来相互联系。再某天观察完敌情之后将军们决定制定一个共同的作战计划同时进攻或者撤退因为敌人非常强大至少有半数的军队同时发动进攻时才能取得胜利。此时将军们遇到了难题如何统一大家的作战计划
将军的难题
首先如果将军之间都是忠诚于拜占庭帝国的那么很容易统一作战方案只需要所有的将军之间彼此通信交换自己的意见进攻还是撤退最后所有的将军根据 少数服从多数 的原则来行动。
这里假设只有三支军队A, B, C, 其中 A, B 认为应该进攻C认为应该撤退将军之间的通信如下: #mermaid-svg-D4XvwoOJ5ZkIyClb {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-D4XvwoOJ5ZkIyClb .error-icon{fill:#552222;}#mermaid-svg-D4XvwoOJ5ZkIyClb .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-D4XvwoOJ5ZkIyClb .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-D4XvwoOJ5ZkIyClb .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-D4XvwoOJ5ZkIyClb .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-D4XvwoOJ5ZkIyClb .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-D4XvwoOJ5ZkIyClb .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-D4XvwoOJ5ZkIyClb .marker{fill:#333333;stroke:#333333;}#mermaid-svg-D4XvwoOJ5ZkIyClb .marker.cross{stroke:#333333;}#mermaid-svg-D4XvwoOJ5ZkIyClb svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-D4XvwoOJ5ZkIyClb .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-D4XvwoOJ5ZkIyClb .cluster-label text{fill:#333;}#mermaid-svg-D4XvwoOJ5ZkIyClb .cluster-label span{color:#333;}#mermaid-svg-D4XvwoOJ5ZkIyClb .label text,#mermaid-svg-D4XvwoOJ5ZkIyClb span{fill:#333;color:#333;}#mermaid-svg-D4XvwoOJ5ZkIyClb .node rect,#mermaid-svg-D4XvwoOJ5ZkIyClb .node circle,#mermaid-svg-D4XvwoOJ5ZkIyClb .node ellipse,#mermaid-svg-D4XvwoOJ5ZkIyClb .node polygon,#mermaid-svg-D4XvwoOJ5ZkIyClb .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-D4XvwoOJ5ZkIyClb .node .label{text-align:center;}#mermaid-svg-D4XvwoOJ5ZkIyClb .node.clickable{cursor:pointer;}#mermaid-svg-D4XvwoOJ5ZkIyClb .arrowheadPath{fill:#333333;}#mermaid-svg-D4XvwoOJ5ZkIyClb .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-D4XvwoOJ5ZkIyClb .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-D4XvwoOJ5ZkIyClb .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-D4XvwoOJ5ZkIyClb .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-D4XvwoOJ5ZkIyClb .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-D4XvwoOJ5ZkIyClb .cluster text{fill:#333;}#mermaid-svg-D4XvwoOJ5ZkIyClb .cluster span{color:#333;}#mermaid-svg-D4XvwoOJ5ZkIyClb div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-D4XvwoOJ5ZkIyClb :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 进攻 进攻 撤退 进攻 撤退 进攻 A B C 通过协商所有的将军最后的行为都是统一的进攻于是大破敌城 但是如果有将军私通敌国发送误导性的信息这样的共识协商还能保证作战计划统一吗答案无疑是否定的假设现在B将领是叛将故意给A,C发送不一样的信息情况会发生改变: #mermaid-svg-NsDWPwJAhGoRTz7d {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-NsDWPwJAhGoRTz7d .error-icon{fill:#552222;}#mermaid-svg-NsDWPwJAhGoRTz7d .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-NsDWPwJAhGoRTz7d .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-NsDWPwJAhGoRTz7d .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-NsDWPwJAhGoRTz7d .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-NsDWPwJAhGoRTz7d .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-NsDWPwJAhGoRTz7d .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-NsDWPwJAhGoRTz7d .marker{fill:#333333;stroke:#333333;}#mermaid-svg-NsDWPwJAhGoRTz7d .marker.cross{stroke:#333333;}#mermaid-svg-NsDWPwJAhGoRTz7d svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-NsDWPwJAhGoRTz7d .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-NsDWPwJAhGoRTz7d .cluster-label text{fill:#333;}#mermaid-svg-NsDWPwJAhGoRTz7d .cluster-label span{color:#333;}#mermaid-svg-NsDWPwJAhGoRTz7d .label text,#mermaid-svg-NsDWPwJAhGoRTz7d span{fill:#333;color:#333;}#mermaid-svg-NsDWPwJAhGoRTz7d .node rect,#mermaid-svg-NsDWPwJAhGoRTz7d .node circle,#mermaid-svg-NsDWPwJAhGoRTz7d .node ellipse,#mermaid-svg-NsDWPwJAhGoRTz7d .node polygon,#mermaid-svg-NsDWPwJAhGoRTz7d .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-NsDWPwJAhGoRTz7d .node .label{text-align:center;}#mermaid-svg-NsDWPwJAhGoRTz7d .node.clickable{cursor:pointer;}#mermaid-svg-NsDWPwJAhGoRTz7d .arrowheadPath{fill:#333333;}#mermaid-svg-NsDWPwJAhGoRTz7d .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-NsDWPwJAhGoRTz7d .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-NsDWPwJAhGoRTz7d .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-NsDWPwJAhGoRTz7d .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-NsDWPwJAhGoRTz7d .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-NsDWPwJAhGoRTz7d .cluster text{fill:#333;}#mermaid-svg-NsDWPwJAhGoRTz7d .cluster span{color:#333;}#mermaid-svg-NsDWPwJAhGoRTz7d div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-NsDWPwJAhGoRTz7d :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 进攻 进攻 撤退 撤退 撤退 进攻 A B C A看到的是撤退进攻 1 2 C看到的是撤退进攻 2 1 接下来按照少数服从多数的原则A会独自发动进攻当然最后会因为寡不敌众而被敌军消灭。可以看到叛将通过发送误导信息非常轻易的干扰了其他将军的作战计划导致忠于拜占庭帝国的将军被逐一击败这就是著名的两忠一叛难题。忠诚的将军该如何统一作战计划呢
解决方案
兰伯特的论文除了提出拜占庭将军之外也给出了两种解决拜占庭将军问题的算法
口信消息型解决方案签名消息型解决方案
接下来我会分别介绍这两种做法如果你觉得逻辑有点绕的话建议找张纸比划比划。
口信消息型拜占庭问题之解
口信型拜占庭之解的核心是选择出一个指挥官和进行多轮信息协商。下面来介绍具体的协商流程
流程
首先我们假设现在有A, B, C, D四位将军并且其中只有D为叛将。在这个解法之中我们首先要选择出一个将军作为指挥官其他的将军作为副将这里我们先让忠诚的将领A作为指挥官与先前的协商方式不同在这个算法中我们需要进行2次作战协商接下来来看两次协商的流程 第一轮由指挥官向所有的副将发送作战信息每位副官将从指挥官处收到的信息作为自己的作战指令 #mermaid-svg-bCVtQHqolCDOkxDL {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-bCVtQHqolCDOkxDL .error-icon{fill:#552222;}#mermaid-svg-bCVtQHqolCDOkxDL .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-bCVtQHqolCDOkxDL .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-bCVtQHqolCDOkxDL .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-bCVtQHqolCDOkxDL .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-bCVtQHqolCDOkxDL .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-bCVtQHqolCDOkxDL .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-bCVtQHqolCDOkxDL .marker{fill:#333333;stroke:#333333;}#mermaid-svg-bCVtQHqolCDOkxDL .marker.cross{stroke:#333333;}#mermaid-svg-bCVtQHqolCDOkxDL svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-bCVtQHqolCDOkxDL .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-bCVtQHqolCDOkxDL .cluster-label text{fill:#333;}#mermaid-svg-bCVtQHqolCDOkxDL .cluster-label span{color:#333;}#mermaid-svg-bCVtQHqolCDOkxDL .label text,#mermaid-svg-bCVtQHqolCDOkxDL span{fill:#333;color:#333;}#mermaid-svg-bCVtQHqolCDOkxDL .node rect,#mermaid-svg-bCVtQHqolCDOkxDL .node circle,#mermaid-svg-bCVtQHqolCDOkxDL .node ellipse,#mermaid-svg-bCVtQHqolCDOkxDL .node polygon,#mermaid-svg-bCVtQHqolCDOkxDL .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-bCVtQHqolCDOkxDL .node .label{text-align:center;}#mermaid-svg-bCVtQHqolCDOkxDL .node.clickable{cursor:pointer;}#mermaid-svg-bCVtQHqolCDOkxDL .arrowheadPath{fill:#333333;}#mermaid-svg-bCVtQHqolCDOkxDL .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-bCVtQHqolCDOkxDL .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-bCVtQHqolCDOkxDL .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-bCVtQHqolCDOkxDL .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-bCVtQHqolCDOkxDL .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-bCVtQHqolCDOkxDL .cluster text{fill:#333;}#mermaid-svg-bCVtQHqolCDOkxDL .cluster span{color:#333;}#mermaid-svg-bCVtQHqolCDOkxDL div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-bCVtQHqolCDOkxDL :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 进攻 进攻 进攻 A B C D 第二轮三位副将之间进行作战信息协商互相告知彼此指挥官发送的信息其中因为D是叛将他会告诉两个将军不同的信息来误导他们 #mermaid-svg-zzuha6f688u3YUyC {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-zzuha6f688u3YUyC .error-icon{fill:#552222;}#mermaid-svg-zzuha6f688u3YUyC .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-zzuha6f688u3YUyC .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-zzuha6f688u3YUyC .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-zzuha6f688u3YUyC .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-zzuha6f688u3YUyC .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-zzuha6f688u3YUyC .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-zzuha6f688u3YUyC .marker{fill:#333333;stroke:#333333;}#mermaid-svg-zzuha6f688u3YUyC .marker.cross{stroke:#333333;}#mermaid-svg-zzuha6f688u3YUyC svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-zzuha6f688u3YUyC .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-zzuha6f688u3YUyC .cluster-label text{fill:#333;}#mermaid-svg-zzuha6f688u3YUyC .cluster-label span{color:#333;}#mermaid-svg-zzuha6f688u3YUyC .label text,#mermaid-svg-zzuha6f688u3YUyC span{fill:#333;color:#333;}#mermaid-svg-zzuha6f688u3YUyC .node rect,#mermaid-svg-zzuha6f688u3YUyC .node circle,#mermaid-svg-zzuha6f688u3YUyC .node ellipse,#mermaid-svg-zzuha6f688u3YUyC .node polygon,#mermaid-svg-zzuha6f688u3YUyC .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-zzuha6f688u3YUyC .node .label{text-align:center;}#mermaid-svg-zzuha6f688u3YUyC .node.clickable{cursor:pointer;}#mermaid-svg-zzuha6f688u3YUyC .arrowheadPath{fill:#333333;}#mermaid-svg-zzuha6f688u3YUyC .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-zzuha6f688u3YUyC .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-zzuha6f688u3YUyC .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-zzuha6f688u3YUyC .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-zzuha6f688u3YUyC .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-zzuha6f688u3YUyC .cluster text{fill:#333;}#mermaid-svg-zzuha6f688u3YUyC .cluster span{color:#333;}#mermaid-svg-zzuha6f688u3YUyC div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-zzuha6f688u3YUyC :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 进攻 进攻 进攻 进攻 撤退 进攻 B C D A 可以发现虽然叛将像先前一样向两个将军发送了不同的信息但是BC根据少数服从多数的原则依旧可以做出和A一样的作战行为最后大破敌军。
也许你会想如果指挥官是叛将呢情况会变回糟糕吗答案是否定的即使指挥官是叛将所有的忠诚的将军依然可以统一作战行为我们假设叛将D作为指挥官先发送作战信息, 他会发送误导的错误信息试图让其中一位将领独自发动进攻 #mermaid-svg-Sz1flLkMuW0siVpS {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-Sz1flLkMuW0siVpS .error-icon{fill:#552222;}#mermaid-svg-Sz1flLkMuW0siVpS .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-Sz1flLkMuW0siVpS .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-Sz1flLkMuW0siVpS .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-Sz1flLkMuW0siVpS .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-Sz1flLkMuW0siVpS .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-Sz1flLkMuW0siVpS .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-Sz1flLkMuW0siVpS .marker{fill:#333333;stroke:#333333;}#mermaid-svg-Sz1flLkMuW0siVpS .marker.cross{stroke:#333333;}#mermaid-svg-Sz1flLkMuW0siVpS svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-Sz1flLkMuW0siVpS .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-Sz1flLkMuW0siVpS .cluster-label text{fill:#333;}#mermaid-svg-Sz1flLkMuW0siVpS .cluster-label span{color:#333;}#mermaid-svg-Sz1flLkMuW0siVpS .label text,#mermaid-svg-Sz1flLkMuW0siVpS span{fill:#333;color:#333;}#mermaid-svg-Sz1flLkMuW0siVpS .node rect,#mermaid-svg-Sz1flLkMuW0siVpS .node circle,#mermaid-svg-Sz1flLkMuW0siVpS .node ellipse,#mermaid-svg-Sz1flLkMuW0siVpS .node polygon,#mermaid-svg-Sz1flLkMuW0siVpS .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-Sz1flLkMuW0siVpS .node .label{text-align:center;}#mermaid-svg-Sz1flLkMuW0siVpS .node.clickable{cursor:pointer;}#mermaid-svg-Sz1flLkMuW0siVpS .arrowheadPath{fill:#333333;}#mermaid-svg-Sz1flLkMuW0siVpS .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-Sz1flLkMuW0siVpS .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-Sz1flLkMuW0siVpS .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-Sz1flLkMuW0siVpS .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-Sz1flLkMuW0siVpS .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-Sz1flLkMuW0siVpS .cluster text{fill:#333;}#mermaid-svg-Sz1flLkMuW0siVpS .cluster span{color:#333;}#mermaid-svg-Sz1flLkMuW0siVpS div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-Sz1flLkMuW0siVpS :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 进攻 撤退 撤退 D B C A 在第二轮的作战信息协商中三位忠诚的副将彼此之间互通指挥官发送的消息 #mermaid-svg-7ocP5LSsbeuqrT16 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-7ocP5LSsbeuqrT16 .error-icon{fill:#552222;}#mermaid-svg-7ocP5LSsbeuqrT16 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-7ocP5LSsbeuqrT16 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-7ocP5LSsbeuqrT16 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-7ocP5LSsbeuqrT16 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-7ocP5LSsbeuqrT16 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-7ocP5LSsbeuqrT16 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-7ocP5LSsbeuqrT16 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-7ocP5LSsbeuqrT16 .marker.cross{stroke:#333333;}#mermaid-svg-7ocP5LSsbeuqrT16 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-7ocP5LSsbeuqrT16 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-7ocP5LSsbeuqrT16 .cluster-label text{fill:#333;}#mermaid-svg-7ocP5LSsbeuqrT16 .cluster-label span{color:#333;}#mermaid-svg-7ocP5LSsbeuqrT16 .label text,#mermaid-svg-7ocP5LSsbeuqrT16 span{fill:#333;color:#333;}#mermaid-svg-7ocP5LSsbeuqrT16 .node rect,#mermaid-svg-7ocP5LSsbeuqrT16 .node circle,#mermaid-svg-7ocP5LSsbeuqrT16 .node ellipse,#mermaid-svg-7ocP5LSsbeuqrT16 .node polygon,#mermaid-svg-7ocP5LSsbeuqrT16 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-7ocP5LSsbeuqrT16 .node .label{text-align:center;}#mermaid-svg-7ocP5LSsbeuqrT16 .node.clickable{cursor:pointer;}#mermaid-svg-7ocP5LSsbeuqrT16 .arrowheadPath{fill:#333333;}#mermaid-svg-7ocP5LSsbeuqrT16 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-7ocP5LSsbeuqrT16 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-7ocP5LSsbeuqrT16 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-7ocP5LSsbeuqrT16 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-7ocP5LSsbeuqrT16 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-7ocP5LSsbeuqrT16 .cluster text{fill:#333;}#mermaid-svg-7ocP5LSsbeuqrT16 .cluster span{color:#333;}#mermaid-svg-7ocP5LSsbeuqrT16 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-7ocP5LSsbeuqrT16 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 进攻 进攻 撤退 撤退 撤退 撤退 B C A D 最终所有的将军收到的作战信息都是撤退撤退进攻根据少数服从多数的原则A, B, C将撤退达成统一的行为保证了作战计划的一致性。
总结
这个算法虽然可以保证无论叛将如何捣乱我们都能做出一行的行为但是这是有前提的。在兰伯特的论文中指出如果叛将人数为m将军人数不能少于3m1只有这样口信型拜占庭将军之解才能生效。或者说这个算法对于能容忍的叛将数m是已知的而且m决定了要执行多少次作战协商即 m 1 轮现在你知道为什么三忠一叛的场景中为什么我们要进行两次作战协商了。该结论具体的推导可以参考论文。
但是我们还是没能解决两忠一叛的问题因为忠诚的将军数量不够此时就可以考虑第二种拜占庭问题的解法了。
签名消息型拜占庭问题之解
签名消息型拜占庭问题之解的核心是信息要格外实现以下两个特性
将军的签名信息无法伪造对其签名信息的内容进行任何的修改都会被发现任何将军都能能力验证将军签名信息的真伪
这样两忠一叛难题就能够被解决了在这种算法下需要指挥官首先发动作战协商然后其余的将军彼此交换指挥官带来的消息。我们以A, B 为忠诚将军C为叛将来推导解释 首先假设A为首先发送信息的指挥官 #mermaid-svg-WHMbgc3YglyImUjG {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-WHMbgc3YglyImUjG .error-icon{fill:#552222;}#mermaid-svg-WHMbgc3YglyImUjG .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-WHMbgc3YglyImUjG .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-WHMbgc3YglyImUjG .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-WHMbgc3YglyImUjG .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-WHMbgc3YglyImUjG .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-WHMbgc3YglyImUjG .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-WHMbgc3YglyImUjG .marker{fill:#333333;stroke:#333333;}#mermaid-svg-WHMbgc3YglyImUjG .marker.cross{stroke:#333333;}#mermaid-svg-WHMbgc3YglyImUjG svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-WHMbgc3YglyImUjG .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-WHMbgc3YglyImUjG .cluster-label text{fill:#333;}#mermaid-svg-WHMbgc3YglyImUjG .cluster-label span{color:#333;}#mermaid-svg-WHMbgc3YglyImUjG .label text,#mermaid-svg-WHMbgc3YglyImUjG span{fill:#333;color:#333;}#mermaid-svg-WHMbgc3YglyImUjG .node rect,#mermaid-svg-WHMbgc3YglyImUjG .node circle,#mermaid-svg-WHMbgc3YglyImUjG .node ellipse,#mermaid-svg-WHMbgc3YglyImUjG .node polygon,#mermaid-svg-WHMbgc3YglyImUjG .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-WHMbgc3YglyImUjG .node .label{text-align:center;}#mermaid-svg-WHMbgc3YglyImUjG .node.clickable{cursor:pointer;}#mermaid-svg-WHMbgc3YglyImUjG .arrowheadPath{fill:#333333;}#mermaid-svg-WHMbgc3YglyImUjG .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-WHMbgc3YglyImUjG .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-WHMbgc3YglyImUjG .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-WHMbgc3YglyImUjG .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-WHMbgc3YglyImUjG .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-WHMbgc3YglyImUjG .cluster text{fill:#333;}#mermaid-svg-WHMbgc3YglyImUjG .cluster span{color:#333;}#mermaid-svg-WHMbgc3YglyImUjG div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-WHMbgc3YglyImUjG :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 进攻 进攻 A:进攻 A:撤退 A B C 因为将军的签名信息的伪造会被发现所以B收到C的作战请求的时候会发现A的作战请求已经被C修改B会执行A直接发送给他的进攻命令大破敌军。
如果是叛将C先发送作战信息结果也不会改变 #mermaid-svg-sGgZSaaa4gXVWJBZ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-sGgZSaaa4gXVWJBZ .error-icon{fill:#552222;}#mermaid-svg-sGgZSaaa4gXVWJBZ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-sGgZSaaa4gXVWJBZ .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-sGgZSaaa4gXVWJBZ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-sGgZSaaa4gXVWJBZ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-sGgZSaaa4gXVWJBZ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-sGgZSaaa4gXVWJBZ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-sGgZSaaa4gXVWJBZ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-sGgZSaaa4gXVWJBZ .marker.cross{stroke:#333333;}#mermaid-svg-sGgZSaaa4gXVWJBZ svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-sGgZSaaa4gXVWJBZ .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-sGgZSaaa4gXVWJBZ .cluster-label text{fill:#333;}#mermaid-svg-sGgZSaaa4gXVWJBZ .cluster-label span{color:#333;}#mermaid-svg-sGgZSaaa4gXVWJBZ .label text,#mermaid-svg-sGgZSaaa4gXVWJBZ span{fill:#333;color:#333;}#mermaid-svg-sGgZSaaa4gXVWJBZ .node rect,#mermaid-svg-sGgZSaaa4gXVWJBZ .node circle,#mermaid-svg-sGgZSaaa4gXVWJBZ .node ellipse,#mermaid-svg-sGgZSaaa4gXVWJBZ .node polygon,#mermaid-svg-sGgZSaaa4gXVWJBZ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-sGgZSaaa4gXVWJBZ .node .label{text-align:center;}#mermaid-svg-sGgZSaaa4gXVWJBZ .node.clickable{cursor:pointer;}#mermaid-svg-sGgZSaaa4gXVWJBZ .arrowheadPath{fill:#333333;}#mermaid-svg-sGgZSaaa4gXVWJBZ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-sGgZSaaa4gXVWJBZ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-sGgZSaaa4gXVWJBZ .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-sGgZSaaa4gXVWJBZ .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-sGgZSaaa4gXVWJBZ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-sGgZSaaa4gXVWJBZ .cluster text{fill:#333;}#mermaid-svg-sGgZSaaa4gXVWJBZ .cluster span{color:#333;}#mermaid-svg-sGgZSaaa4gXVWJBZ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-sGgZSaaa4gXVWJBZ :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 进攻 撤退 C:进攻 C:撤退 C B A A, B在进行协商后会发现C给两人发送的作战信息不一致此时可以先处理叛将再重新制定作战计划。
总结
现在让我们回到计算机世界的分布式场景中
拜占庭的将军代表着计算机节点忠诚的将军指的是正常运行的计算机节点叛变的将军可以认为是出现故障并且会发送误导信息的计算机节点
这样你是否理解了拜占庭将军问题代表的计算机分布式场景问题呢实际上以上提到的两种算法还能解决如下的问题信使被杀或者信使被间谍替换等。
这里强调一下拜占庭将军问题强调的几乎是最困难也最复杂的一种分布式故障场景计算机节点不仅存在故障甚至还存在恶意行为对于存在恶意节点的场景中我们必须使用拜占庭容错算法。
