Почему сплетничать со всеми пирами может быть самым умным ходом для малых сетей
Таблица ссылок
Резюме и 1. Введение
-
Модель системы
-
Начальное состояние узла
-
Процесс добавления
4.1 Локальное добавление
4.2 Добавление с другого узла
4.3 Валидация записи
4.4 Согласованность состояния
-
Процесс репликации
-
Доказательство корректности
-
M-из-N соединений
-
Расширения и оптимизации
Ссылки
8. Расширения и оптимизации
8.1 Gossip для всех пиров
Для ускорения процесса синхронизации узел может отправлять сообщения всем известным пирам. Это решение имеет смысл, когда:
\
-
В системе не так много узлов (например, 5-9)
\
-
Задержка предсказуема
8.2 Уменьшение индекса временных меток
В случае, если решение использует примитивы синхронизации и есть гарантия, что не будет двух или более записей с одинаковой временной меткой, то индекс временных меток может быть уменьшен.
8.3 Битовая карта для публичных ключей
Для уменьшения объема трафика во время репликации алгоритм использует битовую карту в качестве замены публичных ключей. Поскольку все узлы должны знать все публичные ключи в сети, справедливо сказать, что все узлы имеют одинаковый набор публичных ключей. Алгоритм битовой карты (для определенного публичного ключа записи):
\
-
Все публичные ключи отсортированы в порядке возрастания
\
-
Затем алгоритм перебирает отсортированные публичные ключи: если публичный ключ присутствует в записи, то алгоритм возвращает 1, иначе 0. Пример: в сети есть публичные ключи [A, B, C, D], запись включает подписи и публичные ключи для [B, C], тогда битовая карта будет выглядеть: 0110 в двоичной форме или 6 в десятичной форме
\
-
Это число в десятичной форме затем используется вместо публичных ключей во время процесса репликации
\
-
Декодирование происходит в обратном порядке
\
Ссылки
-
Репозиторий ABGP на GitHub: https://github.com/ega-forever/abgp-js
\
-
Cynthia Dwork, Nancy Lynch и Larry Stockmeyer: Консенсус в условиях частичной синхронизации - https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf
\
-
Denis Rystsov. CASPaxos: Реплицированные машины состояний без логов - https://arxiv.org/pdf/1802.07000.pdf
\
-
Paul Miller: Изучение быстрой криптографии на эллиптических кривых - https://paulmillr.com/posts/noblesecp256k1-fast-ecc/
\
-
Robbert van Renesse, Dan Dumitriu, Valient Gough, Chris Thomas. Эффективное согласование и контроль потока для протоколов анти-энтропии - http://www.cs.cornell.edu/home/rvr/papers/flowgossip.pdf
\
-
Márk Jelasity: Протоколы Gossip - http://www.inf.u-szeged.hu/\~jelasity/ddm/gossip.pdf
\
-
Colin J. Fidge. Временные метки в системах передачи сообщений, сохраняющих частичный порядокhttp://fileadmin.cs.lth.se/cs/Personal/Amr_Ergawy/dist-algos-papers/4.pdf
\
-
A. Shamir. Как поделиться секретом", Communications of the ACM 22 (11): 612613, 1979.
\
-
Распределенные системы для удовольствия и пользы - http://book.mixu.net/distsys/single-page.html
\
-
Практическая византийская отказоустойчивость и проактивное восстановление - http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf
\
:::info Автор:
(1) Егор Зуев (zyev.egor@gmail.com)
:::
:::info Эта статья доступна на arxiv под лицензией CC0 1.0 UNIVERSAL.
:::
\
Вам также может быть интересно
Криптоновости: 13-летний BTC-кошелёк перемещает $71 млн, пока Pepeto заполняется перед толпой
Акции Booking Holdings (BKNG) упали до нового минимума на фоне роста геополитических рисков
