Assignment GoalsProblemProgram NotesDeliverablesYALE UNIVERSITYDEPARTMENT OF COMPUTER SCIENCECPSC 427a: Object-Oriented Programming Handout #5Professor M. J. Fischer September 28, 2010Problem Set 3Due before midnight on Wednesday, October 6, 2010.1 Assignment Goals1. To learn how to organize a simulation of a large system.2. To learn about a simple model of asynchronous distributed computing.3. To learn how to use derived classes and virtual functions.2 ProblemWe consider the consensus problem in a simple setting. The players are trying to reachagreement on a course of action. Each player has a current preference called her choice,which is the current value stored in her choice register. We assume a simple binary choice,so the choice value is either 0 or 1. The players communicate with each other, and fromtime to time player may change their choices. The goal is for the players to arrive at a stagewhere all players are making the same choice and nobody subsequently changes her choice.In this case, we say the players have reached consensus, and we call the common choice theconsensus value.We assume a very primitive model of communication. A communication step consistsof a randomly chosen player (called the sender ) sending a message containing her currentchoice value to another randomly chosen player (called the receiver ). The receiver may thenchoose to change her choice, depending on the message received and her internal state. Shemay also update her internal state depending on the message received.A population of players solves the consensus problem if the following is true:1. For all possible initial choices of the players, if the players start in their designatedinitial states, the computation reaches consensus with probability 1.2. Once consensus has been reached, no player ever changes her choice. In particular, ifall players have the same initial choice, then that choice is the consensus value.There are many possible algorithms for reaching consensus. A particularly simple al-gorithm is fickle. Here, whenever a player receives a message, she changes her choice ifnecessary to agree with the sender. That is, she sets her choice register to the value con-tained in the message she receives. It is easy to see that there is some sequence of messagetransmissions that causes the system to reach consensus, and once consensus has beenreached, no player will change her choice. It is also easy to believe that it might take a verylarge number of random steps to reach consensus.The algorithm, follow the crowd, seems to be a big improvement. Here, each player hasa 1-bit state register in which she saves the last message received. She changes her choice2 Problem Set 3only when she gets two messages in a row that both disagree with her current choice. Thus,she waits until she gets a sense of the crowd before deciding to follow. We assume that allplayers start with 0 in their state registers.The purpose of this assignment is to simulate the two algorithms fickle and followthe crowd to determine how long each takes on average to reach consensus. Assume apopulation of numPlayers many players. An experiment for a particular algorithm consistsof numTrials runs of the algorithm. Each run begins with numPlayers/2 players choosing1 and the remaining players choosing 0. Random communication steps are generated andapplied until consensus is reached, at which point the run ends. For each step, a sender isselected uniformly at random from the set of all players, and a receiver is selected uniformlyat random from the remaining players (other than the sender). The receiver’s choice andstate are updated according to the rules of the selected algorithm. Note that in both ofthese algorithms, no further changes of choice are possible once consensus has been reached.The result of the experiment is the number of steps taken to reach consensus, averaged overthe runs in the experiment.The three parameters of interest for an experiment are the algorithm being used, thenumber of runs in the experiment (numTrials), and the population size (numPlayers. Onceyour program is working, you should use it to explore the parameter space. This meansthat you should run experiments with many different combinations of these parameters soas to give one a pretty good idea of the performance characteristics of the two algorithms.Increasing numTrials will reduce the variance in the average run time. This is not astatistic course, and I am not going to ask you to do a confidence analysis. Rather, youmay take numTrials to be 100 in your experiments (but it should still be a parameter toyour program).Increasing the population size numPlayers will cause a big increase in run time. Youmay terminate your experiments once the run time grows to more than a few seconds. Thismay come rather quickly with fickle, but that is for you to find out.3 Program NotesFor ease of testing, your executable program should be called agree and should take upto four command line arguments: The name of the algorithm to run (either fickle orcrowd), numPlayers, numTrials, and seed, where seed is the seed to be used for the pseu-dorandom number generator used to choose the sender and receiver at each step. Missingparameters should use default values of fickle for the algorithm, 10 for numPlayers, 100for numTrials, and the result of time(0) for the seed. Parameters can only be missingfrom the right end of the command line, so if the command has two arguments, for example,then the missing arguments are numTrials and seed.The code should be modular and structured into natural well-defined classes of small tomodest size. In particular, you should define a base class Player to represent the player.This class should have derived classes Fickle and Crowd to represent the two different kindsof players – those that use the fickle algorithm and those that use the follow the crowdalgorithm. The function that updates the receiver’s choice and state registers (perhapscalled receive()) should be virtual in class Player and be defined appropriately in classesFickle and Crowd. You will need several other classes as well. You may use the variousdemo programs such as BarGraph and problem set solutions as guides for how to structurea program of modest complexity such as this.Handout #5—September 28, 2010 34 DeliverablesYou should submit this assignment using the submit script that you will find in/c/cs427/bin/ on the Zoo. Remember to submit the following items:1. Source