We consider a problem that is motivated by the problem of efficiently determining the opinions of a large number of people, where some fraction of the population may be untrustworthy. We propose a class of distributed algorithms called iterative majority voting (IMV), which appears to solve the problem efficiently as long as a positive fraction of the population is trustworthy. IMV consists of two phases: sampling and networking. In the sampling phase each person samples some random set of people for their opinions. In the networking phase each person communicates to random people about their estimates on the group opinion, and the approach benefits from “the power of networking.” We show that IMV is a fair, efficient and robust distributed algorithm by theoretical calculations and simulations. Possible applications include distributed ranking systems, survey and polling systems, social contexts in systems with or without an infrastructure (wireless ad-hoc networks or sensor networks).
展开▼
