Un système multi-agent adaptatif pour la réallocation de tâches au sein d’un job MapReduce
Quentin Baert1 ; Anne-Cécile Caron1 ; Maxime Morge1 ; Jean-Christophe Routier1 ; Kostas Stathis2
1 Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France
2 Department of Computer Science, Royal Holloway, University of London, Egham TW20 0EX, UK
Revue Ouverte d'Intelligence Artificielle, Post-actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA 2018-2019-2020), Volume 3 (2022) no. 5-6, pp. 557-585.

Nous étudions le problème de la réallocation de tâches pour l’équilibrage de jobs MapReduce dans des applications de traitement de données massives. Dans ce contexte, pour optimiser l’ordonnancement de tâches dans un seul job MapReduce, nous proposons une stratégie basée sur des agents coopératifs. L’originalité de notre stratégie réside dans la capacité des agents à identifier des opportunités au sein d’une allocation déséquilibrée qui leur permettent de déclencher des négociations «  un-à-plusieurs  » concurrentes entre agents dans le but de réallouer certaines tâches au sein du job. Notre contribution consiste à réallouer les tâches en fonction de la proximité des ressources pour qu’elles soient exécutées en tenant compte des capacités des nœuds sur lesquels sont situés les agents. Pour évaluer l’adaptivité et la réactitivé de notre approche, nous avons implémenté un prototype et mené de nombreuses expériences dans un environnement hétérogène, selon différentes configurations. Cette large campagne d’expérimentations révèle que notre stratégie améliore significativement le temps d’exécution total par rapport au processus classique de Hadoop.

We study the problem of task reallocation for load-balancing of MapReduce jobs in applications that process large datasets. In this context, we propose a novel strategy based on cooperative agents used to optimise the task scheduling in a single MapReduce job. The novelty of our strategy lies in the ability of agents to identify opportunities within a current unbalanced allocation, which in turn trigger concurrent and one-to-many negotiations amongst agents to locally reallocate some of the tasks within a job. Our contribution is that tasks are reallocated according to the proximity of the resources and they are performed in accordance to the capabilities of the nodes in which agents are situated. To evaluate the adaptivity and responsiveness of our approach, we implement a prototype test-bed and conduct a vast panel of experiments in a heterogeneous environment and by exploring varying hardware configurations. This extensive experimentation reveals that our strategy significantly improves the overall runtime over the classical Hadoop data processing.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/roia.43
Mot clés : Système multi-agents, Résolution collective de problèmes, Négociation multi-agents.
Keywords: Multi-Agents Systems, Distributed Problem Solving, Agent-based Negotiation.

Quentin Baert 1 ; Anne-Cécile Caron 1 ; Maxime Morge 1 ; Jean-Christophe Routier 1 ; Kostas Stathis 2

