Generating uniformly distributed random numbers in distributed environment

Question

I have to generate a "unique Random Number" in a Wireless sensor network which works on the principle of Gossiping.

The requirements are:

1. Each node has to generate a unique Random Number, without having any shared knowledge of what other nodes have generated.
2. The Distribution of the generated Random number should be uniform with respect to each other.
3. It would be preferable if the range of the generated random number is around 10-16 bits or may be lesser.

The limitations are:

1. One node has no idea what number the other nodes in the network are generating.
2. Implementation in C, C++.

I also have the provision of using a unique seed for random number generation. the seed could be any number in the range 0-2^15.

If there is no way of generating such numbers, then it would be helpful if there is any method by which I can meet some of the above requirements.

If you can suggest me some way to achieve this result it would be really helpful.

Answer 1

for this solution to work you must know the total number of nodes in the generation network. let this number be n.

the basic idea is to generate uniformly distributed random numbers on each participating node inside a given interval. the n intervals of the participating nodes must not overlap. a shared seed does not complicate matters if the total number of nodes does not change and each node can be assigned statically some integer i <= n such that each number is issued exactly once. instead of generating a single random number on each turn, n numbers are generated, and node i takes the i-th number from this series.

however, the overall distribution of random numbers generated will not be uniform unless ...:

• you synchronize random number generation.
• all intervals have the same size.

for information on random number generation on individual nodes see here.