Por qué chismear con todos los pares podría ser la jugada más inteligente para redes pequeñas

Tabla de Enlaces

Abstracto y 1. Introducción

1. Modelo del sistema

2. Estado inicial del nodo

3. Proceso de anexión

   4.1 Anexión local

   4.2 Anexión desde otro nodo

   4.3 Validación de registros

   4.4 Consistencia de estado

4. Proceso de replicación

5. Prueba de corrección

6. Conexiones M-de-N

7. Extensiones y optimizaciones

Referencias

8. Extensiones y optimizaciones

8.1 Gossip a todos los pares

Para acelerar el proceso de sincronización, el nodo puede enviar mensajes a todos los pares conocidos. Esta solución tiene sentido cuando:

\

1. No hay tantos nodos en el sistema (como 5-9)

   \

2. La latencia es predecible

8.2 Reducción del índice de marca de tiempo

En caso de que la solución utilice primitivas de sincronización y haya garantía de que no habrá dos o más registros con la misma marca de tiempo, entonces el índice de marca de tiempo puede reducirse.

8.3 Mapa de bitmap para claves públicas

Para reducir la cantidad de tráfico durante la replicación, el algoritmo utiliza bitmap como reemplazo de las claves públicas. Como todos los nodos deben conocer todas las claves públicas en la red, es justo decir que todos los nodos tienen el mismo conjunto de claves públicas. El algoritmo de bitmap (para la clave pública de un registro determinado):

\

1. Todas las claves públicas se ordenan en orden ASC

   \

2. Luego el algoritmo itera sobre las claves públicas ordenadas: en caso de que la clave pública esté presente en el registro, el algoritmo devuelve 1, de lo contrario 0. Ejemplo: hay claves públicas en la red [A, B, C, D], el registro incluye firmas y claves públicas para [B, C], entonces el bitmap se verá: 0110 en forma binaria, o 6 en forma decimal

   \

3. Este número en decimal se utiliza en lugar de las claves públicas durante el proceso de replicación

   \

4. La decodificación ocurre de manera opuesta

\

Referencias

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

   \

2. Cynthia Dwork, Nancy Lynch y Larry Stockmeyer: Consenso en presencia de sincronía parcial - https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf

   \

3. Denis Rystsov. CASPaxos: Máquinas de estado replicadas sin logs - https://arxiv.org/pdf/1802.07000.pdf

   \

4. Paul Miller: Aprendiendo criptografía de curva elíptica rápida - https://paulmillr.com/posts/noblesecp256k1-fast-ecc/

   \

5. Robbert van Renesse, Dan Dumitriu, Valient Gough, Chris Thomas. Reconciliación eficiente y control de flujo para protocolos anti-entropía - http://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf

   \

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

   \

7. Colin J. Fidge. Marcas de tiempo en sistemas de paso de mensajes que preservan el ordenamiento parcial - http://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algos-papers/4.pdf

   \

8. A. Shamir. Cómo compartir un secreto", Communications of the ACM 22 (11): 612613, 1979.

   \

9. Sistemas distribuidos por diversión y beneficio - http://book.mixu.net/distsys/single-page.html

   \

10. Tolerancia a fallos bizantinos práctica y recuperación proactiva - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf

    \

:::info Autor:

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

:::

:::info Este documento está disponible en arxiv bajo la licencia CC0 1.0 UNIVERSAL.

:::

\