# 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.