Моделирование и оптимизация алгоритма распространения сообщений в одноранговой блокчейн-сети NEO

Введение 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] поколения алгоритмов, а также их гибриды. Структурно-ориентированные протоколы применяются в сетях, имеющих заранее определенную практически постоянную топологию (например, дерево), а их преимуществом является эффективное использование сетевых ресурсов из-за отсутствия репликации сообщений. В противовес, с развитием сетей с динамической структурой и количеством участников широкое развитие получили эпидемические алгоритмы.
В протоколах многоадресной коммуникации, основанных на эпидемической модели распространения информации, итерация алгоритма обмена сообщениями состоит из нескольких фаз, в каждой из которых участники сети случайно и независимо друг от друга выбирают одного или нескольких соседей-партнеров для передачи порции информации - так называемого секрета [39]. При таком способе передачи информация распространяется по сети подобно сплетням или вирусу, из-за чего данное семейство алгоритмов получило название gossip. Gossip-алгоритмы принадлежат к вероятностному семейству алгоритмов и являются наиболее удачным решением для организации многоадресной коммуникации в динамических одноранговых сетях благодаря их стойкости к сбоям узлов и изменению структуры сети, высокой степени масштабируемости, наличию внутреннего уровня избыточности протокола, вероятностной устойчивости и надежным математическим оценкам эффективности [23]. Помимо широковещательной коммуникации данное семейство протоколов широко применяется при решении задач управления согласованностью в реплицированных базах данных [16], обнаружения сбоев и системного мониторинга [3, 5], организации распределенных брокеров, основанных на механизме подписок [28] и др.
Однако, данному классу алгоритмов свойственны недостатки, главным из которых является проблема “наводнения” сети [23], когда для достижения высокой степени надежности участники рассылают большое количество сообщений, превышая при этом пропускную способность каналов обмена информацией. Не менее важной задачей при проектировании gossip- протоколов является сокращение задержек при передаче сообщений [22].
За последнее десятилетие эпидемические алгоритмы нашли широкое
применение в одноранговых сетях, основанных на технологии распределенных реестров, в том числе - технологии блокчейн [47]. Примером таких сетей служат наиболее известные блокчейн-системы Bitcoin [51], Hyperledger Fabric [27] и Neo [53]. В данном случае среда, в которой участники осуществляют обмен информацией, предполагается недоверенной - это означает, что сообщения, передаваемые участниками сети, могут содержать неточную или намеренно искаженную информацию. Таким образом, при организации общения в недоверенной среде возникают дополнительные затраты сетевых ресурсов при отправке, пересылке и принятии сообщений, связанные в первую очередь с их верификацией [47]. Учитывая данный факт, проблемы, общие для алгоритмов эпидемического семейства, становятся более актуальными в контексте блокчейн-сетей.
Несмотря на активные исследования и наличие большого количества зарекомендовавших себя подходов к оптимизации gossip-based протоколов, большинство из предлагаемых улучшений оказываются неприменимы в случае недоверенной среды (например, в случае блокчейн-систем), поскольку опираются на локальную информацию о сети, полученную участником от своих соседей [39]. Высокие требования к скорости распространения информации и утилизации сетевого трафика с одной стороны, и обеспечение надежности сообщения - с другой, поддерживают актуальной задачу разработки бережливого протокола общения в недоверенной среде, а дефицит научных трудов в данной области в совокупности с активным развитием блокчейн-технологий говорит о востребованности темы исследования.
В данной работе изложена классификация эпидемических алгоритмов и рассмотрены основные способы их оптимизации; изучен и приведен анализ протокола общения, использующегося в блокчейн-сети Neo, благодаря чему выделены ключевые особенности, характерные для gossip-based алгоритмов в недоверенной среде; исследована возможность применения 6
модифицированных эпидемических алгоритмов в недоверенной среде, в результате чего на основании наиболее удачных решений предложены способы оптимизации протокола общения Neo; проведены серия экспериментов по оценке эффективности предложенных способов оптимизации и сравнительная характеристика наиболее перспективных из них; исследована возможность применения предложенных способов оптимизации к другим gossip-based протоколам в недоверенной среде.

Купить