4

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.

10
  • 4
    The random number generator is going to be your friend on this one.
    – Mike Nakis
    Jan 10, 2012 at 14:02
  • 2
    What's wrong with, say, checking divisibility by five of a random integer between one and five? It will randomly be true 1/5th of the time, so you can use this condition to decide on when to put garbage answers. You could also keep track of the number of garbage runs, to avoid exceeding the 1/5-th threshold, i.e. if the condition tells you to produce garbage, but doing so would exceed the threshold, you put in the correct result instead. Jan 10, 2012 at 14:10
  • 2
    It's hard to suggest something else when we don't know why a random number generator is too simple and not "real" enough. Jan 10, 2012 at 14:23
  • 1
    if this is a purely academic exercise, then there is no solution that is "real enough" by definition. you should try math.se if you want help finding a more complex mathematical function, if you can improve the question your asking and show its a research level question then you could try theoretical cs.
    – Ryathal
    Jan 10, 2012 at 15:44
  • 1
    @FrustratedWithFormsDesigner I have edited the question (IMHO) appropriately. I would please urge you and others to consider reopening the question now. Please give it another chance.
    – Chani
    Jan 10, 2012 at 16:17

4 Answers 4

4

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.

3
  • 2
    I have done a lot to make more sense in the question. Please tell me if its clear now to you. And if yes, please reopen the question.
    – Chani
    Jan 10, 2012 at 16:20
  • The question is much better. See my edits. Jan 10, 2012 at 19:59
  • now that you have given a very nice conceptual pointers, could you add some regarding the practical implementation for the 4 points you talk about? I am talking C++ libraries, or just plain ideas about how to simulate them in the kind of environment i had talked about in the question.
    – Chani
    Jan 10, 2012 at 20:15
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.
4
  • OP insists that it never be more than 1/5 errors, so maybe somewhere they need to log how many times they make a "random" error and when they hit 1/5 of total "runs", they just stop using the random number generator. Of course that implies that it is known ahead of time how many executions of the program there will be. Jan 10, 2012 at 14:58
  • 2
    OP talks about 1/5th but then only wants 1/50 (200 of 10,000) to have errors. Jan 10, 2012 at 15:11
  • Haha! Good point. Either way, if they want such tight control over it, they may even want to predetermine (by choosing randomly) exactly which 200 of the 10000 executions will fail. Jan 10, 2012 at 15:13
  • @mhoran_psprep sry that was a typo. i need 1/5th consistency in the amount of false answers.
    – Chani
    Jan 10, 2012 at 15:57
2

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.

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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