Byzantine Generals Problem

from http://www.nist.gov/dads/HTML/byzantine.html

Definition

The problem of reaching a consensus among distributed units if some of them give misleading answers. The original problem concerns generals plotting a coup. Some generals lie about whether they will support a particular plan and what other generals told them. What percentage of liars can a decision making algorithm tolerate and still correctly determine a consensus?

Note: One variant is: suppose two separated generals will win if both attack at the same time and lose if either attacks alone, but messengers may be captured. If one decides to attack, how can that general be sure that the message has reached the other general and the other general will attack, too?

The variant sounds virtually identical to the PrisonersDilemma, but with some risk in communication instead of absolute separation. The original problem is a different one, opposite to the PrisonersDilemma in that all the parties are communicating with each other, not kept incommunicado

• http://www.cs.wisc.edu/~bart/739/papers/byzantine.pdf
• http://www.cs.cornell.edu/gupta/byzantine.htm
• http://www.google.com/search?hl=en&q=Byzantine+Generals+Problem&btnG=Google+Search