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)?