"Bad apple" algorithm, or process crashes shared sandbox
- by Roger Lipscombe
I'm looking for an algorithm to handle the following problem, which I'm (for now) calling the "bad apple" algorithm.
The problem
I've got a N processes running in M sandboxes, where N M.
It's impractical to give each process its own sandbox.
At least one of those processes is badly-behaved, and is bringing down the entire sandbox, thus killing all of the other processes.
If it was a single badly-behaved process, then I could use a simple bisection to put half of the processes in one sandbox, and half in another sandbox, until I found the miscreant.
This could probably be extended by partitioning the set into more than two pieces until the badly-behaved process was found. For example, partitioning into 8 sets allows me to eliminate 7/8 of the search space at each step, and so on.
The question
If more than one process is badly-behaved -- including the possibility that they're all badly-behaved -- does this naive algorithm "work"? Is it guaranteed to work within some sensible bounds?
