Peer-to-peer (P2P) systems based on distributed hash tables (DHTs) are starting to deliver desirable features such as decentralization, scalability, fault tolerance, self stabilization, data availability, load balancing, and dynamic addition and deletion of peer nodes. However, as keys are hashed, they can only provide hash-table functionality, thereby limiting the types of search queries. Skip graphs are a new distributed data structure that can form the basis of P2P systems. Since they are not based on the hashing of resource keys, related resources are near each other in a skip graph, which allows the P2P system to support complex queries, such as range queries. This is useful for applications such as the prefetching of Web pages, enhanced browsing, and efficient searching.

Skip graphs are a generalization of skip lists. A skip list is a randomized balanced tree data structure organized into levels of increasingly sparse doubly linked lists. A skip graph has multiple lists at any given level of a skip list, and this redundancy aids tolerance of single points of failure and congestion. Simple algorithms for search, insert, and delete operations for a skip graph are presented. In a skip graph with n nodes, search and insert take O(log n) messages and O(log n) time, while delete takes O(log n) messages and O(1) time. Fault-tolerant properties of a skip graph are evaluated under two fault models. Experimental results for a random failure model, and theoretical results for a worst-case failure model, show that search on skip graphs can succeed by using redundant links, making it fairly resilient to node failures in the absence of repair. The redundant links also provide congestion control. Theoretical results are presented to show that the probability that a particular node is traversed during various search conditions is low.

The skip graph is a novel data structure that is worth investigating in the context of distributed data store implementations that require good search performance and high resilience.