拜占庭将军问题（转帖）（1 / 1）

这本书的灵感来自于拜占庭协议，所以取名《拜占庭》。但拜占庭确实容易引起误解，一些想看拜占庭帝国的读者觉得很失望，另外一些可能对本书感兴趣的读者看了看书名就放弃了，没办法，流星正在考虑更换书名……

thebyzantinegeneralsproblem(拜占庭将军问题)

这个问题是在1982年由mport,shostak,pease提出――theproblemofreachingaconsensusamongdistributedunitsifsomeofthemgivemisleadinganswers.theoriginalproblemconcernsgeneralsplottingacoup.somegeneralslieaboutwhethertheywillsupportaparticurpnandwhatothergeneralstoldthem.whatpercentageofliarscanadecisionmakingalgorithmtolerateandstillcorrectlydetermineaconsensus?

一、拜占庭将军问题的背景

对于系统坏掉的风险，可以这样假设：我们的操作员可能会误操作、可能会被贿赂或背叛，系统本身可能就有木马程序，系统可能会被黑客或病毒占领，我们自己开发的系统可能有漏洞，我们的开发人员可能会留下后门，这些都可以导致系统坏掉。因此，在这些假设在变成可能的残酷现实中，生存技术是应真正被采用的一种信息安全技术。入侵容忍体系就是生存技术中的核心。如果我们的网络和系统学会生存，那么也就是建立起一个完善的入侵容忍体系。

入侵容忍的技术在这样的假设空间中实现它的价值：个人的公开行为在一定的概率下是可预知的，系统在一定的概率下能够正确完成基本的功能。一定的概率并不是指全部，所以，可以允许有错误，因此，入侵容忍还有对纠错理论的联想：即利用纠错码可以在一个错误百出、但有信道容量的信道中准确无误地传输数据，网络系统就这样在错误中“生存”下来的，这就是我们说的入侵容忍体系，它的生存技术有两种实现方式：一是攻击响应的入侵容忍方法，它不需要重新设计系统，可通过高效的检测系统发现异常，利用资源配置系统调整系统资源，并对对错误进行修补（修补系统）；二是攻击遮蔽的入侵容忍方法，它需要重新设计整个系统，并通过冗余、容错技术，门槛密码学技术及“拜占庭”技术来实现。

二、算法介绍

“拜占庭”技术，起源于拜占廷将军问题，这是入侵容忍体系的一个基本理论问题。在1982年被提出的“拜占廷将军问题”在今天被许多学者看好，然而在商业上还没有体现其价值。特别是中国的产业界把它放在了一个被遗忘的角落。

拜占庭将军问题可以抽象成：

设计一个协议，一个司令要送一个命令给他的n-1个副官，使得

ic1.所有忠诚的副官遵守同一个命令。

ic2.假如司令是忠诚的，则每一个忠诚的副官遵守他送出的该命令。

约定：忠诚的将军将遵守协议，而叛徒则可能破坏协议，尽可能的干绕其它人的判断。叛徒是匿名的。而且最后不需要确定谁是叛徒。拜占廷将军问题就是要让爱国的将军达成一致，而不是找叛国的将军。

我们的入侵容忍体系就是这样，只要在众多服务器上得到的正确的计算结果，，那么我们就可以相信这个数据，而不需要去寻找到底谁是间谍。如果要容忍一个捣乱的服务器，在数量上究竟会需要几个服务器？

“拜占廷将军”问题可以为我们解答这个问题：在进行混乱真实消息的传播中，两个将军中一个判国，另一个肯定打败仗，三个将军中如果有一个判国，则判国的将军一定有办法让两个爱国的将军不能达成一致，若再增加一个将军，既4个将军中如果只有一个判国，在不知道谁是判国者的情况下，存在一种算法使将军们达成一致，实际上就是三个爱国的将军能够达成一致，而不管判国的将军如何捣乱。

也就是说4个将军的团体能够容忍1个叛国将军。同样我们知道，当有m个判国者在捣乱而又无法找出他们的时候，存在一种算法或称做弹性协议，通过这种协议，能够保证爱国的将军达成一致。如果我们把能够容忍m个叛国者的协议叫m弹性协议，学者证明了，不存在3m个将军下的m弹性协议而一定存在3m+1或以上将军下的m弹性协议。就是说要有3m+1个或以上将军才能保证爱国的将军能够达成一致。如果要想容忍m个判国者，必须保证总的将军的个数大于3m。

三、具体分析

1叛徒数大于或等于1/3，拜占庭问题不可解。

情况一：a，b，c三个司令，c是叛徒。a发消息给b，c“进攻”，c发消息给b“撤退”（因为是叛徒）。b收到两个矛盾的命令，无法作出决策。

情况二：a，b，c三个司令，a是叛徒。a发消息给b“进攻”，发消息给c“撤退”（因为是叛徒）。b。c收到不同的命令。

2.用口头信息(oralmessage,om)，叛徒数少于1/3,拜占庭问题可解.

口头信息三条件

a1)传送正确

a2)接收者知道是谁发的

a3)沉默(不发信息)可被检测

可以证明，多项式复杂性算法om(m)可以解决拜占庭问题.

递归设计协议om(n,m)为

om(n,0)

1.司令发送命令给所有副官。

2.副官按照接收到的命令行事。

om(n,m):

1.司令发送命令给所有副官，设副官i收到命令vi。

2.分为独立的n-1轮：对每个副官i，将其视为司令，使用协议om(n-1,m-1)将vi发送到所有其它副官。

3.这样每个副官都收到n-1条信息，每个副官都按照出现次数更多的命令行事（如果进攻和撤退的命令一样多，则默认取撤退）。

结论：当n=m+2时，n个将军中的m个叛徒可以让将军们可以达成一致，也就是满足交互一致性ic1和ic2。此时共需要信息交换轮数m+1.

原文链接：http://yaowei211.blog.sohu./30757545.html