« | December 2019 | » | 日 | 一 | 二 | 三 | 四 | 五 | 六 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | |
|
公告 |
本站技术贴除标明为“原创”的之外,其余均为网上转载,文中我会尽量保留原作者姓名,若有侵权请与我联系,我将第一时间做出修改。谢谢!
——既瑜 |
统计 |
blog名称:★既瑜★ 日志总数:183 评论数量:636 留言数量:-25 访问次数:1349195 建立时间:2005年3月12日 |
OICQ:215768265
njucs2001@hotmail.com
erichoo1982@gmail.com |
|
W3CHINA Blog首页 管理页面 写新日志 退出
[【趣味文摘】]拜占廷将军问题[转] |
拜占廷将军问题
这个问题是在1982年由Lamport, Shostak, Pease提出,后少人问津。为了利于对“拜占廷将军”问题原意的理解和避免曲解,把英文解释奉上: Byzantine General Problem ——The problem of reaching a consensus among distributed units if some of them give misleading answers. The original problem concerns generals plotting a coup. Some generals lie about whether they will support a particular plan and what other generals told them. What percentage of liars can a decision making algorithm tolerate and still correctly determine a consensus?
在1982年被提出的“拜占廷将军问题”在今天被许多学者看好,然而在商业上还没有体现其价值。特别是中国的产业界把它放在了一个被遗忘的角落。
拜占庭问题讲的是,几个将军围困一座城池,大家必须商量一种策略,是进攻还是撤退。如果有的进攻,有的撤退就有可能打败仗。但将军中有叛国的,他们可能希望爱国的将军打败仗。拜占廷将军问题就是阐述了在这样的环境下,如何让爱国的将军能在最终达成一致意见。判国的将军虽然可以传递了虚假消息,也不会影响爱国的将军得到正确的决策。
拜占廷将军问题就是要让爱国的将军达成一致,而不是找叛国的将军。我们的入侵容忍体系就是这样,只要在众多服务器上得到的正确的计算结果,,那么我们就可以相信这个数据,而不需要去寻找到底谁是间谍。如果要容忍一个捣乱的服务器,在数量上究竟会需要几个服务器?“拜占廷将军”问题可以为我们解答这个问题:在进行混乱真实消息的传播中,两个将军中一个判国,另一个肯定打败仗,三个将军中如果有一个判国,则判国的将军一定有办法让两个爱国的将军不能达成一致,若再增加一个将军,既4个将军中如果只有一个判国,在不知道谁是判国者的情况下,存在一种算法使将军们达成一致,实际上就是三个爱国的将军能够达成一致,而不管判国的将军如何捣乱。既4个将军的团体能够容忍1个叛国将军。同样我们知道,当有t个判国者在捣乱而又无法找出他们的时候,存在一种算法或称做弹性协议,通过这种协议,能够保证爱国的将军达成一致。如果我们把能够容忍t个叛国者的协议叫t弹性协议,学者证明了,不存在3t个将军下的t弹性协议而一定存在3t+1或以上将军下的t弹性协议。就是说要有3t+1个或以上将军才能保证爱国的将军能够达成一致。既要想容忍t个判国者,必须保证总的将军的个数大于3t。
这样看来,“拜占廷将军”问题应用于信息安全就是入侵容忍体系的重要技术基础之一。以上讲述的仅仅是“拜占廷将军”问题中简化描述,加之以叙述的形式,就是一个描述性的推理,实际上“拜占廷将军”问题程序计算的方法是很复杂的
|
阅读全文(8981) | 回复(0) | 编辑 | 精华 |
|