In this dissertation, we present a novel approach to the problem of distributed (peer-to-peer) backup. Our approach requires that data not be transferred more than two-hops from it source and that each peer store exactly the same amount of data as it distributes to be backed up. These two requirements address two import features of any distributed backup solution - trust and fairness.
In a social network, the hop distance requirement means that in the worst case, a peer's data is backed up in the local storage of a friend of a friend (FoaF). Our assumption is that this offers a higher degree of trust than simply choosing a random peer. We achieve fairness through the requirement that peers store exactly the same amount of data that they distribute for backup. To facilitate this requirement, our approach uses symmetric exchanges of data. This not only supports fairness, but also enhances trust by introducing a vested interest between peers to preserve the data that they are storing.
We call our approach the fair two-hop exchange scheme, or FTHES. We show that existing f-factor theory and algorithms can be used to compute an FTHES. Then we introduce and prove a fundamental existence theorem which states that an FTHES always exists under two fairly weak conditions. This theorem leads to a linear time sequential algorithm and an efficient distributed algorithm. We also prove a theorem stating that at most 2n-3 exchanges are needed to backup all of the data in our scheme and later conjecture that this may actually have a lower bound of n. Finally, we present an application of the FTHES in a content management system.