【正文】 , then nodes forward queries to their predecessors. If the queries have lower and upper bounds such as “” and“1GBmemory2GB”, the queries will be forwarded in both directions. Cycloid has a selforganization mechanism to maintain its structure and stored objects, which helps LORM to handle dynamism with node joins and departures.IV. COMPARATIVE STUDY AND ANALYSISWe use Mercury , SWORD , MAAN as representatives of multipleDHTbased, singleDHTbased centralized and singleDHTbased decentralized classes, and analyze LORM in parison with the approaches. LORM maps resource attribute and value or string description to two levels of a hierarchical Cycloid DHT. Mercury uses multiple DHTs with one DHT responsible for each attribute and maps resource value to each DHT. SWORD maps resource information including both attribute and value in a flat DHT,and MAAN maps attribute and value separately to a flat DHT. To be parable, we use Chord for attribute hubs in Mercury, and we replace Bamboo DHT with Chord in SWORD.In Mercury, for higher efficiency of resource query, a node within one of the hubs can hold the data record while the other hubs can hold a pointer to the node. This strategy can also be applied to other methods. To make the different methods be parable, we don’t consider this strategy in the parative study. We analyze their performance in terms of structure maintenance overhead, resource information maintenance overhead, and the efficiency of resource discovery. In the analysis, we use “attribute value” to represent the locality preserving hash value of both attribute value and attribute string description. We use directory size to represent the number of resource information pieces in a directory.A . Maintenance OverheadTheorem : In a grid system with n nodes and m resource attributes, with high probability, LORM can improve the structure maintenance overhead of multipleDHTbased methods (. Mercury) by no less than m times.Proof: LORM is based on Cycloid, in which each node is responsible for maintaining d ≤ log(n) neighbors. In multipleDHTbased methods such as Mercury, each node is responsible for maintaining log(n) neighbors for each DHT of one resource. Therefore, each node has mlog(n) neighbors. The structure maintenance overhead that can be saved is times. Theorem : In a grid system, the total number of resource information pieces in singleDHTbased decentralized resource discovery methods (. MAAN) is twice of those in LORM, singleDHTbased centralized methods () and multiDHTbased methods (. Mercury).Proof: For each piece of resource information, MAAN splits its a and , and stores the two pieces of information separately, while LORM, singleDHTbased centralized () and multiDHTbased methods (. Mercury) only store one information piece. Therefore, the size of the total resource information of MAAN is twice of others.Theorem : In a grid system with n nodes and m resource attributes, with the assumption that each type of resource attribute has k pieces of resource information and its values are uniformly distributed, ., LORM can reduce the number of resource information pieces in a directory node in the singleDHTbased decentralized resource discovery methods (. MAAN) by d(1+ ) times.Proof: For k pieces of resource information of a resource attribute, MAAN splits the attribute and value. K pieces are stored in the same node, and the other k pieces are uniformly distributed among the n nodes based on the directory node has a total of k +m一、英文原文：Performance Analysis of DHT Algorithms for RangeQuery and MultiAttribute Resource Discovery in GridsHaiying Shen ChengZhong XuAbstract—Resource discovery is critical to the usability and accessibility of grid puting systems. Distributed Hash Table (DHT) has been applied to grid systems as a distributed mechanism for providing scalable rangequery and multiattribute resource discovery. MultiDHTbased approaches depend on multiple DHT networks with each network responsible for a single attribute. SingleDHTbased approaches keep the resource information of all attributes in a single classes of approaches lead to high overhead. Recently,we proposed a heuristic LowOverhead Rangequery Multiattribute DHTbased resource discovery approach (LORM). It relies on a single hierarchical DHT network and distributes resource information among nodes in balance by taking advantage of the hierarchical structure. We demonstrated its effectiveness and efficiency via simulation. In this paper, we analyze the performance of the LORM approach rigorously by paring it with other multiDHTbased and singleDHTbased approaches with respect to their overhead and efficiency.