Is there a name for "yield first result parallel map"?

Question

Context

In randomized algorithms two schemes of computation are common:

• Las Vegas algorithms with random running time
• Randomized algorithms that have a probability of success, and have to be executed multiple times before getting the answer

You can also transform the latter in the former with a loop but they really don't have the same properties (like an optimal restart sequence for Las Vegas algorithms), so I want to distinguish the two. It is also possible to have randomized algorithms that can fail AND that take a random amount of time.

Parallelization with map

When parallelizing, it is common to use a map primitive: just execute those algorithms in parallel.

However, while waiting the answers from each of the nodes at each "batch", one loses tremendous amounts of time, for example if one instance of the algorithm takes much more time than the others: most processes will be idle. Of course, it is possible to group batches to avoid this situation, but then one will have to wait for the end of the batch which will take more time.

"Yield first result parallel map"

The good solution would to be able to return the result in the parent node immediately when one node finds it, hence the name "yield first result parallel map". Then there should be a way to either stop directly the children (I don't know any clean way) or be able to use the free nodes while the busy ones finish their now useless computation. Maybe one should also be able to get those calculations back in a queue if they have a result.

Another way to express it would be "getting the results of a parallel map in an asynchronous queue".

Is this concept known? Does it have another name? Is it implemented somewhere (I implemented it in MPI but was wondering whether there are other implementations)?

Answer 1

You might be able to achieve this in a system for distributed promises / distributed futures.

Some systems will have an operation any that does what you want: if p1,p2,..,pn are promises, then any(p1,p2,..,pn) returns a new promise q that resolves as soon as any of the promises p1,..,pn do. In other words, once the first promise resolves, q immediately resolves (with that value), without waiting for any of the other promises to resolve. See, e.g., promise.any in Javascript Q, Promise.any in Bluebird or Promise.any? in Concurrent Ruby.

That said, this is only half the story. When one promise resolves, what happens to the other promises? Do they keep executing or get terminated? The answer will probably depend on the specific system. If you're unlucky, all the other computations keep running, eventually the other promises resolve, and then their result is just thrown away. That'd be a waste.

However, if you're lucky -- if the system supports it, and the underlying scheduler is smart enough -- then perhaps the scheduler will terminate the computations associated with the other promises as soon as it is known that they are not needed. How could that be implemented? One way is that the implementation of any might cancel all of the other promises as soon as one of them resolves. The system could be designed to propagate cancellation transitively, and the scheduler could be implemented to terminate any in-progress computation that exists solely to resolve a promise that has subsequently been cancelled.

Ultimately, it's likely to be system-dependent whether the other computations are terminated or not in this situation, and you might need to test individual systems to determine whether they do what you want.