拜占庭将军问题 The Byzantine Generals Problem

拜占庭帝国就是5～15世纪的东罗马帝国，拜占庭即现在土耳其的伊斯坦布尔。我们可以想象，拜占庭军队有许多分支，驻扎在敌人城外，每一分支由各自 的将军指挥。将军们只能靠通讯员进行通讯。在观察了敌人以后，忠诚的将军们必须制订一个统一的行动计划——进攻或者撤退。然而，这些将军中有叛徒，他们不 希望忠诚的将军们能达成一致，因而影响统一行动计划的制订与传播。问题是：将军们必须有一个协议，使所有忠诚的将军们能够达成一致，而且少数几个叛徒不能 使忠诚的将军们做出错误的计划——使有些将军进攻而另一些将军撤退了。
抽象出来，可以表述成：
拜占庭将军问题：设计一个协议，一个司令要送一个命令给他的n-1个副官，使得
IC1. 所有忠诚的副官遵守同一个命令。
IC2. 假如司令是忠诚的，则每一个忠诚的副官遵守他送出的该命令。
约定：忠诚的将军将遵守协议，而叛徒则可能破坏协议，尽可能的干绕其它人的判断。叛徒是匿名的。而且最后不需要确定谁是叛徒。
注意司令也有可能是叛徒，所以IC2与IC1是不同的。
递归设计协议OM(n, m)为
OM(n, 0):
  1. 司令发送命令给所有副官。
  2. 副官按照接收到的命令行事。
OM(n, m):
  1. 司令发送命令给所有副官，设副官i收到命令vi。
  2. 分为独立的n-1轮：对每个副官i，将其视为司令，使用协议A(n-1, m-1)将vi发送到所有其它副官。
  3. 这样每个副官都收到n-1条信息，每个副官都按照出现次数更多的命令行事（如果进攻和撤退的命令一样多，则默认取撤退）。
递归证明
引理：当n>2m+k，n个将军中至多k个叛徒，协议A(n, m)满足IC2，即司令是忠诚的，每个忠诚的副官将会执行司令的命令。
进而说明：
当n>3m时，n个将军，且至多m个叛徒，协议A(n, m)可以同时满足IC1和IC2。
更深刻的结论：
当n<=3m时，n个将军中的m个叛徒可以让将军们无法达成一致，也就是满足IC1和IC2的协议不可能存在。
参考：
  1. The Byzantine Generals Problem, the first paper involved
  2. 可信计算VII:拜占庭将军问题
  3. Byzantine failure -- Wikipedia, the free encyclopedia

评论

发表评论

此博客中的热门博文

AVR Tutorial - Input / Output

图片
Overview You cannot imagine to use microcontroller without using any of its i/o pins. Finally its all about : taking input , processing it and generating output ! Thus i/o registers and their correct settings is indispensable part while learning to program any uC. We will learn how to use AVR ports and actually ‘code’ for writing/reading data to/from port pins. It is slightly confusing for beginners, however once you understand it, you will certainly appreciate the way it is designed. NOTE : I will frequently refer to ‘configuring pin’ or simply ‘pin’. Remember, a port has multiple pins. Thus in order to change setting for one port, you have to change setting for all port pins of that port. To change setting for one single pin of the port, you have to change a particular bit in associated register. Got that ? If not read this para again. Registers AVR is 8 bit microcontroller. All its ports are 8 bit wide. Every port has 3 registers associated with it each one with 8 bits...
阅读全文

AVR ADC Analog to Digital Converter

图片
What is an ADC? An ADC, or Analog to Digital Converter, allows one to convert an analog voltage to a digital value that can be used by a microcontroller. There are many sources of analog signals that one might like to measure. There are analog sensors available that measure temperature, light intensity, distance, position, and force, just to name a few. Introduction The AVR ADC The AVR ADC allows the AVR microcontroller to convert analog voltages to digital values with few to no external parts. The author wrote this tutorial with the ATMega128 in mind, though other AVRs use similar hardware. The ADC built into the ATMega128 is capable of 10 bit resolution. The ATMega128 microcontroller has 8 ADC channels, allowing up to 8 analog sources to be attached to the microcontroller. The 8 ADC channels are connected to the internal DAC through a device called a multiplexer. The multiplexer connects the 8 ADC channels (the 8 pins of Port F on the ATMega128) to the internal ADC. One channel...
阅读全文

Introduction to REST

Building Web Services the REST Way Roger L. Costello I will first provide a brief introduction to REST and then describe how to build Web services in the REST style. What is REST? REST is a term coined by Roy Fielding in his Ph.D. dissertation [1] to describe an architecture style of networked systems. REST is an acronym standing for Representational State Transfer. Why is it called Representational State Transfer? The Web is comprised of resources. A resource is any item of interest. For example, the Boeing Aircraft Corp may define a 747 resource. Clients may access that resource with this URL: http://www.boeing.com/aircraft/747 A representation of the resource is returned (e.g., Boeing747.html). The representation places the client application in a state . The result of the client traversing a hyperlink in Boeing747.html is another resource is accessed....
阅读全文