拜占庭将军问题

未来网络 netlab 23280℃ 0评论

拜占庭帝国,也就是东罗马帝国,是欧洲最悠久的君主专制国家。帝国核心位于君士坦丁堡和欧洲东南部的巴尔干半岛,极盛时期的领土更为辽阔,包括意大利、叙利亚、巴勒斯坦、埃及、高加索、西班牙南部沿海和北非的地中海沿岸。

假设有这样一个场景:拜占庭帝国有一个敌人,这个敌人虽不如拜占庭帝国强大,但也足够抵御5支拜占庭军队的同时进攻。因此若要攻下这一强大的敌人,拜占庭帝国至少得有6支军队同时进攻。现派出10支军队去攻打敌人。由于敌国也同样幅员辽阔,这10支军队无法集合在一起单点突破,处于分开的包围状态分散在敌国的四周,各军队的将军之间只能通过信使互相传递消息来达成“进攻”或“撤退”的共识。困扰这些将军的问题是,他们不确定信使中是否有叛徒,叛徒可能传递虚假的进攻意向。由此,拜占庭将军们能否找到一种分布式的协议来达成进攻意向的共识,从而攻下敌人?这就是著名的拜占庭将军问题,由2013年的图灵奖得主Leslie  Lamport抽象出来一个例子,用于描述分布式系统一致性问题。

需要注意的是,军中可能存在叛徒的前提下,将军们想要达成一致进攻或者一致撤退的共识,是拜占庭将军问题探讨的核心内容。但是,仅具有“一致”就能攻下敌军吗?假设由于叛徒的存在,原本天时地利人和理应进攻而最终达成“一致撤退”的共识;反之,条件不利不宜进攻,却因为叛徒的存在 “一致进攻”。因此,仅有 “一致性”不足以使得拜占庭将军取得胜利。如何达成一致、正确的共识,同样值得深入探讨。

欢迎投稿“第一届IEEE 信息中心未来网络学术会议”,由北京大学和 CCF Yocsef 深圳联合主办、知名学者同行评审、EI收录, 全球检索。大会官网:http://www.hoticn.com。期待与您在“拜占庭将军问题”上碰撞出学术的火花。

转载请注明:命名数据网络(Named Data Netwoking)中文社区 » 拜占庭将军问题

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址