周末回到基础阅读:拜占庭将军

| | 评论( )

在可靠的配电系统中,我们需要处理不同的故障场景许多处理信息损失和过程失败然而,有一种场景,处理故障的过程中,发出相互矛盾的信息面临的挑战是必威体育精装版应用官网荷兰国际集团(ing)算法能够达成协议在这些失败的存在。

Lamport描述他沮丧的注意力Dijkstra算法已经用于描述计算机科学问题,哲学家就餐的故事He decided the best way to attract attention to a particular distributed systems problem was to present it in terms of a story; hence, the Byzantine Generals.

抽象,问题可以被描述的一群拜占庭军队的将军们,与他们的军队驻扎在敌人的城市只有通过交流使者,将军们被要求达成一致共同的作战计划然而,其中的一个或多个可能叛徒会混淆问题是:找到一种算法,保证了忠诚的将军们将达成一项协议。

所示,仅使用口头信息,这个问题是可以解决的,当且仅当超过三分之二的将军们忠诚所以,一个叛徒可以混淆两个忠诚的将军With unforgeable written messages, the problem is solvable for any number of generals and possible traitors. This weekend, I will be going back in time and reading three fundamental papers that laid-out the problems, and its first solutions筛选的,问题是第一个描述,“达成协议”阐述了基本3 n + 1处理器解决方案,最后论文评审和推广了以前的结果。

Maybe you will enjoy them as well. "筛选:设计和分析飞机的容错计算机控制“约翰H杰克•温斯利表示,这种情况Leslie Lamport戈德堡,弥尔顿W绿色,卡尔·N莱维特,P米Melliar-Smith罗伯特E肖斯塔克,Charles B魏因斯托克,在IEEE 66学报》,1978年10月5日

"达成协议的缺点“M皮斯,R肖斯塔克,L1980年Lamport,JACM 27日2(1980年4月),228 - 234。

"拜占庭将军的问题", Lamport, L.; Shostak, R.; Pease, M(1982),ACM事务编程语言和系统4(3):382 - 401doi:10.1145/357172.357176。

评论

博客评论的Disqus