オフライン環境での分散型メッセージブロードキャストに必要なアルゴリズム

Question

システムは、登録済みのコミュニティに電話（音声またはテキスト）でメッセージをブロードキャストするための高速かつ信頼性の高い分散型の方法を許可する必要があります。メッセージは、事前に定義されたルールと連絡先リストに従ってメンバー間で転送されます。

準備フェーズは、オンラインである：

「放送局」は「メーリングリスト」

の人が自分の電話番号（およびセキュリティフレーズ）

に登録することにより、参加を開いている

1. 各連絡先を入手他の2〜4人のメンバーのリスト（セキュリティフレーズとともに）。

ブロードキャストは、連絡先リストを呼び出すことによってメッセージを開始します。 ブロードキャストルールは簡単です：電話を受けて（セキュリティフレーズを聞く）、メッセージを聞いて同じ方法で連絡先リストに転送します。

私の質問がある - に最適化された方法で（自分の連絡先リストを作成する方法を意味する）メンバーをリンクする方法：

1. 迅速（ツリーの最小レベルの）メッセージを配布し
2. 各リストに4つ以下の連絡先（より良い2または3）
3. 冗長性のあるレベル（メンバーが利用できない場合は、ブランチ全体を切断しません）。

Answer 1

簡単な答えは、ツリーをブランチアウトし、各ブランチの "葉"を他のブランチのすべての非葉に接続させます。

詳細を説明させてください。あなたは15人の人がいるとします。

が

{ 
    1: [2, 3], 
    2: [4, 5], 
    3: [6, 7], 
    4: [8, 9], 
    5: [10, 11], 
    6: [12, 13], 
    7: [14, 15], 

その後2ある8、9、10、11以下の葉と下の葉が3ある12、13、14、15は、だから今あなたがそれらを接続します：次のようにそれらをオフに開始

8: [3, 6], 
    9: [7, 12], 
    10: [13, 14], 
    11: [15], 
    12: [2, 4], 
    13: [5, 8], 
    14: [9, 10], 
    15: [11] 
    } 

したがって、2より下のツリー、3より下のツリーがあります。一方の側に欠落しているものがあれば、他方の側には接続されています。

分岐係数を増やすと、ツリーの葉部分が増え、すべてを多重接続できるようになります。 （ルートから任意の要素までの距離も短くなります。）