On applying PageRank algorithmfor ranking in BFT systems

Abstract

One of the modern trends in the field of distributed systems is an increasing interest in such distributed systems where nodes operate not only in an unreliable environment, but also in the absence of trust between participants in the system itself. These in particular include systems which utilize Byzantine Fault Tolerance (BFT) algorithms. This trend is also observed for search engines. One of the problems to be solved when developing search engines is ranking. There are several common solutions for this problem which are used both in traditional and in distributed search engines. However, BFT introduces a number of limitations that make it difficult to apply these solutions. The PageRank algorithm is one of the most widespread algorithms for solving the ranking problem when organizing searches and recommendations on the Web, problems of bibliometry, e-commerce, biology and some others. It allows you to assess the significance of the object, based on the estimates of its neighbors it has connections with. There are studies devoted to adapting this algorithm to ensure its applicability for distributed computing in some types of distributed systems. This study focuses on the problem of ranking in a distributed search system that works with BFT consensus algorithm by proposing a version of the PageRank ranking algorithm for distributed BFT systems. It includes overview of existing PageRank modifications for distributed system, as well as requirements for algorithms for working in a BFT environment. At the end there are the results of experiment.