Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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)

Total latency and selfish behavior in P2P data-sharing

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.)

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login