Extended skip graphs for efficient key search in P2P environment

In this paper, we propose three techniques to improve the cost/performance of the skip graph that was recently proposed by Aspnes and Shah in 2003. More concretely, the skip graph, in which each node is connected with exactly log₂ N neighbors among N nodes contained in the system, is extended in the following two directions: 1) proposal of a subgraph of the skip graph which realizes a graceful degradation of the routing performance when the number of neighbors reduces from log₂ N, and 2) proposal of a supergraph of the skip graph which realizes a significant performance improvement when the number of neighbors increases from log₂ N. The performance of those extended graphs is evaluated analytically with concrete numerical results.