小規模ネットワークにおいて全てのピアにゴシップすることが最も賢明な選択である理由
リンク一覧
概要と1. はじめに
-
システムモデル
-
初期ノード状態
-
追加プロセス
4.1 ローカル追加
4.2 別ノードからの追加
4.3 レコード検証
4.4 状態の一貫性
-
レプリケーションプロセス
-
正確性の証明
-
M-of-N接続
-
拡張と最適化
参考文献
8. 拡張と最適化
8.1 全ピアへのゴシップ
同期プロセスを高速化するために、ノードは既知の全ピアにメッセージを送信することができます。このソリューションは以下の場合に有効です：
\
-
システム内のノード数が多くない場合（5-9程度）
\
-
遅延が予測可能な場合
8.2 タイムスタンプインデックスの削減
ソリューションが同期プリミティブを使用し、同じタイムスタンプを持つレコードが2つ以上存在しないことが保証されている場合、タイムスタンプインデックスを削減することができます。
8.3 公開鍵用のビットマップマップ
レプリケーション中のトラフィック量を削減するために、アルゴリズムは公開鍵の代わりにビットマップを使用します。すべてのノードがネットワーク内のすべての公開鍵を認識している必要があるため、すべてのノードが同じ公開鍵セットを持っていると言えます。ビットマップアルゴリズム（特定のレコードの公開鍵用）：
\
-
すべての公開鍵は昇順でソートされます
\
-
その後、アルゴリズムはソートされた公開鍵を反復処理します：公開鍵がレコードに存在する場合、アルゴリズムは1を返し、そうでなければ0を返します。例：ネットワークに公開鍵[A, B, C, D]があり、レコードに[B, C]の署名と公開鍵が含まれている場合、ビットマップは二進形式で0110、または十進形式で6となります
\
-
この十進数は、レプリケーションプロセス中に公開鍵の代わりに使用されます
\
-
デコードは逆の方法で行われます
\
参考文献
-
ABGP GitHubリポジトリ: https://github.com/ega-forever/abgp-js
\
-
Cynthia Dwork, Nancy Lynch and Larry Stockmeyer: 部分同期の存在下でのコンセンサス - https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf
\
-
Denis Rystsov. CASPaxos: ログなしのレプリケートされたステートマシン - https://arxiv.org/pdf/1802.07000.pdf
\
-
Paul Miller: 高速楕円曲線暗号の学習 - https://paulmillr.com/posts/noblesecp256k1-fast-ecc/
\
-
Robbert van Renesse, Dan Dumitriu, Valient Gough, Chris Thomas. アンチエントロピープロトコルのための効率的な調整とフロー制御 - http://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf
\
-
Márk Jelasity: ゴシッププロトコル - http://www.inf.u-szeged.hu/\~jelasity/ddm/gossip.pdf
\
-
Colin J. Fidge. 部分順序を保持するメッセージパッシングシステムにおけるタイムスタンプ - http://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algos-papers/4.pdf
\
-
A. Shamir. 秘密の共有方法", Communications of the ACM 22 (11): 612613, 1979.
\
-
楽しみと利益のための分散システム - http://book.mixu.net/distsys/single-page.html
\
-
実用的なビザンチン障害耐性と積極的な回復 - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf
\
:::info 著者:
(1) Egor Zuev (zyev.egor@gmail.com)
:::
:::info この論文は arxivで入手可能 であり、CC0 1.0 UNIVERSALライセンスの下で提供されています。
:::
\
