区块链学习笔记7——什么是拜占庭将军问题?

了解过比特币和区块链的人,多少都听说过拜占庭将军问题,或听说过区块链的一个重要成就正是解决了拜占庭将军问题。但真正明白这个问题的人并不多,甚至知道这个问题实质的人都很罕见。

关于拜占庭问题,我学到的是如下几个知识点:

1.拜占庭将军问题(Byzantine Generals Problem)是一个共识问题,它并不是真实存在的历史事件,而是图灵奖得主Leslie Lamport和他的两位同事于1982年在其论文中提出的一个问题。

2.这个问题其中一种描述是这样的:在很久很久以前,有一个强大的帝国叫作拜占庭,它的军队非常强大,周围有10个小国家,饱受拜占庭帝国的欺压,但是,必须同一时间有6个以上的国家进攻才有可能打败拜占庭帝国,否则就一定会战败。

这个时候,问题就出现了,古时候军队之间的通信完全依赖于人,如果一个国家的军队里有奸细,无论是下令的将军还是传信的通信兵,都可能会使得另外9个国家收到假消息,从而造成作战失败。那么,如果你是其中一个小国的国王,你该如何判断一定会有另外5个以上的国家与你并肩作战呢?毕竟一个不小心,你就亡国了。

3.与拜占庭将军问题高度相似的描述是类两军问题:白军驻扎在沟渠里,蓝军则分散在沟渠两边。白军比任何一支蓝军都更为强大,但是蓝军若能同时合力进攻则能够打败白军。他们不能够远程的沟通,只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议,这就是两军问题。

看到这里您可能发现拜占庭将军问题(第一种描述)和两军问题(第二种描述)有一定的相似性,但我们必须注意的是,通信兵得经过敌人的沟渠,在这过程中他可能被捕,也就是说,两军问题中信道是不可靠的,并且其中没有叛徒之说,这就是两军问题和拜占庭将军问题的根本性不同。由此可见,大量混淆了拜占庭将军问题和两军问题的文章并没有充分理解两者。

两军问题的根本问题在于信道的不可靠,反过来说,如果传递消息的信道是可靠的,两军问题可解。然而,并不存在这样一种信道,所以两军问题在经典情境下是不可解的,为什么呢?

倘若1号蓝军(简称1)向2号蓝军(简称2)派出了通信兵,若1要知道2是否收到了自己的信息,1必须要求2给自己传输一个回执,说“你的信息我已经收到了,我同意你提议的明天早上10点9分准时进攻”。

然而,就算2已经送出了这条信息,2也不能确定1就一定会在这个时间进攻,因为2发出的回执1并不一定能够收到。所以,1必须再给2发出一个回执说“我收到了”,但是1也不会知道2是否收到了这样一个回执,所以1还会期待一个2的回执。

4.随着技术的发展,解决两军问题的信道问题已经得到解决,比如TCP协议,比如量子纠缠技术。所以回到拜占庭将军问题本身上来,其实质见下一条。

5.拜占庭将军问题的实质是:军中可能有叛徒,却要保证进攻一致,这里“一致性”才是拜占庭将军问题探讨的内容,如果本来叛徒数量就已经多到了问题不可解的地步,这个就是“反叛”的问题了;同时,我们的目标是忠诚的将军能够达成一致,对于这些忠诚的将军来说,进攻或者撤退都是可以的,只要他们能够达成一致就行。

由此引申到计算领域,发展成了一种容错理论。换句话说我们无法保证没有叛徒,关键是我们要保证叛徒在一定的数量之内,否则必败无疑。我们需要达成某种共识,这也是一种共识机制。

拜占庭将军问题是一个共识问题。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 221,695评论 6 515
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 94,569评论 3 399
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 168,130评论 0 360
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 59,648评论 1 297
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,655评论 6 397
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 52,268评论 1 309
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,835评论 3 421
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,740评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,286评论 1 318
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,375评论 3 340
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,505评论 1 352
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 36,185评论 5 350
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,873评论 3 333
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,357评论 0 24
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,466评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,921评论 3 376
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,515评论 2 359

推荐阅读更多精彩内容