Adaptive Collaboration in Peer-to-Peer Systems

We consider a simple model for reputation systems such as the one used by eBay. In the model there are n players, some of which may exhibit arbitrarily malicious (Byzantine) behavior, and there are m objects, some of which are bad. The goal of the honest players is to find a good object. To facilitate collaboration, the system maintains a shared billboard. A basic step of a player consists of consulting the billboard, probing an object to learn its true value, and posting the result on the billboard for the benefit of others. Probing an object incurs a unit cost to the player, and consulting the billboard is free. The dilemma of an honest player is how to balance between the desire to reduce its cost by taking advantage of the reports posted by honest peers, and the fear of being exploited by adopting reports posted by malicious players. In prior work, the authors presented an algorithm solving this problem in an asynchronous model, and the total cost of the probes made by honest players during the algorithm was analyzed. In this paper, the focus is on the individual cost, and a synchronous model in which each player takes a step in each round was considered. The prior algorithm has individual cost O(1/alphalog n) in this model, assuming that an alpha fraction of players are honest. In this paper, it is proven that no algorithm could guarantee individual cost of less than Omega(1/alpha), which is essentially constant if there are enough honest players. The main result is a new algorithm that achieves O(1) individual cost when there are many honest players, and achieves individual cost O((1/alpha)(log n/ log log n)) even when there are not. It is also shown that this algorithm generalizes to other interesting scenarios