[Colloq] Talk, Tuesday, January 13, 12noon

[Rachel Bates]

College of Computer and Information Science Colloquium
presents
Boaz Patt-Shamir

who will speak on:
Effective Collaboration Without Trust in Peer-to-Peer Systems


Tuesday, January 13, 2004
12:00pm
149 Cullinane Hall
Northeastern University


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.

Host:  Karl Lieberherr