dagfans / consensus_paper Goto Github PK

一个可靠的计算机系统必须处理某些部件出故障的情况，即故障部件向系统的不同部分提供相互冲突的信息。这种情况可以抽象地表示为拜占庭军队的将领们带着他们的军队驻扎在一个敌城周围，只有通过信使才能沟通。将军们必须就作战计划达成一致。然而，他们中的一个或多个可能是试图迷惑他人的叛徒。问题是要找到一种算法来确保所有忠诚的将军们会达成一致。结果表明，如果且仅使用口头传递信息，只有当三分之二以上的将军忠诚时，这个问题才能得到解决，因此一个叛徒就可以迷惑两个忠诚的将军。而如果使用不可伪造的书面信息，则可以允许将军中存在任何数量的叛徒，使得本问题有解。

Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement. It is shown that, using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals. With unforgeable written messages, the problem is solvable for any number of generals and possible traitors. Applications of the solutions to reliable computer systems are then discussed.

Impossibility

• asynchronous vs. synchronous
• safety & liveness

Consensus in the presence of partial synchrony

• asynchronous vs. synchronous & partial synchronous

• PSL80是拜占庭将军问题的起源，更早地根源于科学家为了研究飞行器的安全而遇到的问题。
• 也是规约与验证（specification and verification ）这种研究方法的早期表现。可目为形式化验证滥觞之一。
• PSL80需要解决的是正确输入的有效性。即决策值必须来自非故障节点，而不能受到故障节点的干扰。也就是如何能拒绝故障节点的假消息。
• PSL80的牛逼在于证明了33%这个结论（n>=3m+1), m为故障节点，n为节点总数。也就是说故障节点不能多于33%，这个是后世所有BFT协议的理论基础。
• 另外注意论文提到可以对故障节点的行为的进行弱化假设，如果故障节点只是拒绝传递消息，但不能修改传递的消息（欺骗），则该问题可以突破33%的限制。实践上可以通过加密学方法解决。
• PSL80获得了2005年的Dijkstra奖

Abstract

The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each non-faulty processor has a private value of information that must be communicated to each other non-faulty processor.
Non-faulty processors always communicate honestly, whereas faulty processors may lie.
The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each non-faulty processor to refer a value for each other processor.The value referred for a non-faulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other non-faulty processor.
It is shown that the problem is solvable for, and only for, n >= 3m + 1, where m IS the number of faulty processors and n is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary n >= m >=0. This weaker assumption can be approximated in practice using cryptographic methods