Class SynchLubyMIS

source code

        distalgs.Algorithm --+    
                             |    
distalgs.Synchronous_Algorithm --+
                                 |
                                SynchLubyMIS

A randomized algorithm that constructs a Maximal Independent Set

The algorithm works in stages, each consisting of three rounds.

• Round 1: In the first round of a stage, the processes choose their respective vals and send them to their neighbors. By the end of round 1, when all the val messages have been received, the winners--that is, the processes in F--know who they are.
• Round 2: In the second round, the winners notify their neighbors. By the end of round 2, the losers--that is, the processes having neighbors in F--know who they are.
• Round 3: In the third round, each loser notifies its neighbors. Then all the involved processes--the winners, the losers, and the losers' neighbors-- remove the appropriate nodes and edges from the graph. More precisely, this means the winners and losers discontinue participation after this stage, and the losers' neighbors remove all the edges that are incident on the newly removed nodes.

Requires:

• Every process knows state['n'], the size of the network

Effect:

• Every process knows state['MIS']. A boolean representing whether it is a member of the Maximal Independent Set found by Luby's algorithm.