為何對小型網絡而言向所有節點傳播可能是最明智的選擇

連結表

摘要和 1. 引言

1. 系統模型

2. 節點初始狀態

3. 附加流程

   4.1 本地附加

   4.2 從其他節點附加

   4.3 記錄驗證

   4.4 狀態一致性

4. 複製流程

5. 正確性證明

6. M-of-N 連接

7. 擴展和優化

參考文獻

8. 擴展和優化

8.1 向所有對等節點傳播

為了加速同步過程，節點可以向所有已知的對等節點發送訊息。這種解決方案在以下情況下有意義：

\

1. 系統中的節點數量不多（如 5-9 個）

   \

2. 延遲是可預測的

8.2 減少時間戳索引

如果解決方案使用同步原語，並且保證不會有兩個或更多具有相同時間戳的記錄，則可以減少時間戳索引。

8.3 用於公鑰的位圖映射

為了減少複製過程中的流量，該算法使用位圖代替公鑰。由於所有節點都應該知道網絡中的所有公鑰，可以公平地說，所有節點都有相同的公鑰集合。位圖算法（針對特定記錄的公鑰）：

\

1. 所有公鑰按升序排序

   \

2. 然後算法遍歷排序後的公鑰：如果記錄中存在該公鑰，則算法返回 1，否則返回 0。例如：網絡中有公鑰 [A, B, C, D]，記錄包含 [B, C] 的簽名和公鑰，則位圖將為：二進制形式的 0110，或十進制形式的 6

   \

3. 在複製過程中，使用這個十進制數字代替公鑰

   \

4. 解碼過程則以相反的方式進行

\

參考文獻

1. ABGP GitHub 倉庫：https://github.com/ega-forever/abgp-js

   \

2. Cynthia Dwork, Nancy Lynch 和 Larry Stockmeyer：部分同步環境下的共識 - https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf

   \

3. Denis Rystsov. CASPaxos：無日誌的複製狀態機 - https://arxiv.org/pdf/1802.07000.pdf

   \

4. Paul Miller：快速學習橢圓曲線密碼學 - https://paulmillr.com/posts/noblesecp256k1-fast-ecc/

   \

5. Robbert van Renesse, Dan Dumitriu, Valient Gough, Chris Thomas. 反熵協議的高效協調和流量控制 - http://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf

   \

6. Márk Jelasity：傳播協議 - http://www.inf.u-szeged.hu/\~jelasity/ddm/gossip.pdf

   \

7. Colin J. Fidge. 保留部分順序的消息傳遞系統中的時間戳 - http://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algos-papers/4.pdf

   \

8. A. Shamir. 如何共享秘密", Communications of the ACM 22 (11): 612613, 1979.

   \

9. 分佈式系統的樂趣與收益 - http://book.mixu.net/distsys/single-page.html

   \

10. 實用拜占庭容錯和主動恢復 - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf

    \

:::info 作者：

(1) Egor Zuev ([email protected])

:::

:::info 本論文可在 arxiv 上獲取，採用 CC0 1.0 通用許可協議。

:::

\