MPI Basics: a Real Deadlock That Only Shows Up at Scale

MPI processes don’t share memory — the only way data moves between them is a message, sent and received explicitly. That explicitness is also where a very real deadlock comes from.

rank and size: every process knows its place

// mpi_hello.c
#include <stdio.h>
#include <mpi.h>

int main(int argc, char** argv) {
    MPI_Init(&argc, &argv);
    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    printf("Hello from rank %d of %d\n", rank, size);
    MPI_Finalize();
    return 0;
}

mpicc -o mpi_hello mpi_hello.c
mpirun -np 4 ./mpi_hello

Hello from rank 0 of 4
Hello from rank 1 of 4
Hello from rank 2 of 4
Hello from rank 3 of 4

mpirun -np 4 launches four independent OS processes, each running the same program — rank is each process’s own identity within that group, not a thread ID within one process.

A basic send and receive

// mpi_sendrecv.c (basic Send/Recv, not to be confused with the MPI_Sendrecv call later)
if (rank == 0) {
    int value = 42;
    MPI_Send(&value, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
    printf("rank 0 sent %d to rank 1\n", value);
} else if (rank == 1) {
    int received;
    MPI_Recv(&received, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    printf("rank 1 received %d from rank 0\n", received);
}

mpirun -np 2 ./mpi_sendrecv

rank 0 sent 42 to rank 1
rank 1 received 42 from rank 0

The bug: a deadlock that only appears at scale

// mpi_deadlock.c
int buf[500000];
for (int i = 0; i < 500000; i++) buf[i] = rank;
int recvbuf[500000];

int other = (rank == 0) ? 1 : 0;
printf("rank %d: sending to rank %d\n", rank, other);
MPI_Send(buf, 500000, MPI_INT, other, 0, MPI_COMM_WORLD);
MPI_Recv(recvbuf, 500000, MPI_INT, other, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
printf("rank %d: done\n", rank);

mpicc -o mpi_deadlock mpi_deadlock.c
mpirun -np 2 ./mpi_deadlock

rank 1: sending to rank 0
rank 0: sending to rank 1
[hangs forever]

Both ranks print “sending” — and then nothing. Each is blocked inside MPI_Send, waiting for the other rank to call MPI_Recv before its own send can complete. But neither rank reaches MPI_Recv — both are still stuck on the MPI_Send line above it. This is a real, classic deadlock: two ranks each waiting on the other to do something neither will ever get to do.

Why the exact same pattern worked earlier

// mpi_small.c -- identical Send-then-Recv structure, one int instead of 500,000
MPI_Send(&value, 1, MPI_INT, other, 0, MPI_COMM_WORLD);
MPI_Recv(&received, 1, MPI_INT, other, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
printf("rank %d: done, received %d\n", rank, received);

mpirun -np 2 ./mpi_small

rank 1: done, received 0
rank 0: done, received 1

No deadlock — MPI_Send is allowed to buffer a small message internally and return immediately, without waiting for the matching MPI_Recv at all. A single int fits in that buffer; 500,000 ints don’t. This is what makes the bug genuinely dangerous: the same code structure works perfectly with small test data and deadlocks the first time it runs against a realistically large one.

The fix: MPI_Sendrecv

// mpi_fixed.c
int other = (rank == 0) ? 1 : 0;
MPI_Sendrecv(buf, 500000, MPI_INT, other, 0,
             recvbuf, 500000, MPI_INT, other, 0,
             MPI_COMM_WORLD, MPI_STATUS_IGNORE);
printf("rank %d: done, received first value %d from rank %d\n", rank, recvbuf[0], other);

mpicc -o mpi_fixed mpi_fixed.c
mpirun -np 2 ./mpi_fixed

rank 1: exchanging with rank 0
rank 0: exchanging with rank 1
rank 1: done, received first value 0 from rank 0
rank 0: done, received first value 1 from rank 1

MPI_Sendrecv combines both operations into one call that MPI implements to avoid exactly this ordering problem — both ranks can call it simultaneously, each naming who to send to and who to receive from, with no risk of both being stuck waiting on the other’s plain Send.

Practice

int other = (rank == 0) ? 1 : 0;
if (rank == 0) {
    MPI_Send(buf, 500000, MPI_INT, other, 0, MPI_COMM_WORLD);
    MPI_Recv(recvbuf, 500000, MPI_INT, other, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
} else {
    MPI_Recv(recvbuf, 500000, MPI_INT, other, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    MPI_Send(buf, 500000, MPI_INT, other, 0, MPI_COMM_WORLD);
}
printf("rank %d: done\n", rank);

rank 0: done
rank 1: done

int size;
MPI_Comm_size(MPI_COMM_WORLD, &size);
printf("running with %d ranks\n", size);

mpirun -np 6 ./mpi_hello

Hello from rank 5 of 6
Hello from rank 0 of 6
Hello from rank 1 of 6
Hello from rank 2 of 6
Hello from rank 4 of 6
Hello from rank 3 of 6

Next: collective communication — broadcasting, reducing, and scattering data across every rank at once.