Warum das Gossipping an alle Peers der klügste Schachzug für kleine Netzwerke sein könnte

Inhaltsverzeichnis

Abstrakt und 1. Einleitung

1. Systemmodell

2. Anfangszustand des Knotens

3. Anhangsprozess

   4.1 Lokaler Anhang

   4.2 Anhang von einem anderen Knoten

   4.3 Datensatzvalidierung

   4.4 Zustandskonsistenz

4. Replikationsprozess

5. Korrektheitsbeweis

6. M-von-N Verbindungen

7. Erweiterungen und Optimierungen

Referenzen

8. Erweiterungen und Optimierungen

8.1 Gossip an alle Peers

Um den Synchronisierungsprozess zu beschleunigen, kann der Knoten Nachrichten an alle bekannten Peers senden. Diese Lösung ist sinnvoll, wenn:

\

1. Es nicht so viele Knoten im System gibt (wie 5-9)

   \

2. Die Latenz vorhersehbar ist

8.2 Reduzierung des Zeitstempelindex

Falls die Lösung Synchronisierungsprimitive verwendet und es eine Garantie gibt, dass es nicht zwei oder mehr Datensätze mit demselben Zeitstempel geben wird, dann kann der Zeitstempelindex reduziert werden.

8.3 Bitmap-Map für öffentliche Schlüssel

Um die Verkehrsmenge während der Replikation zu reduzieren, verwendet der Algorithmus Bitmap als Ersatz für öffentliche Schlüssel. Da alle Knoten alle öffentlichen Schlüssel im Netzwerk kennen sollten, ist es fair zu sagen, dass alle Knoten den gleichen Satz öffentlicher Schlüssel haben. Der Bitmap-Algorithmus (für den bestimmten öffentlichen Schlüssel des Datensatzes):

\

1. Alle öffentlichen Schlüssel werden in aufsteigender Reihenfolge sortiert

   \

2. Dann iteriert der Algorithmus über sortierte öffentliche Schlüssel: falls der öffentliche Schlüssel im Datensatz vorhanden ist, gibt der Algorithmus 1 zurück, andernfalls 0. Beispiel: Es gibt öffentliche Schlüssel im Netzwerk [A, B, C, D], der Datensatz enthält Signaturen und öffentliche Schlüssel für [B, C], dann sieht die Bitmap so aus: 0110 in binärer Form oder 6 in dezimaler Form

   \

3. Diese Zahl in Dezimalform wird dann anstelle der öffentlichen Schlüssel während des Replikationsprozesses verwendet

   \

4. Die Dekodierung erfolgt auf umgekehrte Weise

\

Referenzen

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

   \

2. Cynthia Dwork, Nancy Lynch und 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

    \

:::info Autor:

(1) Egor Zuev (zyev.egor@gmail.com)

:::

:::info Dieses Papier ist auf arxiv verfügbar unter der CC0 1.0 UNIVERSAL-Lizenz.

:::

\