[Fwd: [Brown CS Talks] Brown CS Theory Colloquium: Boaz Patt Shamir in Lubrano on 3/3/04 at 4 pm]

-------- Original Message --------
Subject: [Brown CS Talks] Brown CS Theory Colloquium:  Boaz Patt Shamir in 
Lubrano on 3/3/04  at 4 pm
Date: Thu, 19 Feb 2004 11:16:10 -0500
From: [email protected]
Reply-To: [email protected]
To: <[email protected]>

Please note: The date for this talk is changed to March 3rd, 2004, instead
February 25th.



			     BROWN UNIVERSITY

			    THEORY COLLOQUIUM


			    Boaz Patt Shamir
	

	   Tel Aviv University (currently visiting HP Labs)


		 Wednesday, March 3, 2004 at 4 pm

	       Lubrano Conference Room (CIT 4th floor)

		Refreshments will be served at 3:45 pm


     Effective Collaboration Without Trust in Peer-to-Peer Systems

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>0, with improved
bounds for alpha 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: Professor Anna Lysyanskaya


_______________________________________________
The Computer Science Department is located at 115 Waterman St., Providence, 
RI.  Our Calendar of Events at http://www.cs.brown.edu/events lists all of our 
talks.

If you would like to be removed from (or added to) our seminar mailing list, 
or if you would prefer to receive only announcements pertaining to IPP talks, 
please send email containing your request to mailto:[email protected]

We'd very much appreciate your forwarding these announcements to colleagues 
who may also have an interest.  Thanks for your cooperation.