Моделирование и оптимизация алгоритма распространения сообщений в одноранговой блокчейн-сети NEO
В данной работе изложена классификация эпидемических алгоритмов и рассмотрены основные способы их оптимизации. Изучен и приведен анализ протокола общения, использующегося в блокчейн-сети Neo, благодаря чему выделены ключевые особенности, характерные для gossip-based алгоритмов в недоверенной среде. Исследована возможность применения модифицированных эпидемических алгоритмов в недоверенной среде, в результате чего на основании наиболее удачных решений предложены способы оптимизации сетевого протокола Neo. Проведены серия экспериментов по оценке эффективности предложенных способов оптимизации и сравнительная характеристика наиболее перспективных из них. Протокол, реализованный с применением наиболее эффективного способа оптимизации, позволяет достичь 88% и 27% уменьшения нагрузки на сетевой трафик для консенсусных и регулярных узлов сети соответственно; уменьшения вероятности нераспространения порции информации за 10 итераций алгоритма распространения сообщений на 3.7%; уменьшения максимальной задержки при передаче сообщений на уровне узлов и блоков на 54%. Исследована возможность применения предложенных способов оптимизации к другим gossip-based протоколам в недоверенной среде.
Введение…………………………………………………………………………………………… 4
Постановка задачи ……………………………………………………………………………. 8
Обзор литературы …………………………………………………………………………… 10
Глава 1 Выбор инструментов для реализации задачи ……………………….. 15
1.1 Выбор языка программирования ……………………………………………….. 15
1.2 Выбор аппаратного обеспечения……………………………………………….. 16
1.3 Выбор окружения для моделирования ………………………………………. 16
Глава 2 Исследование gossip-протоколов в недоверенной среде ………. 18
2.1 Проблема византийских генералов ……………………………………………. 18
2.2 Делегированный алгоритм консенсуса византийской
отказоустойчивости …………………………………………………………………………………….. 20
2.3 Анализ алгоритма распространения сообщений в Neo ………………. 24
2.4 Характерные особенности gossip-протокола в недоверенной
среде 27
2.5 Выводы …………………………………………………………………………………….. 29
Глава 3 Разработка методов оптимизации алгоритма распространения
сообщений в Neo ……………………………………………………………………………………… 30
3.1 Целевые метрики………………………………………………………………………. 30
3.2 Формализация условий задачи ………………………………………………….. 34
3.3 Оптимизация протокола ……………………………………………………………. 34
3.4 Выбор параметров…………………………………………………………………….. 38
3.5 Выводы …………………………………………………………………………………….. 39
Глава 4 Моделирование и оценка эффективности оптимизированного
алгоритма ………………………………………………………………………………………………… 40
4.1 Описание экспериментального окружения ………………………………… 40
4.2 Описание структуры экспериментов …………………………………………. 42
4.3 Эксперименты ………………………………………………………………………….. 44
4.4 Оценка эффективности оптимизированного алгоритма ……………… 55
4.5 Выводы …………………………………………………………………………………….. 57
Заключение …………………………………………………………………………………….. 59
Результаты выполненной работы ………………………………………………………… 59
Способы применения результатов работы …………………………………………… 60
Направления дальнейших исследований……………………………………………… 60
Список используемых сокращений ………………………………………………….. 62
Список литературы …………………………………………………………………………. 63
С возрастанием потребности в отказоустойчивости, масштабируемости и конфиденциальности компьютерных сетей высокую востребованность приобрела одноранговая (пиринговая, Peer-to-Peer) архитектура [1]. Одноранговые сети представляют собой альтернативу стандартной клиент- серверной архитектуре построения компьютерных сетей, а их основной идеей является объединение ресурсов множества равноправных компьютеров для формирования глобальной системы распределения контента.
На заре развития одноранговых сетей существовало несколько основных подходов к организации взаимодействия между участниками сети. Первый из них – многоадресная рассылка на сетевом уровне, также известная как IP мультикаст [1]. Данный подход позволяет осуществлять бессерверные коммуникации между участниками, однако его применение оказывается непрактичным в глобальном пространстве интернета [29]. Аналогичным подходом к конструированию одноранговых сетей стало создание полносвязной оверлейной сети на прикладном уровне [4], подразумевающее, что каждый участник сети имеет связь с любым другим. Подобные алгоритмы общения требуют высокой пропускной способности информационных каналов от каждого пира, возрастающей с увеличением общего количества участников сети, а также плохо масштабируются [1].
С развитием вычислительных мощностей, графических ускорителей и технологий параллельных вычислений масштаб и сложность структуры одноранговых сетей начали возрастать, что привело к необходимости оптимизации процесса сообщения между компонентами сети. С данной задачей успешно справились занимающие в настоящий момент лидирующие позиции структурно-ориентированные [2, 34] и эпидемические [12, 32] поколения алгоритмов, а также их гибриды. Структурно-ориентированные протоколы применяются в сетях, имеющих заранее определенную
практически постоянную топологию (например, дерево), а их 4
преимуществом является эффективное использование сетевых ресурсов из-за отсутствия репликации сообщений. В противовес, с развитием сетей с динамической структурой и количеством участников широкое развитие получили эпидемические алгоритмы.
В протоколах многоадресной коммуникации, основанных на эпидемической модели распространения информации, итерация алгоритма обмена сообщениями состоит из нескольких фаз, в каждой из которых участники сети случайно и независимо друг от друга выбирают одного или нескольких соседей-партнеров для передачи порции информации – так называемого секрета [39]. При таком способе передачи информация распространяется по сети подобно сплетням или вирусу, из-за чего данное семейство алгоритмов получило название gossip. Gossip-алгоритмы принадлежат к вероятностному семейству алгоритмов и являются наиболее удачным решением для организации многоадресной коммуникации в динамических одноранговых сетях благодаря их стойкости к сбоям узлов и изменению структуры сети, высокой степени масштабируемости, наличию внутреннего уровня избыточности протокола, вероятностной устойчивости и надежным математическим оценкам эффективности [23]. Помимо широковещательной коммуникации данное семейство протоколов широко применяется при решении задач управления согласованностью в реплицированных базах данных [16], обнаружения сбоев и системного мониторинга [3, 5], организации распределенных брокеров, основанных на механизме подписок [28] и др.
Однако, данному классу алгоритмов свойственны недостатки, главным из которых является проблема “наводнения” сети [23], когда для достижения высокой степени надежности участники рассылают большое количество сообщений, превышая при этом пропускную способность каналов обмена информацией. Не менее важной задачей при проектировании gossip- протоколов является сокращение задержек при передаче сообщений [22].
5
За последнее десятилетие эпидемические алгоритмы нашли широкое применение в одноранговых сетях, основанных на технологии распределенных реестров, в том числе – технологии блокчейн [47]. Примером таких сетей служат наиболее известные блокчейн-системы Bitcoin [51], Hyperledger Fabric [27] и Neo [53]. В данном случае среда, в которой участники осуществляют обмен информацией, предполагается недоверенной – это означает, что сообщения, передаваемые участниками сети, могут содержать неточную или намеренно искаженную информацию. Таким образом, при организации общения в недоверенной среде возникают дополнительные затраты сетевых ресурсов при отправке, пересылке и принятии сообщений, связанные в первую очередь с их верификацией [47]. Учитывая данный факт, проблемы, общие для алгоритмов эпидемического семейства, становятся более актуальными в контексте блокчейн-сетей.
Несмотря на активные исследования и наличие большого количества зарекомендовавших себя подходов к оптимизации gossip-based протоколов, большинство из предлагаемых улучшений оказываются неприменимы в случае недоверенной среды (например, в случае блокчейн-систем), поскольку опираются на локальную информацию о сети, полученную участником от своих соседей [39]. Высокие требования к скорости распространения информации и утилизации сетевого трафика с одной стороны, и обеспечение надежности сообщения – с другой, поддерживают актуальной задачу разработки бережливого протокола общения в недоверенной среде, а дефицит научных трудов в данной области в совокупности с активным развитием блокчейн-технологий говорит о востребованности темы исследования.
В данной работе изложена классификация эпидемических алгоритмов и рассмотрены основные способы их оптимизации; изучен и приведен анализ протокола общения, использующегося в блокчейн-сети Neo, благодаря чему выделены ключевые особенности, характерные для gossip-based алгоритмов в недоверенной среде; исследована возможность применения
6
модифицированных эпидемических алгоритмов в недоверенной среде, в результате чего на основании наиболее удачных решений предложены способы оптимизации протокола общения Neo; проведены серия экспериментов по оценке эффективности предложенных способов оптимизации и сравнительная характеристика наиболее перспективных из них; исследована возможность применения предложенных способов оптимизации к другим gossip-based протоколам в недоверенной среде.
Результаты выполненной работы
6. Изучены важнейшие исследования и публикации в области применения
эпидемических протоколов общения в одноранговых сетях, и, в
частности, применение gossip-протоколов в блокчейн-сетях.
7. Исследована проблема доверия в распределенных блокчейн-системах и ее
влияние на используемые протоколы общения. Рассмотрен и
классифицирован сетевой протокол, применяемый в блокчейн-сети Neo,
на основе чего выявлены ключевые особенности gossip-протоколов в
недоверенной среде, влияющие на эффективность распространения
информации в блокчейн-сетях.
8. Выявлена группа целевых метрик, определяющих эффективность работы
сетевого протокола в сети блокчейн. Сформулирована задача
оптимизации gossip-протокола блокчейна Neo.
9. На основе сравнительного анализа изученной литературы и выявленных
особенностей gossip-протоколов в недоверенной среде сформулированы
гипотезы о способах оптимизации сетевого протокола блокчейна Neo.
Изложено математическое обоснование выбора параметров
предложенных моделей.
10. Для каждого из выдвинутых способов реализован модифицированный
сетевой протокол. Проведены эксперименты по оценке эффективности
оригинального и модифицированного протоколов.
11. Достигнуты 88% и 27% уменьшение нагрузки на сетевой трафик для
консенсусных и регулярных узлов сети соответственно; уменьшение
вероятности нераспространения порции информации за 10 итераций
алгоритма распространения сообщений на 3.7%; уменьшение задержки
при передаче сообщений на уровне узлов и блоков на 54%.
12. Проведена сравнительная характеристика результатов экспериментов и
выделение наиболее эффективных предложений по улучшению.
Реализован оптимизированный gossip-протокол блокчейн-сети Neo.
Способы применения результатов работы
Настоящая работа является вкладом в мало изученную область
исследования применимости оптимизаций gossip-алгоритмов в доверенной
среде к организации сетевого общения в одноранговых блокчейн-системах.
Согласно заключениям, изложенным в части 2.4, выделенные
характерные особенности применения gossip-протокола в блокчейн-сети Neo
являются общими для группы блокчейн-сетей, использующих в качестве
консенсусного алгоритма варианты «proof-of-stake», следовательно, могут
быть применены в исследованиях эффективности протоколов указанных
блокчейн-сетей.
Способы оптимизации gossip-протокола блокчейн-сети Neo,
предложенные в части 3.3 также могут быть перенесены на более широкий
круг блокчейн-систем, использующих консенсусные алгоритмы семейства
«proof-of-stake».
Направления дальнейших исследований
1. Более детальное исследование комбинации техники «infect-upon-
contagion» для push-фазы и возможности конфигурации параметра .
2. Исследование возможности применения других способов оптимизации
gossip-алгоритмов в доверенной среде к организации сетевого общения в
одноранговых блокчейн-системах.
3. Изучение проблемы агрегации информации о сети в недоверенной среде
и разработка надежных и эффективных методов агрегации сетевой
информации в блокчейн-системах.
4. Исследование ключевых особенностей применения gossip-протоколов в
блокчейн-системах, использующих консенсусные алгоритмы семейства
«proof-of-work».
Список используемых сокращений
dBFT – Delegated Byzantine fault tolerance
LBL – Latency at the block level
LPL – Latency at the peer level
NU – Network utilization
P2P – Peer-to-peer
PoS – Proof of stake
PoW – Proof of work
RPC – Remote procedure call
TTL – Time-to-life
ЦПУ – Центральное процессорное устройство
ОЗУ – Оперативное запоминающее устройство
ЭВМ – Электронно-вычислительная машина
1. Распределенные системы. Принципы и парадигмы / Таненбаум Э, ван
Стеен М // СПб.: Питер – 2003.
2. A case for end system multicast, Selected Areas in Communications. / Yang-
hua C, Rao S // IEEE Journal – 2002, 1456–1471.
3. A gossip-style failure detection service. / van Renesse R, Minsky Y, Hayden M
// Technical Report TR98-1687, Dept. of Computer Science, Cornell
University – 1998.
4. A protocol for reliable decentralized conferencing. / Lennox J, Schulzrinne H //
In NOSSDAV ’03: Proceedings of the 13th International Workshop on
Network and Operating Systems Support for Digital Audio and Video.
Monterey, CA, USA – 2003.
5. A robust and scalable technology for distributed system monitoring,
management, and data mining. / van Renesse R, Birman K, Vogels W //
Astrolabe: ACM Transactions on Computer Systems 21(2) – 2003, 164–206.
6. A scalable real-time peer-to-peer system with probabilistic timing assurances. /
Fei H, Ravindran B, Jensen ED // RT-P2P: Shanghai, China: Embedded and
Ubiquitous Computing, 2008. EUC ’08. IEEE/IFIP International Conference –
2008, 97–103.
7. A scalable reliable multicast system for dynamic environments. / Melamed R,
Keidar I // Cambridge, MA, USA: Network Computing and Applications,
2004. (NCA 2004). Proceedings. Third IEEE International Symposium – 2004,
5–14.
8. Algebraic gossip: a network coding approach to optimal multiple rumor
mongering, Information Theory. / Deb S, Medard M, Choute C // IEEE
Transactions on 2006 – 2006, 2486–2507.
9. Analysis of the Evolution of Peer-to-Peer Systems. / Liben-nowell D,
Balakrishnan H, Karger D // Proceedings of the Annual ACM Symposium on
Principles of Distributed Computing – 2004.
10. Bimodal multicast. / Birman K, Hayden M, Ozkasap O, Xiao Z, Budiu M, and
Minsky Y // ACM Trans.Comput. Syst.,17(2) – 1999, 41–88.
11. Continuous Gossip-Based Aggregation through Dynamic Information Aging. /
Rapp V, Graffi K // Proceedings – International Conference on Computer
Communications and Networks, ICCCN – 2013.
12. Controlling gossip protocol infection pattern using adaptive fanout. / Verma S,
Wei Tsang O // Distributed Computing Systems, 2005. ICDCS 2005.
Columbus, OH: Proceedings. 25th IEEE International Conference – 2005, 665–
674.
13. Dependably scheduling real-time distributable threads in large-scale, unreliable
networks. / Kai H, Ravindran B, Jensen ED // RTG-L: Melbourne, Qld:
Dependable Computing, 2007. PRDC 2007. 13th Pacific Rim International
Symposium – 2007, 314–321.
14. Efficient and adaptive epidemic-style protocols for reliable and scalable
multicast, Parallel and Distributed Systems. / Gupta I, Kermarrec A, Ganesh A
// IEEE Transactions on 2006 – 2006, 593–605.
15. Efficient reconciliation and flow control for anti-entropy protocols / van
Renesse R, Dumitriu D, Gough V, and Thomas C // Proceedings of the 2nd
Workshop on Large-Scale Distributed Systems and Middleware, ACM,LADIS
– 2008.
16. Epidemic Algorithms for Replicated Database Management / Demers, A et al.
// Proc. of 6th ACM Symposium on Principles of Distributed Computing,
Vancouver, PODC – 1987.
17. Epidemic broadcast trees. / Leitao J, Pereira J, Rodrigues L // Beijing, China:
Reliable Distributed Systems, 2007. SRDS 2007. 26th IEEE International
Symposium – 2007, 301–310.
18. Epidemic information dissemination in distributed systems. / Eugster P,
Guerraoui R, Kermarrec A, and Massoulié L // IEEE Computer 37 (5) – 2004.
19. Epistemic Protocols for Distributed Gossiping. / Apt K, Grossi D, Hoek W //
Electronic Proceedings in Theoretical Computer Science – 2016.
20. Fair and Efficient Gossip in Hyperledger Fabric / Berendea N, Mercier H,
Onica E and Rivière E // Proc. of the IEEE ICDCS – 2020.
21. GoCast: Gossip-enhanced overlay multicast for fast and dependable group
communication. / Chang R, Ward C // In Dependable Systems and Networks,
2005. DSN 2005. Proceedings. International Conference – 2005, 140–149.
22. Gossip and Epidemic Protocols / Montresor A // Lecture Notes in Artificial
Intelligence – 2004, 265–282
23. Gossip-Based Broadcast. / Leitão J, Pereira J, Rodrigues L // Handbook of
Peer-to-Peer Networking – 2010, 831-860.
24. Gossip-based aggregation in large dynamic networks. / Jelasity M, Montresor
A, and Babaoglu O // ACMTrans. Comput. Syst.,23 – 2005.
25. Gossip-based computation of aggregate information. / Kempe D, Dobra A,
Gehrke J // Cambridge, MA, USA: Foundations of Computer Science, 2003.
Proceedings. 44th Annual IEEE Symposium – 2003, 482–491.
26. Gossip-based peer sampling. / Jelasity M, Voulgaris S, Guerraoui R,
Kermarrec A, and van Steen M // ACM Trans. Comput. Syst.,25(3) – 2007.
27. Hyperledger fabric: a distributed operating system for permissioned
blockchains. / Androulaki E at al. // arXiv preprint arXiv:1801.10228v2 – 2018.
28. Lightweight probabilistic broadcast / Eugster P, Guerraoui R, Handurukande S,
Kouznetsov P, and Kermarrec A // ACM Trans. Comput. Syst.,21(4) – 2003,
341–374.
29. Multicast routing in datagram internetworks and extended LANs. / Deering SE,
Cheriton DR // ACM Trans Comput Syst – 1990.
30. NEO Delegated Byzantine Fault Tolerance Consensus Mechanism / Monoppo
M // Medium – 2018.
31. New directions in cryptography. / Deffie W, Hellman M // IEEE Trans. Inf.
Theory IT-22 – Nov. 1976, 644-654.
32. On the complexity of asynchronous gossip. / Georgiou C, Gilbert S, Guerraoui
R, Kowalski D // Canada, Toronto: Proceedings of the Twenty-Seventh ACM
Symposium on Principles of Distributed Computing – 2008, 135–144.
33. Optimization Scheme of Consensus Mechanism Based on Practical Byzantine
Fault Tolerance Algorithm / Zhipeng G, Lulin Y // Researchgate – 2020.
34. Peer-to-peer multipoint video conferencing with layered video. / Akkus I,
Ozkasap O, Civanlar M // J Netw Comput Appl – 2011, 137–150.
35. Practical Byzantine Fault Tolerance / Castro M, Liskov B // Third Symposium
on Operating Systems Design and Implementation – Feb. 1999.
36. Probabilistic reliable dissemination in large-scale systems. / Kermarrec A,
Massouli ́e L, and Ganesh A // IEEE Trans. Parallel Distrib. Syst.,14(3) – 2003,
248–258.
37. Push-gossip protocol efficiency with network topology propagation. / Vanin A,
Bogatyrev V // Proc. of the 10th Majorov International Conference on Software
Engineering and Computer Systems, MICSECS – 2018.
38. Push-pull gossiping for information sharing in peer-to-peer communities. /
Mujtaba M // Proc. International Conference on Parallel and Distributed
Processing Techniques and Applications (PDPTA). Las Vegas – 2003, 1393–
1399.
39. RRG: redundancy reduced gossip protocol for real-time N-to-N dynamic group
communication. / Luk, V.WH., Wong, A.KS., Lea, CT. et al. // J Internet Serv
Appl 4, 14 – 2013.
40. Randomized gossip algorithms, Information Theory. / Boyd S, Ghosh A,
Prabhakar B, Shah D // IEEE Transactions on 2006 – 2006, 2508–2530.
41. Randomized rumor spreading. / Karp R, Schindelhauer C, Shenker S, Vocking
B // Redondo Beach, CA: Foundations of Computer Science, 2000.
Proceedings. 41st Annual Symposium – 2000, 565–574.
42. Reaching agreement in the presence of faults. / Pease M, Shostack R, Lamport
L // ACM 27, 2 – Apr. 1980, 228-234.
43. Simple gossiping with balls and bins. / Koldehofe B // Stud. Inform. Univ. 3
(1) – 2004, 43–60.
44. Spatial gossip and resource location protocols. / Kempe D, Kleinberg J, and
Demers A // J. ACM,51(6) – 2004, 943–967.
45. T-Man: Gossip-based fast overlay topology construction. / Jelasity M,
Montresor A, and Babaoglu O // Computer Networks,53(13) – 2009, 2321 –
2339.
46. The Byzantine Generals Problem / Lamport L, Shostack R, and Pease M // SRI
International – 1981.
47. The Science of the Blockchain / Wattenhofer R // CreateSpace Independent
Publishing; 1st edition – 2016.
48. Towards robust distributed systems. / Brewer E // PODC – 2000.
49. Исходный код проекта NeoBench – Accessed: 2021-04-11. URL:
https://github.com/nspcc-dev/neo-bench
50. ИсходныйкодпроектаNeoGo-Accessed:2021-04-11.URL:
https://github.com/nspcc-dev/neo-go
51. Bitcoin: A Peer-to-Peer Electronic Cash System. / Nakamoto S // Cryptography
Mailing list – 2009. Accessed: 2021-02-04. URL: https://bitcoin.org/bitcoin.pdf
52. Docker – Accessed: 2021-04-23. URL: https://www.docker.com/
53. NEO / Zhang E // Neo whitepaper – 2018. Accessed: 2021-01-26. URL:
https://docs.neo.org/docs/en-us/basic/whitepaper.html
54. Neo 3.0.0-preview4 nodes benchmarking / Neo Saint Petersburg Competence
Center(NeoSPCC)//Medium-Accessed:2021-03-15.URL:
https://neospcc.medium.com/neo-3-0-0-preview4-nodes-benchmarking-
bb4ef291dcca
Последние выполненные заказы
Хочешь уникальную работу?
Больше 3 000 экспертов уже готовы начать работу над твоим проектом!
5 (428 отзывов)
5 (188 отзывов)
4.9 (5 отзывов)
5 (9 отзывов)
4.7 (18 отзывов)
5 (8 отзывов)
4.2 (5 отзывов)
4.8 (17 отзывов)
4.5 (9 отзывов)
