LinkNet:一种用于大规模P2P系统查找的新方法

LinkNet: A New Approach for Searching in a Large Peer-to-Peer System

提出了一种新的可扩展分布式数据结构LinkNet来支持大规模P2P系统中的数据查找.在LinkNet中,所有的元素存储在一个有序的双向链表中,该链表中的每个结点都可以存储多个元素.LinkNet使用虚拟链接来减少存储开销和加速查找过程.在一个包含N个结点M个元素的网络中,LinkNet占用的存储空间期望值为O(M),并且当M足够大时,查找操作期望只需要传递O(logN)条消息.

This paper presents a new scalable distributed data structure LinkNet for searching in a large Peer-to-Peer system. In LinkNet, all elements are stored in a sorted doubly linked list, and one node stores many elements. LinkNet uses virtual links to decrease storage cost and speed search. In an N nodes M elements network, the expected total space this data structure takes is O（M）, and when M is big enough, the search operation takes expected O（logN） messages among nodes.