Distributed Ranking in Networks with Limited Memory and Communication

We consider the problem of information ranking in a network where each node has an individual preference over a set of candidates and the goal for each node is to correctly identify a list of top ranked candidates with respect to aggregate ranking scores. This is to be achieved by a distributed algorithm that uses limited memory per node and limited communication between each pair of nodes.

We show that this problem reduces to a plurality selection problem where the goal for each node is to identify one candidate with the largest aggregate ranking score and we provide an efficient randomized algorithm for this reduction.

We further study a plurality selection algorithm for the general case of m > 1 candidates that is lightweight in using only log₂(m)+1 bits of memory per node and the same amount of bits per node pair-wise communication. We establish correctness of the algorithm for the case of complete graphs with high probability as the number of nodes grows large, and establish tight convergence time bounds.