MPI distributed, unordered work
You can use MPI_ANY_SOURCE and MPI_ANY_TAG for receiving from anywhere. After receiving you can read the Information (source and tag) out of the MPI_Status structure that has to passed to the MPI_Recv call.
If you use this you do not neccessary need any asynchronous communication, since the master 'listens' to everybody asking for new jobs and returning results; and each slave does his task and then sends the result to the master asks for new work and waits for the answer from the master.
You should not have to work with scatter/gather at all since those are ment for use on an array of data and your problem seems to have more or less independant tasks.
I would like to write a MPI program where the master thread continuously submits new job to the workers (i.e. not just at the start, like in the MapReduce pattern).
Initially, lets say, I submit 100 jobs onto 100 workers.
Then, I would like to be notified when a worker is finished with a job. I would send the next job off, whose parameters depend on all the results received so far. The order of results does not have to be preserved, I would just need them as they finish.
I can work with C/C++/Python.
From the documentation, it seems like I can broadcast N jobs, and gather the results. But this is not what I need, as I don't have all of them available, and gather would block. I am looking for a asynchronous, any-worker recv call, essentially.