资源描述：
《拜占庭将军问题的verilog模拟实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、拜占庭将军问题报告在容错计算机系统中，经常需要部件之间的信息传递与分发，而一个失效的部件将会向其他部件发送错误的消息。容错计算机中失效部件向不同部件发送错误消息的问题，可被抽象为拜占庭将军问题。本文将依次介绍拜占庭将军问题的定义，解决方法，通过硬件编程语言verilog编程实现结点，模拟n=7，m=2的拜占庭问题。拜占庭将军问题定义：我们假设有几支拜占庭的军队驻扎在敌军城池的各个方向，每支军队都由其唯一的将军领导，而所有军队的将军们仅可以通过信使交流信息。在发现敌军后，军队的总司令发布命令，所有将军必须按照该命令采取一致的行动，但不幸的是，其中一些将军（也
2、可能是司令）是叛徒，试图阻止将军们达成一致。拜占庭将军问题就是将军们如何达成一致的问题，详细的定义如下：拜占庭将军问题：司令给他的n-1位下属将军发出一条命令，找到一种算法使得：条件1、所有忠诚的将军达成一致；条件2、如果司令是忠诚的，所有忠诚的将军遵守其命令。条件1和条件2被称为交互一致性条件。需要注意的是，如果司令是忠诚的，那么条件1服从于条件2；而司令不忠诚，则仅需条件1生效。经过数学证明，拜占庭将军问题能够被解决，必须满足下面的条件：解决条件：若存在m个叛徒，则将军数n>=3*m+1时，拜占庭问题才能被解决。下面介绍拜占庭将军算法，在上述条件下，解
3、决拜占庭将军问题。拜占庭将军算法：首先对算法中所用符号进行定义：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，除当前
4、司令外，每位将军自己作为司令进行Byz(n-1,m-1)，并将发布命令的结果也保存在vector(i)中；第三步：如果m>0，将军i的vector(i)中包含了司令发出的命令以及其他将军作为司令时的命令，最终根据算法的规则修改司令发出的命令。如果m=0，则直接将司令发出的命令当做正确命令。一致性判断：每个结点n从自己的ICV集合（即vector[]）中选择结点i作为二级节点转发的信息组成一个子集，算出此子集中的多数者，则n认为此为将军结点S发送给结点i的指令。如果没有多数者，就采用缺省值default作为S发送给i的指令。i是除自己和将军结点以外的所有结点
5、。等n将所有的i（i=1,2,3……）从S结点收到的信息都判断出后，根据所有节点收到的信息以及自己从将军结点直接收到的信息的集合中的超半数者来做出自己的选择。算法描述：为直观的讲解算法流程，我们采用Byn(7,2)问题，通过图例的方式进行讲解。1、问题条件：a)N=7，m=2；b)将军为S，中尉R1和R6为叛徒。S在第一轮发出的消息为S.S1(1),S.S2(1),S.S3(1),S.S4(1),S.S5(1),S.S6(1)；每个中尉在第二步运行Byn(6,1)算法。首先考虑R1。这个单元是叛徒，可以发送任意他想发的消息。假设他在Byn（6,1）第一阶段
6、发出以下消息：S.R1.R2(1),S.R1.R3(2),S.R1.R4(3),S.R1.R5(4),S.R1.R6(0)在Byn(6,1)的第二阶段，剩余的所有中尉运行Byn(5,0)来发布他们从R1收到的消息，如下：S.R1.R2.R3(1)S.R1.R2.R4(1)S.R1.R2.R5(1)S.R1.R2.R6(1)S.R1.R3.R2(2)S.R1.R3.R4(2)S.R1.R3.R5(2)S.R1.R3.R6(2)S.R1.R4.R2(3)S.R1.R4.R3(3)S.R1.R4.R5(3)S.R1.R4.R6(3)S.R1.R5.R2(4)S.
7、R1.R5.R3(4)S.R1.R5.R4(4)S.R1.R5.R6(4)S.R1.R6.R3(1)S.R1.R6.R3(8)S.R1.R6.R3(0)S.R1.R6.R3(2)因为R6也是叛徒结点，所以他发出的消息也是任意的。每个节点保存的与S.R1(1)相关的ICV消息如下：ICVs.r1(R2)=(1,2,3,4,1)ICVs.r1(R3)=(1,2,3,4,8)ICVs.r1(R4)=(1,2,3,4,0)ICVs.r1(R5)=(1,2,3,4,0)因为R6也是叛徒结点，所以他收到的消息不用考虑。当R2，R3，R4，R5查看他们的ICV的时候，他
8、们发现没有超过半数的结果，因此认为S发送给R1的是缺省值0.同样的
