为何在小型网络中向所有节点八卦可能是最明智的选择

链接表

摘要和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. "如何共享秘密"，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通用许可协议。

:::

\