2 The simplified scheme

Each computer that wishes to participate in our backup scheme runs special software. Under the software's direction, these computers link up and form a peer-to-peer system over the Internet or a corporate intranet. The same software, performing the same functions, runs on each computer--except for a single external matching server (see Section 2.1), the system is decentralized and functionally symmetric. Like most peer-to-peer systems, computers are free to join or quit the system at any time.

Each participating computer has some number of backup partners. For example, $\cal A$ might have partners $\cal B$, $\cal C$, and $\cal D$. Partnership is a symmetric relation: $\cal A$ is also a partner of $\cal B$, $\cal C$, and $\cal D$. Partnership is not, however, transitive: $\cal B$ and $\cal C$ need not be partners, and in general $\cal B$ and $\cal C$ may share no partners other than $\cal A$.

How many and which partners a given computer has varies over time. Computers start with zero partners on joining and quickly add enough partners to handle their current backup needs. As their backup needs change, they may want to add or remove partners. Partners may also be changed if an existing partner is found to be wanting (e.g., due to excessive downtime) or a new computer needs partners.

Each pair of partners agrees at partnership-formation time to an amount of storage to be swapped and a level of uptime (time that they are running and connected) that they must maintain. Different pairs may reach different agreements. Suppose $\cal A$ and $\cal B$ agree to swap $s$ blocks. Then each must reserve $s$ blocks of their local disk for use by each other. The software, running in the background, performs reads from and writes to this space on behalf of requests from the other partner.