BitTorrent is a peer-to-peer protocol used for collaborative downloading. It allows peers to exchange blocks of the file they are downloading with each other, rather then obtaining them from a central server. Despite the decentralized nature of the protocol, BitTorrent has traditionally relied on a centralized tracker, which bootstraps the system by providing new clients with a random set of peers. The tracker has previously been perceived as a critical part of BitTorrent systems, and efforts to make it more fault-tolerant have focused on tracker replication and on tracker implementations using Distributed Hash Tables, which have been entitled "Trackerless BitTorrent." The tracker's sole responsibility, whether implemented in a centralized or distributed manner, is to allow peers to randomly select other peers to connect to, in an effort to construct a robust graph. We propose completely removing the tracker and replacing it with a set of distributed protocols based on random walks, accomplishing the work of the tracker without explicitly tracking every peer in the system. We use expansion as a measure by which to compare the quality of the graphs generated by distributed, trackerless algorithms to the graphs generated by a centralized tracker. We also explore the implications of various design decisions related to the random walks which are the key component of our proposal.

21 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]