Почему сплетничать со всеми пирами может быть самым умным ходом для малых сетей

Таблица ссылок

Резюме и 1. Введение

1. Модель системы

2. Начальное состояние узла

3. Процесс добавления

   4.1 Локальное добавление

   4.2 Добавление с другого узла

   4.3 Валидация записи

   4.4 Согласованность состояния

4. Процесс репликации

5. Доказательство корректности

6. M-из-N соединений

7. Расширения и оптимизации

Ссылки

8. Расширения и оптимизации

8.1 Gossip для всех пиров

Для ускорения процесса синхронизации узел может отправлять сообщения всем известным пирам. Это решение имеет смысл, когда:

\

1. В системе не так много узлов (например, 5-9)

   \

2. Задержка предсказуема

8.2 Уменьшение индекса временных меток

В случае, если решение использует примитивы синхронизации и есть гарантия, что не будет двух или более записей с одинаковой временной меткой, то индекс временных меток может быть уменьшен.

8.3 Битовая карта для публичных ключей

Для уменьшения объема трафика во время репликации алгоритм использует битовую карту в качестве замены публичных ключей. Поскольку все узлы должны знать все публичные ключи в сети, справедливо сказать, что все узлы имеют одинаковый набор публичных ключей. Алгоритм битовой карты (для определенного публичного ключа записи):

\

1. Все публичные ключи отсортированы в порядке возрастания

   \

2. Затем алгоритм перебирает отсортированные публичные ключи: если публичный ключ присутствует в записи, то алгоритм возвращает 1, иначе 0. Пример: в сети есть публичные ключи [A, B, C, D], запись включает подписи и публичные ключи для [B, C], тогда битовая карта будет выглядеть: 0110 в двоичной форме или 6 в десятичной форме

   \

3. Это число в десятичной форме затем используется вместо публичных ключей во время процесса репликации

   \

4. Декодирование происходит в обратном порядке

\

Ссылки

1. Репозиторий ABGP на GitHub: https://github.com/ega-forever/abgp-js

   \

2. Cynthia Dwork, Nancy Lynch и Larry Stockmeyer: Консенсус в условиях частичной синхронизации - https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf

   \

3. Denis Rystsov. CASPaxos: Реплицированные машины состояний без логов - https://arxiv.org/pdf/1802.07000.pdf

   \

4. Paul Miller: Изучение быстрой криптографии на эллиптических кривых - https://paulmillr.com/posts/noblesecp256k1-fast-ecc/

   \

5. Robbert van Renesse, Dan Dumitriu, Valient Gough, Chris Thomas. Эффективное согласование и контроль потока для протоколов анти-энтропии - http://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf

   \

6. Márk Jelasity: Протоколы Gossip - http://www.inf.u-szeged.hu/\~jelasity/ddm/gossip.pdf

   \

7. Colin J. Fidge. Временные метки в системах передачи сообщений, сохраняющих частичный порядокhttp://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algos-papers/4.pdf

   \

8. A. Shamir. Как поделиться секретом", Communications of the ACM 22 (11): 612613, 1979.

   \

9. Распределенные системы для удовольствия и пользы - http://book.mixu.net/distsys/single-page.html

   \

10. Практическая византийская отказоустойчивость и проактивное восстановление - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf

    \

:::info Автор:

(1) Егор Зуев (zyev.egor@gmail.com)

:::

:::info Эта статья доступна на arxiv под лицензией CC0 1.0 UNIVERSAL.

:::

\