database - 分散環境での一様分布乱数の生成

Question

ゴシップの原理で動作するワイヤレスセンサーネットワークで「一意の乱数」を生成する必要があります。

要件は次のとおりです。

1. 各ノードは、他のノードが生成したものを共有することなく、一意の乱数を生成する必要があります。
2. 生成された乱数の分布は、互いに均一である必要があります。
3. 生成された乱数の範囲が約 10 ～ 16 ビットであるか、それよりも小さい場合が望ましいでしょう。

制限事項は次のとおりです。

1. 1 つのノードは、ネットワーク内の他のノードが生成している数を認識していません。
2. C、C++ での実装。

また、乱数の生成に一意のシードを使用することもできます。シードは0-2^15の範囲の任意の数値です。

そのような数値を生成する方法がない場合、上記の要件のいくつかを満たす方法があれば助かります。

この結果を達成する方法を教えていただければ、本当に助かります。

Answer 1

このソリューションが機能するには、生成ネットワーク内のノードの総数を知る必要があります。この数を とするn。

基本的な考え方は、特定の間隔内の各参加ノードで均一に分散された乱数を生成することです。参加ノードのn間隔が重複してはなりません。共有シードは、ノードの総数が変化せず、各ノードに整数i<=nを静的に割り当てて、各番号を 1 回だけ発行できる場合、問題を複雑にしません。各ターンで単一の乱数を生成する代わりに、n数字が生成され、ノードiはiこのシリーズから - 番目の数字を取得します。

ただし、生成される乱数の全体的な分布は、次の場合を除き均一ではありません。

• 乱数生成を同期します。
• すべての間隔は同じサイズです。

個々のノードでの乱数生成については、こちらを参照してください。