Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 27, 2003, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Csaba Dávid Tóth (University of California, Santa Barbara)
Peer to peer networks are distributed data-sharing systems without a centralized infrastructure. The absence of a central coordinator raises many problems in distributed systems. We consider one such fundamental problem: how much system performance is sacrificed by the uncoordinated assignment of client peers to server peers? We study this problem as a non-cooperative game among the data requesting peers: the players are selfish clients who (independently) choose servers to optimize their individual payoffs (e.g. download latency) rather than aim for a system-wide social optimum.
In our model, each client peer wishing to download a (huge) file is assigned to one of those peers who store that file (server peer). The latency suffered by the client peer depends on the load on the server peer. We show that an assignment with minimum total latency is also a Nash equilibrium assignment (but not vice versa), and that an optimum assignment can be computed in polynomial time by a distributed algorithm. Our main result is the analysis of a simple and selfish assignment scheme, which we prove is within a constant factor of the optimum.
(Joint work with Anshul Kothari and Subhash Suri at UCSB.)
Automatic MiSe System Software Version 1.4803M | admin login