Problem Description:The Byzantine
Generals Problem is an abstraction of the problem of reaching an agreement
in a system where components can fail in an arbitrary manner. In such a
case, the component can behave arbitrarily and can send different messages
to different components.
The abstraction of the problem deals with the idea of generals of the Byzantine Army communicating with each other. The generals must reach a consensus among themselves whether to attack or retreat based on the messages exchanged. The problem is complicated by the fact that some of the generals can be traitors who may send conflicting messages to the other generals. The solution to the problem must allow all the loyal generals to agree upon a common plan of action. Also, if the commanding general is loyal then all the loyal generals must obey the order he sends.
Problem Solution:The application implements two Byzantine Agreement Protocols : Oral Message Algorithm and Signed Message Algorithm.
Solution with Oral Messages: This algorithm works only when the number of generals 'N' is atleast 3M+1 where 'M' is the number of faulty nodes (traitors). The algorithm works in rounds where in each round messages are exchanged between the generals. In Round 1, the commander sends a command to N-1 other generals. In the next round, each receiver communicates the value he receives from the commander to the other N-2 generals and so on. Eventually when all rounds are completed each loyal general takes the majority of the messages that he has recieved and uses that as the value.
Solution with Signed Messages: In this algorithm, each general can send only unforgeable signed messages. This will prevent a traitor general from sending a value other than what he receives. This algorithm can handle 'M' traitors with any number of generals. Also, since only unforgeable signed messages are sent the number of messages exchanged is smaller.
Example of 4 Generals with 1 traitor: This is to demonstrate the Oral Message Algorithm with 4 generals in the presence of a single traitor. Here, the messages exchanged are also displayed graphically.
About the Application: This application has been developed as a part of the course requirement for ECE655(Fault Tolerant Computing),Spring 2001,ECE Dept, UMass, Amherst. The application has been developed using Java. The algorithms are implemented as Java Applets. For help on using the application refer to the Help page.
System Requirements: The application makes use of Java Swing Applets which requires that the web browser supports Java PlugIn. The JavaPlugIn is available with JRE1.3.1 and also here.
Acknowledgements: Prof. Israel Koren, ECE Dept, UMass, Amherst.
Lamport, Shostak and Pease. "The Byzantine Generals Problem". ACM Transactions
on Programming Languages and Systems, July 1982.
2. Pankaj Jalote. Fault Tolerance in Distributed Systems.
3. Dhiraj Pradhan. Fault-tolerant Computer System Design.
4. Chandy and Misra. Parallel Program Design, A Foundation.
5. Nitin Vaidya. "Degradable Agreement in the Presence of Faults". Technical Report.
6. Gong, Lincoln and Rushby. "Byzantine Agreement with Authentication: Observations and Applications in Tolerating Hybrid and Link Faults"