The PageRank algorithm, employed at Google assigns a measure of importance to each web page for ranking purposes. Recently, we have proposed a distributed randomized approach for this algorithm, where web pages compute their own PageRank by communicating over selected links. Here, the focus is on the effects of unreliability in communication, where random data losses are modeled as an outcome of Markov chains. We provide a generalization of the distributed scheme along with analysis on its convergence.

Inspec keywords: convergence; distributed algorithms; randomised algorithms

Other keywords: web page; convergence; random data losses; distributed randomized approach; distributed scheme; unreliable channels; Markov chains; pagerank algorithms

Subjects: Parallel programming and algorithm theory