Milan Vojnovic ( Microsoft Research Cambridge )
The problem of ranking of a set of alternatives based on preferences held by nodes connected by a network is considered under limited memory per node and limited information communicated between nodes. In particular, for the case of binary alternatives, each node in the network is assumed to prefer one of the two alternatives, and the goal for each node is to correctly identify the alternative that is preferred by majority of nodes. This type of a distributed computation problem has been studied under various names such as consensus, k-selection, majority, median and quantile computation. The model is an abstraction that is of interest in various systems such as distributed peer-to-peer systems, databases, dynamics of opinion formation in social networks, and biological computations.