Events — Colloquia & Seminars
Effective Collaboration Without Trust in Peer-to-Peer Systems
Speaker: Boaz Patt-Shamir, HP Laboratories &, Department of Electrical Engineering, Tel Aviv University
Date: Tuesday, January 13, 2004
Talk: 12:00 PM, 149 Cullinane
Abstract
We formalize and analyze a simple model for reputation systems, which are expected to be a central part of the infrastructure of peer-to-peer systems. In our 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 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 her cost by taking advantage of the reports posted by honest peers, and the fear of being exploited by adopting reports posted by malicious players. As we show, if an alpha fraction of players are honest, then no algorithm can guarantee expected running time smaller than Omega(1/alpha); our main result is a randomized algorithm that guarantees, for each player, expected running time of O(log n/(alpha log log n)) even when there is just one good object and O(n) bad objects. The result holds for any alpha > O, with improved bounds for Omega close to 1. We also present a few simple generalizations of our algorithm: First, to the model where each object has a different cost, and the goal is to minimize the cost per player; and second, to the model where each object has a real numeric value, and the goal is to find the object of maximal value, where that maximum is unknown in advance. Finally, we study a repeated game variant of our model. Using a different algorithm, we prove that the expected gain for a dishonest player is at most O(log n), which allows the system to cheaply discourage dishonesty.
Joint work with B. Awerbuch, D. Peleg and M. Tuttle.
Brief Biography
none provided