MPI Topology Validation Using Epidemic Algorithm

Creating a full program implementation that includes all stages—leader election, topology validation through an epidemic algorithm, and constructing a topology matrix using a tree algorithm.

Assumptions:

• Every process can communicate with every other process (full connectivity).
• Leader election is based on the highest rank.
• After the leader is elected, it starts the epidemic algorithm to count the nodes.
• The tree algorithm for topology matrix construction assumes a simple tree structure.

mpi-topology-validation.c

#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_ITERATIONS 5
 
int main(int argc, char** argv) {
    MPI_Init(&argc, &argv);
 
    int world_rank, world_size;
    MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
    MPI_Comm_size(MPI_COMM_WORLD, &world_size);
 
    // Phase 1: Leader Election
    int leader = world_rank;
    for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
        for (int i = 0; i < world_size; i++) {
            if (i != world_rank) {
                MPI_Send(&leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
                int received_leader;
                MPI_Recv(&received_leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                if (received_leader > leader) {
                    leader = received_leader;
                }
            }
        }
    }
 
    // Phase 2: Epidemic Algorithm for Node Count
    double val = (world_rank == leader) ? 1.0 : 0.0;
    for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) {
        for (int i = 0; i < world_size; i++) {
            if (i != world_rank) {
                MPI_Send(&val, 1, MPI_DOUBLE, i, 0, MPI_COMM_WORLD);
                double recv_val;
                MPI_Recv(&recv_val, 1, MPI_DOUBLE, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                val = (val + recv_val) / 2.0;
            }
        }
    }
    double node_count = 1.0 / val;
 
    // Phase 3: Tree Algorithm for Topology Matrix
    int *topology = (int*)malloc(world_size * sizeof(int));
    for (int i = 0; i < world_size; i++) {
        topology[i] = -1;  // Initialize topology array
    }
 
    if (world_rank == leader) {
        for (int i = 0; i < world_size; i++) {
            if (i != leader) {
                topology[i] = leader;  // Leader assumes it is the parent
            }
        }
    } else {
        topology[world_rank] = world_rank;  // Non-leader nodes assume they are their own parent
    }
 
    // Broadcast the topology
    MPI_Bcast(topology, world_size, MPI_INT, leader, MPI_COMM_WORLD);
 
    // Print results
    printf("Process %d: Leader is %d, Node count is %.0f\n", world_rank, leader, node_count);
    for (int i = 0; i < world_size; i++) {
        printf("Process %d: Parent of node %d is %d\n", world_rank, i, topology[i]);
    }
 
    free(topology);
    MPI_Finalize();
    return 0;
}

This program is a simplification and idealization of the concepts. Practical implementations in a distributed system would likely require more sophisticated handling of network topologies and error conditions.

The epidemic algorithm used here is a basic version for demonstrating the concept. In a real-world scenario, it would need to be adapted to the specific network topology and conditions.

The topology matrix in this program is highly simplified and assumes a direct parent-child relationship based on the rank. In reality, constructing a topology matrix would depend on the actual network structure and might involve more complex algorithms.