Overlay networks are application-level networks, or networks of acquaintances, established on top of physical networks, such as the Internet. Nodes in an overlay are connected through ‘virtual links’, each of which corresponds to a path, comprising perhaps of many physical links, in the underlying network.

Peer-to-Peer (P2P) systems are one class of overlay networks, in which all nodes in the system are equivalent and all tasks are carried out without the presence of any central authority. Despite their relatively short history, peer-to-peer overlays are now deployed in a multitude of new and highly popular applications. In addition, with the explosive increase of high bandwidth connections around the world, these networks can only grow larger, more anonymous and more heterogeneous in time.

There has hence been an immense amount of interest in the research community to classify and understand the design choices available for the construction of such networks, keeping in mind the specific problems they face: namely very high dynamism, lack of control, arbitrary geographical location of the constituent peers and differing bandwidth capabilities.

In this colloquium, we describe some of the seminal work that has been done in this area in the field of computer science. We also describe our own physics-based approach to thinking about these issues.