Decentralized Self-adaptation in the Presence of Partial Knowledge with Reduced Coordination Overhead

Full Text (PDF, 507KB), PP.9-19

Views: 0 Downloads: 0

Author(s)

Kishan Kumar Ganguly 1,* Moumita Asad 1 Kazi Sakib 1

1. Institute of Information Technology, University of Dhaka

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2022.01.02

Received: 16 Sep. 2021 / Revised: 7 Nov. 2021 / Accepted: 21 Nov. 2021 / Published: 8 Feb. 2022

Index Terms

Decentralized Self-Adaptation, Partial Knowledge, Coordination Overhead, Q-learning

Abstract

Decentralized self-adaptive systems consist of multiple control loops that adapt some local and system-level global goals of each locally managed system or component in a decentralized setting. As each component works together in a decentralized environment, a control loop cannot take adaptation decisions independently. Therefore, all the control loops need to exchange their adaptation decisions to infer a global knowledge about the system. Decentralized self-adaptation approaches in the literature uses the global knowledge to take decisions that optimize both local and global goals. However, coordinating in such an unbounded manner impairs scalability. This paper proposes a decentralized self-adaptation technique using reinforcement learning that incorporates partial knowledge in order to reduce coordination overhead. The Q-learning algorithm based on Interaction Driven Markov Games is utilized to take adaptation decisions as it enables coordination only when it is beneficial. Rather than using unbounded number of peers, the adaptation control loop coordinates with a single peer control loop. The proposed approach was evaluated on a service-based Tele Assistance System. It was compared to random, independent and multiagent learners that assume global knowledge. It was observed that, in all cases, the proposed approach conformed to both local and global goals while maintaining comparatively lower coordination overhead.

Cite This Paper

Kishan Kumar Ganguly, Moumita Asad, Kazi Sakib, "Decentralized Self-adaptation in the Presence of Partial Knowledge with Reduced Coordination Overhead", International Journal of Information Technology and Computer Science(IJITCS), Vol.14, No.1, pp.9-19, 2022. DOI: 10.5815/ijitcs.2022.01.02

Reference

[1] D. Weyns, S. Malek, J. Andersson, On decentralized self-adaptation: lessons from the trenches and challenges for the future (2010) 84–93.
[2] M. T. Spaan, F. S. Melo, Interaction-driven markov games for decentralized multiagent planning under uncertainty, in: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 1, International Foundation for Autonomous Agents and Multiagent Systems, 2008, pp. 525–532.
[3] V. Grassi, M. Marzolla, R. Mirandola, Qos-aware fully decentralized ser-vice assembly, in: Software Engineering for Adaptive and Self-Managing Systems (SEAMS), 2013 ICSE Workshop on, IEEE, 2013, pp. 53–62.
[4] H. Wang, Q. Wu, X. Chen, Q. Yu, Z. Zheng, A. Bouguettaya, Adaptive and dynamic service composition via multi-agent reinforcement learning, in: Web Services (ICWS), 2014 IEEE International Conference on, IEEE, 2014, pp. 447–454.
[5] C. Claus, C. Boutilier, The dynamics of reinforcement learning in cooperative multiagent systems, AAAI/IAAI 1998 (1998) 746–752.
[6] F. S. Melo, M. Veloso, Learning of coordination: Exploiting sparse interactions in multiagent systems, in: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, International Foundation for Autonomous Agents and Multiagent Systems, 2009, pp. 773–780.
[7] D. Weyns, R. Calinescu, Tele assistance: A self-adaptive service-based system examplar, in: Proceedings of the 10th International Symposium on Soft-ware Engineering for Adaptive and Self-Managing Systems, IEEE Press, 2015, pp. 88–92.
[8] R. De Lemos, H. Giese, H. A. Muller,¨ M. Shaw, J. Andersson, M. Litoiu, B. Schmerl, G. Tamura, N. M. Villegas, T. Vogel, et al., Software engineering for self-adaptive systems: A second research roadmap, in: Software Engineering for Self-Adaptive Systems II, Springer, 2013, pp. 1–32.
[9] D. Weyns, B. Schmerl, V. Grassi, S. Malek, R. Mirandola, C. Prehofer, J. Wuttke, J. Andersson, H. Giese, K. M. Goschka,¨ On patterns for de-centralized control in self-adaptive systems, in: Software Engineering for Self-Adaptive Systems II, Springer, 2013, pp. 76–107.
[10] I. Georgiadis, J. Magee, J. Kramer, Self-organising software architectures for distributed systems, in: Proceedings of the first workshop on Self-healing systems, ACM, 2002, pp. 33–38.
[11] D. Sykes, J. Magee, J. Kramer, Flashmob: distributed adaptive self-assembly, in: Proceedings of the 6th International Symposium on Soft-ware Engineering for Adaptive and Self-Managing Systems, ACM, 2011, pp. 100–109.
[12] J. Dowling, R. Cunningham, E. Curran, V. Cahill, Building autonomic systems using collaborative reinforcement learning, The Knowledge Engineering Review 21 (3), 2006, pp. 231–238.
[13] Kishan Kumar Ganguly, Md. Saeed Siddik, Rayhanul Islam, Kazi Sakib, "An Environment Aware Learning-based Self-Adaptation Technique with Reusable Components", International Journal of Modern Education and Computer Science, Vol.11, No.6, pp. 53-64, 2019.
[14] M. Caporuscio, M. D’Angelo, V. Grassi, R. Mirandola, Reinforcement learning techniques for decentralized self-adaptive service assembly, in: European Conference on Service-Oriented and Cloud Computing, Springer, 2016, pp. 53–68.
[15] A. Nowe,´ P. Vrancx, Y.-M. De Hauwere, Game theory and multi-agent reinforcement learning, in: Reinforcement Learning, Springer, 2012, pp. 441– 470.
[16] H. B. Mann, D. R. Whitney, On a test of whether one of two random variables is stochastically larger than the other, The annals of mathematical statistics (1947) 50–60.
[17] Bechar Rachid, Haffaf Hafid, "Distributed Monitoring for Wireless Sensor Networks: a Multi-Agent Approach", International Journal of Computer Network and Information Security, vol.6, no.10, pp.13-23, 2014.