examples of the most interesting techniques rather than try to be exhaustive or precise about a particular system or protocol.

Degree of centralization. We can broadly categorize the architecture of P2P systems according to the presence or absence of centralized components in the system design.

Partly centralized P2P systems have
a dedicated controller node that main-
tains the set of participating nodes and
controls the system. For instance, Nap-
ster had a Web site that maintained the
membership and a content index; early
versions of Bit Torrent have a “tracker,”
which is a node that keeps track of the
set of nodes uploading and download-
ing the same content, and periodically
provides nodes with a set of peers they
can connect to; 10 the BOINC platform
for volunteer computing has a site that
maintains the membership and as-
signs compute tasks; 3 and Skype has
a central site that provides log-in, ac-
count management, and payment.

figure 1. an example KBR implementation.

O | 2160 – 1

node 65a1fc invokes
Kbr with the key
d46a1c, producing
a route to the
responsible node
d462ba via a sequence
of nodes whose ids
share increasingly
longer prefixes with
the key.

d462ba

d4213f

d13da3

65a1fc

figure 2. Locating objects in unstructured overlays.

r
S
?

dedicated nodes that are critical for the operation of the system. Decentralized P2P systems have no inherent bottlenecks and can potentially scale very well. Moreover, the lack of dedicated nodes makes them potentially resilient to failure, attack, and legal challenge.

In some decentralized P2P systems, nodes with plenty of resources, high availability and a publicly routable IP address act as supernodes. These supernodes have additional responsibilities, such as acting as a rendez-vous point for nodes behind firewalls, storing state or keeping an index of available content. Supernodes can increase the efficiency of a P2P system, but may also increase its vulnerability to node failure.

Overlay maintenance. P2P systems maintain an overlay network, which can be thought of as a directed graph G = (N,E), where N is the set of participating computers and E is a set of overlay links. A pair of nodes connected by a link in E is aware of each other’s IP address and communicates directly via the Internet. Here, we discuss how different types of P2P systems maintain their overlay.

In partly centralized P2P systems, new nodes join the overlay by connecting to the controller located at a well-known domain name or IP address (which can be, for instance, hardcoded in the application). Thus, the overlay initially has a star-shaped topology with the controller at the center. Additional overlay links may be formed dynamically among participants that have been introduced by the controller.

In decentralized overlays, newly joining nodes are expected to obtain, through an outside channel, the network address (for example, IP address and port number) of some node that already participates in the system. The address of such a bootstrap node can be obtained, for instance, from a Web site. To join, the new node contacts the bootstrap node.

We distinguish between systems that maintain an unstructured or a structured overlay network.

Unstructured overlays. In an unstructured P2P system, there are no constraints on the links between different nodes, and therefore the overlay graph does not have any particular structure. In a typical unstructured P2P system,