Kyomin Jung, Bo Young Kim, and Milan Vojnovic
We study a basic information ranking problem in networks where each node holds an individual preference over a set of items and the goal for each node is to identify a sorted list of items with largest aggregate preference. We would like to achieve this with a fully decentralized algorithm that uses a limited per-node memory and limited pair-wise communications. We show how this problem can be reduced to a plurality selection problem where the goal for each node is to identify an item with largest aggregate ranking score, and show that solving the reduced plurality selection problem solves the original ranking problem with high probability.We introduce a simple and natural plurality selection algorithm for the selection over m > 1 items that uses only log2(m) + 1 bits of per-node memory and per pair-wise communication. We prove correctness of the algorithm with high probability as the number of nodes grows large for the case when each node communicates with any other node, and establish tight convergence time bounds.
The information ranking problem studied in this paper is a basic ranking problem that arises in various applications such as sorting of elements in distributed computing systems, parallel databases, and may as well serve as a model of decentralized inference and opinion formation in distributed environments.
In ISIT 2012 - IEEE International Symposium on Information Theory