MPI Wave algorithm with leader election and spanning tree construction

Implementing a wave algorithm with leader election and spanning tree construction in MPI is a complex task that involves multiple phases: leader election using a heartbeat algorithm, constructing a spanning tree, and optionally, broadcasting the tree structure to all nodes.

The following implementation assumes a simple network where each process can communicate directly with any other process. In a real-world scenario, the network topology might be more complex, affecting how processes communicate.

mpi-wave-algorithm-advanced.c

#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.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: Spanning Tree Construction
    int parent = -1;
    if (world_rank == leader) {
        for (int i = 0; i < world_size; i++) {
            if (i != leader) {
                MPI_Send(&leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
            }
        }
    } else {
        MPI_Recv(&parent, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        for (int i = 0; i < world_size; i++) {
            if (i != world_rank && i != parent) {
                MPI_Send(&leader, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
            }
        }
    }
 
    // Phase 3: Broadcasting the Tree Structure (Optional)
    int* tree = malloc(world_size * sizeof(int));
    if (world_rank == leader) {
        // Initialize tree structure
        for (int i = 0; i < world_size; i++) {
            tree[i] = -1; // -1 indicates no parent
        }
    } else {
        MPI_Recv(tree, world_size, MPI_INT, parent, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    }
    tree[world_rank] = parent;
 
    // Propagate the tree structure to children
    for (int i = 0; i < world_size; i++) {
        if (i != world_rank && i != parent) {
            MPI_Send(tree, world_size, MPI_INT, i, 0, MPI_COMM_WORLD);
        }
    }
 
    // Display the tree structure
    printf("Process %d: Leader is %d, Parent is %d\n", world_rank, leader, tree[world_rank]);
    for (int i = 0; i < world_size; i++) {
        printf("Process %d: Parent of %d is %d\n", world_rank, i, tree[i]);
    }
 
    free(tree);
    MPI_Finalize();
    return 0;
}

Leader Election: Each process sends and receives leader values to determine the global leader.

Spanning Tree Construction: The leader initiates the spanning tree construction. Each node sets its parent and forwards the message to other nodes.

Broadcasting the Tree: The leader initializes the tree structure and sends it to its children. Each node then propagates this structure down the tree.

The output will display the leader and parent of each process, along with the spanning tree structure.