How can a group of agents achieve a goal despite efforts by some of the agents to prevent this? This important question cuts across many disciplines including political science, economics, mathematics and computer science. In this proposal, we are exploring this question by focusing on the following problem. A set of n agents wants to compute the value of a function, f, of n inputs, where each agent holds a unique input of f. Our goal is to create a distributed algorithm that ensures that each agent learns the output of f. Our algorithm will be attack-resistant in that it works correctly even when up to a constant fraction of the agents are controlled by an omniscient adversary that tries to prevent the function from being computed. Our algorithm will also be scalable in the sense that each node in the network sends and receives a number of messages and bits that is only polylogarithmic in n i.e. O(logc n) where c is a fixed constant. We are making use of several tools to solve this problem including: the use of expander-like graphs to enable robust communication; the use of small randomly chosen committees as single trustworthy functional units; and algorithmic techniques to harden against denial of service attacks. Solving this problem will likely have broader impact in such diverse areas as voting, spam detection, worm and malware detection, distributed file systems, auction and mechanism enforcement, collaborative filtering, and web search.
CAREER: Foundations for Attack-Resistant, Collaborative Peer-to-peer Systems