一、英文原文：Performance Analysis of DHT Algorithms for Range-Query and Multi-Attribute Resource Discovery in GridsHaiying Shen Cheng-Zhong XuAbstractResource discovery is critical to the usability and accessibility of grid computing systems. Distributed Hash Table (DHT) has been applied to grid systems as a distributed mechanism for providing scalable range-query and multiattribute resource discovery. Multi-DHT-based approaches depend on multiple DHT networks with each network responsible for a single attribute. Single-DHT-based approaches keep the resource information of all attributes in a single node.Both classes of approaches lead to high overhead. Recently,we proposed a heuristic Low-Overhead Range-query Multiattribute DHT-based 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 comparing it with other multi-DHT-based and single-DHTbased approaches with respect to their overhead and efficiency. The analytical results are consistent with simulation results.The results prove the superiority of the LORM approach in theory.Keywords Resource discovery Grids Peer-to-peer system Distributed hash tableI. INTRODUCTIONGrid systems integrate computers, clusters, storage systems and instruments to provide a highly available infrastructure for large scientific computing centers. They make possible the sharing of existing resources such as CPU time, storage, equipment, data, and software applications.In many grid systems, resources are highly dynamic and vary significantly over time such as available CPU time and memory. Because of this variability, scalable and efficient resource discovery is critical to providing usability and accessibility for large-scale grid computing systems.The resources required by applications are often described by a set of attributes such as available computing power and memory with range for each attribute (multi-attribute range queries). A fundamental service of resource discovery is to locate resources across multiple administrative domains according to the attribute inputs. Recently, Distributed Hash Table (DHT) architecture has been applied to grid systems for large-scale and dynamic resource discovery due to its high scalability and dynamism-resilience features. DHT can efficiently route messages to the unique owner of any given object. Because of its single deterministic object location,the object can be either resource attribute or value. Therefore,it is a challenge to realize resource discovery with both range-query and multi-attribute features.Most DHT-based approaches can be classified into multi-DHT-based, single-DHT-based centralized and single-DHT-based decentralized approaches. Multi-DHT-based approaches support multi-attribute range queries by relying on multiple DHT networks with each network responsible for a single attribute . To locate resources specified by several attributes and ranges, each query for a resource is presented to the appropriate DHT and then the results are concatenated in a database-like “join” operation. Single-DHT-based centralized approaches keep the resource information of all values for a specific attribute in a single node. Single-DHT-based decentralized approach is based on one DHT and provides range searching. It maps resource attribute and value of a resource separately to one DHT, and processes a query by searching them separately.To reduce overhead and enhance efficiency of resource discovery in grids, we recently proposed a DHT-based resource discovery approach with features of Low-Overhead,Range-query and Multi-attribute (LORM) . Unlike the three types of approaches mentioned, LORM is built on a single DHT called Cycloid . LORM arranges each node to be responsible for the information of a specific attribute within a value range by taking advantage of the hierarchical structure of Cycloid. We demonstrated its effectiveness and efficiency via simulation. In this paper, we analyze the performance of the LORM approach rigorously and compare it with multi-DHT-based and single-DHT-based approaches with respect to their overhead and efficiency. The analytical results are consistent with the simulation results. The results prove the superiority of the LORM approach in theory. The remainder of this paper is structured as follows.Section II describes a review of representative DHT-based resource discovery approaches for grid systems. Section III presents an overview of the DHT-based LORM resource discovery approach and theoretical analysis of its features.Section IV presents the performance analysis of LORM in comparison to other representative resource discovery methods. Section V presents the performance comparison between LORM and other