Pourquoi Bavarder avec Tous les Pairs Pourrait Être la Décision la Plus Intelligente pour les Petits Réseaux

Table des liens

Abstrait et 1. Introduction

1. Modèle du système

2. État initial du nœud

3. Processus d'ajout

   4.1 Ajout local

   4.2 Ajout depuis un autre nœud

   4.3 Validation des enregistrements

   4.4 Cohérence d'état

4. Processus de réplication

5. Preuve de correction

6. Connexions M-of-N

7. Extensions et optimisations

Références

8. Extensions et optimisations

8.1 Gossip à tous les pairs

Pour accélérer le processus de synchronisation, le nœud peut envoyer des messages à tous les pairs connus. Cette solution a du sens quand :

\

1. Il n'y a pas beaucoup de nœuds dans le système (comme 5-9)

   \

2. La latence est prévisible

8.2 Réduction de l'index d'horodatage

Dans le cas où la solution utilise des primitives de synchronisation et qu'il existe une garantie qu'il n'y aura pas deux ou plusieurs enregistrements avec le même horodatage, alors l'index d'horodatage peut être réduit.

8.3 Carte bitmap pour les clés publiques

Pour réduire la quantité de trafic pendant la réplication, l'algorithme utilise une bitmap comme remplacement pour les clés publiques. Comme tous les nœuds doivent être conscients de toutes les clés publiques du réseau, il est juste de dire que tous les nœuds ont le même ensemble de clés publiques. L'algorithme bitmap (pour la clé publique d'un certain enregistrement) :

\

1. Toutes les clés publiques sont triées par ordre croissant

   \

2. Ensuite, l'algorithme itère sur les clés publiques triées : si la clé publique est présente dans l'enregistrement, l'algorithme renvoie 1, sinon 0. Exemple : il y a des clés publiques dans le réseau [A, B, C, D], l'enregistrement inclut des signatures et des clés publiques pour [B, C], alors la bitmap ressemblera à : 0110 sous forme binaire, ou 6 sous forme décimale

   \

3. Ce nombre en décimal est ensuite utilisé à la place des clés publiques pendant le processus de réplication

   \

4. Le décodage se fait de manière opposée

\

Références

1. Dépôt GitHub ABGP : https://github.com/ega-forever/abgp-js

   \

2. Cynthia Dwork, Nancy Lynch et 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 Auteur :

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

:::

:::info Cet article est disponible sur arxiv sous licence CC0 1.0 UNIVERSAL.

:::

\