Topology Sensitive Replica Selection

With the proliferation of peer-to-peer storage it is now possible to protect one's data at a level that is comparable to traditional replication systems but at reduced cost and complexity. These systems provide the needed flexibility, reliability, and scalability to operate in present day environments, and handle present day loads. These peer-to-peer storage systems must be able to replicate data on hosts that are trusted, secure, and available. However, recent research has shown that the traditional model, where nodes are assumed to have identical levels of trust, to behave independently, and to have similar failure modes, is incorrect. Thus, there is a need for a mechanism that automatically, correctly, and efficiently selects replica nodes from a large number of available hosts with varying capabilities and trust levels. In this paper we present an algorithm to handle node selection either for new replica groups or to replace failed replicas in a peer-to-peer replication system. We show through simulation that our algorithm maintains the interconnection topology such that the cost of recovery from a failed replica, measured by the number of messages and bandwidth, is minimized.