I'm looking for an algorithm to handle the following problem, which I'm (for now) calling the bad apple algorithm.The problemI'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.The questionIf 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?SimplificationsFor the sake of argument, let's assume that a bad process brings down its sandbox instantaneously, and a good process never does.
Bad apple algorithm, or process crashes shared sandbox
algorithms