HW#3 --- last modified March 02 2019 21:25:32..
Solution set.
Due date: Mar 22
Files to be submitted:
Hw3.tex
Byzantine.zip
Purpose: To learn more about algorithms for parallel computation. To implement
a distributed algorithm.
Specification:
Do problems 29.1-6, 29.2-1, 29.3-5 from Handout 1 and Exercise 12.2
p338 from Handout 2. Submit these problems in Hw3.tex.
For the coding part of the homework I would like you to code up the Byzantine agreement algorithm from
Handout 2 and submit this in Byzantine.zip . Your program should consist of a driver class
ElectionManager and another class Voter. The driver class should be run from the command line with a line like:
java ElectionManager number_of_voters number_faulty
The ElectionManager should then construct, initialize, and start number_of_voters many
Voter objects. Of these, the first number_faulty should be faulty and the rest normal.
The class Voter is a subclass of javax.swing.Timer which implements ActionListener.
The constructor for this class takes an int delay and a boolean faultyNotFaulty and then call its parent's
constructor with this delay and with argument null for the ActionListener. After the Voter is constructed use its
addActionListener method with argument this so that it's actionPerformed method will be called when the timer goes off. Voter
should have an internal field to store faultyNotFaulty. Voter should also have a int field roundNumber, which
keeps track of which round in the agreement process we are at. This should initially be 0. The class
ElectionManager should randomly choose the delay of each Voter object it creates from 1 mS to 5000 mS.
As ElectionManager constructs each Voter it should add it to an ArrayList<Voter> object. Then when all of the
Voter's have been constructed it should call each Voter's public void initialize(ArrayList<Voter> list)
method to set an electorate field of each Voter object. Once this is done, the ElectionManager calls the start
method of each Voter. The actionPerformed method of a Voter checks roundNumber. If this is zero, it immediately
votes, outputs the vote to the standard output as well as which Voter it was, increments its roundNumber, and then informs all of the
other Voter's. If this is greater than zero, it checks if it has received
votes from all the other Voter's this round. If `no', actionPerformed finishes (and so the voter
goes to sleep
for delay mS). If `yes',
it votes, outputs the vote
to the standard output as well as which Voter it was, increments its roundNumber, and then informs all of the other Voter's.
To vote, a Voter either follows the algorithm from the handout if it is normal and votes either 1 for heads or 0 for tails, or if its
faulty, it should randomly choose between 1 or 0. To inform the other Voters, it iterates through its electorate ArrayList<Voter>
and
for each Voter other than itself, calls that Voter's, receiveVote(int i, Voter v) method with either 0 or 1 depending on its vote and
with itself as the Voter. If following the algorithm from the book a Voter sets its vote value permanently
then the Voter outputs which Voter it is followed by "Agreement reached !!", says what the agreement was, and then calls its stop() method.
If a faulty voter ever sees that more than 7/8 th of the Voters vote the same way for two consecutive rounds it also prints its name and
calls
its halt method. The algorithm from the book uses a global coin. This can be implemented as a public static method in the ElectionManager
named flip() which returns 0 or 1. The value of flip is randomly choosen the first time it is called. The next number_of_voter's many times
it is called it stays constant, then a new coin flip is done, etc. If you modify the algorithm so as not to use a global coin you should say
how and why your resulting protocol works in the comments in your files. (up to 2 point bonus for doing this well). It should be noted that
the handout's faulty Voter can give a different vote value
to each element in its list. If you like you can implement this more generalized faulty Voter or if you like stick with my simplified one.
This method should increment the given Voter's vote count as well as increment either the heads or tails count depending on what the
vote was.
Point Breakdown
Handout problems (1pt each) |
4pts
|
Departmental coding guidelines for Java followed |
1pt
|
ElectionManager works as described |
1pt
|
Voter's constructor, initialize and receive method as described (1pt each) |
3pts
|
Voter's actionPerformed method as described |
2pts
|
Total | 10pts |
|