Topology Verification

After the leader has been chosen and the topology has been distributed to all nodes, it is useful to validate the information. Validation can involve very complex processes, but for this laboratory, we will use validation based on the number of nodes present in the cluster.

Calculating the number of nodes can be done using an epidemic algorithm.

Calculating the Number of Nodes Using an Epidemic Algorithm

The functionality of an epidemic algorithm is similar to the spread of a disease in which there is a patient zero:

1. "Patient zero" transmits information to their neighbors.
2. The neighbors of patient zero become "infected" and also transmit the information to their neighbors.

To calculate the number of nodes, node 0 will be the leader node. It will hold an initial value equal to 1. All other nodes hold a value of 0. The leader node will calculate the arithmetic average between its value and the values of its neighbors. Information will be synchronized in both directions. Other nodes will perform the same operation with their neighbors.

The algorithm repeats until convergence is achieved. In the end, all nodes will have the same subunitary value. Dividing 1 by this value will result in the number of nodes in the cluster.

Pseudocode:

val = 0
if (rank == leader)
    val = 1
else
    val = 0

for (step = 0; step < convergence; step++) {
    for (i = 0 to nr_neighbours) {
        send to process neighbour[i]
	receive recv_val from neighbour[i]
	val = (val + recv_val) / 2;
    }
}

return (1 / val); // number of nodes in the network

tip

An example of running this algorithm can be seen here.

Building the Topology Matrix Using the Tree Algorithm

The tree algorithm is a wave algorithm used for tree topologies or for a graph topology with a covering tree, where the initiator nodes are the leaf nodes in the topology. In this algorithm, nodes transmit messages to their parents, which are then forwarded along the same path to the root of the topology (the root of the tree), which will make a decision that will be distributed throughout the network of nodes.

We can build the matrix of the entire topology using the tree algorithm, specifically by applying this algorithm to the covering tree of the node graph. Initially, each node has its topology matrix, where initially only the neighbors of that node will appear.

The steps are as follows:

• Each node, except the leader, which is the root node in the covering tree, will send its topology to the parent node, which will complete its topology with the topologies received from the child nodes.
• The leader will have the complete topology of the node network and will spread it to the entire network of nodes. Specifically, each non-leaf node will send the completed topology to the child nodes.

Pseudocode:

// Information is received from all children of the current node, and the topology matrix is updated
for (i = 0 to nr_proc) {
    // For the children of the current node
    if (rank == parents[i]) {
        for (j = 0 to nr_proc) {
	    // Receive the local topology of node i, line by line
	    receive recvTop[j] from node i
	    for (k = 0 to nr_proc) {
	        if (top[j][k] == 0) {
		    // Update the topology matrix
		    top[j][k] = recvTop[j][k];
                }
            }
        }
    }
}

// The current node sends its own topology matrix to its parent, row by row
for (i = 0 to nr_proc) {
    // If the current node has a parent
    if (parents[rank] != -1) {
        send top[i] to parents[rank]
    }
}

// If the current node is not the leader, it receives the topology, row by row, from its parent
if (rank != leader) {
    // The leader node has no parent
    for (i = 0 to nr_proc) {
	receive top[i] from parents[rank]
    }
}

// The complete topology is sent to child nodes, line by line
for (i = 0 to nr_neighbors) {
    if (neighbor[i] != parents[rank]) {
	for (j = 0 to nr_proc) {
            send top[j] to neighbor[i]
        }
    }
}

tip

An example of running this algorithm can be seen here.