MPI_Recv message ordering vs MPI_Send message ordering

Question

While trying to simulate the behaviour of a network using OpenMPI, I am experiencing an issue which can be summed up as follows:

Rank 2 sends a message (message1) to rank 0;

Rank 2 sends a message (message2) to rank 1;

Rank 2 sends a message (message3) to rank 0;

At his own turn, rank 0 receives both messages from rank 2 and forwards them to rank 1 (in the correct order);

Rank 1 receives the messages in the following order: message1, message3 and message2.

This behaviour only occurs only once in a while running the program. Usually (6 times out of 7), following the same pattern, rank 1 appears to receive the messages in the expected order (i.e: message2, message1, message3)

I am only using the basic MPI_Recv and MPI_Send functions.

Answer 1

MPI makes no guarantee about the order in which messages from different processes will be recieved. In fact, a receive operation can begin after a send has completed if an output buffer is used in standard mode: http://www.mpi-forum.org/docs/mpi-1.1/mpi-11-html/node40.html#Node40. The only order you can guarantee with standard mode send is that message3 will always arrive after message1. Here is a possible (not unique) sequence that would lead to your anomalous scenario:

1. Rank 2 sends a message (message1) to rank 0;
2. Rank 0 receives message1 from rank2;
3. Rank 0 sends a message (message1) to rank 1;
4. Rank 1 receives message1 from rank0;
5. Rank 2 sends a message (message2) to rank 1;
6. Rank 2 sends a message (message3) to rank 0;
7. Rank 0 receives message3 from rank2;
8. Rank 0 sends a message (message3) to rank 1;
9. Rank 1 receives message3 from rank0;
10. Rank 1 receives message2 from rank2;

Essentially, MPI_Send is an alias for either MPI_BSend or MPI_SSend, and it is not up to you which one is picked. Your anomaly is caused by MPI_BSend. You can guarantee a write to the corresponding receive buffer using synchronous mode (MPI_SSend) or ready mode (MPI_RSend). The main diffrerence between the two is that ready mode requires the receiver to already be waiting for the message for it not to fail, while synchronous mode will wait for it to happen.

If you are on a Linux platform, you can play with the standard mode by using the nice command to increase the priority of rank0 and decrease that of rank2. The anomaly should happen more consistently the more you increase the priority difference. Here is a brief tutorial on the subject: http://www.nixtutor.com/linux/changing-priority-on-linux-processes/