The GHS algorithm is used for finding the minimum spanning tree in a weighted graph. By considering all the assumptions for this algorithm, a graph will be given to you in a file with the following format Format:

you can learn more about kompics in /KopmicsGuidance

Initially, every singleton node is a fragment, which is the root of the fragment. Each node then looks for the least weight edge connecting to a neighbor. If both nodes pick each other, then a fragment of two nodes is formed at level 1. When two fragments join, the node with higher id across the least weight outgoing edge serves as the new root. However, during absorb, the root of the higher level fragment continues to serve as the new root. The notification about the change of root is sent out using the changeroot message. Communication within a fragment takes place via the edges of the spanning tree. Thus, each node keeps track of its parent and children

Root broadcasts “initiate” in its own fragment, collects the report from other nodes about eligible edges using a convergecast, and determines the least weight outgoing edge. To test if an edge is outgoing, each node sends a test message through a candidate edge. The receiving node may send a reject message (when it belongs to same fragment) or an accept message (when it belongs to a different fragment).

Let process i send “test” to process j:

1. Item 1 Case 1. If name(i) = name(j) then send “reject”
2. Item 2 Case 2. If name(i) 6= name(j) ∧ level(i) ≤ level(j), then node j sends“accept”
3. Item 3 Case 3. If name(i) 6= name(j) ∧ level(i) > level(j), then wait until level(j) =level(i) and then send “accept/reject”.

repeat

1. Test edges as outgoing or not
2. Determine least weight outgoing edge - it becomes a tree edge
3. Send join (or respond to join)
4. Update level & name & identify new coordinator/root until there are no outgoing edges

1. Basic: initially all branches are basic
2. Branch: all tree edges
3. Rejected: not a tree edge

Once the lwoe has been found, the root broadcasts a changeroot message to its fragment. The node that found the lwoe receives a changeroot message, it sends a join message along that edge indicating willingness to join

If i sends a join message to j, where level(i) = level(j) = L and receives a join message from j, then:

• Edge (i, j) becomes a branch message.
• Between i and j whoever has the larger id becomes the new root.
• The name of the fragment will be w(i, j).
• Its level will be L + 1.
• The root will broadcast (initiate, L + 1, name) message to the entire combine fragment.

If i in fragment T at level L sends a join message to j in fragment T' at level L' , where

L < L' , and

T' has not yet found lwoe , then T' absorbs T:

• Process j sends a join message to i, indicating that T has been absorbed.
• The root of T' will be the root of the combined fragment.
• T changes its level to L' and adopts the name of T'.
• They collectively search for a lwoe.
• Edge (i, j) becomes a branch message.

If T'has already chosen a lwoe, then the lwoe cannot be(i, j). That means T'is joining another T''. Once this join is complete, the combined fragment of T'and T'' starts a new search and will send an initiate message to T to signal that T has been absorbed.