1 Introduction
Peer-to-peer (P2P) networks (or overlays) have recently become an active research area. Applications over P2P networks include information retrieval, content distribution, processor cycle sharing, etc. These applications often demand that their underlying P2P network infrastructures be scalable and have low diameter and overhead. For example, an Internet-scale file sharing system, namely, Oceanstore [1], is designed and deployed on top of a P2P network Tapestry [2]. Tapestry is scalable in that each node participates in the network by using connections. Its overlay diameter is equal to , where is the total number of nodes in the system.