Por que Fazer Gossip para Todos os Pares Pode Ser a Jogada Mais Inteligente para Redes Pequenas

Tabela de Links

Resumo e 1. Introdução

1. Modelo do sistema

2. Estado inicial do nó

3. Processo de anexação

   4.1 Anexação local

   4.2 Anexação de outro nó

   4.3 Validação de registro

   4.4 Consistência de estado

4. Processo de replicação

5. Prova de correção

6. Conexões M-de-N

7. Extensões e otimizações

Referências

8. Extensões e otimizações

8.1 Gossip para todos os pares

Para acelerar o processo de sincronização, o nó pode enviar mensagens para todos os pares conhecidos. Esta solução faz sentido quando:

\

1. Não há tantos nós no sistema (como 5-9)

   \

2. A latência é previsível

8.2 Reduzindo o índice de Timestamp

Caso a solução use primitivas de sincronização e haja garantia de que não haverá dois ou mais registros com o mesmo timestamp, então o timestampIndex pode ser reduzido.

8.3 Mapa de bitmap para chaves públicas

Para reduzir a quantidade de tráfego durante a replicação, o algoritmo usa bitmap como substituto para chaves públicas. Como todos os nós devem estar cientes de todas as chaves públicas na rede, é justo dizer que todos os nós têm o mesmo conjunto de chaves públicas. O algoritmo de bitmap (para a chave pública de um determinado registro):

\

1. Todas as chaves públicas são ordenadas em ordem ASC

   \

2. Em seguida, o algoritmo itera sobre as chaves públicas ordenadas: caso a chave pública esteja presente no registro, o algoritmo retorna 1, caso contrário 0. Exemplo: existem chaves públicas na rede [A, B, C, D], o registro inclui assinaturas e chaves públicas para [B, C], então o bitmap será: 0110 em forma binária, ou 6 em forma decimal

   \

3. Este número em decimal é então usado em vez de chaves públicas durante o processo de replicação

   \

4. A decodificação acontece de maneira oposta

\

Referências

1. Repositório GitHub ABGP: https://github.com/ega-forever/abgp-js

   \

2. Cynthia Dwork, Nancy Lynch e Larry Stockmeyer: Consenso na Presença de Sincronização Parcial - https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf

   \

3. Denis Rystsov. CASPaxos: Máquinas de Estado Replicadas sem logs - https://arxiv.org/pdf/1802.07000.pdf

   \

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

   \

5. Robbert van Renesse, Dan Dumitriu, Valient Gough, Chris Thomas. Reconciliação Eficiente e Controle de Fluxo para Protocolos Anti-Entropia - 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. Timestamps em Sistemas de Passagem de Mensagens que Preservam a Ordenação Parcial - http://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algos-papers/4.pdf

   \

8. A. Shamir. Como compartilhar um segredo", Communications of the ACM 22 (11): 612613, 1979.

   \

9. Sistemas distribuídos por diversão e lucro - http://book.mixu.net/distsys/single-page.html

   \

10. Tolerância a Falhas Bizantinas Prática e Recuperação Proativa - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf

    \

:::info Autor:

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

:::

:::info Este artigo está disponível no arxiv sob licença CC0 1.0 UNIVERSAL.

:::

\