Early Solutions
Several solutions were originally described by Lamport, Shostak, and Pease in 1982. They began by noting that the Generals' Problem can be reduced to solving a "Commander and Lieutenants" problem where Loyal Lieutenants must all act in unison and that their action must correspond to what the Commander ordered in the case that the Commander is Loyal. Roughly speaking, the Generals vote by treating each others' orders as votes.
- One solution considers scenarios in which messages may be forged, but which will be Byzantine-fault-tolerant as long as the number of traitorous generals does not equal or exceed one third. The impossibility of dealing with one-third or more traitors ultimately reduces to proving that the 1 Commander + 2 Lieutenants problem cannot be solved, if the Commander is traitorous. The reason is, if we have three commanders, A, B, and C, and A is the traitor: when A tells B to attack and C to retreat, and B and C send messages to each other, forwarding A's message, neither B nor C can figure out who is the traitor, since it isn't necessarily A – the other commander could have forged the message purportedly from A. It can be shown that if n is the number of generals in total, and t is the number of traitors in that n, then there are solutions to the problem only when n is greater than or equal to 3t + 1.
- A second solution requires unforgeable signatures (in modern computer systems, this may be achieved in practice using public-key cryptography), but maintains Byzantine fault tolerance in the presence of an arbitrary number of traitorous generals.
- Also presented is a variation on the first two solutions allowing Byzantine-fault-tolerant behavior in some situations where not all generals can communicate directly with each other.
Read more about this topic: Byzantine Fault Tolerance
Famous quotes containing the words early and/or solutions:
“Love is the hardest thing in the world to write about. So simple. You’ve got to catch it through details, like the early morning sunlight hitting the gray tin of the rain spout in front of her house. The ringing of a telephone that sounds like Beethoven’s “Pastoral.” A letter scribbled on her office stationery that you carry around in your pocket because it smells of all the lilacs in Ohio.”
—Billy Wilder (b. 1906)
“Every man is in a state of conflict, owing to his attempt to reconcile himself and his relationship with life to his conception of harmony. This conflict makes his soul a battlefield, where the forces that wish this reconciliation fight those that do not and reject the alternative solutions they offer. Works of art are attempts to fight out this conflict in the imaginative world.”
—Rebecca West (1892–1983)