MP1 uses Go-channels and Go-routines to simulate three major types of Gossip protocols in a synchronous network.
These types are Push-based Gossip, Pull-based Gossip, and Push/Pull-based Gossip. Two types of Push/Pull-based Gossip are presented, making for a total of four possible Gossip protocol options.
The user specifies which Gossip protocol they would like to see tested. Then, the user provides a value for the maximum number of nodes in a system to test. Finally, the user selects whether they would like to see the results for each round printed (Y or N).
Depending on the user's answer to the last question, the program prints the results of each infection round. Also, if the user's current directory is writeable, an HTML file is output. The HTML file displays a plot with the number of nodes tested in a system against the number of rounds it took to infect all the nodes in that system.
Once the user inputs the type of Gossip protocol to run, the number of nodes to test until, and whether to print the round results in the terminal, a call to initiateGossip() is made. To begin, a variable i (the number of nodes in the currently tested system) is set to 1. The function then begins a loop wherein it first creates an array (of length i) of Nodes. Each node in that array, except the first, is initialized with an infected value of false, representing its infection status, as well as its own personal bool channel, which will be used for communication with other nodes. The first node, however, is initialized with an infected value of true, as well as its own personal bool channel. Afterwards, the program executes the instructions specific to the user-chosen Gossip protocol until all the nodes in the system are infected. Once those results are recorded, the loop will be run again with i+1 nodes in a system. This loop is run until the variable i has reached the number of nodes the user chose to test until.
For example, if the user inputs 50 for the number of nodes, the following systems will be tested: a system with 1 node, a system with 2 nodes, a system with 3 nodes,..., a system with 50 nodes.
During each round, each node runs three total Go-routines in lockstep. The first is PushInfect(): if a node is infected, then it randomly selects a peer node and sends a true value to this peer's channel. The second is PushUpdate(): each node checks its channel to see if it has received one or more true values from its peer nodes. If it has, then it updates its infected state to true, to reflect that it has been infected. The third is clearChannel(): each node clears its bool channel using the clearChannel() function, which iterates through the node's channel and re-assigns the node's infected status to these values. Because only true values are ever passed into the channel, there is a net-zero effect on the ultimate infected status. Each of these three Go-routine functions are performed in lockstep by all nodes, made possible by synchronizing their completion through the sync.WaitGroup package. Once all nodes have been infected, which is checked each round by a call to completionCheck(), the push loop in initiateGossip() breaks, and the number of rounds is recorded and passed to Plot() to be plotted. An HTML file is created that maps number of nodes to number of rounds (convergence time).
As in the Push protocol, each node runs three total Go-routines in lockstep. The first is PullUpdate(): if a node is infected, it sends as many true values as their are nodes to its own channel. The second is PullInfect(): if a node is not infected, it selects a random peer node and makes a pull request from this peer's bool channel. If the peer node's channel has a true value, the pulling node then updates its infected status to true. The third is clearChannel(), which is executed as in the Push protocol to clear the channels for the next round. Once all nodes have been infected, which is confirmed by completionCheck(), the pull loop in initiateGossip() breaks, and the number of rounds is recorded and passed to Plot() to be plotted. An HTML file is created that maps nodes to Convergence Time.
Push/Pull combines the functions of Push and Pull protocols, as the name suggests. PushInfect() is called first in Go-routines for by each node, followed by PushUpdate(). Then, PullUpdate() and PullInfect() are called, completing the round. Each of them are executed in lockstep as in the previous protocols, and the outputs are created in the same manner.
*This version of Push/Pull is implemented as an extra feature of this MP. Its purpose is to explicitly demonstrate the efficiency of the Push/Pull protocol.
Push/Pull Switch Gossip is identical to Push/Pull, except that instead of executing both Push and Pull commands every round, it acknowledges the different phases of a general Gossip protocol, and implements the commands that are optimal to the current phase. More specifically, while the number of susceptible nodes is more than half the number of total nodes, the Push protocol is implemented. Conversely, while the number of susceptible nodes is less than half, the Pull protocol is implemented.
This timing of the switch from Push to Pull makes optimal use of random peer node selection. Push works best when random peer selection is more likely to select susceptible nodes. Pull works best when random peer selection is more likely to select infected nodes. So, when the number of susceptible nodes is greater than the number of infected, infected nodes are more likely to select and infect a susceptible node, rather than re-selecting an already-infected node--Push Gossip is used. On the other hand, as the infection spreads and the number of infected nodes is greater than the number of susceptible nodes, susceptible nodes are more likely to select and pull the gossip from an infected node, rather than selecting another susceptible node to no net-effect--Pull Gossip is used.
Clone the following git repository with git clone https://github.com/standardrhyme/mp1.
Change the current directory into the recently cloned mp1 folder. Start the Gossip protocol with go run mp1.
If an error of the following form (plot.go:7:2: cannot find package "github.com/go-echarts/go-echarts/v2/charts" in any of: /usr/local/Cellar/go/1.17/...) is triggered, run export GO111MODULE=on.
If an error of the following form (cannot find package "mp1") is triggered, start the gossip protocol with go run .
A) Enter the Integer Code corresponding to the type of Gossip protocol you wish to implement, and press ENTER.
1: Push2: Pull3: Push/Pull Original4: Push/Pull Switch
If you wish to quit the program, enter q or Q.
B) Next, enter a postive integer value of the number of nodes you want your system to test, and press ENTER.
C) Lastly, enter whether you wish to print out in your terminal the infection results of each Gossip round, and press ENTER.
Y: YesN: No
Node Struct
type Node struct {
infected bool
channel *chan bool
}0: Successful1: Incorrect command line input format2: External package function error
- The plotting function
plotinplot.gois a modified version of sample code from Go E-Charts Examples.