Analysis on Behavior of Byzantine Algorithm
Chun Zhang
Computer Science Department
Kent State University
Kent, OH, 44242
Abstract
1
Byzantinealgorithm is an efficient way to handle malfunctioning components that give conflicting information to different parts of the system[1].In this project, it is implemented in a simulated engine, and severalexperimentswere done on it, 10 pairs of input numbers according to faulty tolerance with 60 running times is tested on each experiment. The resultscompare these experiments with different pairs of input number according to faulty tolerance to show the behavior of Byzantine algorithm.
1Introduction
The objective of this experiment is to implement Byzantine algorithm for purpose of understanding the behavior of the algorithm to build reliable systems in the presence of faulty components. The program implemented is run several times with different experiment parameters to show the behavior of Byzantine algorithm under the different pair of input number based on faulty tolerance. The data is used to plot results and analyze the behavior of the algorithms.
The paper is structured as follows: section 2 is a brief introduction toByzantine algorithm,section 3is an explanation of the experiment and thevariables being tested, section 4 presents the behavior of Byzantine algorithm, section 5 presents the results of theexperiment, section 6 presents the conclusion and section 7discusses future work.
2ByzantineAlgorithm
In Byzantine algorithm, there is a commanding-general and several lieutenants, each general(process) will be either loyalty or traitor (faulty), the commanding-general sends two types of orders: attack and retreat, the lieutenants will receive the order from the commanding-general, and then sends this order to the other lieutenant who does not receive the order, until all the lieutenants get order. Because there would be one or more traitors among the lieutenants and commanding-general, so the loyalty lieutenantswould receivedifferent orders, so Byzantine algorithm would solve the following problem to make sure the algorithm finally work out that 1) all lieutenants decide on the order to obey; 2) all loyal lieutenants decide on the same order; 3) if the commanding-general is loyal, then every loyal lieutenant obeys the order he sends[1]. In order to solve these problem, Byzantine algorithm gets faulty tolerance that is: if n>= 3m+1(n is total number of all lieutenants and m is total number of all traitors), the algorithm can solve the problem; but ifn <3m+1, the algorithm won’t work properly. The experimentscompares the results with different pairs of input number according to faulty tolerance to show the behavior of Byzantine algorithm.
3 Experiments
3.1 ExperimentalSetup
Because of the feature of the Byzantine algorithm which has two different parts, loyalty and traitor, the parameter used in Byzantine algorithm simulation has n numbers represent traitor and m numbers represent lieutenant.The vector will store the number of vilieutenant’s order. The majority-vector is used to keep the majority order among all the orders(which include loyalty-order and traitor-order). The default is used to store the default order when it is hard to find whether the order is majority or not among all the orders. There is also an engine which is responsible for picking random messages from the channel to send to each process.
3.2SimulationEngine
The parameters used in Byzantine algorithm simulation started by the number of 4 nodes, 1 of 4 nodes are traitors. First, to initialize the nodes and send the initial message. Second, for each pair of input number, the program would run 60 times. Third, the input number is according to n>=3m+1 and n<3m+1 (n represents the total number of lieutenants and m represents the number of traitor). The range of input number is between 4 and 10.
4 Behavior Analysis
By inputting a pair of number (4, 1), and running the program, we can see that commanding-general 0 sent the order retreat to lieutenant 1,lieutenant 2, and lieutenant 3. Lieutenant 1 received retreat order but sent attack order to lieutenant 2 and lieutenant 3. Lieutenant 2 received retreat order and sent this order to lieutenant 1 andlieutenant 3. Lieutenant 3 did the same way withlieutenant 2, so the traitor is lieutenant 1. After receiving the message from all lieutenants, each lieutenant stored all orders and made a decision based on the majority, and result shows that all loyalty lieutenant 2 and lieutenant 3 made the same decision attack in figure 4.1.
But the following result tested based on the input number of (4,2) which violate the faulty tolerance (n>=3m+1), the result shows that loyalty lieutenant 1 and loyalty lieutenant 3 made the different decision, so if all lieutenants n is smaller than total number of 3m+1, the system would not work very well (Figure 4.2).
5 Results
The result is based on the 10 pairs of different input number according to the faulty tolerance. Figure 5.1 shows the decision after input 10 different pairs of number based on n>=3m+1. And Figure 5.2 shows the result of decisions after input 10 different pairs of number based on n<3m+1.
According to the decision based on faultytolerance, I got the column chart as following:
This column chart (figure 5.3) shows the comparison of decision that the retreat is in majority percent of the total decision, agree and wait decision is in small portion of total decision no matter the input number is n>=3m+1 or n<3m+1.
The following chart shows the changetendency of decision according to the input number:
According to Figure 5.4 we can see that the change tendency of decision is smooth if the input number based on n>=3m+1, but the change tendency of decision is a little sharp smooth if the input numberbased on n<3m+1comparing to the input number based on n>=3m+1.
6 Conclusion
The simulation engine and the result shows if total number of general is larger than or equal to 3 times of traitor plus 1, Byzantine algorithm can work very well,the retreat order has large portion of the decision and the change is smooth. The attack and wait order has small portion of the decision, most of the time, the change is smooth. Iftotal number of general is smaller than 3 times of traitor plus 1, the system cannot work very well.
The retreat is still in large portion of the decision but the change is a little bit sharp comparing the change in n>3m+1.The attack and wait still is in small portion of the decision, but the change is a little bit sharp comparing the change in n>3m+1
7Future Work
In this report, I analyzed and researched on the behavior of Byzantine algorithm on the simulated engine. The result of the experiment is based on the input number according to the faulty tolerance, however the input number ranges only from 4 to 10, in order to get more accurate result, I will test the algorithm by inputting the number from 10 and above, and will observe the running time if the input number is more than 10.
References
[1]Lamport L., Shostak R., and Pease M. “The Byzantine Generals Problem”, ACM transactions on Programming Languages and Systems 4(3), 1982
1