Чому пліткування з усіма учасниками може бути найрозумнішим кроком для малих мереж

Таблиця посилань

Анотація та 1. Вступ

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

2. Початковий стан вузла

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

   4.1 Локальне додавання

   4.2 Додавання з іншого вузла

   4.3 Перевірка запису

   4.4 Узгодженість стану

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

5. Доказ коректності

6. M-з-N з'єднань

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

Посилання

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

8.1 Розсилка всім вузлам

Для прискорення процесу синхронізації вузол може надсилати повідомлення всім відомим вузлам. Це рішення має сенс, коли:

\

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 and 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 Автор:

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

:::

:::info Ця стаття доступна на arxiv за ліцензією CC0 1.0 UNIVERSAL.

:::

\