Table of Links Abstract and 1. Introduction Abstract and 1. Introduction System model


Initial node state


Append process
4.1 Local append
4.2 Append from another node
4.3 Record validation
4.4 State consistency


Replication process


Proof of correctness


M-of-N connections


Extensions and optimizations System model System model System model Initial node state Initial node state Initial node state Append process
4.1 Local append
4.2 Append from another node
4.3 Record validation
4.4 State consistency Append process 4.1 Local append 4.1 Local append 4.2 Append from another node 4.2 Append from another node 4.3 Record validation 4.3 Record validation 4.4 State consistency 4.4 State consistency Replication process Replication process Replication process Proof of correctness Proof of correctness Proof of correctness M-of-N connections M-of-N connections M-of-N connections Extensions and optimizations Extensions and optimizations Extensions and optimizations References 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: There are not so many nodes in the system (like 5-9)


The latency is predictable There are not so many nodes in the system (like 5-9) There are not so many nodes in the system (like 5-9) The latency is predictable 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): All public keys are sorted in ASC order


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


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


The decoding happens in the opposite way All public keys are sorted in ASC order All public keys are sorted in ASC order 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 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 This number in decimal is then used instead of public keys during replication process This number in decimal is then used instead of public keys during replication process The decoding happens in the opposite way The decoding happens in the opposite way References ABGP GitHub repository: https://github.com/ega-forever/abgp-js


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


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


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


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


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


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


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


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


Practical Byzantine Fault Tolerance and Proactive Recovery - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf ABGP GitHub repository: https://github.com/ega-forever/abgp-js ABGP GitHub repository: https://github.com/ega-forever/abgp-js https://github.com/ega-forever/abgp-js Cynthia Dwork, Nancy Lynch and Larry Stockmeyer: Consensus in the Presence of Partial Synchrony - https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf Cynthia Dwork, Nancy Lynch and Larry Stockmeyer: Consensus in the Presence of Partial Synchrony - https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf Denis Rystsov. CASPaxos: Replicated State Machines without logs - https://arxiv.org/pdf/1802.07000.pdf Denis Rystsov. CASPaxos: Replicated State Machines without logs - https://arxiv.org/pdf/1802.07000.pdf https://arxiv.org/pdf/1802.07000.pdf Paul Miller: Learning fast elliptic-curve cryptography - https://paulmillr.com/posts/noblesecp256k1-fast-ecc/ Paul Miller: Learning fast elliptic-curve cryptography - https://paulmillr.com/posts/noblesecp256k1-fast-ecc/ https://paulmillr.com/posts/noblesecp256k1-fast-ecc/ 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 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 http://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf Márk Jelasity: Gossip Protocols - http://www.inf.u-szeged.hu/\~jelasity/ddm/gossip.pdf Márk Jelasity: Gossip Protocols - http://www.inf.u-szeged.hu/\~jelasity/ddm/gossip.pdf http://www.inf.u-szeged.hu/\~jelasity/ddm/gossip.pdf 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 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 A. Shamir. How to share a secret”, Communications of the ACM 22 (11): 612613, 1979. A. Shamir. How to share a secret”, Communications of the ACM 22 (11): 612613, 1979. Distributed systems for fun and profit - http://book.mixu.net/distsys/single-page.html Distributed systems for fun and profit - http://book.mixu.net/distsys/single-page.html http://book.mixu.net/distsys/single-page.html Practical Byzantine Fault Tolerance and Proactive Recovery - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf Practical Byzantine Fault Tolerance and Proactive Recovery - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf Author:
(1) Egor Zuev (zyev.egor@gmail.com) Author: Author: (1) Egor Zuev (zyev.egor@gmail.com) This paper is available on arxiv under CC0 1.0 UNIVERSAL license. This paper is available on arxiv under CC0 1.0 UNIVERSAL license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

GitHub

Gossip Protocol Replication, Multi-Signatures, and M-of-N Consensus Explained

EScholar Technologies

Too Long; Didn't Read

Download free Tech Leaders Productivity Report!

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

15 Common Types of Unethical Behavior Found in Open-Source Projects

7 Consensus Mechanisms Developers Must Know to BUIDL for Web3

BFT Consensus: Will Your Car Full of Passengers Turn Right, Left, or Fly Over a Cliff?

Consensus Protocol in Blockchain

ConsensusPedia: An Encyclopedia of 30+ Consensus Algorithms

15 Common Types of Unethical Behavior Found in Open-Source Projects

7 Consensus Mechanisms Developers Must Know to BUIDL for Web3

BFT Consensus: Will Your Car Full of Passengers Turn Right, Left, or Fly Over a Cliff?

Consensus Protocol in Blockchain

ConsensusPedia: An Encyclopedia of 30+ Consensus Algorithms

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps