dindinw
commented
6 years ago - 编故事这个传统来自Dijkstra（哲学家就餐问题：多线程同步），显然这个传统得到了有效的延续。
- Lamport从中国将军问题（两将军问题）创造出了拜占庭将军问题。只所以不用具体国别是为了消除可能存在的读者不适（例如他最初计划用阿尔巴尼亚）
Lamport comments
I have long felt that, because it was posed as a cute problem about philosophers seated around a table, Dijkstra's dining philosopher's problem received much more attention than it deserves. (For example, it has probably received more attention in the theory community than the readers/writers problem, which illustrates the same principles and has much more practical importance.) I believed that the problem introduced in [41] was very important and deserved the attention of computer scientists. The popularity of the dining philosophers problem taught me that the best way to attract attention to a problem is to present it in terms of a story.
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.
The main reason for writing this paper was to assign the new name to the problem. But a new paper needed new results as well. I came up with a simpler way to describe the general 3n+1-processor algorithm. (Shostak's 4-processor algorithm was subtle but easy to understand; Pease's generalization was a remarkable tour de force.) We also added a generalization to networks that were not completely connected. (I don't remember whose work that was.) I also added some discussion of practical implementation details.
一个可靠的计算机系统必须处理某些部件出故障的情况，即故障部件向系统的不同部分提供相互冲突的信息。这种情况可以抽象地表示为拜占庭军队的将领们带着他们的军队驻扎在一个敌城周围，只有通过信使才能沟通。将军们必须就作战计划达成一致。然而，他们中的一个或多个可能是试图迷惑他人的叛徒。问题是要找到一种算法来确保所有忠诚的将军们会达成一致。结果表明，如果且仅使用口头传递信息，只有当三分之二以上的将军忠诚时，这个问题才能得到解决，因此一个叛徒就可以迷惑两个忠诚的将军。而如果使用不可伪造的书面信息，则可以允许将军中存在任何数量的叛徒，使得本问题有解。
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.