Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
I am a theoretical computer scientist. I have heard the following:
Practitioners do not like randomized algorithms because they are notoriously difficult to debug. So deterministic algorithms are much more preferred.
How true is this statement? If you have can provide examples or counter-examples that would be great.
One big problem is reproducibility.
Let's say your code roughly works. Most of the time it gives the right result. But sometimes it gets into a situation where it goes wrong. For a deterministic algorithm, once you find an input that gives the wrong result, you can use the same input and use the debugger to follow all the steps until you find where it goes wrong.
With a probabilistic algorithm, you may run into a situation where there is no input that always gives the wrong result, but any input can sometimes give the wrong result. So you cannot provide an input that will go wrong. You cannot provide an input where you know that following all steps will end up at some step that goes wrong.
At the very least you need to be able to provide both input and the state of the random number generator to the code, which would make the algorithm deterministic. Of course in normal operation the algorithm should be as random as possible, but you need it to be reproducible.
I went about this answer in a bit of a different direction - not from a debugging, but a testing perspective:
Usually a pure function has a very simple setup:
Same input in, same result out.
That makes it very easy to define proper test cases - You select a set of standard test values and a few of special interest (depending on what your function does), write your testing methods for it, comparing what the function returns to what you expected it to return. This gives you a solid set of testing methods that you can run whenever you make any changes.
Once you start having randomness in your methods, you run into this issue:
Same input in, many possible values out.
Now you need to know ALL the possible values that your randomized function could return for a given input, and test against those. And depending on what your randomized function does, that's just either plainly unfeasible (due to many options that you need to manually or programmatically add in), or straight up impossible.
Suddenly the amount of effort to create a solid test suite went up dramatically, at which point it usually just gets straight skipped.
How would we avoid this?
To avoid this during writing your algorithms, you would encapsulate the piece of randomness. You would try to put the snippet that actually causes the random part inside its own object, outside of the algorithm. Now you can actually mock that object during your test suite - basically fixing the values that the "randomized" object would return. It's not ideal, and does not cover every scenario, but so does barely any testing. The effort to create your test suite went up only slightly, since the "randomness" is gone now, and you can treat it like a normal, pure function for testing purposes.
Similar principles apply to debugging a function manually: Most of the time you do not actually know what random value the algorithm generated, and thus it's difficult to recreate what exactly happened in the function that broke it. That makes manual debugging very difficult.
I'll answer with the worst possible example I know: A race condition due to improper locking in kernel code.
A race condition is the very notion of non-determinism: You have no control on whether it occurs or not. You are not even putting in random input on purpose, but rather the machine itself acts as the random generator.
As such, if you have such a race condition, you cannot reliably reproduce it. Every time you try your code, the results will be different. Worse: The code may work fine in the majority of cases, but trigger a kernel panic or corrupted data in one-in-a-million cases.
How do you collect information about a condition that you can only observe once in a while? You absolutely must resort to logging, a debugger won't do you any good. As such, your perception is limited to the log output that you have introduced into the code. Worse, the very action of writing a log may well make the race condition next to impossible to trigger, the error may turn into a heisenbug.
Because the condition is non-deterministic, your log output will read different each time you run your code. That means, one time you might get a kernel panic, the next time you might get corrupted data, the third time you may get corrupted data in some other location, and so on, and so forth. Your bug is not so much a moving target, but rather a jumping target that shows up somewhere, and when you investigate, it's gone to pop up right behind your back the next time it shows itself.
Debugging such conditions can be very frustrating.
On the other hand, if you have a deterministic bug, you can always backtrace its genesis step by step. You see the result, you get a question about which input was responsible for the wrong result, you run again looking at those inputs, and then you recurse on the wrong input until you identify the place where good inputs lead to a wrong output.
In short:
Debugging nondeterministic code is a nondeterministic algorithm itself which is not guaranteed to terminate.
Debugging deterministic code is a deterministic algorithm.
