{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:51:05Z","timestamp":1750308665447,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ATEI grant titled \u201cAdaptive QoS control and optimization of computing systems\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>This work investigates a particular instance of the problem of designing efficient adaptive systems, under the condition that each adaptation decision incurs some nonnegligible cost when enacted. More specifically, we deal with the problem of dynamic, intraquery load balancing in parallel database queries across heterogeneous nodes in a way that takes into account the inherent cost of adaptations and thus avoids both overreacting and deciding when to adapt in a completely heuristic manner. The latter may lead to serious performance degradation in several cases, such as periodic and random imbalances. We follow a control theoretical approach to this problem; more specifically, we propose a multiple-input multiple-output feedback linear quadratic regulation (LQR) controller, which captures the tradeoff between reaching a balanced state and the cost inherent in such adaptations. Our approach, apart from benefitting from and being characterized by a solid theoretical foundation, exhibits better performance than state-of-the-art heuristics in realistic situations, as verified by thorough evaluation.<\/jats:p>","DOI":"10.1145\/2168260.2168265","type":"journal-article","created":{"date-parts":[[2012,5,1]],"date-time":"2012-05-01T13:43:38Z","timestamp":1335879818000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient load balancing in partitioned queries under random perturbations"],"prefix":"10.1145","volume":"7","author":[{"given":"Anastasios","family":"Gounaris","sequence":"first","affiliation":[{"name":"Aristotle University of Thessaloniki, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos A.","family":"Yfoulis","sequence":"additional","affiliation":[{"name":"Alexander Technological Educational Institute of Thessaloniki, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Norman W.","family":"Paton","sequence":"additional","affiliation":[{"name":"University of Manchester, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,5,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Astr\u00f6m K. J. and Wittenmark B. 1995. Adaptive Control. Addison-Wesley Reading MA.  Astr\u00f6m K. J. and Wittenmark B. 1995. Adaptive Control. Addison-Wesley Reading MA."},{"volume-title":"Proceedings of the ACM Symposium on Networked Systems Design and Implementation (NSDI). 197--210","author":"Balazinska M.","key":"e_1_2_1_2_1","unstructured":"Balazinska , M. , Balakrishnan , H. , and Stonebraker , M . 2004. Contract-based load management in federated distributed systems . In Proceedings of the ACM Symposium on Networked Systems Design and Implementation (NSDI). 197--210 . Balazinska, M., Balakrishnan, H., and Stonebraker, M. 2004. Contract-based load management in federated distributed systems. In Proceedings of the ACM Symposium on Networked Systems Design and Implementation (NSDI). 197--210."},{"volume-title":"Proceedings of the American Control Conference.","author":"Birdwell J.","key":"e_1_2_1_3_1","unstructured":"Birdwell , J. , Zhong , T. , Chiasson , J. , Abdallah , C. , and Hayat , M . 2006. Resource-constrained load balancing controller for a parallel database . In Proceedings of the American Control Conference. Birdwell, J., Zhong, T., Chiasson, J., Abdallah, C., and Hayat, M. 2006. Resource-constrained load balancing controller for a parallel database. In Proceedings of the American Control Conference."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/37.980246"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/129888.129894"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECBS.2005.60"},{"volume-title":"Proceedings ofthe IEEE Real-Time and Embedded Technology and Applications Symposium. 376--387","author":"Diao Y.","key":"e_1_2_1_8_1","unstructured":"Diao , Y. , Hellerstein , J. L. , Storm , A. J. , Surendra , M. , Lightstone , S. , Parekh , S. S. , and Garcia-Arellano , C . 2004. Incorporating cost of control into the design of a load balancing controller . In Proceedings ofthe IEEE Real-Time and Embedded Technology and Applications Symposium. 376--387 . Diao, Y., Hellerstein, J. L., Storm, A. J., Surendra, M., Lightstone, S., Parekh, S. S., and Garcia-Arellano, C. 2004. Incorporating cost of control into the design of a load balancing controller. In Proceedings ofthe IEEE Real-Time and Embedded Technology and Applications Symposium. 376--387."},{"volume-title":"Proceedings of the American Control Conference. 1484--1490","author":"Diao Y.","key":"e_1_2_1_9_1","unstructured":"Diao , Y. , Wu , C. W. , Hellerstein , J. L. , Storm , A. J. , Surendra , M. , Lightstone , S. , Parekh , S. , Garcia-Arellano , C. , Carroll , M. , Chu , L. , and Colaco , J . 2005b. Comparative studies of load balancing with control and optimization techniques . In Proceedings of the American Control Conference. 1484--1490 . Diao, Y., Wu, C. W., Hellerstein, J. L., Storm, A. J., Surendra, M., Lightstone, S., Parekh, S., Garcia-Arellano, C., Carroll, M., Chu, L., and Colaco, J. 2005b. Comparative studies of load balancing with control and optimization techniques. In Proceedings of the American Control Conference. 1484--1490."},{"volume-title":"Proceedings of the American Control Conference.","author":"Dumont G.","key":"e_1_2_1_10_1","unstructured":"Dumont , G. and Huzmezan , M . 2002. Concepts, methods and techniques in adaptive control . In Proceedings of the American Control Conference. Dumont, G. and Huzmezan, M. 2002. Concepts, methods and techniques in adaptive control. In Proceedings of the American Control Conference."},{"key":"e_1_2_1_11_1","unstructured":"Franklin G. Powell J. and Workman M. 1998. Digital Control of Dynamic Systems 3rd Ed. Addison-Wesley Reading MA.   Franklin G. Powell J. and Workman M. 1998. Digital Control of Dynamic Systems 3rd Ed. Addison-Wesley Reading MA."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2006.20"},{"volume-title":"Proceedings of the IEEE International Conference on Distributed Computer Systems (ICDCS). 490--499","author":"Gedik B.","key":"e_1_2_1_13_1","unstructured":"Gedik , B. and Liu , L . 2003. Peercq: A decentralized and self-configuring peer-to-peer information monitoring system . In Proceedings of the IEEE International Conference on Distributed Computer Systems (ICDCS). 490--499 . Gedik, B. and Liu, L. 2003. Peercq: A decentralized and self-configuring peer-to-peer information monitoring system. In Proceedings of the IEEE International Conference on Distributed Computer Systems (ICDCS). 490--499."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1352789.1352791"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497468"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings ofthe 3rd IEEE Multi-Conference on Systems and Control","author":"Gounaris A.","year":"2009","unstructured":"Gounaris , A. , Yfoulis , C. A. , and Paton , N. W . 2009. An efficient load balancing LQR controller in parallel databases queries under random perturbations . In Proceedings ofthe 3rd IEEE Multi-Conference on Systems and Control ( 2009 ). Gounaris, A., Yfoulis, C. A., and Paton, N. W. 2009. An efficient load balancing LQR controller in parallel databases queries under random perturbations. In Proceedings ofthe 3rd IEEE Multi-Conference on Systems and Control (2009)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98720"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199604)26:4%3C427::AID-SPE20%3E3.3.CO;2-8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Hellerstein J. L. Diao Y. Parekh S. and Tilbury D. M. 2004. Feedback Control of Computing Systems. John Wiley & Sons.   Hellerstein J. L. Diao Y. Parekh S. and Tilbury D. M. 2004. Feedback Control of Computing Systems. John Wiley & Sons.","DOI":"10.1002\/047166880X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304209"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2003.1160055"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2007.2"},{"volume-title":"Proceedings of the IEEE Workshop Autonomic Computing Principles and Architectures (AUCOPA). 419--424","author":"Lightstone S.","key":"e_1_2_1_23_1","unstructured":"Lightstone , S. , Schiefer , B. , Zilio , D. , and Kleewein , J . 2003. Autonomic computing for relational databases: The ten-year vision . In Proceedings of the IEEE Workshop Autonomic Computing Principles and Architectures (AUCOPA). 419--424 . Lightstone, S., Schiefer, B., Zilio, D., and Kleewein, J. 2003. Autonomic computing for relational databases: The ten-year vision. In Proceedings of the IEEE Workshop Autonomic Computing Principles and Architectures (AUCOPA). 419--424."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2007.4401022"},{"volume-title":"Proceedings ofthe 3rd International Conference on Extending Database Technology (EDBT). 357--372","author":"Lu H.","key":"e_1_2_1_25_1","unstructured":"Lu , H. and Tan , K . -L. 1992. Dynamic and load-balanced task-oriented datbase query processing in parallel systems . In Proceedings ofthe 3rd International Conference on Extending Database Technology (EDBT). 357--372 . Lu, H. and Tan, K.-L. 1992. Dynamic and load-balanced task-oriented datbase query processing in parallel systems. In Proceedings ofthe 3rd International Conference on Extending Database Technology (EDBT). 357--372."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007642"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645921.673299"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.1999.787642"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0090-x"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 395--406","author":"Rahm E.","key":"e_1_2_1_30_1","unstructured":"Rahm , E. and Marek , R . 1995. Dynamic multi-resource load balancing in parallel database systems . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 395--406 . Rahm, E. and Marek, R. 1995. Dynamic multi-resource load balancing in parallel database systems. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 395--406."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 61--72","author":"Raman V.","key":"e_1_2_1_31_1","unstructured":"Raman , V. , Han , W. , and Narang , I . 2005. Parallel querying with non-dedicated computers . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 61--72 . Raman, V., Han, W., and Narang, I. 2005. Parallel querying with non-dedicated computers. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 61--72."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.v18:1"},{"volume-title":"Proceedings of the International Conference on Data Engineering Workshops (ICDE). 25--36","author":"Shah M. A.","key":"e_1_2_1_33_1","unstructured":"Shah , M. A. , Hellerstein , J. M. , Chandrasekaran , S. , and Franklin , M. J . 2003. Flux: An adaptive partitioning operator for continuous query systems . In Proceedings of the International Conference on Data Engineering Workshops (ICDE). 25--36 . Shah, M. A., Hellerstein, J. M., Chandrasekaran, S., and Franklin, M. J. 2003. Flux: An adaptive partitioning operator for continuous query systems. In Proceedings of the International Conference on Data Engineering Workshops (ICDE). 25--36."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.250117"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.53"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2168260.2168265","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2168260.2168265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:00:33Z","timestamp":1750276833000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2168260.2168265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1145\/2168260.2168265"],"URL":"https:\/\/doi.org\/10.1145\/2168260.2168265","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2012,4]]},"assertion":[{"value":"2009-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}