9

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

Simplifications

For the sake of argument, let's assume that a bad process brings down its sandbox instantaneously, and a good process never does.

Improve this question
6
  • How guaranteed is that the badly-behaved process will bring the sandbox down? I mean - can we assume a finite time when we know for sure given sandbox is running only "clean" processes because it didn't crash?
    – SF.
    Oct 30, 2013 at 11:11
  • Unfortunately not: the fact that a sandbox doesn't crash for 5 minutes doesn't mean that all of the processes are well-behaved, but it does give us more confidence of that fact.
    – Roger Lipscombe
    Oct 30, 2013 at 11:14
  • ...but for the purposes of this question, we could approximate by allowing a finite time, I guess.
    – Roger Lipscombe
    Oct 30, 2013 at 11:14
  • You have to atomize what you consider to be a "passed" and "failed" process. If it runs 5 minutes without failing, it could still technically be a bad apple, but like the halting problem, you're never going to have 100% certainty when it passes without making some hard lines in the sand.
    – Neil
    Oct 30, 2013 at 11:20
  • Sounds like you are on the right track. If there are many processes and multiple bad apples, then you may have to use a large value of M, or uneven groups so that you can isolate known good apples, then keep the known-good in one sandbox and keep dividing the unknown processes between your other sandboxes until you have identified the individuals. The more sandboxes you have, the faster this will go. As @Neil pointed out, this is a big O of log base M of N algorithm, so increasing M will cut your trials.
    – GlenPeterson
    Oct 30, 2013 at 12:58

1 Answer 1

Reset to default
2

If you were finding one bad apple, then you could apply the algorithm:

  1. Divide N into M groups
  2. Perform the test on each group.
  3. If group size greater than 1, return to step 1, replacing N with number of items in bad group.

Likewise, if you were finding the one "good" apple, then the same algorithm applies, but rather finding the good group.

This algorithm has a O(log_M (N)) performance rate but it depends on the fact that there is only one bad apple.

If you don't know how many good/bad apples there are, then you could use the following algorithm:

For each M processes in N
  Test M processes

This is the worst case scenario, but it runs in O(N/M) time (or O(N) depending on if you consider a single pass as a single test or as a collection of tests performed in parallel). All things considered, this is not a bad approach by any means.

There may be algorithms which perform better than this, but it requires that you know how many bad apples/good apples there are in the batch. Not knowing this factor, while I can't prove it, I'd be willing to bet that you cannot do better than the latter algorithm listed above.

Hope that helps!

Edit: From a practical perspective, I understand that some of these operations are not easily performed. That's true, however, the unfortunate reality is that you cannot determine the bad apple strictly from which processes were running on the sandbox that was running at that moment without being to at least activate or disactivate processes. If the question pertains to the algorithm, I think I have answered that. If the question pertains to how to deal with a situation like this, then perhaps the question would be better suited for superuser SE.

Improve this answer
5
  • 1
    Unfortunately, I can't "test" the processes; all I know is that one of the sandboxes crashed, and that it was caused by one or more of the processes therein.
    – Roger Lipscombe
    Oct 30, 2013 at 11:07
  • 1
    The problem is that, after bisecting the set, both partitions could have bad apples in them. Which makes me think that I need more than a simple partition...
    – Roger Lipscombe
    Oct 30, 2013 at 11:10
  • @RogerLipscombe You're trying to apply an algorithm to a real world scenario. Of course you're not going to be able to test the processes one at a time, and it may prove difficult to test these processes on different machines, however, if you want to get to the bottom of this, you're going to have to find a way one way or another. If you insert variables which cannot be resolved, you're simply not going to be able to find an algorithm which can accurately pinpoint the bad apple(s).
    – Neil
    Oct 30, 2013 at 11:17
  • OK, so by "test", you merely mean "leave them running for long enough to be confident"...?
    – Roger Lipscombe
    Oct 30, 2013 at 11:31
  • @RogerLipscombe I suppose so. May take more time, but you are the one that has to figure out how long to wait. Knowing that and following this algorithm, you could technically find out any and all bad apples. However, it may be faster to simply look at the windows event log for crashes.
    – Neil
    Oct 30, 2013 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.