搜索
拜占庭将军问题报告在容错计算机系统中，经常需要部件之间的信息传递与分发，而一个失效的部件将会向其他部件发送错误的消息。容错计算机中失效部件向不同部件发送错误消息的问题，可被抽象为拜占庭将军问题。本文将依次介绍拜占庭将军问题的定义，解决方法，通过硬件编程语言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)中；第二步：如果m0，除当前司令外，每位将军自己作为司令进行Byz(n-1,m-1)，并将发布命令的结果也保存在vector(i)中；第三步：如果m0，将军i的vector(i)中包含了司令发出的命令以及其他将军作为司令时的命令，最终根据算法的规则修改司令发出的命令。如果m=0，则直接将司令发出的命令当做正确命令。一致性判断：每个结点n从自己的ICV集合（即vector[]）中选择结点i作为二级节点转发的信息组成一个子集，算出此子集中的多数者，则n认为此为将军结点S发送给结点i的指令。如果没有多数者，就采用缺省值default作为S发送给i的指令。i是除自己和将军结点以外的所有结点。等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）第一阶段发出以下消息：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.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的时候，他们发现没有超过半数的结果，因此认为S发送给R1的是缺省值0.同样的，S发送给其他任何一个结点的消息都可以通过这种方法来得到统一。2、算法流程图示：1、N=7，m=2第一步，刘备发布命令2、N=7，m=2，第二步，关羽首先对接到的命令表示怀疑，希望召集其他将领对其确认3、N=6，m=1，第一步，进入以关羽为司令的Byz(6,1)4、N=6，m=1，第二步，张飞对关羽的命令表示怀疑5、N=5，m=0，第一步，进入以张飞为司令的Byz(5,0)6、N=5，m=0，第三步，由于m=0，将军们接受到命令时无法再对其进行确认，所以直接将接受到的命令认为是真。7、N=6，m=1，第三步，周瑜，魏延，赵云，马超依次做司令后，将军们的vector被填满，此时将对上一层的命令进行确认。8、N=6，m=1，第三步完，关羽的全部命令被确认完毕后的vector情况9、N=7，m=2，第三步，张飞，周瑜，魏延，赵云，马超依次为司令过后，将对刘备发出的命令做确认10、N=7，m=2，结束，大家统一命令3、从上面的例子中可以看出，理解该算法的要点有如下几个：a)因为有叛徒，所以每个将军要对每条收到的命令持怀疑的态度。这才有了递归确认的算法结构；b)永远别问自己的上司“你这命令是真的假的？”。这就要求在递归的时候不能把给自己命令的人包括进来；c)跟平级的同志们交换意见。这就是说要跟一起接收到命令的将军们互相通讯，以确定上级的命令是否为真。硬件编程verilog实现：上一部分给出了比较直观的例子，但是对于算法精确的定义及实现还需要通过编程来解决。下面介绍拜占庭将军算法的编程实现。我们在此假设1为正确消息，0为错误消息。当某个节点为忠诚节点时，它会诚实的转发上级节点的信息，如果某个节点为内奸节点，它不管收到什么消息，都只会转发0，错误消息。程序框架如下：我们是实现的是七个节点的问题，其中有两个是叛徒节点。所以每个节点模块应该按如下定义：modulenode(in0,in1,in2,in3,in4,out0,out1,out2,out3,out4,rst,num,trust,clk,result)；在司令给各位将军发完第一次消息之后，就该6个将军节点之间相互发送消息确认司令发送的消息到底是什么。所以每个节点需要有5个输入in0，in1，in2，in3，in4,5个输出out0，out1，out2，out3，out4，分别对应除自己以外的5个节点；rst引脚的作用是初始化节点，并模拟司令给节点一个初始消息；num是这个节点的编号，除司令以为共六个将军节点，编号分别为0,1,2,3,4,5；trust指示此节点是否可信，1为可信节点，0为内奸节点；clk外部时钟输入；result输出次节点最终结果。节点输入输出引脚定义：input[3:0]in0;input[3:0]in1;input[3:0]in2;input[3:0]in3;input[3:0]in4;input[3:0]num;inputrst;inputclk;inputtrust;outputout0,out1,out2,out3,out4;reg[3:0]out0;reg[3:0]out1;reg[3:0]out2;reg[3:0]out3;reg[3:0]out4;outputregresult;根据算法要求，输入输出都是四位的，其内容为该消息经司令之后第一次转发的节点的节点编号加消息内容1或0。消息内容：前三位是节点序号000或001或010或011或100或101消息内容1或0rst，trust，clk，result均是一位的。定义的一些内部寄存器：reg[3:0]m[25:0];reg[3:0]q0[3:0];reg[3:0]q1[3:0];reg[3:0]q2[3:0];reg[3:0]q3[3:0];reg[3:0]q4[3:0];reg[5:0]count;reg[5:0]count0;reg[5:0]count1;reg[5:0]count2;reg[5:0]count3;reg[5:0]count4;reg[5:0]count5;reg[5:0]count6;每个节点总共会收到26条消息，每条消息都是4位的，用寄存器m存储。寄存器q0，q1，q2，q3，q4分别对应5个输出口，存储输出口即将输出但还未输出的内容。count是计数器，每两个时钟节拍加1。count0记录最后存储在寄存器中内容为0001的消息条数，count1记录内容为0011的消息条数，以此类推count5存储1011的消息条数。count6用来存放count0~count5中数字大于等于3的个数，从而决定最后本节点result的输出。初始化：always@(posedgeclkornegedgerst)if(rst==0)begincount=0;count0=0;count1=0;count2=0;count3=0;count4=0;count5=0;count6=0;endelsecount=count+1;rst为0时，对所有内部寄存器进行初始化。初始化之后，每一拍当count为4时：if(count==4)beginfor(i=0;i26;i=i+1)m[i]=0;m[0]=1;if(trust==1)beginout0=((num1)+1);out1=((num1)+1);out2=((num1)+1);out3=((num1)+1);out4=((num1)+1);endelsebeginout0=(num1);out1=(num1);out2=(num1);out3=(num1);out4=(num1);endend在接收到司令的消息1之后，如果trust为1，即为忠诚将军节点，转发（本节点序列号+1），否则转发（本节点序列号+0）。本次为第一次转发消息。当count为5时：elseif(count==5)beginm[1]=in0;m[2]=in1;m[3]=in2;m[4]=in3;m[5]=in4;q1[0]=in0;q2[0]=in0;q3[0]=in0;q4[0]=in0;q0[0]=in1;q2[1]=in1;q3[1]=in1;q4[1]=in1;q1[1]=in2;q0[1]=in2;q3[2]=in2;q4[2]=in2;q2[2]=in3;q0[2]=in3;q1[2]=in3;q4[3]=in3;q3[3]=in4;q0[3]=in4;q1[3]=in4;q2[3]=in4;end这一拍接收消息，把从五个输入接口in0~in4收到的消息存入寄存器m中，并把这些消息转存在5个发送端缓存中q0~q4，依据的原则是从接收端x接收到的消息只转发给其他接口，不给x节点转发。当count为6~13时：elseif(count==6)beginif(trust==1)beginout0=q0[0];out1=q1[0];out2=q2[0];out3=q3[0];out4=q4[0];endelsebeginout0=((q0[0]1)1);out1=((q1[0]1)1);out2=((q2[0]1)1);out3=((q3[0]1)1);out4=(