Cluster-K+: Network topology for searching replicated data in p2p systems

This paper proposes a new scheme for ensuring data consistency in unstructured p2p networks where peers can subscribe to multiple content types (identified by labels) and are rapidly informed of content updates. The idea is based on using a static tree structure, the Cluster-K+ tree, that maintains most of the structural information about peers and labels. A label denotes a set of replicated or co-related data in the network. The Cluster-K+ tree provides efficient retrieval, addition, deletion and consistent updates of labels. Our proposed structure guarantees a short response search time of O(H + K), where H denotes the height of the tree and K the degree of an internal tree node. We present theoretical analytic bounds for the worst-case performance. To verify the bounds, we also present experimental results obtained from a network simulation. The results demonstrate that the actual performance of our system is significantly better than the theoretical bounds. (C) 2010 Elsevier Ltd. All rights reserved.