下载文档原格式
拜占庭将军：背后的数学证明我们介绍了著名的拜占庭将军问题的由来及其结论：1. 在存在 m 个叛徒将军的情况下，将军总数⼩于等于 3m 时，忠诚将军之间的⼀致性⽆法达成；2. 当将军总是⼤于等于 3m+1 时，忠诚将军之间可以达成⼀致。
不知道你是否对这个结论存在疑惑，我们只是讲了⼀个叛徒存在的情况下三个将军⽆法达成⼀致，⽽四个将军可以达成⼀致，那到底是怎么推导出 3m 个将军⽆法达成⼀致和 3m+1 个将军能够达成⼀致的呢？如果你有这个疑问，那么说明你是个治学严谨并且随时独⽴思考的好同学。
上⼀讲的主要精⼒集中在对问题进⾏描述和简化上，这⼀讲我们就⼀起进⼊实打实的数学证明的学习。
为什么要进⾏数学证明呢？你可能会有疑问，我知道结论不就好了么，为什么还要去弄明⽩证明过程？我想告诉你的是：⼀来是知道证明的过程，可以帮助你更好地从本质上去更深层次理解拜占庭将军整个问题和结论。
⼆来是拜占庭将军问题的证明过程利⽤到了算法领域中⼗分常见的解题思路，通过学习证明过程，能让你获得触类旁通的能⼒，之后可以解决更多的问题。
具体来说，在这⼀讲的证明过程中，将使⽤到两种⽅法：反证法和数学归纳法，它们是普通算法推导中最常⽤的⽅法。
熟练掌握它们，你将具备⾃⼰创造算法的能⼒。
我曾经在⼀次⾯试中遇到⼀道没见过的题，就是⽤这两种⽅法现场编了⼀个⾯试官都没见过的算法。
当⾯试官质疑我的算法正确性时，我就⽤反证法和数学归纳当场证明了⼀下，直接把⾯试官给征服了。
三来是我希望能够通过我的理解进⾏证明过程推导，以此来消除之前你对数学证明或多或少所存在的畏难⼼理，之后，你可以更加从容地⾯对数学证明相关的问题。
再看拜占庭将军问题上⼀讲中，主要是以易懂的⽅式来讲拜占庭将军问题的，现在到了证明阶段，那么就来看⼀下拜占庭将军严格的形式化表达形式是到底是怎样的。
拜占庭将军问题：发令将军将指令发送给 n-1 个副官（传递消息的将军），副官之间需要通过协作达成下列两个⽬标：IC1：所有忠诚的副官对发令将军发送的指令达成⼀致。
分布式系统复习I1.分布式系统目标：资源共享、协同计算。
2.分布式系统问题源于三大特点：并发性、无全局时钟、故障独立性。
3.Internet & Intranet 难点：可扩展性（DNS、IP）、资源的定位、异构。
4.移动计算要解决的问题：避免由于移动需要重新配置的问题（DHCP）；无线带宽有限，需要考虑QoS；私密和安全问题；Ad hoc网络的路由问题。
5.P2P定义：计算机借助直接交换实现资源共享。
6.P2P与C/S的区别：P2P网络中的节点既可以获取其他节点的资源或服务同时也是资源或服务的提供者，即兼具client和sever双重身份。
7.挑战：异构性、开放性、安全性、故障处理、可扩展性、并发性、透明性（访问、位置、并发、复制、故障、移动、性能、扩展）。
II1.结构模型：构成系统各部分的位置、角色、它们之间的关系。
C/S、P2P、C/S变种2.基础模型：为分布式系统设计者揭示若干关键问题。
交互模型：处理消息发送的性能问题，解决分布式系统中设置时间限制的难题。
故障模型：试图给出对进程和信道故障的一个精确的约定，它定义了什么是可靠的信道和正确的进程。
安全模型：讨论对进程和信道的各种可能的威胁，引入了安全通道的概念，它可以保证在存在各种威胁的情况下通信的安全。
3.中间件：软件层，一组计算机上的进程和对象，它们相互交互，实现分布式系统的通信和资源共享。
为系统开发者屏蔽系统的异构性，提供更方便的编程模式。
4.交互模型：进程之间通过消息传递进行交互，实现系统的通信和协作功能；有较大的时延；时间是进程间进行协调的参考，在分布式系统中，很难有相同的时间概念；独立进程间相互配合的准确性受限于上面两个因素。
5.故障模型：计算机和网络发生故障，会影响服务的正确性；故障模型的意义在于定义可能出现的故障形式，为分析故障带来的影响提供依据；设计系统时，知道如何考虑容错需求。
6.安全模型：分布式系统的模块特性及开放性，使它们暴露在内部和外部的攻击下；安全模型的目的是提供依据，以此分析系统可能受到的侵害，并在设计系统时防止这些侵害的发生。
共识机制是区块链技术的核心，那什么是“共识”呢？对于现实世界，共识就是一群人对一件或者多件事情达成一致的看法或者协议。
在计算机世界当中，共识包含两个层面，第一个层面是点的层面，即多个节点对某个数据达成一致共识。
第二个层面是线的问题，即多个节点对多个数据的顺序达成一致共识。
这里的节点可以是任意的计算机设备，比如PC 电脑，笔记本，手机，路由器等，这里的数据可以是交易数据、状态数据等。
现阶段的共识算法分类如下图所示：共识机制来源于著名的“拜占庭将军问题”，拜占庭将军问题是由莱斯利·兰伯特提出的点对点通信的基本问题，主要是用于分析在分布式节点传输信息时如何保持数据的一致。
Pbft 算法的提出主要是为了解决拜占庭将军问题。
那什么是拜占庭将军问题呢？拜占庭位于如今的土耳其的伊斯坦布尔，是古代东罗马帝国的首都。
拜占庭罗马帝国国土辽阔，为了达到防御目的，每块封底都驻扎着一支由将军统领的军队，每个军队都分隔很远，将军与将军之间只能靠信差传递消息。
在战争的时候，拜占庭军队内所有将军必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。
但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定影响将军们达成一致的共识。
在已知有将军是叛徒的情况下，其余忠诚的将军如何达成一致协议的问题，这就是拜占庭将军问题。
应该明确的是，拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传递信息等问题，即消息传递的信道绝无问题。
如果信道不能保证可靠，那么拜占庭问题无解。
关于信道可靠问题，会引出两军问题。
如上图所示，白军驻扎在沟渠里，蓝军则分散在沟渠两边。
白军比任何一支蓝军都更为强大，但是蓝军若能同时合力进攻则能够打败白军。
他们不能够远程的沟通，只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。
是否存在一个能使蓝军必胜的通信协议，这就是两军问题。
看到这里你可能发现两军问题和拜占庭将军问题有一定的相似性，但是我们必须注意到是，通信兵得经过敌人的沟渠，在这个过程中他可能被捕，也就是说，两军问题中信道是不可靠的，并且其中没有叛徒之说，这就是两军问题和拜占庭将军问题的根本性不同。
PBFT共识算法详解PBFT（Practical Byzantine Fault Tolerance，实⽤拜占庭容错）⼀.概述拜占庭将军问题最早是由 Leslie Lamport 在 1982 年发表的论⽂《The Byzantine Generals Problem 》提出的，他证明了在将军总数⼤于 3f ，背叛者为f 或者更少时，忠诚的将军可以达成命令上的⼀致，即 3f+1<=n 。
算法复杂度为 O(n f+1) 。
⽽ Miguel Castro 和 Barbara Liskov 在1999年发表的论⽂《 Practical Byzantine Fault Tolerance 》中⾸次提出PBFT算法，该算法容错数量也满⾜3f+1<=n，也即最⼤的容错作恶节点数f=(n-1)/3。
算法复杂度为 O(n2)，将系统的复杂度由指数级别降低为多项式级别，使得拜占庭容错算法在实际系统应⽤中变得可⾏。
那么为什么PBFT算法的容错数量满⾜3f+1<=n呢？因为 PBFT 算法的除了需要⽀持容错故障节点之外，还需要⽀持容错作恶节点。
假设集群节点数为 N，有问题的节点为 f。
有问题的节点中，可以既是故障节点，也可以是作恶节点，或者只是故障节点或者只是作恶节点。
那么会产⽣以下两种极端情况：1. 这f 个有问题节点既是故障节点，⼜是作恶节点，那么根据少数服从多数的原则，集群⾥正常节点只需要⽐f个节点再多⼀个节点，即 f+1 个节点，确节点的数量就会⽐故障节点数量多，那么集群就能达成共识，即总节点数为f+(f+1)=n，也就是说这种情况⽀持的最⼤容错节点数量是 (n-1)/2。
2. 故障节点和作恶节点都是不同的节点。
那么就会有 f 个作恶节点和 f 个故障节点，当发现节点是作恶节点后，会被集群排除在外，剩下 f 个故障节点，那么根据少数服从多数的原则，集群⾥正常节点只需要⽐f个节点再多⼀个节点，即 f+1 个节点，确节点的数量就会⽐故障节点数量多，那么集群就能达成共识。
拜占庭将军问题之⼝头协议本⽂介绍了在将军之间直接传送⼝头消息(Oral Messages)时，解决拜占庭将军问题的算法OM(m)，并对其在m=1且n=4时进⾏了举例说明，最后对OM(m)算法进⾏了证明。
起源位于如今的⼟⽿其的，是的⾸都。
由于当时拜占庭罗马帝国国⼟辽阔，为了达到防御⽬的，每个军队都分隔很远，将军与将军之间只能靠信差传消息。
在战争的时候，拜占庭军队内所有将军和副官必须达成⼀致的共识，决定是否有赢的机会才去攻打敌⼈的阵营。
但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定⼜扰乱整体军队的秩序。
在进⾏共识时，结果并不代表⼤多数⼈的意见。
这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成⼀致的协议，拜占庭问题就此形成。
拜占庭将军问题实际上反映的是⼀个协议问题。
拜占庭帝国军队的将军们必须全体⼀致的决定是否攻击某⼀⽀敌军。
问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。
⽽这些叛徒可以采取任意的⾏动来破坏将军们的共识。
当这个问题出现的时候，只有满⾜了N≥3F+1才使得该问题有解。
⽐如说将军总数为10，那么叛徒的个数不能⼤于3，即叛徒的数量不能超过三分之⼀。
实际上这便是少数服从多数的问题。
前提拜占庭将军问题⼀致性也需要⼀定的条件作为基础：IC1. 所有忠诚副官遵守同⼀命令IC2. 如果发令官是忠诚的，每个忠诚的副官遵守他的命令。
⾸先，为定义⼝头消息，拜占庭将军消息系统具有以下假设：A1. 每个消息被正确发送。
A2. 消息的接收者知道是谁发送的消息A3. 可以被检测到缺少消息假设A1和A2防⽌叛徒⼲扰其他两个将军的通信，假设A3防⽌叛徒通过不发消息⼲扰⼀致性达成。
另外，⼝头协议算法要求每个将军可以与其他任意将军直接进⾏通信，Leslie在其原⽂中的第五章中描述了不需要满⾜这个条件的算法。
OM(m)算法Lamport针对⼝头消息(Oral Messages)的情况，提出了⼝头协议算法OM(m)，其中m为⾮负。
拜占庭将军问题报告六院五队丰瑶11060016六院五队万强11060071引言：在容错计算机系统中，经常需要部件之间的信息传递与分发，而一个失效的部件将会向其他部件发送错误的消息。
容错计算机中失效部件向不同部件发送错误消息的问题，可被抽象为拜占庭将军问题。
本文将依次介绍拜占庭将军问题的定义，解决方法，通过硬件编程语言verilog编程实现结点，模拟n=7，m=2的拜占庭问题。
拜占庭将军问题定义：我们假设有几支拜占庭的军队驻扎在敌军城池的各个方向，每支军队都由其唯一的将军领导，而所有军队的将军们仅可以通过信使交流信息。
在发现敌军后，军队的总司令发布命令，所有将军必须按照该命令采取一致的行动，但不幸的是，其中一些将军（也可能是司令）是叛徒，试图阻止将军们达成一致。
拜占庭将军问题就是将军们如何达成一致的问题，详细的定义如下：拜占庭将军问题：司令给他的n-1位下属将军发出一条命令，找到一种算法使得：条件1、所有忠诚的将军达成一致；条件2、如果司令是忠诚的，所有忠诚的将军遵守其命令。
条件1和条件2被称为交互一致性条件。
需要注意的是，如果司令是忠诚的，那么条件1服从于条件2；而司令不忠诚，则仅需条件1生效。
经过数学证明，拜占庭将军问题能够被解决，必须满足下面的条件：解决条件：若存在m个叛徒，则将军数n>=3*m+1时，拜占庭问题才能被解决。
下面介绍拜占庭将军算法，在上述条件下，解决拜占庭将军问题。
拜占庭将军算法：首先对算法中所用符号进行定义：Byz(n,m)：叛徒数为m，将军数（包括司令）为n的拜占庭将军算法；vector(i)：第i位将军保存命令的数组；majority (vector(i) )：从vector(i)中的命令选出占多数的命令；default_command：在majority函数不能选出占多数的命令时，或将军为收到命令时默认采取的命令。
下面定义拜占庭将军算法，对于Byz(n,m)问题，算法分为三步：第一步：司令将命令传给余下N-1位将军，每位将军（编号为i）将保存命令到vector(i)中；第二步：如果m>0，除当前司令外，每位将军自己作为司令进行Byz(n-1,m-1)，并将发布命令的结果也保存在vector(i)中；第三步：如果m>0，将军i的vector(i)中包含了司令发出的命令以及其他将军作为司令时的命令，最终根据算法的规则修改司令发出的命令。
1。
2。
3循环结构［学习目标]1。
掌握两种循环结构的流程图的画法，能进行两种循环结构流程图间的转化.2.掌握画流程图的基本规则，能正确画出流程图．知识点一循环结构的含义1．循环结构的定义在算法中,需要重复执行同一操作的结构称为循环结构．2．循环结构的特点（1）重复性：在一个循环结构中，总有一个过程要重复一系列的步骤若干次，而且每次的操作完全相同．(2）判断性:每个循环结构都包含一个判断条件，它决定这个循环的执行与终止．（3）函数性：循环变量在构造循环结构中起了关键作用，蕴含着函数的思想．知识点二两种循环结构的比较1．常见的两种循环结构2。
设计一个算法的流程图的步骤（1）用自然语言表述算法步骤；(2)确定每一个算法步骤所包含的基本结构，并用相应的流程图表示,得到该步骤的流程图；（3)将所有步骤的流程图用流程线连接起来，并加上起止框，得到表示整个算法的流程图．［思考］（1）循环结构的流程图中一定含有判断框吗？（2）任何一个算法的流程图中都必须含有三种基本结构吗？答(1)循环结构的流程图中一定含有判断框．(2)不一定．但必须会有顺序结构．题型一当型循环结构与直到型循环结构例1设计一个计算1＋2＋…＋100的值的算法，并画出流程图．解方法一S1i←1，S←0。
S2若i≤100成立，则执行S3；否则，输出S，结束算法；S3S←S＋i；S4i←i＋1，转S2。
流程图:方法二S1i←1,S←0。
S2S←S＋i。
S3i←i＋1。
S4若i＞100不成立，则执行S2；否则，输出S,结束算法．流程图：反思与感悟当型循环结构与直到型循环结构的联系和区别（1)联系：①当型循环结构与直到型循环结构可以相互转化；②循环结构中必然包含选择结构,以保证在适当的时候终止循环；③循环结构只有一个入口和一个出口;④循环结构内不存在死循环，即不存在无终止的循环．（2）区别:直到型循环结构是先执行一次循环体，然后再判断是否继续执行循环体,当型循环结构是先判断是否执行循环体；直到型循环结构是在条件不满足时执行循环体，当型循环结构是在条件满足时执行循环体．要掌握这两种循环结构,必须抓住它们的区别．跟踪训练1设计一个算法，求13＋23＋33＋…＋1003的值，并画出流程图．解算法如下：S1S←0；S2I←1;S3S←S＋I3；S4I←I＋1;S5若I＞100，则输出S，算法结束;否则，执行S3。
最短路径问题（将军饮马问题）教学设计最短路径问题——将军饮马问题及延伸最短路径问题教学内容解析：本节课的主要内容是利用轴对称研究某些最短路径问题，最短路径问题在现实生活中经常遇到，初中阶段，主要以“两点之间，线段最短”“三角形两边之和大于第三边”为知识根底，有时还要借助轴对称、平移变换进行研究。
本节课以数学史中的一个经典故事----“将军饮马问题”为载体开展对“最短路径问题”的课题研究，让学生经历将实际问题抽象为数学的线段和最小问题，再利用轴对称将线段和最小问题转化为“两点之间、线段最短”的问题。
教学目标设置： 1、能利用轴对称解决最短路径问题。
2、在解题过程能总结出解题方法，，能进行一定的延伸。
3、体会“轴对称”的桥梁作用，感悟转化的数学思想。
教学重点难点：重点：利用轴对称将最短路径问题转化为“两点之间、线段最短”问题。
难点：如何利用轴对称将最短路径问题转化为线段和最小问题。
学情分析： 1、八年级学生的观察、操作、猜想能力较强，但演绎推理、归纳和运用数学意识的思想比较薄弱，自主探究和合作学习能力也需要在课堂教学中进一步引导。
此年龄段的学生具有一定的探究精神和合作意识，能在一定的亲身经历和体验中获取一定的数学新知识，但在数学的说理上还不标准，集合演绎推理能力有待加强。
2、学生已经学习过“两点之间，线段最短。
”以及“垂线段最短”。
以及刚刚学习的轴对称和垂直平分线的性质作为本节知识的根底。
教学条件分析: 在初次解决问题时，学生出现了多种方法，通过测量，发现利用轴对称将同侧两点转化为异侧两点求得的线段和比较短；进而利用PPT动画演示，实验验证了结论的一般性；最后通过逻辑推理证明。
教具准备：直尺、ppt 教学过程：环节教师活动学生活动设计意图一复习引入 1.【问题】：看到图片，回忆如何用学过的数学知识解释这个问题？ 2.这样的问题，我们称为“最短路径”问题。
1、两点之间，线段最短。
2、两边之和大于第三边。
