Decentralized multi-attribute range search for resource discovery and load balancing

The recent trend toward heterogeneity among, and even within, computers requires new expressiveness in the way resource descriptions are created, and new sophistication in systems that attempt to match jobs with resources. In this paper, we propose a novel resource discovery and load balancing method to support multi-attribute, range-based job constraints in a peer-to-peer grid system. The common approach of using simple attribute indexes does not suffice, as range-based constraints may be satisfied by more than a single value. We show via simulation that our approach matches these new heterogeneous jobs to heterogeneous resources both effectively (good matches are found, load is balanced) and efficiently (the new functionality imposes little overhead). Our system relies on resource descriptions being aggregated and periodically disseminated. Decentralized algorithms are often sensitive to the “freshness” of this information. However, we show that our approach is not sensitive to stale data, allowing the information movement to happen rarely enough that it imposes only insignificant overhead.