Why Gossiping to All Peers Might Be the Smartest Move for Small Networks

Table of Links

Abstract and 1. Introduction

2. System model

3. Initial node state

4. Append process

   4.1 Local append

   4.2 Append from another node

   4.3 Record validation

   4.4 State consistency

5. Replication process

6. Proof of correctness

7. M-of-N connections

8. Extensions and optimizations

References

8. Extensions and optimizations

8.1 Gossip to all peers

To speed up synchronization process, node may send messages to all known peers. This solution make sense when:

1. There are not so many nodes in the system (like 5-9)

2. The latency is predictable

8.2 Reducing Timestamp index

In case the solution use synchronization primitives and there is a guarantee that there won’t be two or more records with the same timestamp, then timestampIndex may be reduced.

8.3 bitmap map for public keys

To reduce amount of traffic during replication, the algorithm uses bitmap as replacement for public keys. As all nodes should be aware of all public keys in network, it’s fair to say, that all nodes have the same set of public keys. The bitmap algorithm (for the certain record’s public key):

1. All public keys are sorted in ASC order

2. Then algorithm iterate over sorted public keys: in case the public key is present in record then algorithm return 1 otherwise 0. Example: there are public keys in network [A, B, C, D], the record includes signatures and public keys for [B, C], then bitmap will look: 0110 in binary form, or 6 in decimal form

3. This number in decimal is then used instead of public keys during replication process

4. The decoding happens in the opposite way

References

1. ABGP GitHub repository: https://github.com/ega-forever/abgp-js

2. Cynthia Dwork, Nancy Lynch and Larry Stockmeyer: Consensus in the Presence of Partial Synchrony - https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf

3. Denis Rystsov. CASPaxos: Replicated State Machines without logs - https://arxiv.org/pdf/1802.07000.pdf

4. Paul Miller: Learning fast elliptic-curve cryptography - https://paulmillr.com/posts/noblesecp256k1-fast-ecc/

5. Robbert van Renesse, Dan Dumitriu, Valient Gough, Chris Thomas. Efficient Reconciliation and -Flow Control for Anti-Entropy Protocols - http://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf

6. Márk Jelasity: Gossip Protocols - http://www.inf.u-szeged.hu/\~jelasity/ddm/gossip.pdf

7. Colin J. Fidge. Timestamps in Message-Passing Systems That Preserve the Partial Orderinghttp://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algos-papers/4.pdf

8. A. Shamir. How to share a secret”, Communications of the ACM 22 (11): 612613, 1979.

9. Distributed systems for fun and profit - http://book.mixu.net/distsys/single-page.html

10. Practical Byzantine Fault Tolerance and Proactive Recovery - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf