I'm looking for an algorithm to handle the following problem, which I'm (for now) calling the "bad apple" algorithm.
- I've got 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 in the same sandbox.
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.
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?
For the sake of argument, let's assume that a bad process brings down its sandbox instantaneously, and a good process never does.