Abstract
We consider the query allocation problem in open and large distributed information systems. Provider sources are heterogeneous, autonomous, and have finite capacity to perform queries. A main objective in query allocation is to obtain good response time. Most of the work towards this objective has dealt with finding the most efficient providers. But little attention has been paid to satisfy the providers interest in performing certain queries. In this paper, we address both sides of the problem. We propose a query allocation approach which allows providers to express their intention to perform queries based on their preference and satisfaction. We compare our approach to both query load balancing and economic approaches. The experimentation results show that our approach yields high efficiency while supporting the providers’ preferences in adequacy with the query load. Also, we show that our approach guarantees interesting queries to providers even under low arrival query rates. In the context of open distributed systems, our approach outperforms traditional query load balancing approaches as it encourages providers to stay in the system, thus preserving the full system capacity.
Work partially funded by ARA “Massive Data” of the French ministry of research (projects MDP2P and Respire) and the European Strep Grid4All project.
An erratum to this chapter can be found at http://dx.doi.org/10.1007/11914853_71.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced Allocations. SIAM Journal on Computing (1999)
Buyya, R., Stockinger, H., Giddy, J., Abramson, D.: Economic Models for Management of Resources in Grid Computing. CoRR Journal (2001)
Feldman, M., Lai, K., Stoica, I., Chuang, J.: Robust Incentive Techniques for Peer-to-Peer Networks. In: Procs. of the EC ACM Conference (2004)
Ferguson, D., Nikolaou, C., Sairamesh, J., Yemini, Y.: Economic Models for Allocating Resources in Computer Systems. In: Market-based control: a paradigm for distributed resource allocation. World Scientific Publishing Company, Singapore (1996)
Ferguson, D., Yemini, Y., Nikolaou, C.: Microeconomic Algorithms for Load Balancing in Distributed Computer Systems. In: Procs. of the ICDCS Conference (1988)
Genova, Z., Christensen, K.: Challenges in URL Switching for Implementing Globally Distributed Web Sites. In: Procs. of the ICPP Workshops (2000)
Kamvar, S., Schlosser, M., Garcia-Molina, H.: The Eigentrust Algorithm for Reputation Management in P2P Networks. In: Procs. of the WWW Conference (2003)
Lamarre, P., Cazalens, S., Lemp, S., Valduriez, P.: A Flexible Mediation Process for Large Distributed Information Systems. In: Procs. of the CoopIS Conference (2004)
Li, L., Horrocks, I.: A Software Framework for Matchmaking Based on Semantic Web Technology. In: Procs. of the WWW Conference (2003)
Markatos, E.P.: Tracing a Large-Scale Peer to Peer System: An Hour in the Life of Gnutella. In: CCGRID Symposium (2002)
Mirchandaney, R., Towsley, D., Stankovic, J.: Adaptive Load Sharing in Heterogeneous Distributed Systems. Parallel and Distributed Computing Journal (1990)
Nodine, M., Bohrer, W., Ngu, A.: Semantic Brokering over Dynamic Heterogeneous Data Sources in InfoSleuth. In: Procs. of the ICDE Conference (1999)
Sah, A., Blow, J., Dennis, B.: An introduction to the Rush language. In: Procs. of the TCL Workshop (1994)
Saroiu, S., Gummadi, P.K., Gribble, S.: A Measurement Study of Peer-to-Peer File Sharing Systems. In: Procs. of the MCN Conference (2002)
Shivaratri, N., Krueger, P., Singhal, M.: Load Distributing for Locally Distributed Systems. Computer IEEE Journal (1992)
Stonebraker, M., Aoki, P., Litwin, W., Pfeffer, A., Sah, A., Sidell, J., Staelin, C., Yu, A.: Mariposa: A Wide-Area Distributed Database System. VLDB Journal (1996)
Sycara, K., Klusch, M., Widoff, S., Lu, J.: Dynamic Service Matchmaking Among Agents in Open Information Environments. In: SIGMOD Record (1999)
Zhu, H., Yang, T., Zheng, Q., Watson, D., Ibarra, O., Smith, T.: Adaptive Load Sharing for Clustered Digital Library Servers. In: HPDC Symposium (1998)
Özsu, T., Valduriez, P.: Principles of Distributed Database Systems, 2nd edn. Prentice-Hall, Englewood Cliffs (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Quiané-Ruiz, JA., Lamarre, P., Valduriez, P. (2006). Satisfaction-Based Query Load Balancing. In: Meersman, R., Tari, Z. (eds) On the Move to Meaningful Internet Systems 2006: CoopIS, DOA, GADA, and ODBASE. OTM 2006. Lecture Notes in Computer Science, vol 4275. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11914853_4
Download citation
DOI: https://doi.org/10.1007/11914853_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-48287-1
Online ISBN: 978-3-540-48289-5
eBook Packages: Computer ScienceComputer Science (R0)