Применение алгоритма PageRank для задачи ранжирования в BFT системах

Аннотация

Одной из тенденций в области распределенных систем является повышение интереса к таким распределенным системам, в которых узлы функционируют не только в ненадежной среде, но и в условиях отсутствия доверия между участниками самой системы. К таким, в частности, относятся системы, работающие на основе алгоритмов Byzantine Fault Tolerance (BFT). Эта тенденция имеет место и для поисковых систем. Стандартной задачей, решаемой поисковыми системами, является задача ранжирования результатов запросов. Для неё существуют несколько распространенных решений, которые применяются как в традиционных, так и в распределенных поисковых системах. Однако ориентация на BFT вводит ряд ограничений, которые затрудняют их применение. Алгоритм PageRank является одним из наиболее широко распространенных алгоритмов решения задачи ранжирования при организации поиска и рекомендаций в Web, задачах библиометрии, электронной коммерции, биологии и других. Он позволяет проводить оценку значимости объекта, основываясь на оценках его соседей, с которыми он имеет связи. Существуют исследования, посвященные адаптации данного алгоритма для некоторых типов распределенных систем. В рамках настоящего исследования решается проблема ранжирования результатов поиска в распределенной поисковой системе, работающей по BFT-алгоритму консенсуса. Предлагается вариант алгоритма ранжирования PageRank для распределенных BFT-систем, рассматриваются существующие модификации PageRank для распределенных систем, обсуждаются требования, предъявляемые к алгоритмам для работы в BFT-среде, исследуются параметры систем. В конце приводятся результаты эксперимента.