How the Program Works

Luby's algorithm consists of a while loop.

The while loop of Luby's algorithm is implemented with a while loop in Run method of MisAlgorithm class.

The while loop calls six methods- Round1, Round2, ..., and Round6. In Round1 method, the node generates a random number and sends it to all of its neighbors.

In Round2 method, the node receives the generated random numbers of neighbors and find the maximum of them.

In Round3 method, if the random number of the node is greater than all of the neighbors' random numbers, the status of the node changes to Mis. After that, the node sends its status to all of its neighbors to inform them if its status is changed or not.

In Round4 method, each node receives the sent messages that contains the status of its neighbors. If there is at least one neighbor with status Mis, then the status of the node will be ComMis.

In Round5 method, if the status of a node is ComMis, then it sends its Id to its neighbors. The reasen of this task is explained in the explanation of the next method.

In Round6 method, if the status of the node is Unknown, it updates the list (vecNeiId) that contains the neighbors Ids. In the update task, the node deletes the Ids of all ComMis neighbors from vecNeiId. It should be noted that the nodes with status Mis or ComMis are deactivate at the end of each iteration. The update task is necessary because if it is not done, in the next iteration, the node waits for receiving messages from the deactivate neighbors.

Nodes with status Unknown continue to run the while loop until their statuses are changed.