Leopard (DHT)
From Wikipedia, the free encyclopedia
 |
This article or section may require cleanup to meet Wikipedia's quality standards. Please help improve this article or replace this tag with a more specific message. This article has been tagged since March 2006. (help, talk) |
In computing, Leopard is a distributed hash table searching system written by Yinzhe Yu, Sanghwan Lee and Zhi-Li Zhang, and originally published in NETWORKING, 2005. It creates a DHT which has good locality properties -- not of lookup, but of cached copies which are physically close to the requestor. This could be used to search for the (physically) nearest neighbor containing certain keys (such as a lookup of peers with a certain file).
Leopard does this by assigning each node "network coordinates", using a coordinate system like Vivaldi, such that neighbors close in the coordinate space are proportionally close geographically. It then divides the network coordinate into quarters, and then each quarter into quarters, etc., assigning each of those (small and getting smaller) quarters a unique number. To search for a peer geographically close that has an "answer" to a query, it runs a hash of the query+name_of_the_closest_smallest_quarter. Peers close in the geographic area will also use therefore use this query (since they are close in the coordinate space). If none is found then it uses its next level up (size-wise) quarter name, hashes that with the query, and queries this in the DHT (note that it can use any DHT). It also adds itself to the DHT at these rendezvous points. This next query will discover close peers within a larger area who have answers to the same query (if they have registered themselves there).
Leopard therefore allows peers close to each other to contact one another regarding certain keys (or learn of one another). Note that it requires possibly more than one look up (acceptable), and that peers must register themselves as they 'ascend' with their queries, so that other peers can find them when they do similar queries.
