点击上方“云象区块链”可订阅哦！
前言：区块链技术作为交易各方信任机制建设的完美数学解决方案，之所以能解决信任机制的问题，是因为它起源于分布式系统中重要的算法问题：拜占庭将军问题。今天我们就来分析下区块链技术翻过的大山----拜占庭将军问题。拜占庭将军问题
拜占庭帝国国土辽阔，当攻打敌人的时候，每个军队都分隔很远，将军之间只能靠信使传消息。
在战争的时候，拜占庭军队内所有将军必须达成一致的共识，决定是否去攻打敌人的阵营。但是，军队可能有叛徒和敌军间谍，左右将军们的决定，扰乱军队的秩序，使达成的共识并不代表大多数人的意见。这时，在已知有间谍的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，就是拜占庭将军问题。
将军之间的联络通过信使，在这个问题中信使不会被截获（信道可靠，不可靠的情况见文末的“两军问题”）。拜占庭将军们需要设计出一种算法，能够满足下列条件：
一个司令向他的n-1个副官发送命令，使得：
所有忠诚的副官都遵守相同的命令
如果司令是忠诚的，那么每个忠诚的副官必须遵守他发出的命令。
P.S：条件A和B被称为交互一致性条件。可以看到，当发令将军是忠诚的时候，A可以由B导出。但值得注意的是，发令将军不一定是忠诚的。
当我们去掉故事的伪装后，我们发现问题的内核是：如何在一个不基于信任的分布式网络中就信息达成共识？例子中的将军换成计算机网络中的节点，把信使换成节点之间的通信，把进攻与否换成需要达成共识的信息，你就可以理解问题所描述的困境了。达成共识的能力对于一个支付系统来说重要性不言而喻，这正是区块链技术需要解决的问题。
拜占庭将军问题需要解决一致性和正确性的算法问题。一致性指的是将军们行动一致（统一进攻或撤退），正确性指的是每个将军（司令和副官）都可以正确表达自己的想法，并使别人判断真伪。关于提出者
上面照片中头发胡须白成一片的就是拜占庭将军问题的提出者，计算机科学史上的传奇人物莱斯利?兰伯特（Leslie Lamport）。作为研究分布式系统的先锋人物，微软研究院首席研究员，他为提升计算机系统的可靠性以及稳定性做出了杰出贡献，因此他获得了2013年图灵奖----计算机界的诺贝尔奖。他在1978年发表的论文《分布式系统内的时间、时钟事件顺序（Time, Clocks, and the Ordering of Events in a Distributed System）》成为计算机科学史上被引用最多的文献。可以说，只要你在使用建立在分布式系统上的互联网，你就该感谢这位伟大的科学家！
兰伯特曾说，是故事让问题变得受欢迎，因此他在提出观点和问题时常用故事背景吸引眼球。拜占庭将军的故事就是兰伯特在研究分布式系统容错性的时候编出的一个故事。
1972年，兰伯特加入斯坦福国际研究院（SRI）。SRI有一个项目，旨在为NASA建立容错型航电计算机系统。考虑到系统的工作性质，故障是不允许发生的。这段经历孕育了两篇旨在解决拜占庭故障（故障节点不但会丢失信息，还会给出错误信息）的论文，由兰伯特和SRI同事Marshall Pease 及Robert Shostak合作完成。（点击原文查看兰伯特博士论文原文《The Byzantine General Problem》）
有趣的是，兰伯特在伯克利的一间咖啡馆，在一张餐巾纸上写出了第一种数字签名算法，作为解决拜占庭将军问题的方法。只可惜那张餐巾纸已经消逝在时间的流沙中。问题的可解性“（1）叛徒数大于或等于1/3，拜占庭问题不可解
如果有三位将军，一位副官是叛徒。当司令发出进攻命令时，副官2可能告诉副官1，他收到的是“撤退”的命令。这时副官1收到一个“进攻”，一个“撤退”，而无所适从。
如果司令是叛徒。他告诉副官1“进攻”，告诉副官2“撤退”。当副官2告诉副官1，他收到“撤退”命令时，副官1由于收到了司令“进攻”的命令，而无法与副官2保持一致。
正由于上述原因，在三模冗余系统中，如果一机有拜占庭故障，即叛徒数等于1/3，拜占庭问题不可解。三模冗余只能容故障-冻结(fail-frost)那类的故障,就是元件故障后冻结在某一个状态不动。对付这类故障，用三模冗余比较有效。“（2）用口头信息，如果叛徒数少于1/3，拜占庭问题可解
这里说“少于1/3”表明，要对付一个叛徒，至少要用四模冗余。在四模中有一个叛徒，叛徒数是少于1/3的。所谓口头信息，是指满足三个条件：
①被发送的消息都能够被正确的投递
②接收者知道是谁发的
③沉默（不发信息）可以被检测
简而言之，信道绝对可信，且消息来源可知。但口头协议并不会告知消息的上一个来源是谁。
我们可以给出一个多项式复杂性的算法来解这一问题。算法的中心思想很简单，就是司令把命令发给每一副官，各副官又将收到的司令的命令转告给其他副官，递归下去，最后用多数表决。
如果司令是忠诚的，他送一个命令v给所有副官。若副官3是叛徒，当他转告给副官2时命令可能变成x。但副官2收到{v, v, x}，多数表决以后仍为v，忠诚的副官可达成一致。
如果司令是叛徒，他发给副官们的命令可能互不相同，为x, y, z。当副官们互相转告司令发来的信息时，他们会发现，他们收到的都是{x,y,z}，因而也取得了一致。“（3）用书写信息，如果至少有2/3的将军是忠诚的，拜占庭问题可解
所谓书写信息，是指带签名的信息，即可认证的信息。它是在口头信息的基础上，增加两个条件：
①忠诚司令的签名不能伪造，内容修改可被检测。
②任何人都可以识别司令的签名，叛徒可以伪造叛徒司令的签名。
一种已经给出的算法是，接收者收到信息后，签上自己的名字后再发给别人。由于书写信息的保密性，可以证明，用书写信息，如果至少有2/3的将军是忠诚的，拜占庭问题可解。
如果司令是叛徒，他送“进攻”命令给副官1，并带有他的签名0，送“撤退”命令给副官2，也带签名0。副官们转送时也带了签名。于是副官1收到{“进攻”：0，“撤退”：0,2}，说明司令发给自己的命令是“进攻”，而发给副官2的命令是“撤退”，司令对我们发出了不同的命令。对副官2也同样。区块链的解决方案
区块链的基本结构也是用数字签名的形式解决拜占庭将军问题。
但是，问题在于（还是以将军为例）
可能每一封都写着不同的进攻时间。
除此以外，部分将军会故意背叛发起人，他们将重新广播超过一条的信息链。这个系统迅速变质成不可信的信息和攻击时间相互矛盾的纠结体。
因此，区块链采用了PoW（工作量证明）的方法来确认，提交一个所有人都必须经过大量尝试计算才能得出，却十分容易证明正确的计算结果。例如，只有一个前13个字符是0的哈希值结果可以被系统接受成为“工作量证明”，这就需要全网花费一定时间算出大量的无效值。这就是减慢信息传递速率，但使得整个系统可用的“工作量证明”。
人们把一段时间内的信息，包括数据、代码打包成一个区块，盖上时间戳，与上一个区块衔接在一起，每下一个区块的页首都包含了上一个区块的索引（哈希值），然后再在页中写入新的信息，从而形成新的区块，首尾相连，最终形成了区块链。
此外，PoS（权益证明机制）和广义的零知识证明技术（ generalized zero knowledge proof technology）等发展中的技术在保护区块链不可篡改的安全性上也有很大的前景。 意义
可信计算中必须考虑人为的故障，特别是人为恶意的攻击。这是保证计算安全性的基本出发点，在今天的网络环境下有非常重要的现实意义。拜占庭将军问题不过是保持并行计算中数据一致性问题的一个抽象表达。一种抽象表达往往能把本质问题从繁琐的工程实现中提取出来，对于基础研究极其重要。
解拜占庭将军问题的算法给我们提供数据一致性的思路和算法。而在该算法中就有各位将军的同步问题。这些问题都为计算可信性的提高以启发。要解决拜占庭将军问题需要四模冗余，硬件开销是很大的。从中还可以看出，签名和认证对保证数据安全有节省硬件的效果
现在银行的异地备份受制于硬件并不都是四模冗余，然而在区块链中这并不是问题，作为分布式账簿，区块链在这方面有着先天的优势。互联网成功实现了信息去中心化，区块链则将借此实现信用去中心化。拓展阅读：两军问题
白军驻扎在沟渠里，蓝军则分散在沟渠两边。白军比任何一支蓝军都更为强大，但是蓝军若能同时合力进攻则能够打败白军。他们不能远程的沟通，只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议，这就是两军问题。
两军问题和拜占庭将军问题有一定的相似性，但必须注意的是，通信兵得经过敌人的沟渠，在这过程中他可能被捕，也就是说，两军问题中信道是不可靠的，并且其中没有叛徒之说，而拜占庭将军问题中，并不去考虑通信兵是否会被截获或无法传达信息等问题。这就是两军问题和拜占庭将军问题的根本性不同。
两军问题的根本问题在于信道的不可靠，反过来说，如果传递消息的信道是可靠的，两军问题可解。然而，并不存在这样一种信道，所以两军问题在经典情境下是不可解的。但通过量子通讯协议，理论上是可以解决信道不可靠的问题，具体内容我们在此不表。这样的话便可将两军问题转化为拜占庭将军问题。国内区块链专业技术互联网企业长按下方二维码关注我们微信号：云象区块链【联系我们】【邮件】
/点击原文查看兰伯特博士论文原文《The Byzantine General Problem》
本文来自微信公众账号提交，由微讯啦收录，转载请注明出处。
微信扫码 分享文章当前位置：
拜占庭将军问题算法的动态模拟
来源： 联系QQ： 作者： 佚名 来源： 网络 发布时间： 13/05/09
【编者按】：网学网计算机其他语言为您提供拜占庭将军问题算法的动态模拟参考，解决您在拜占庭将军问题算法的动态模拟学习中工作中的难题，参考学习。***咨询，网学网竭诚为您服务，本站永久域名： &
1．本毕业设计（论文）课题应达到的目的：
拜占庭帝国就是5～15世纪的东罗马帝国。拜占庭军队有许多分支，驻扎在敌人城外，每一分支由各自的将军指挥。将军们只能靠通讯员进行通讯。在观察了敌人以后，忠诚的将军们必须制订一个统一的行动计划&&进攻或撤退。然而，将军中有叛徒，他们不希望忠诚的将军们能达成一致，因而影响统一行动计划的制订与传播。Lamport于1982年发表文章首次提出了上述拜占庭将军问题，并提出了基于口头信息传递和书面信息传递两种解决方案。本项目要求学生能够通过动画模拟演示当任意指定忠诚和叛徒将军个数的时候，整个Lamport算法的运行流程。制作动画（动态演示）的软件可以任选。
2．本毕业设计（论文）课题任务的内容和要求（包括原始数据、技术要求、工作要求等）：
1. 理解拜占庭将军问题算法原理和过程；
2. 详细分析编程中可能遇到的问题及想出解决办法；
3. 用Java语言做核心程序模拟，并完成算法程序；
4. 使用动画模拟算法的执行流程，提供可交互式的用户演示；
5. 对程序安全性及正确性的调试及维护；
6. 对动态演示的细节进行优化，实现算法细节的良好展示。
毕 业 设 计（论 文）任务 书
3．对本毕业设计（论文）课题成果的要求〔包括毕业设计论文、图表、实物样品等〕：
毕业论文，程序代码
测试用例及报告
4．主要参考文献：
[1] (美)特尼博姆 等著, 辛春生 等译. 分布式系统原理与范型[M]. 北京：清华大学出版社，2008.
[2] (美)特尼博姆 等著. 分布式系统原理与范型[M]. 北京：清华大学出版社，2008.
[3] (英)库劳里斯 等著, 金蓓弘 等译. 分布式系统概念与设计[M]. 北京：机械工业出版社，2008.
[4] (英)库劳里斯 等著. 分布式系统：概念与设计[M]. 北京：机械工业出版社，2006.
[5] LAMPORT L., SHOSTAK R., and PEASE M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems, ):382-401.
本站发布的计算机毕业设计均是完整无错的***作品，包含开题报告+程序+论文+源代码+翻译+答辩稿PPT
本文选自计算机毕业设计论文文章部分只是部分简介，如需了解更多详情请咨询本站***！QQ3710167
上一篇资讯：
下一篇资讯：
文章排行榜