1 Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France
2 Department of Computer Science, Royal Holloway, University of London, Egham TW20 0EX, UK
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{ROIA_2022__3_5-6_557_0,
     author = {Quentin Baert and Anne-C\'ecile Caron and Maxime Morge and Jean-Christophe Routier and Kostas Stathis},
     title = {Un syst\`eme multi-agent adaptatif pour la r\'eallocation de t\^aches au sein d{\textquoteright}un job {MapReduce}},
     journal = {Revue Ouverte d'Intelligence Artificielle},
     pages = {557--585},
     publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
     volume = {3},
     number = {5-6},
     year = {2022},
     doi = {10.5802/roia.43},
     language = {fr},
     url = {https://roia.centre-mersenne.org/articles/10.5802/roia.43/}
}
TY  - JOUR
AU  - Quentin Baert
AU  - Anne-Cécile Caron
AU  - Maxime Morge
AU  - Jean-Christophe Routier
AU  - Kostas Stathis
TI  - Un système multi-agent adaptatif pour la réallocation de tâches au sein d’un job MapReduce
JO  - Revue Ouverte d'Intelligence Artificielle
PY  - 2022
SP  - 557
EP  - 585
VL  - 3
IS  - 5-6
PB  - Association pour la diffusion de la recherche francophone en intelligence artificielle
UR  - https://roia.centre-mersenne.org/articles/10.5802/roia.43/
DO  - 10.5802/roia.43
LA  - fr
ID  - ROIA_2022__3_5-6_557_0
ER  - 
%0 Journal Article
%A Quentin Baert
%A Anne-Cécile Caron
%A Maxime Morge
%A Jean-Christophe Routier
%A Kostas Stathis
%T Un système multi-agent adaptatif pour la réallocation de tâches au sein d’un job MapReduce
%J Revue Ouverte d'Intelligence Artificielle
%D 2022
%P 557-585
%V 3
%N 5-6
%I Association pour la diffusion de la recherche francophone en intelligence artificielle
%U https://roia.centre-mersenne.org/articles/10.5802/roia.43/
%R 10.5802/roia.43
%G fr
%F ROIA_2022__3_5-6_557_0
Quentin Baert; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier; Kostas Stathis. Un système multi-agent adaptatif pour la réallocation de tâches au sein d’un job MapReduce. Revue Ouverte d'Intelligence Artificielle, Post-actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA 2018-2019-2020), Volume 3 (2022) no. 5-6, pp. 557-585. doi : 10.5802/roia.43. https://roia.centre-mersenne.org/articles/10.5802/roia.43/

[1] Alessandro Agnetis; Jean-Charles Billaut; Stanislaw Gawiejnowicz; Dario Pacciarelli; Ameur Soukhal Multiagent Scheduling – Models and Algorithms, Springer, 2014 | DOI | Zbl

[2] Bedour Alrayes; Özgür Kafalı; Kostas Stathis Concurrent bilateral negotiation for open e-markets : the CONAN strategy, Knowledge and Information Systems, Volume 56 (2017) no. 2, pp. 463-501 | DOI

[3] Bo An; Victor Lesser; David Irwin; Michael Zink, Proc. of 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2010), pp. 981-988 | DOI

[4] Gamal Attiya; Yskandar Hamam Task allocation for maximizing reliability of distributed systems : A simulated annealing approach, Journal of Parallel and Distributed Computing, Volume 66 (2006) no. 10, pp. 1259-1266 | DOI | Zbl

[5] Quentin Baert; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier MAS4Data : Multiagent systems for processing very large datasets (https://github.com/cristal-smac/mas4data, visited 2019-12-17)

[6] Quentin Baert; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier, Actes des 25èmes journées francophones sur les systèmes multi-agents (2017), pp. 65-74

[7] Quentin Baert; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier Fair multi-agent task allocation for large datasets analysis, Knowledge and Information Systems, Volume 54 (2018) no. 3, pp. 591-615 | DOI

[8] Quentin Baert; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier; Kostas Stathis, Proc. of the 31st International Conference on Tools with Artificial Intelligence (ICTAI) (2019) | DOI

[9] Quentin Baert; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier; Kostas Stathis, Actes des 27ièmes journées francophones sur les systèmes multi-agents (2019), pp. 9-18

[10] Quentin Baert; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier; Kostas Stathis An adaptive multi-agent system for task reallocation in a MapReduce job, Journal of Parallel and Distributed Computing, Volume 153 (2021), pp. 75-88 | DOI

[11] Soumya Banerjee; Joshua P. Hecker, First Complex Systems Digital Campus World E-Conference 2015 (2017), pp. 41-54 | DOI

[12] Ellie Beauprez; Luc Bigand; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier, Vingt-neuvièmes journées francophones sur les systèmes multi-agents (JFSMA) (2021), pp. 1-10 | HAL

[13] Ellie Beauprez; Luc Bigand; Anne-Cécile Caron; Maxime Morge; Jean-Christophe Routier, Vingt-neuvièmes journées francophones sur les systèmes multi-agents (JFSMA) (JFSMA 2021. Collectifs cyber-physiques) (2021), pp. 51-60

[14] James Bennett; Stan Lanning et al., Proceedings of KDD cup and workshop, Volume 2007 (2007), p. 35

[15] Bo Chen; Chris N. Potts; Gerhard J. Woeginger A review of machine scheduling : Complexity, algorithms and approximability, Handbook of combinatorial optimization (1998), pp. 1493-1641 | DOI | Zbl

[16] Quan Chen; Daqiang Zhang; Minyi Guo; Qianni Deng; Song Guo, Proc. of the 14th International Conference on Computer and Information Technology (2010), pp. 2736-2743 | DOI

[17] J. Dean; S. Ghemawat, Proc. of the 9th Symposium on Operating Systems Design and Implementation (2004), pp. 137-150 | DOI

[18] Ulle Endriss; Nicolas Maudet; Fariba Sadri; Francesca Toni Negotiating Socially Optimal Allocations of Resources, Journal of Artificial Intelligence Research, Volume 25 (2006) no. 1, pp. 315-348 | DOI | MR

[19] Saurabh Kumar Garg; Srikumar Venugopal; James Broberg; Rajkumar Buyya Double auction-inspired meta-scheduling of parallel applications on global grids, Journal of Parallel and Distributed Computing, Volume 73 (2013) no. 4, pp. 450-464 | DOI

[20] Mohammad Hammoud; M. Rehman; Majd Sakr, Proc. of the 5th International Conference on Cloud Computing (CLOUD) (2012), pp. 49-58 | DOI

[21] A. M. A. Hariri; N. Potts Heuristics for scheduling unrelated parallel machines, Computers & operations research, Volume 18 (1991) no. 3, pp. 323-331 | DOI | Zbl

[22] Ellis Horowitz; Sartaj Sahni Exact and approximate algorithms for scheduling nonidentical processors, Journal of the ACM, Volume 23 (1976) no. 2, pp. 317-327 | DOI | MR | Zbl

[23] Oscar H. Ibarra; Chul E. Kim Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors, Journal of ACM, Volume 24 (1977) no. 2, pp. 280-289 | DOI | MR | Zbl

[24] Yichuan Jiang A survey of task allocation and load balancing in distributed systems, IEEE Transactions on Parallel and Distributed Systems, Volume 27 (2016) no. 2, pp. 585-599 | DOI

[25] Yichuan Jiang; Zhichuan Huang The rich get richer : Preferential attachment in the task allocation of cooperative networked multiagent systems with resource caching, IEEE Transactions on Systems, Man, and Cybernetics-Part A : Systems and Humans, Volume 42 (2012) no. 5, pp. 1040-1052 | DOI

[26] Yichuan Jiang; Jiuchuan Jiang Contextual resource negotiation-based task allocation and load balancing in complex software systems, IEEE Transactions on Parallel and Distributed Systems, Volume 20 (2008) no. 5, pp. 641-653 | DOI

[27] Yichuan Jiang; Zhaofeng Li Locality-sensitive task allocation and load balancing in networked multiagent systems : Talent versus centrality, Journal of Parallel and Distributed Computing, Volume 71 (2011) no. 6, pp. 822-836 | DOI | Zbl

[28] Yichuan Jiang; Yifeng Zhou; Wanyuan Wang Task allocation for undependable multiagent systems in social networks, IEEE Transactions on Parallel and Distributed Systems, Volume 24 (2012) no. 8, pp. 1671-1681 | DOI

[29] Sarit Kraus; Onn Shehory; Gilad Taase, Proc. of 2nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2003), pp. 1-8 | DOI

[30] YongChul Kwon; Magdalena Balazinska; Bill Howe; Jerome Rolia, Proc. of the SIGMOD International Conference on Management of Data (2012), pp. 25-36 | DOI

[31] YongChul Kwon; Kai Ren; Magdalena Balazinska; Bill Howe Managing Skew in Hadoop, IEEE Data Eng. Bull., Volume 36 (2013) no. 1, pp. 24-33

[32] Jan Karel Lenstra; David B. Shmoys; Eva Tardos Approximation algorithms for scheduling unrelated parallel machines, Mathematical programming, Volume 46 (1990) no. 1-3, pp. 259-271 | DOI | MR | Zbl

[33] Lightbend, Inc Akka toolkit (https://akka.io, visited 2019-12-17)

[34] Miguel Liroz-Gistau; Reza Akbarinia; Patrick Valduriez FP-Hadoop : efficient execution of parallel jobs over skewed data, VLDB Endowment, Volume 8 (2015) no. 12, pp. 1856-1859 | DOI

[35] Silvano Martello; François Soumis; Paolo Toth Exact and approximation algorithms for makespan minimization on unrelated parallel machines, Discrete applied mathematics, Volume 75 (1997) no. 2, pp. 169-188 | DOI | MR | Zbl

[36] Météo France Données SYNOP essentielles OMM, 2019 (Accessed 2019-09-01 https://donneespubliques.meteofrance.fr/?fond=produit&id_produit=90&id_rubrique=32)

[37] Ethel Mokotoff Parallel machine scheduling problems : A survey, Asia-Pacific Journal of Operational Research, Volume 18 (2001) no. 2, pp. 193-242 | MR | Zbl

[38] Satish Penmatsa; Anthony T. Chronopoulos Game-theoretic static load balancing for distributed systems, Journal of Parallel and Distributed Computing, Volume 71 (2011) no. 4, pp. 537-555 | DOI | Zbl

[39] Andrea Schaerf; Y. Shoham; Moshe Tennenholtz Adaptive Load Balancing : A Study in Multi-Agent Learning, Journal of Artificial Intelligence Research, Volume 2 (1995), pp. 475-500 | DOI | Zbl

[40] Michael Schillo; Christian Kray; Klaus Fischer, Proc. of 1st International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2002), pp. 599-606 | DOI

[41] Oguz Selvitopi; Gunduz Vehbi Demirci; Ata Turk; Cevdet Aykanat Locality-aware and load-balanced static task scheduling for MapReduce, Future Generation Computer Systems, Volume 90 (2019), pp. 49-61 | DOI

[42] Onn Shehory; Sarit Kraus Methods for task allocation via agent coalition formation, Artificial Intelligence, Volume 101 (1998) no. 1-2, pp. 165-200 | DOI | MR | Zbl

[43] Reid G. Smith The Contract Net Protocol : High-Level Communication and Control in a Distributed Problem Solver, IEEE Transactions on computers, Volume 29 (1980) no. 12, pp. 1104-1113 | DOI

[44] The Apache Software Foundation Apache Hadoop (https://hadoop.apache.org, visited 2019-07-01)

[45] Joanna Turner; Qinggang Meng; Gerald Schaefer; Andrea Soltoggio, Proc. of 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2018), pp. 739-747

[46] William E. Walsh; Michael P. Wellman, Proc. of the International Conference on Multi-Agent Systems (ICMAS) (1998), pp. 325-332 | DOI

Cité par Sources :