拜占庭将军问题（1982）

导读

这篇 1982 年论文提出并形式化了拜占庭将军问题：在分布式系统中，部分节点可能叛变或故障、通信不可完全信任时，忠诚节点如何达成一致行动。论文给出了达成共识所需的条件、算法与容错界限，是分布式共识和拜占庭容错研究的奠基性工作。

HN 关注点：是因为这篇论文奠定了分布式共识与拜占庭容错的理论基础，并与区块链等现代系统直接相关；评论区还讨论了命名轶事和区块链是否算解法。

关键词　Byzantine fault tolerancedistributed consensusLeslie Lamportblockchain

后来怎么样

这篇论文奠定了分布式共识与拜占庭容错的理论基础，其容错界限和模型成为后续 BFT 协议、区块链共识机制等工作的核心参照。

HN 评论精选

这几条评论里：质疑 1　补充 3

补充作者自述问题命名由来：原拟“阿尔巴尼亚将军”，因顾虑改名“拜占庭将军”。

摘自[0]：分布式计算中有一个问题有时被称为“中国将军问题”，即两位将军必须就进攻还是撤退达成一致，但只能派可能永远到不了的信使通信。我借用了将军这个想法，把问题表述为一群将军，其中一些人可能是叛徒，他们必须达成共同决定。我想给将军们指定一个不会冒犯任何读者的国籍。当时阿尔巴尼亚是完全封闭的社会，我觉得不太可能有阿尔巴尼亚人在场反对，所以这篇论文原题是《阿尔巴尼亚将军问题》。Jack Goldberg 足够聪明，意识到阿尔巴尼亚之外也有阿尔巴尼亚人，而且阿尔巴尼亚未必永远是黑洞，所以建议我另找名字。随后我想到显然更合适的“拜占庭将军”。

arberavdullahu查看英文原文

Taken from [0]: There is a problem in distributed computing that is sometimes called the Chinese Generals Problem, in which two generals have to come to a common agreement on whether to attack or retreat, but can communicate only by sending messengers who might never arrive. I stole the idea of the generals and posed the problem in terms of a group of generals, some of whom may be traitors, who have to reach a common decision. I wanted to assign the generals a nationality that would not offend any readers. At the time, Albania was a completely closed society, and I felt it unlikely that there would be any Albanians around to object, so the original title of this paper was The Albanian Generals Problem. Jack Goldberg was smart enough to realize that there were Albanians in the world outside Albania, and Albania might not always be a black hole, so he suggested that I find another name. The obviously more appropriate Byzantine generals then occurred to me. [0] https://www.microsoft.com/en-us/research/publication/byzantine-generals-problem/

补充提问区块链/PoW/PoS 是否可视为拜占庭将军问题的解法，并指出 51% 攻击边界。

我犹豫要不要提这个话题，但基于区块链的系统是拜占庭将军问题的解决方案吗？> A. 所有忠诚将军决定同一行动计划。所有参与者达成不可变的共识（区块链中当前交易组）。> B. 少数叛徒不能使忠诚将军采纳坏计划。它对少数坏参与者有保护，因为需要工作量证明/权益证明，在 51% 攻击之前可防止坏交易。不过我这方面知识不多，大家怎么看？

gitgud查看英文原文

I'm reluctant to broach the subject, but is a "Blockchain" based system a solution to the "The Byzantine Generals Problem"? > A. All loyal generals decide upon the same plan of action. All actors arrive at an immutable consensus (the current transaction group in the blockchain). > B. A small number of traitors cannot cause the loyal generals to adopt a bad plan It has protection against a small number of bad-actors as they require proof of work/stake which prevents against bad-transactions up until 51% attacks. I don't have much knowledge in the area though, any thoughts?

补充转述 Lamport 自嘲该问题没人感兴趣，并提供领导者选举算法链接。

我有一位教授对拜占庭将军问题感兴趣，并曾在微软研究院与 Lamport 共事。她声称 Leslie 告诉她，没人对这个题目感兴趣/它无关紧要。这里[1]是她展示给我们的一个巧妙的领导者选举算法。

ahendy查看英文原文

I have a professor who is interested in the Byzantine Generals Problem and worked with Lamport at Microsoft Research. She claimed that Leslie told her that no one was interested in the problem/it didn't matter. Here[1] is a clever algorithm for leader election that she presented to us. [1]https://youtu.be/UVzCZqNngaU?t=1364

质疑批评许多 ICO 算法对消息传递/选举协议规定不足，而 PBFT 等会明确设计这些机制。

PBFT 算法，或任何拜占庭容错算法，都会仔细设计消息传递方案和选举协议。然而在最近的 ICO 热潮中，很多算法（除了比特币，也许还有其他我没读过的）除了“我们会向所有人广播”之外并没有走很远。这些规定不足的消息传递方案可能带来麻烦，尤其是对那些没有工作量证明的算法。

liuliu查看英文原文

The PBFT algorithm, or any Byzantine fault tolerant algorithms are deliberate on what's the message-passing scheme and election protocol would look like. However, in recent ICO craze, a lot of algorithms (with the exception of Bitcoin, and maybe others I didn't read) don't go very long way other than "we will broadcast to everyone". These under-specified message passing scheme can be troublesome, especially for these algorithms without Proof-of-work.

历次讨论

2018Hacker News 讨论帖127 分 · 21 评
2020Hacker News 讨论帖163 分 · 56 评

HN 二十年，最值得读的论文。

朋友分享的书单

专题阅读路线

本周最多人读

我的书单

必读 30 篇

论文库

这些论文是怎么挑出来的

全量扫一遍

只留论文本身

写导读、译评论

拜占庭将军问题（1982）

导读

后来怎么样

HN 评论精选

相关资源

历次讨论

同领域还值得读

Paxos vs. Raft：分布式共识是否已达成共识？

Stellar 协议：互联网级共识的联邦模型

Google 变差了吗？对搜索引擎中 SEO 垃圾的纵向调查

使 CRDT 能够容忍拜占庭故障

Filecoin：去中心化存储网络

打赏支持

关注向阳乔木