Comparing multilateral and bilateral exchanges for content distribution

Seminar
Friday, December 04, 2009
11:00am
ENS 637

Abstract:

Users of the BitTorrent file sharing protocol and its variants are incentivized tocontribute their upload capacity in a bilateral manner: downloading is possible inreturn for uploading to the same user. An alternative is to use multilateral exchangeto match user demand for content to available supply at other users in the system. Weprovide a formal comparison of peer-to-peer system designs based on bilateral exchangewith those that enable multilateral exchange via a price-based market mechanism to matchsupply and demand.First, we compare the two types of exchange in terms of the equilibria that arise. Amultilateral equilibrium allocation is Pareto efficient, while we demonstrate thatbilateral equilibrium allocations are not Pareto efficient in general. We show thatPareto efficiency represents the ``gap'' between bilateral and multilateral equilibria:a bilateral equilibrium allocation corresponds to a multilateral equilibrium allocationif and only if it is Pareto efficient.Second, we compare the two types of exchange through the expected percentage of usersthat can trade in a large system, assuming a fixed file popularity distribution. Ourtheoretical results as well as analysis of a BitTorrent dataset provide quantitativeinsight. In particular, we illustrate regimes where bilateral exchange may performquite well even though it does not always give rise to Pareto efficient equilibriumallocations.

Biography:

Ramesh Johari is an Assistant Professor at Stanford University, with a full-timeappointment in the Department of Management Science and Engineering (MS&E), and courtesyappointments in the Departments of Computer Science (CS) and Electrical Engineering(EE). He is a member of the Operations Research group in MS&E, and the InformationSystems Laboratory in EE. He received an A.B. in Mathematics from Harvard (1998), aCertificate of Advanced Study in Mathematics from Cambridge (1999), and a Ph.D. inElectrical Engineering and Computer Science from MIT (2004).He is the recipient of a British Marshall Scholarship (1998), First Place in the INFORMSGeorge E. Nicholson Student Paper Competition (2003), the George M. Sprowls Award forthe best doctoral thesis in computer science at MIT (2004), Honorable Mention for theACM Doctoral Dissertation Award (2004), the Okawa Foundation Research Grant (2005), theMS&E Graduate Teaching Award (2005), the INFORMS Telecommunications Section DoctoralDissertation Award (2006), and the NSF CAREER Award (2007). He has served on the programcommittees of ACM Electronic Commerce (2007, 2009, 2010), ACM SIGCOMM (2006), IEEEInfocom (2007, 2008, 2009, 2010), and ACM SIGMETRICS (2008, 2009).

Speaker

Assistant Professor
Stanford University

Biography:

Ramesh Johari is an Assistant Professor at Stanford University, with a full-timeappointment in the Department of Management Science and Engineering (MS&E), and courtesyappointments in the Departments of Computer Science (CS) and Electrical Engineering(EE). He is a member of the Operations Research group in MS&E, and the InformationSystems Laboratory in EE. He received an A.B. in Mathematics from Harvard (1998), aCertificate of Advanced Study in Mathematics from Cambridge (1999), and a Ph.D. inElectrical Engineering and Computer Science from MIT (2004).He is the recipient of a British Marshall Scholarship (1998), First Place in the INFORMSGeorge E. Nicholson Student Paper Competition (2003), the George M. Sprowls Award forthe best doctoral thesis in computer science at MIT (2004), Honorable Mention for theACM Doctoral Dissertation Award (2004), the Okawa Foundation Research Grant (2005), theMS&E Graduate Teaching Award (2005), the INFORMS Telecommunications Section DoctoralDissertation Award (2006), and the NSF CAREER Award (2007). He has served on the programcommittees of ACM Electronic Commerce (2007, 2009, 2010), ACM SIGCOMM (2006), IEEEInfocom (2007, 2008, 2009, 2010), and ACM SIGMETRICS (2008, 2009).