S. Fujita (Japan)
Skip graph, P2P overlay, data structure.
This paper proposes a new distributed data structure for efficient key search in purely distributed systems such as Peer-to-Peer (P2P) networks. More concretely, we show that by extending a distributed data struc ture known as skip graphs, we could obtain an overlay network for distributed systems in which each mes sage can be routed to its destination in O((lg lg N)2 )expected number of hops, where N is the number of nodes in the overlay. This is a significant improvement of the skip graph which takes O(lg N) hops in expec tation. In addition, the expected number of neighbors of each node in the resultant overlay is bounded by o(N ) for any fixed > 0.
Important Links:
Go Back
