BitTorrent Protocol and a Modified Secretary Problem

Abstract

BitTorrent is a popular file sharing protocol in which a user downloads a file from a large collection of seeders, each of which has the file. The user downloads from b of these seeders, but repeatedly drops its worst connection and establishes a new one in search of the best b connections. In this paper we model the BitTorrent protocol using a modified secretary problem, and in doing so find precise stopping times for an arbitrary b. We show that every b gives the same success probability, and that this probability asymptotically approaches 1/e.