Simulating/developing_a_testing_strategy for factors that might cause the same algorithm to produce different results in Distributed Systems

Question

This is a Purely Academic Question

Context:

I am working with some algorithms which are meant to arrive at a consensus in distributed systems. I intended to tackle Byzantine faults with these algorithms. For this I have implemented several algorithms published in IEEE papers and need a platform to test these algorithms. I wanted to test the merit of existing algorithms. For this I implemented thousands of Linux Containers on my system and now i want to do message passing between them, or say simulate my distributed system. But the question is the data that is flowing must have faults. This is the genesis of this question. Why I need something more sophisticated than RNG's is that I will need to attach some real credibility to my work. I want it to tackle some real world application generating faults rather than just fix the faults I myself generated in an algorithm.

So, I need to simulate the factors that result in Byzantine faults.

OR, to quote FrustatedWithFormsDesigner: I need to develop a testing strategy that will have a deliberate number of faults to test fault-handling

To Summarize:

Say I am running a program in a distributed environment, then what are the factors that might end up generating Byzantine faults and is it possible for me to inculcate these factors in my simulation and how?

So, what I need is:

A program that will make a small no. of mistakes every now and then, and I should not know what mistakes it has made and when.

I do not need it to make multiple mistakes in one set(run of the algorithm), but rather I plan on making (say) 10,000 runs of the program, and I need it to make mistakes 2000 times ..

Very importantly, I must be sanguine that there are no more than (1/5)n mistakes, where n is the total no. of results generated using the program.

The results that I am talking about here can be anything that is quantifiable and verifiable, like eg. an array of values.

Doing something like this:

1for(int i=0; i<10000; i++)
2   //one fifth of the times put garbage in the array using random function!!
3   for (int j=0; j<5; j++)
4      array[j]=j;

using a RNG in step 2 to hide where the fault is present is too simplistic, trivial and not real enough.

I thought I could use some algorithm built around some mathematical function that is bound to fail 1/5th of the times, But I could not think of any.

P.S. Please tell me if you need more data to understand the problem.

Answer 1

There are a few different kinds of faults that can occur in a distributed system:

1. Sensor noise
2. Dropped messages
3. Duplicate messages
4. Corrupted messages

All of these can occur in isolation, or as a "run" of several failures of the same type in a row.

The best way to simulate sensor noise is with a gaussian distribution, which you get by feeding a uniformly distributed RNG into a Box-Muller transform. This will produce values that look more "real," by usually being only off by a little bit, but every once in a while off by a lot.

For the others, you just use a regular RNG to cause the fault with a certain probability. The trick is figuring out the individual probability so you aren't likely to exceed 20% faults at the same time. This is where my math gets rusty, but you could probably solve it monte carlo style. Set the probability of one fault to a certain value, then run your simulation 10,000 times to see if you ever get more than 20% at once, then adjust your individual probability accordingly. You aren't going to be able to guarantee it without flat out disallowing more faults than that, but you can make the probability sufficiently small. It depends if you want a realistic simulation or a thorough test of boundary conditions, because in real life you can't guarantee less than 20% either.

Answer 2

There are two approaches:

• non-random: use a counter, and every 5th run tell the software to make a mistake. It will work perfectly, but it will be predictable.
• Random: use the random method/command/function in your language of choice to pick a number between 1 and 5 inclusive. If it is 1 then tell the software to make a mistake. For a low number of runs you might get too many or too few runs with mistakes. For a large number of runs you will get closer to the expected number. You will not be able to anticipate which runs will have errors.

Answer 3

Is the problem that you want faults to occur randomly, and with something like a uniform distribution, but want a hard cap?

If you want k events out of n tries, randomly, create an event with a probability of k/n. Now, do this again: you want either k or k-1 events out of n-1 tries, depending on whether you got the event or not. Continue until the denominator (i.e., number of remaining tries) hits zero. Once you have k events, the numerator will be stuck at 0, so you don't get any more. The distribution will (IIRC) be uniform.

Answer 4

You are not offering much information here, and you seem to contradict yourself several times. To rephase your question--so if I head off in the wrong direction you will at least know what wrong direction I headed in--you want to run a short program 10,000 times and have it give one wrong answer in 200 runs. This gives a 2% failure rate, and even in the failures only one (out of maybe 10,000 numbers output) is wrong.

A random number generator will do this for you. Decide at the start of a run if it is to be good or bad. Then pick an output number at random and give it a bad value. (You don't want to check each number or you might get less than or more than one bad number in the run.)

Now the real trick is that a random number generator starts with a seed, which usually comes from the system time. If system time comes in, say 100ths of a second rather than microseconds, and your program runs real fast, most of your runs will have identical random numbers. In short, your numbers aren't random. You are going to need to save the seed from one run and feed it into the next one, presumably with a disk file. (Or space out your runs somehow.)

I have no idea why you want to do this, but you might want to arrange to have your failures come in waves. You could divide your runs into groups of 1000, half of which would have no failures and the other half of which would average 40 failures each. This could lure testers into a false sense of security, or get them so bored they're not looking when the shooting starts. Of course, if this is what you are trying to do, you should come up with much more fiendish patterns that this.