A distributed algorithm with consistency for PageRank-like linear algebraic systems

We present a novel solution algorithm for a specific set of linear equations arising in large scale sparse interconnections, such as the PageRank problem. The algorithm is distributed, exploiting the underlying graph structure, and completely asynchronous. The main feature of the proposed algorithm is that it ensures that the consistency constraint (the sum of the solution components summing to one) is satisfied at every step, and not only when convergence is reached, as in the case of the different algorithms available in the literature. This represents an important feature, since in practice this kind of algorithms are stopped after a fixed number of steps. The algorithm is based on two projection steps, and represents a variation of the classical Kaczmarz method. In this paper, we present a completely deterministic version, and prove its convergence under mild assumptions on the node selection rule. Numerical examples testify for the goodness of the proposed methodology.