Building a reliable P2P system out of unreliable P2P clients: the case of KAD

Distributed Hash Tables (DHT) provide a framework for managing information in a large distributed network of nodes. One of the main challenges DHT systems must face is node churn, i.e., nodes can arrive and depart at any time. To assure that information published in a DHT remains available despite node churn is equivalent to building a reliable system out of unreliable components. In this paper we analyze KAD, a widely deployed DHT system. We focus on how to assure that information published in KAD remains available despite churn. We apply reliability theory to understand how the probability of finding an object published in KAD evolves over time. We also evaluate the cost, in terms of message exchanges, associated with the publishing scheme. Once we have identified the main weaknesses of the existing system, we propose an improved publishing scheme that is able to assure the same reliability but at a dramatically reduced cost. By exploiting knowledge about the lifetime of the nodes used to store the information, it is possible to reduce the publishing cost by one order of magnitude