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

||评论 (

可靠的配电系统,我们需要处理不同的故障情况。其中许多处理消息丢失和过程中出现故障。但是,有一类的场景是处理错误的过程,它发出相互矛盾的信息。我们面临的挑战是开发算法,可以达到必威体育精装版app官网这些故障的情况下达成协议。

兰波特描述他在与注意,Dijkstra算法已经得到了用于描述计算机科学问题,哲学家就餐的故事感到沮丧。他决定注意力吸引到特定的分布式系统问题的最佳途径是目前它在故事方面;因此,拜占庭将军。

抽象,这个问题可以在一组拜占庭军队的将军,谁与他们的部队驻扎周围敌人的城市来描述。只能通过信使沟通,要求将军在一个共同的作战计划达成一致。然而,一个或更多的人可能是叛徒谁也试图迷惑别人。问题是:找到确保忠诚的将军将达成协议的算法。

结果表明,仅使用口服的消息,这个问题是可以解决的,当且仅当将军的超过三分之二的忠诚。因此,单一的叛徒可以混淆两名忠诚将领。凭借伪造的书面信息,这个问题是可以解决的任何数量的将领和可能的叛徒。这个周末,我将要在后面的时间和阅读奠定出的问题,三个基本文件,它的第一个解决方案。在SIFT纸,问题是首先描述的那样,“达成一致意见”阐述的基本3N + 1处理器解决方案,最后文章回顾和概括了以前的结果。

也许你会喜欢他们。“SIFT:设计和容错计算机飞机控制分析“约翰·H·温斯利,张国荣兰波特,杰克·戈德堡,米尔顿·W·格林,卡尔·莱维特N.,P. M. Melliar - 史密斯,罗伯特·E·绍斯塔克,查尔斯B.温斯托克,在IEEE 66论文集,1978年10月5日

在故障的存在达成协议“M.皮斯,R.肖斯塔克和L.兰波特,1980,J. ACM 27,2(1980年4月),228-234。

拜占庭将军问题”,兰波特,L。;肖斯塔克,R。;皮斯,M。(1982),关于编程语言和系统ACM交易4(3):382-401 DOI:10.1145 / 357172.357176。

评论

博客评论由Disqus