<figure><img src="image_1.png" /></figure>

ELLIE BEAUPREZ, ANNE-CÉCILE CARON,
MAXIME MORGE, JEAN-CHRISTOPHE ROUTIER

Négociation pour la consommation adaptative d'allocation continue
Volume 5, n° 4 (2024), p. 9-35.

https://doi.org/10.5802/roia.85

© Les auteurs, 2024.

<figure><img src="image_2.png" /></figure>

Cet article est diffusé sous la licence

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_3.png" /></figure>
# Négociation pour la consommation adaptative d'allocation continue

Ellie Beauprez<sup>a</sup>, Anne-Cécile Caron<sup>a</sup>,
Maxime Morge<sup>b</sup>, Jean-Christophe Routier<sup>a</sup>

<sup>a</sup> Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France

<sup>b</sup> Univ Lyon, UCBL, CNRS, INSA Lyon, UMR 5205 LIRIS, F-59622 Villeurbanne, France

E-mail: Ellie.Beauprez@univ-lille.fr, Anne-Cecile.Caron@univ-lille.fr, Maxime.Morge@univ-lyon1.fr, Jean-Christophe.Routier@univ-lille.fr.

RÉSUMÉ. — Nous étudions ici le problème de l'allocation continue de jobs concurrents, composés de tâches situées, sous-jacent au déploiement distribué du patron de conception MapReduce sur une gruppe de serveurs. Afin de mettre en œuvre notre stratégie multi-agents qui vise à minimiser le délai moyen de réalisation des jobs (*flowtime*), nous proposons une architecture composite d'agent qui permet la concurrence des négociations et des consommations. Nos expérimentations montrent que, lorsqu'elle est exécutée de manière concurrente au processus de consommation, notre stratégie de réallocation : (1) réduit significativement le temps de réordonnancement ; (2) améliore le délai moyen de réalisation ; (3) ne pénalise pas la consommation ; (4) est robuste aux aléas d'exécution ; et (5) s'adapte à la libération de jobs.

MORS-CLÉS. — Système multi-agents, Résolution collective de problèmes, Négociation multi-agents, Architecture d'agent.

# 1. INTRODUCTION

Les sciences des données exploitent de larges volumes de données sur lesquelles des calculs sont effectués en parallèle par différents nœuds. Ces applications mettent à l'épreuve l'informatique distribuée en ce qui concerne l'allocation de tâches et l'équilibrage de charge. C'est le cas de l'application pratique que nous considérons dans cet article : le modèle de traitement le plus répandu pour traiter des données massives sur une gruppe de serveurs, c'est-à-dire le patron de conception MapReduce [11].

Nous nous intéressons à l'allocation de plusieurs jobs concurrents, soumis au fil de l'eau par différents utilisateurs et pouvant arriver à des dates différentes. L'objectif est de minimiser le délai moyen de réalisation de ces jobs, appelée *flowtime*, qui est une mesure de la performance du système du point de vue des jobs et donc de leur commanditaire. Chaque job est composé de plusieurs tâches. Chacune des tâches, qui consiste à traiter des données, doit être assignée à un nœud de calcul chargé de son exécution. Les ressources nécessaires à l'exécution d'une tâche, c'est-à-dire les données à traiter, sont réparties éventuellement répliquées parmi les nœuds. Ces
ressources sont immédiatement accessibles pour un nœud s'il s'agit de ressources locales à ce nœud. Dans le cas contraire, les ressources restent accessibles, mais la tâche est plus onéreuse en raison du temps nécessaire pour collecter les ressources.

<figure><img src="image_4.png" /><figcaption>FIGURE 1.1 – Vue d'ensemble de l'architecture multi-agents où un agent superviseur surveille l'exécution et les échanges des tâches (rectangles) réalisés par des agents-nœuds pour lesquels les ressources (barres) éventuellement répliquées sont locales (dans l'ellipse) ou distantes.</figcaption></figure>

L'approche centrée « individus » est appropriée pour aborder des problèmes d'allocation intraitables en pratique de par la combinatoire de l'ordonnancement et dont la formulation est complexe. Le paradigme multi-agents, modulaire, décentralisé et adaptatif permet la distribution d'heuristiques qui passe à l'échelle. Intrinsèquement réactives, les méthodes multi-agents d'allocation continue s'adaptent, sans nécessiter d'apprentissage ou d'exploration préalable, aux estimations inexactes des temps d'exécution, aux perturbations (comme le ralentissement des exécutants) ainsi qu'à la consommation et la libération des tâches caractéristiques d'une allocation continue [2].

Nous proposons dans cet article un modèle multi-agents d'assignation tâches-exécutants où les nœuds de calcul sont contrôlés par des agents collaboratifs, appelés agents-nœuds, qui négocient des réallocations locales pour aboutir à une meilleure répartition des tâches (cf. figure 1.1). Ces négociations se déroulent au fil de l'exécution des tâches. Grâce à leur modèle des pairs, les agents-nœuds sont capables d'identifier des opportunités au sein de l'allocation courante pour marchander des délégations voire des échanges de tâches avec leurs semblables. Pour améliorer la réactivité (responsiveness) de la stratégie multi-agents qui repose sur l'exécution asynchrone de
comportements individuels en interaction, le processus de négociation s'appuie sur
de multiples négociations bilatérales concurrentes plutôt que sur des enchères répé-
tées synchronisées par des commissaires priseurs. Dénué de mécanismes de prise de
décision, un agent superviseur est chargé de démarrer, surveiller et d'arrêter les pro-
cessus de négociation et de consommation. Il cadence les changements de phases qui
alternent successivement à l'initiative des agents-nœuds. Après une phase de recherche
de délégations pour atteindre des allocations de qualité dans un temps raisonnable, si
les agents-nœuds détectent des minima locaux, ils déclenchent une phase de recherche
d'échanges pour s'en extraire.

Au delà de nos travaux préliminaires exposés dans [4], nos contributions sont les
suivantes.

(1) Nous introduisons un cadre formel pour l'allocation continue de tâches situées qui sont traitées progressivement et où les jobs sont soumis au fil de l'eau. De plus, nous introduisons un critère de rationalité des échanges locaux qui garantit la terminaison du processus.

(2) Nous proposons une architecture d'agent composite qui permet la co-occu-
rence du processus de réallocation avec celui de la consommation. Afin de
séparer les comportements de consommation et de négociation, chaque agent-
nœud est composé de trois sous-agents composants : le premier est dédié à la
consommation des tâches, le deuxième gère les négociations avec les pairs,
et un dernier coordonne les deux précédents.

(3) Nos expérimentations montrent que, lorsqu'elle est exécutée de manière concurrente au processus de consommation, contrairement aux méthodes d'allocation et de réallocation fondées sur des enchères [13], notre stratégie de réallocation ne pénalise pas la consommation et peut améliorer le délai moyen de réalisation jusqu'à 29 %. Le système s'adapte à la libération de jobs, et aux aléas d'exécutions (i.e. le ralentissement de nœuds), bien que les agents aient alors une connaissance imparfaite de l'environnement d'exécution.

Après un aperçu des travaux connexes dans la section 2, nous rappelons dans la
section 3 la formalisation du problème d'allocation continue de jobs composés de
tâches situées. La section 4 formalise les opérations de consommation/réallocation.
Nous décrivons ensuite, dans la section 5, comment le processus de consommation et
celui de réallocation sont entrelacés. Nous esquissons notre architecture d'agent dans
la section 6 et nous détaillons le comportement des agents-nœuds en particulier celui
de négociation dans la section 7. La section 8 analyse nos résultats expérimentaux. La
section 9 résume notre contribution et présente nos perspectives.

2. TRAVAUX CONNEXES

De nombreux travaux ont abordé le problème de la réallocation de tâches parmi
de multiples exécutants. L'approche centrée individus permet de surmonter les limites
des solutions centralisées : l'impossibilité de résoudre les problèmes à grande échelle
et la faible réactivité aux changements [2]. Les problèmes d'allocation dynamique des
tâches nécessitent notamment de proposer des processus continus qui s'ajustent en permanence aux changements de l'environnement d'exécution ou de performance des exécutants [14].

La plupart de ces travaux s'appuie sur des mécanismes d'enchère pour répartir les tâches (e.g. [13, 8, 1]). Les agents font des offres pour des tâches uniques ou des lots de tâches et les gagnants sont déterminés en fonction de la valeur des offres. Une méthode d'allocation fondée sur des enchères séquentielles à un seul article – *Sequential Single-Item (SSI) auctions*, consiste à considérer initialement les tâches comme non-allouées. Un unique commissaire-priseur annonce les tâches une par une. Les enchérisseurs émettent une offre en connaissant l'allocation des tâches précédentes. Le processus est répété jusqu'à ce que toutes les tâches soit allouées. De manière alternative, chaque exécutant enchérit sur des lots de tâches dans une enchère combinatoire à un seul tour. Toutefois, il convient de noter que, dans une telle enchère combinatoire, le calcul par les enchérisseurs de leurs offres est NP-difficile car le nombre de lots possibles est exponentiel selon le nombre de tâches. De même, le problème de détermination du gagnant est soit de taille exponentielle, soit NP-difficile. Une méthode de réallocation fondée sur des enchères parallèles à un seul article – *Parallel Single-Item (PSI) auctions* consiste à considérer autant de commissaires-priseurs que d'exécutants qui annonce le lot de tâches qu'il lui est assigné. La complexité des méthodes fondées sur SSI et PSI est polynomiale selon le nombre de tâches et d'exécutants, mais, contrairement à la méthode fondée sur PSI, celle qui s'appuie sur SSI offre des garanties sur la qualité de la solution [13].

Contrairement aux méthodes centralisées précédentes, l'algorithme à base de consensus (CBBA – *Consensus Based Bundle Algorithm*) [8] est une méthode multi-agents d'allocation en deux phases : (a) un processus d'enchère où chaque agent sélectionne les tâches sur lesquelles il souhaite placer une offre ; (b) un processus décentralisé de résolution des conflits fondé sur un consensus parmi les agents portant sur les valeurs des offres gagnantes. L'objectif consiste à minimiser le débit de réalisation (*throughput*), i.e. une mesure de la performance du système du point de vue des exécutants qui est agnostique vis-à-vis de l'ordonnancement.

Dans [1], un processus multi-enchères permet à un agent de participer à plusieurs négociations concurrentes dans le but d'améliorer le processus de réallocation des tâches. Ici, notre architecture d'agent modulaire s'inspire largement de [1]. Toutefois, nos agents ne visent pas à minimiser le *makespan* (i.e. le temps d'exécution global) mais le *flowtime*. De plus, nous avons préféré ici un protocole de négociation bilatérale qui permet, en sélectionnant l'interlocuteur, de faire des propositions ciblées et donc permet la concurrence de multiples marchangages qui améliore la réactivité (*responsiveness*) de la méthode. Finalement, la simulation de l'environnement d'exécution nous permet d'en contrôler les perturbations.

Chen et al. envisagent des problèmes d'allocation dynamique de tâches où les tâches sont libérées à des moments incertains [7]. Ils proposent d'ajuster l'allocation des tâches de façon continue en combinant le réordonnancement local des agents avec la réallocation des tâches entre agents. De manière similaire, notre stratégie multi-agents
s'appuie sur une stratégie de consommation pour définir l'ordonnancement local des tâches et sur une stratégie de négociation des tâches à réallouer. Contrairement à [7], nos agents sont susceptibles d'avoir une connaissance imparfaite de l'environnement d'exécution.

La plupart des travaux qui considèrent que les perturbations de l'environnement d'exécution font varier le coût des tâches s'appuient sur des techniques de recherche opérationnelle comme l'analyse de sensibilité pour évaluer la robustesse des optima aux perturbations [18], des méthodes incrémentales pour réparer l'allocation optimale initiale lorsque les coûts changent [17] ou l'optimisation combinatoire pour exploiter les mesures de dégradation [16]. De manière similaire, notre stratégie mesure notamment l'écart entre les progrès attendus et ceux observés en vue de modifier l'allocation. Toutefois, notre approche centrée individus permet de résoudre des problèmes à grande échelle.

Creech et al. aborde le problème de l'allocation des ressources et de la hiérarchisation des tâches dans les systèmes multi-agents distribués pour des environnements dynamiques [9]. Ils proposent un algorithme d'optimisation de l'allocation des ressources multi-groupes (MG-RAO) qui combine des algorithmes de mise à jour et de priorisation et qui utilise des techniques d'apprentissage par renforcement. À l'inverse des techniques d'apprentissage, notre solution ne nécessite aucun modèle préalable, ni des données, ni de l'environnement, et aucune phase d'exploration car cela ne serait pas pertinent pour l'application pratique qui nous concerne. En effet, le volume de données rend les pré-traitements et l'exploration trop coûteux. De plus, la variabilité des données les rend rapidement obsolètes.

Nos précédentes expérimentations ont montré que la durée moyenne de réalisation atteinte par notre stratégie est meilleure que celle obtenue avec les techniques d'optimisation sous contraintes distribuée (DCOP) et reste proche de celle obtenue avec une heuristique classique, avec dans tous les cas un temps de réordonnancement significativement réduit [5]. Nous montrons dans cet article comment déployer cette stratégie de manière continue au cours du processus de consommation.

## 3. PROBLÈME

Cette section présente la formalisation du problème d'allocation continue de jobs concurrents composés de tâches situées. Nous considérons ici un problème dynamique où les tâches sont peu à peu consommées et les jobs sont soumis au fil de l'eau.

Un système distribué est composé d'un ensemble de nœuds de calcul capables d'exécuter des tâches. Ces tâches requièrent des ressources, transférables et non consommables, réparties parmi différents nœuds de ressources.

**DÉFINITION 3.1 (Système distribué).** — *Un système distribué est un quadruplet* $\mathcal{D} = (\mathcal{P}, \mathcal{N}_r, \mathcal{E}, \mathcal{R})$ où :

* $\mathcal{P}$ est un ensemble de p nœuds de calcul;

* $\mathcal{N}_r$ est un ensemble de r nœuds de ressource;
• $\mathcal{E} : \mathcal{P} \times \mathcal{N}_r \rightarrow \{\top, \bot\}$ est une propriété de voisinage qui évalue si un nœud de calcul de l'ensemble $\mathcal{P}$ est local à un nœud de ressource dans $\mathcal{N}_r$;

• $\mathcal{R} = \{\rho_1, \dots, \rho_k\}$ est un ensemble de ressources ayant des tailles $|\rho_i|$. La localisation des ressources, qui sont éventuellement répliquées, est déterminée par la fonction :

$$l : \mathcal{R} \rightarrow 2^{\mathcal{N}_r} \qquad (3.1)$$

Une ressource peut être locale ou distante d'un nœud de calcul, selon sa présence ou non sur un nœud de ressource dans le voisinage du nœud de calcul. À partir des fonctions $\mathcal{E}$ et $l$, nous définissons le prédicat de localité :

$$\forall v_c \in \mathcal{P}, \forall \rho \in \mathcal{R}, \text{ local}(\rho, v_c) \text{ ssi } \exists v_r \in l(\rho) \text{ t.q. } \mathcal{E}(v_c, v_r) \qquad (3.2)$$

Les ressources sont accessibles pour tous les nœuds de calcul, même celles sur les nœuds de ressource distants.

Libérés au cours temps, les jobs sont des ensembles de tâches sans date butoir, indépendantes, non divisibles et non-préemptables. L'exécution de chaque tâche nécessite l'accès à des ressources distribuées sur les nœuds du système. L'exécution d'un job consiste à exécuter l'ensemble de ses tâches pour produire un résultat.

**DÉFinition 3.2 (Job/Tâche).** — Soit $\mathcal{D}$ un système distribué. On considère un ensemble de $l$ jobs $\mathcal{J} = \{J_1, \dots, J_l\}$. Chaque job $J_i \in \mathcal{J}$, associé à la date de libération $t_{j_i}^0$, est un ensemble non vide de $k_i$ tâches $J_i = \{\tau_1, \dots, \tau_{k_i}\}$. On note $\mathcal{T} = \bigcup_{1 \le i \le l} J_i$ l'ensemble des n tâches sous-jacentes à $\mathcal{J}$.

Comme les jobs sont libérés à des dates différentes, on peut s'intéresser aux jobs libérés avant un temps donné $t$. Ainsi, $\mathcal{J}_t$ est l'ensemble des $l_t$ jobs libérés avant l'instant $t$ ($\forall J \in \mathcal{J}_t$, $t_j^0 \le t$) et $\mathcal{T}_t$ est l'ensemble des tâches sous-jacentes à $\mathcal{J}_t$. $\mathcal{R}_\tau \subseteq \mathcal{R}$ dénote l'ensemble des ressources requises pour la tâche $\tau$. Par souci de concision, on note job($\tau$) le job contenant la tâche $\tau$. Nous faisons l'hypothèse que le nombre de jobs est négligeable par rapport au nombre de tâches, $|\mathcal{J}| \ll |\mathcal{T}|$.

Le coût d'une tâche pour un nœud $v_i$ est une estimation a priori de son temps d'exécution.

**DÉFinition 3.3 (Coût d'une tâche pour un nœud).** — Soient $\mathcal{D}$ un système distribué et $\mathcal{T}$ un ensemble de tâches. La fonction de coût $c : \mathcal{T} \times \mathcal{N} \mapsto \mathbb{R}_+^*$ est telle que :

$$c(\tau, v_j) = \sum_{\rho_j \in \mathcal{R}_\tau} c(\rho_j, v_j) \\ \text{avec } c(\rho_j, v_i) = \begin{cases} |\rho_j| & \text{si local}(\rho_j, v_i) \\ \kappa \times |\rho_j| & \text{avec } \kappa > 1 \text{ sinon.} \end{cases} \qquad (3.3)$$

Comme la collecte de ressources distantes représente un surcoût, une tâche est plus coûteuse si les ressources nécessaires sont « moins locales ». La valeur de $\kappa$ sera discutée dans la section 8.

La fonction de coût peut être étendue à un ensemble de tâches :

$$\forall T \subseteq \mathcal{T}, c(T, v_i) = \sum_{\tau \in T} c(\tau, v_i) \qquad (3.4)$$
En substance, nous considérons le problème d'allocation continue de jobs composés de tâches situées.

**DÉFinition 3.4 (STAP).** — *Un problème d'allocation continue de tâches situées à l'instant $t$ est un quadruplet STAP = $\langle \mathcal{D}, \mathcal{T}_t, \mathcal{J}_t, c \rangle$ où :*

* $\mathcal{D}$ est un système distribué de m nœuds;

* $\mathcal{T}_t = \{\tau_1, \dots, \tau_n\}$ est un ensemble de n tâches;

* $\mathcal{J}_t = \{J_1, \dots, J_{\ell_t}\}$ est un partitionnement des tâches en $\ell_t$ jobs;

* $c: \mathcal{T}_t \times \mathcal{N} \to \mathbb{R}_+^*$ est la fonction de coût.

Une allocation de tâches est une répartition des tâches des jobs libérés dans des lots ordonnés.

**DÉFinition 3.5 (Allocation).** — *Une allocation pour un problème STAP à l'instant $t$ est un vecteur de m lots de tâches ordonnées $\vec{A}_t = ((B_{1,t}, <_1), \dots, (B_{m,t}, <_m))$ où chaque lot $(B_{i,t}, <_i)$ est l'ensemble des tâches $(B_{i,t} \subseteq \mathcal{T}_t)$ affectées au nœud $v_i$ à l'instant $t$, associé à un ordre total strict $(<_i \subseteq \mathcal{T}_t \times \mathcal{T}_t)$. $\tau_j <_i \tau_k$ signifie que si $\tau_j, \tau_k \in B_{i,t}$ alors $\tau_j$ est exécutée avant $\tau_k$ par $v_i$. L'allocation $\vec{A}_t$ vérifie pour l'instant $t$ :*

$$ \forall \tau \in \mathcal{T}_t, \exists v_i \in \mathcal{N}, \tau \in B_{i,t} \qquad (3.5) $$

$$ \forall v_i \in \mathcal{N}, \forall v_j \in \mathcal{N} \setminus \{v_i\}, B_{i,t} \cap B_{j,t} = \emptyset \qquad (3.6) $$

Toutes les tâches des jobs libérés sont allouées (3.5) et chacune n'est allouée qu'à un seul nœud (3.6). Par souci de concision, on note :

* $\vec{B}_{i,t} = (B_{i,t} <_i)$, le lot trié de $v_i$;

* $\min_{<_i} B_{i,t}$, la prochaine tâche à exécuter par $v_i$.

Pour évaluer la qualité d'une allocation de tâches, nous considérons le délai moyen de réalisation (*flowtime*), qui mesure le temps moyen écoulé entre la date de libération des jobs et leur date d'achèvement.

**DÉFinition 3.6 (Flowtime).** — *Soient STAP un problème et $\vec{A}_t$ une allocation à l'instant $t$. On définit :*

* le délai d'attente d'une tâche $\tau \in \mathcal{T}_t$ dans le lot $\vec{B}_{i,t}$,

$$ \Delta(\tau, v_i) = \sum_{\tau' \in B_{i,t} | \tau' <_i \tau} c(\tau', v_i) \qquad (3.7) $$

* la durée de réalisation d'une tâche $\tau \in \mathcal{T}_t$ pour l'allocation $\vec{A}_t$,

$$ C_{\tau}(\vec{A}_{t}) = \Delta(\tau, v(\tau, \vec{A}_{t})) + t - t_{\text{job}}^{0}(\tau) + c(\tau, v(\tau, \vec{A}_{t})) \qquad (3.8) $$

* la durée de réalisation d'un job $J \in \mathcal{J}_t$ pour $\vec{A}_t$,

$$ C_J(\vec{A}_t) = \max_{\tau \in J} \{C_{\tau}(\vec{A}_t)\} \qquad (3.9) $$
* le délai moyen de réalisation des jobs libérés $\mathcal{J}_t$ pour $\vec{A}_t$,

$$C_{\text{mean}}(\vec{A}_t) = \frac{1}{\ell_t} C(\vec{A}_t) \quad \text{avec} \quad C(\vec{A}_t) = \sum_{J \in \mathcal{J}_t} C_J(\vec{A}_t) \quad (3.10)$$

Plus particulièrement le délai d'attente (3.7) correspond au délai d'attente à partir de l'instant courant $t$ avant que la tâche $\tau$ ne soit traitée. Il est à noter que les temps de réalisation, et par conséquent le flowtime, dépendent de l'ordre d'exécution des tâches sur chacun des nœuds.

## 4. OPÉRATIONS

Nous formalisons ici les opérations locales de transformation des allocations : les consommations et les reallocations de tâches. Ces opérations élémentaires sont combinées dans des processus distribués et concurrents : le processus de consommation et le processus de réallocation.

La **consommation** d'une tâche par un nœud consiste pour ce dernier à retirer cette tâche de son lot pour l'exécuter. Cette opération mène à une nouvelle instance de problème où cette tâche a été retirée. En d'autres termes, l'accomplissement d'une tâche est un évènement disruptif qui modifie non seulement l'allocation des tâches mais également le problème sous-jacent.

**DÉFinition 4.1 (Consommation de tâche).** — Soient STAP = $\langle \mathcal{D}, \mathcal{T}_t, \mathcal{J}_t, c \rangle$ un problème d'allocation continue de tâches et $\vec{A}_t$ une allocation à l'instant $t$. La consommation par un nœud consommateur $v_i$ dont le lot n'est pas vide ($B_{i,t} \neq \emptyset$), aboutit à l'allocation $\vec{A}_t' = \lambda(v_i, \vec{B}_{i,t})$ pour le problème STAP' = $\langle \mathcal{D}, \mathcal{T}'_t, \mathcal{J}'_t, c \rangle$ où :

$$\mathcal{T}'_t = \mathcal{T}_t \setminus \{\min_{<i} B_{i,t}\} \quad (4.1)$$

$$\mathcal{J}'_t = \begin{cases} \mathcal{J}_t \setminus \{\text{job}(\min_{<i} B_{i,t})\} & \text{si } \text{job}(\min_{<i} B_{i,t}) = \{\min_{<i} B_{i,t}\} \\ \mathcal{J}_t & \text{sinon} \end{cases} \quad (4.2)$$

Dans ce dernier cas :

$$\forall J_j \in \mathcal{J} \exists J'_j \in \mathcal{J}' \ t.q. J'_j = \begin{cases} J_j \setminus \{\min_{<i} B_{i,t}\} & \text{si } \text{job}(\min_{<i} B_{i,t}) = J_j \\ J_j & \text{sinon} \end{cases} \quad (4.3)$$

et $\vec{A}_t' = (\vec{B}_{1,t}', \dots, \vec{B}_{m,t}')$ avec

$$\vec{B}_{j,t}' = \begin{cases} \overrightarrow{B_{i,t}} \ominus \min_{<i} \vec{B}_{i,t} & \text{si } j = i \\ \overrightarrow{B_{j,t}} & \text{sinon} \end{cases} \quad (4.4)$$

Lorsqu'une tâche est consommée, elle est retirée du problème résultant non seulement dans l'ensemble des tâches mais également du job correspondant. Ce dernier peut également être retiré si la tâche était la seule (la dernière) du job. L'allocation résultante est également modifiée. La tâche est retirée du lot où elle se trouvait. Les tâches sont destinées à être consommées une à une jusqu'à atteindre l'allocation vide.
En théorie, la consommation d'une tâche ne peut augmenter le flowtime. En effet, la consommation d'une tâche fait décroître localement le flowtime, à l'instant $t$,

$$ \Sigma_{J \in \mathcal{J}_t} C_J(\lambda(\nu_i, \vec{B}_{i,t})) < \Sigma_{J \in \mathcal{J}_t} C_J(\vec{B}_{i,t}) \quad (4.5) $$

Cela n'est cependant pas toujours vrai en pratique. En effet, comme nous le verrons dans la section 8, les coûts effectifs des tâches peuvent être différents des coûts estimés (cf. définition 3.3). Si une tâche s'avère plus coûteuse que prévu lors de son exécution, le flowtime peut augmenter après sa consommation, comme dans l'exemple 4.2.

**Exemple 4.2.** — Soit le problème STAP = $\langle \mathcal{D}, \mathcal{F}_t, \mathcal{J}_t, c \rangle$ avec :

* $\mathcal{D} = \langle \mathcal{P}, \mathcal{N}_r, \mathcal{E}, \mathcal{R} \rangle$, un système distribué avec un unique nœud de calcul $\mathcal{P} = \{v_1\}$ associé au seul nœud de ressource $\mathcal{N}_r = \{v_1^r\}$, tel que $\mathcal{E}(v_1, v_1^r) = \top$ et une unique ressource $\mathcal{R} = \{\rho_1\}$ sur le nœud de ressource $v_1^r$;

* deux tâches $\mathcal{J}_t = \{\tau_1, \tau_2\}$;

* un unique job $\mathcal{J}_t = \{J_1\}$ libéré à $t_{J_1}^0 = 0$ composé des deux tâches $J_1 = \{\tau_1, \tau_2\}$;

* la fonction de coût $c$ telle que $c(\tau_1, v_1) = 2$ et $c(\tau_2, v_1) = 4$.

L'allocation $\vec{A}_0 = (\vec{B}_{1,t})$ avec $\vec{B}_{1,t} = (\tau_1, \tau_2)$. Selon l'équation 3.10, le flowtime est $C_{\text{mean}}(\vec{A}_0) = C_{J_1}(\vec{A}_0) = C_{\tau_2}(\vec{A}_0) = \Delta(\tau_2, v_1) + t + t_{J_1}^0 + c(\tau_2, v_1) = c(\tau_1, \vec{A}_t) + 0 + 0 + c(\tau_2, v_1) = 2 + 4 = 6$.

Si la consommation de $\tau_1$ se termine à l'instant $t_1 = 3$, cela signifie que cette tâche s'avère plus coûteuse que prévu lors de son exécution. Par conséquence, le flowtime de $\vec{A}_{t_1} = (\vec{B}_{v_1,t_1})$ avec $\vec{B}_{v_1,t_1} = (\tau_2)$ est $C_{\text{mean}}(\vec{A}_{t_1}) = C_{J_1}(\vec{A}_{t_1}) = t_1 + t_{J_1}^0 + c(\tau_2, v_1) = 3 + 0 + 4 = 7 > C_{\text{mean}}(\vec{A}_0)$.

Une **réallocation bilatérale** est une opération élémentaire lors de laquelle une ou plusieurs tâches sont déplacées. Elle consiste en un échange local de tâches entre deux exécutants.

**DÉFinition 4.3 (Réallocation bilatérale).** — Soit $\vec{A}_t = (\vec{B}_{1,t}, \dots, \vec{B}_{m,t})$ une allocation pour le problème STAP = $\langle \mathcal{D}, \mathcal{F}_t, \mathcal{J}_t, c \rangle$ à l'instant $t$. La **réallocation bilatérale** de la liste non vide de tâches $T_1$ allouées au proposant $v_i$ en échange de la liste de tâches $T_2$ allouées au répondant $v_j$ dans $\vec{A}_t$ ($T_1 \subseteq B_{i,t}$ et $T_2 \subseteq B_{j,t}$) aboutit à l'allocation $\gamma(T_1, T_2, v_i, v_j, \vec{A}_t)$ avec les m lots $\gamma(T_1, T_2, v_i, v_j, \vec{B}_{k,t})$ définis tels que :

$$ \gamma(T_1, T_2, v_i, v_j, \vec{B}_{k,t}) = \begin{cases} \overrightarrow{B_{i,t}} \oplus T_1 \oplus \overrightarrow{T_2} & \text{si } k = i, \\ \overrightarrow{B_{j,t}} \oplus T_2 \oplus \overrightarrow{T_1} & \text{si } k = j, \\ \overrightarrow{B_{k,t}} & \text{sinon} \end{cases} \quad (4.6) $$

Si $T_2$ est vide, on parle de délégation. Sinon, une **réallocation bilatérale** est un échange de tâches.

Comme nous privilégions un protocole de négociation bilatérale plutôt qu'un protocole d'enchère, nous nous restreignons ici aux échanges bilatéraux et nous excluons les
réallocations multilatérales. Par la suite, $\delta(\tau, v_i, v_j, \vec{A}_t)$ et $\sigma(\tau_1, \tau_2, v_i, v_j, \vec{A}_t)$ dénotent respectivement une délégation unaire et un échange unaire.

Contrairement à la plupart des autres travaux (e.g. [10]), nos agents ne sont pas individuellement rationnels mais ils ont un but commun qui prime sur leur intérêt individuel : réduire le flowtime de l'allocation courante.

**DÉFINITION 4.4** (Réallocation bilatérale socialement rationnelle). — Soit $\vec{A}_t$ une allocation pour le problème STAP = $\langle \mathcal{D}, \mathcal{T}_t, \mathcal{J}_t, c \rangle$ à l'instant t. La réallocation bilatérale $\gamma(T_1, T_2, v_i, v_j, \vec{A}_t)$ est socialement rationnelle si et seulement si cette réallocation fait décroître le flowtime,

$$C(\gamma(T_1, T_2, v_i, v_j, \vec{A}_t)) < C(\vec{A}_t) \quad (4.7)$$

Une allocation est dite **stable** s'il n'existe aucune réallocation bilatérale socialement rationnelle. Dans [5], nous avons démontré la terminaison du processus qui itère ce type de réallocations. La preuve est identique à celles dans [12, 1].

# 5. PROCESSUS

Afin d'exécuter de manière concurrente le processus de consommation et celui de réallocation, nous considérons deux types d'agents : (a) les agents-nœud, chacun d'entre eux représentant un nœud de calcul en gérant son lot de tâches (cf. section 6); (b) le superviseur qui synchronise les phases du processus de négociation.

Le processus de consommation se résume à l'exécution concurrente ou séquentielle des différentes tâches par les nœuds de calcul sous la supervision de leur agent. Le processus de réallocation est constitué de multiples reallocations locales qui sont le résultat de négociations bilatérales entre agents-nœud, réalisées de manière séquentielle ou concurrente. Ces processus sont complémentaires. Tandis que les consommations se déroulent au fur et à mesure, les agents négocient leurs lots de tâches jusqu'à atteindre une allocation stable. La consommation d'une tâche peut rendre instable une allocation et ainsi déclencher de nouvelles négociations. Le processus de consommation se termine quand toutes les tâches sont exécutées. L'allocation finale, qui est vide, met un terme au processus.

Il est important de noter que ce système multi-agents est intrinsèquement adaptatif. En effet, si le coût d'une tâche s'avère plus élevé que prévu, parce que le temps d'exécution a été sous-estimé ou parce que le nœud l'exécutant est ralenti, alors le processus de réallocation qui se déroule permet progressivement de corriger l'allocation en prenant en compte le temps effectivement mesuré après la réalisation des tâches.

**La stratégie de consommation** des agents, détaillée dans [3], spécifie l'ordonnancement des tâches, au sein du lot de tâches, pour leur exécution par le nœud dont ils ont la charge. Afin de réduire la durée de réalisation des jobs, cette stratégie exécute les tâches des jobs les moins coûteux avant celles des jobs les plus coûteux.
La **stratégie de négociation** des agents-nœud, détaillée dans [5], s'appuie sur un modèle des pairs, notamment une base de croyances, construit à partir des messages échangés et grâce auquel elle détermine si une réallocation est socialement rationnelle, selon les croyances de l'agent. Les agents disposent : (a) d'une stratégie d'offre qui propose des reallocations bilatérales ; (b) d'une stratégie d'acceptabilité qui évalue si toute ou partie d'une proposition reçue est ou non socialement rationnelle avant de l'accepter ou de la refuser ; et (c) d'une stratégie de contre-offre qui sélectionne une contre-partie à une délégation afin de proposer un échange de tâches.

Le processus de négociation se décompose en deux phases successives : (1) les agents proposent des délégations qu'ils croient socialement rationnelles et qui sont acceptées ou refusées par leurs pairs ; (2) les agents proposent des délégations qui ne sont pas nécessairement socialement rationnelles mais qui sont susceptibles de déclencher des contre-offres et ainsi des échanges socialement rationnels. Ces phases alternent jusqu'à la fin du processus, c'est-à-dire lorsque toutes les tâches ont été consommées, comme illustré sur la figure 5.1. Tant que l'un des agents-nœuds a encore des tâches à consommer, le superviseur re-déclenche la première phase à l'issue de la deuxième phase. Quand il est informé qu'aucun agent-nœud ne détecte d'opportunité de réallocation, le superviseur enclenche le changement de phase de négociation. Il collecte les métriques nécessaire à la surveillance (*monitoring*) et à l'évaluation empirique de la stratégie multi-agents (cf. section 8) puis stoppe le processus lorsque toutes les tâches ont été consommées.

<figure><img src="image_5.png" /><figcaption>FIGURE 5.1 – Comportement global du système cadencé par le superviseur</figcaption></figure>

# 6. ARCHITECTURE

Pour concevoir un agent-nœud, nous avons adopté une architecture modulaire qui permet la concurrence des négociations et des consommations.

Un agent-nœud est un agent composite constitué de trois agents composants (cf. figure 6.1), chacun ayant un rôle limité :

* l'exécutant consomme les tâches;

* le négociateur s'appuie sur un modèle des pairs pour négocier des tâches;
* le gestionnaire gère le lot de tâches du nœud de calcul en y ajoutant ou supprimant les tâches selon les réallocations bilatérales marchandées par le négociateur. La stratégie de consommation détermine dans quel ordre il va confier les tâches à l'exécutant pour leur consommation.

Afin de prioriser la consommation des tâches, le gestionnaire, dès qu'il est informé que l'exécutant est libre, fournit à ce dernier la prochaine tâche à exécuter, quitte à annuler la réallocation de cette tâche en cours de négociation. Cette tâche n'est alors plus éligible pour une potentielle réallocation. À la différence de l'architecture proposée dans [1], le modèle des pairs (y compris de lui-même) n'est pas associé au gestionnaire mais au négociateur pour qu'il soit autonome vis-à-vis du gestionnaire dans la conduite de l'ensemble des fils de négociations bilatérales.

<figure><img src="image_6.png" /><figcaption>FIGURE 6.1 – Architecture composite d'un agent-nœud qui sert d'interface entre ses agents composants et les agents composants des autres nœuds et d'intermédiaire avec l'agent superviseur</figcaption></figure>

Nous représentons ici les interactions entre les agents composants sous la forme de diagrammes d'interaction où les flèches pleines représentent des appels synchrones (comme dans la figure 6.2b), les flèches ouvertes des messages asynchrones (comme dans la figure 6.2a) et les lignes pointillées des messages de réponse.

Après que le gestionnaire a confié à l'exécutant une tâche, ce dernier signale au gestionnaire quand elle est accomplie (cf. figure 6.2a). Pour prioriser la consommation plutôt que la négociation, la demande de la prochaine tâche à accomplir par l'exécutant au gestionnaire est prioritaire et préempte les interactions de ce dernier avec le négociateur. Pour raffiner son estimation du délai d'attente des tâches dans son lot, le gestionnaire peut demander à l'exécutant une estimation du temps d'exécution restant pour la tâche en cours – QRC(task), Query Remaining Cost (cf. figure 6.2b).
<figure><img src="image_7.png" /><figcaption>FIGURE 6.2 – Interactions entre le gestionnaire et l'exécutant</figcaption></figure>

Les interactions entre le gestionnaire et le négociateur lors de la première phase de négociation dédiée aux délégations, sont représentées sur la figure 6.3 dans le cas d'une délégation unaire. Pour opérer une réallocation bilatérale, le négociateur demande de façon synchrone à son gestionnaire de mettre à jour le lot de tâches afin de retirer ou d'ajouter les tâches réallouées. La réponse du gestionnaire lui permet de mettre à jour son modèle des pairs pour pouvoir confirmer la transaction et s'engager

<figure><img src="image_8.png" /><figcaption>FIGURE 6.3 – Interactions entre le gestionnaire et le négociateur lors de la première phase de négociation pour la délégation d'une unique tâche. Les étiquettes QRC font référence à l'interaction de la figure 6.2b</figcaption></figure>
plus tard dans de nouvelles négociations. Lorsqu'il met à jour le lot de tâches, le gestionnaire demande de manière synchrone à l'exécutant le temps estimé restant pour la tâche en cours d'exécution afin d'avoir une estimation plus fine du délai d'attente des tâches du lot. Le gestionnaire peut donc ensuite répondre au négociateur pour lui transmettre les nouveaux coûts estimés des jobs pour le lot de tâches à l'aide d'un message GiveUpdatedBundle.

Lors d'une seconde phase de négociation, les agents marchandent des échanges de tâches. Les interactions entre le gestionnaire et le négociateur, représentées sur la figure 6.4 sont similaires à celles dans le cas des délégations. Toutefois, la concurrence

<figure><img src="image_9.png" /><figcaption>FIGURE 6.4 – Interactions entre le gestionnaire et le négociateur lors de la deuxième phase de négociation. Dans le cas où le répondant n'identifie pas d'échange socialement rationnel, les interactions sont les mêmes que dans le cas des délégations</figcaption></figure>
du processus de réallocation avec le processus de consommation nécessite la mise en œuvre d'un double acquittement. Quand la réallocation est un échange, elle doit être non seulement confirmée par le proposant pour garantir la disponibilité de la tâche à déléguer mais également par le répondant pour garantir la disponibilité de la contre-partie.

## 7. COMPORTEMENTS

Notre modèle de comportement d'agent est une machine à états finis où chaque transition est étiquetée par l'événement qui la déclenche, par exemple la réception d'un message, et par les actions qu'elle amorce comme l'émission d'une réponse ou la mise à jour de l'état mental de l'agent. L'implémentation du prototype dans [6] est la directe mise en œuvre de la spécification sous la forme d'automates<sup>(1)</sup>

L'exécutant est soit disponible lorsqu'il attend de recevoir une tâche à consommer, soit en train d'exécuter une tâche et il peut alors estimer le temps d'exécution restant pour la tâche en cours.

Le gestionnaire gère le lot de tâches et coordonne les opérations de consommation des tâches réalisées par l'exécutant avec celles de réallocations marchandées par le négociateur. Quand ce dernier lui signale qu'il n'a plus de délégation socialement rationnelle à proposer et qu'il attend les propositions des autres agents-nœuds, le gestionnaire en informe le superviseur. Il continue également à confier à l'exécutant des tâches à réaliser jusqu'à ce que son lot soit vide. Informé qu'aucun agent-nœud ne détecte d'opportunité de réallocation, le superviseur enclenche le changement de phase de négociation. Enfin, le superviseur clôt le processus quand il apprend par les gestionnaires que toutes les tâches ont été consommées.

Le négociateur répond aux propositions et met à jour son modèle des pairs, ce qui lui permet de détecter des opportunités de réallocation. Conformément aux diagrammes d'interactions 6.3 et 6.4, après avoir proposé une délégation, il attend, avant une date butoir, une acceptation, un refus ou une contre-proposition. L'essentiel du comportement du négociateur, noté $v_i$, est représenté de manière simplifiée dans la figure 7.1.

Dans l'état Répondant, le négociateur peut se mettre lui-même en recherche d'une offre à proposer ($v_i$ ! Next), ou répondre aux propositions des pairs. Lors de la réception d'un message Next, si sa stratégie d'offre ne donne pas de résultat ($O_i = \emptyset$), il passe dans l'état Pause en s'envoyant un message Close. Si une offre est trouvée, il l'envoie au pair concerné (recipient($O_i$) ! Propose($O_i$)) et passe dans l'état Proposant. Lorsqu'il reçoit une proposition ($v_j$: Propose($\delta(\tau, v_j, v_i, \vec{A}_t)$)) qui est acceptable ou pour laquelle une contre-offre est possible, il passe dans l'état Contractant, et répond en conséquence ($v_j$ ! Accept($\delta(\tau, v_j, v_i, \vec{A}_t)$) ou $v_j$ ! CounterPropose($O_i(v_j, \tau)$)). Dans le cas contraire, il refuse l'offre ($v_j$ ! Reject($\delta(\tau, v_j, v_i, \vec{A}_t)$)) et cherche de nouvelles opportunités ($v_i$ ! Next).

<footnote><sup>(1)</sup>https://gitlab.univ-lille.fr/maxime.morge/smastaplus/-/tree/master/doc/specification.</footnote>
<figure><img src="image_10.png" /><figcaption>FIGURE 7.1 – Comportement simplifié du négociateur</figcaption></figure>
Dans l'état **Contractant**, le négociateur attend la confirmation d'une transaction qu'il a acceptée ou pour laquelle il a proposé une contre-offre. Lorsqu'il reçoit la confirmation d'une délégation ($v_j:Confirm(\delta(\tau, v_j, v_i, \vec{A}_t))$), il demande au gestionnaire d'ajouter la tâche au lot (**manager?Add(\tau)**). Lorsqu'il reçoit la confirmation d'un échange toujours valide ($v_j:ConfirmSwap(\sigma(\tau, \tau_{swap}, v_j, v_i, \vec{A}_t))$), il demande au gestionnaire de remplacer la tâche déléguée par sa contrepartie (**manager?Replace(\tau_{swap}, \tau)**) et répond à son tour par un message **ConfirmSwap**. Si l'échange n'est plus valide, il répond par un message **WithdrawSwap**. Dans tous ces cas de figure, le négociateur retourne ensuite dans l'état **Répondant**.

Dans l'état **Proposant**, si le négociateur reçoit une acceptation ($v_j:Accept(\delta(\tau, v_i, v_j, \vec{A}_t))$) pour une offre toujours valide, il demande au gestionnaire de retirer la tâches cédée (**manager?Remove(\tau)**) et confirme la délégation auprès du receveur ($v_j!Confirm(\delta(\tau, v_i, v_j, \vec{A}_t))$). S'il reçoit une acceptation ou une contreproposition pour une offre qui n'est plus valide (i.e. la tâche a été confiée à l'exécutant pour consommation), il répond par une annulation ($v_j!Withdraw(\delta(\tau, v_i, v_j, \vec{A}_t))$). Dans ces deux cas, ainsi que lors de la réception d'un refus d'une offre ($v_j:Reject(O_i)$), le négociateur retourne ensuite dans l'état **Répondant**. Lors de la réception d'une contre-proposition acceptable pour une offre toujours valide, le négociateur demande au gestionnaire de retirer du lot la tâche cédée et répond à son pair par un message **ConfirmSwap** avant de passer dans l'état **Troqueur**.

Dans l'état **Troqueur**, le négociateur attend de recevoir la confirmation ou l'annulation d'un échange en cours. S'il reçoit une confirmation ($v_j:ConfirmSwap(\sigma(\tau, \tau_{swap}, v_j, v_i, \vec{A}_t))$), il demande au gestionnaire d'ajouter dans le lot la tâche reçue (**manager ? Add(\tau)**). S'il reçoit une annulation ($v_j:WithdrawSwap(\sigma(\tau, \tau_{swap}, v_j, v_i, \vec{A}_t))$), le négociateur demande au gestionnaire de remettre dans le lot la tâche précédemment retirée. Dans les deux cas, le gestionnaire retourne dans l'état **Répondant**.

## 8. EXPÉRIMENTATIONS

Nos expériences visent à valider que, lorsqu'elle est exécutée de manière concurrente au processus de consommation, la stratégie de réallocation : (1) réduit significativement le temps de réordonnancement ; (2) améliore le *flowtime* ; (3) ne pénalise pas la consommation ; (4) est robuste aux aléas d'exécution (i.e. le ralentissement de nœuds) ; et (5) s'adapte à la libération de jobs. Nous présentons ici nos méthodes de référence, nos métriques, notre protocole expérimental et nos résultats$^{(2)}$.

Nous considérons ici le processus de réalisation des tâches où notre stratégie de consommation spécifie leurs ordonnancements au sein du lot de chaque nœud (cf. section 5). Afin de comparer notre stratégie de réallocation exécutée manière concurrente à ce processus de consommation, nous considérons :

<footnote>$^{(2)}$Ces expérimentations sont reproductibles à partir des instructions suivantes : https://gitlab.univ-lille.fr/maxime.morge/smastaplus/-/tree/master/doc/experiments</footnote>
* une méthode d'allocation fondée sur des enchères séquentielles à un seul article (ASSI), où une offre correspond au *flowtime* si la tâche est attribuée à l'enchérisseur. Le processus d'allocation précède le processus de consommation. Lors de la libération de nouveaux jobs, les tâches supplémentaires sont affectées de la même manière;

* une méthode de réallocation fondée sur des enchères séquentielles à un seul article (RSSI) exécutée de manière concurrente au processus de consommation où les agent-nœuds, chacun à leur tour, proposent de déléguer une de leurs tâches en attente. Lors de la libération de nouveaux jobs, les tâches supplémentaires sont réaffectées de la même manière.

Nos expérimentations sont réalisées en simulant la consommation des tâches. C'est pourquoi, pour définir nos métriques, plutôt que le temps estimé d'exécution des tâches par les nœuds (cf. définition 3.3), nous considérons le **coût simulé** $c^S(\tau, v)$ comme le temps que l'exécutant du nœud $v_i$ consacre à la tâche $\tau$ :

* avec une connaissance parfaite de l'environnement d'exécution,

$$c^{SE}(\tau, v_i) = c(\tau, v_i) \qquad (8.1)$$

* avec le ralentissement de la moitié des nœuds,

$$c^{SH}(\tau, v_i) = \begin{cases} 2 \times c(\tau, v_i) & \text{si } i \bmod 2 = 1 \\ c(\tau, v_i) & \text{sinon.} \end{cases} \qquad (8.2)$$

C'est pourquoi nous distinguons :

* le *flowtime simulé* $C_{\text{mean}}^{S}(\vec{A}_t)$ calculé à partir d'une allocation $\vec{A}_t$ selon les coûts simulés;

* le *flowtime réalisé* $C_{\text{mean}}^{R}(\vec{A}_t)$ calculé à partir des temps de réalisation des tâches effectivement mesurés.

On définit le taux d'amélioration de performance :

$$\Gamma = \frac{C_{\text{mean}}^{R}(\vec{A}_0) - C_{\text{mean}}^{R}(\vec{A}_e)}{C_{\text{mean}}^{R}(\vec{A}_0)} \qquad (8.3)$$

où $\vec{A}_e$ est l'allocation des tâches au moment de leur exécution et $\vec{A}_0$ est l'allocation initiale. Il est à noter que si aucune réallocation n'a lieu pendant le processus, $\vec{A}_e = \vec{A}_0$. Le taux d'amélioration est positif si le *flowtime réalisé* de l'allocation atteinte par le processus de réallocation est meilleur (c'est-à-dire plus faible) que celui de l'allocation initiale. À ces métriques, s'ajoutent le temps de réordonnancement, le taux de disponibilité locale qui mesure la proportion des ressources traitées localement, le nombre de tâches déjà réalisées par le processus de consommation et le nombre de tâches déjà déléguées pour un processus de réallocation, que cela soit RSSI ou notre propre stratégie.
Notre prototype SMASTA+ [6] est implémenté avec le langage de programmation Scala et la bibliothèque Akka [15] adaptée aux applications orientées messages, fortement concurrentes, distribuées et robustes. Les expériences ont été réalisées sur une lame munie de 20 CPUs avec 512Go de RAM. Nous avons fixé empiriquement $\kappa = 2$ comme une valeur réaliste pour capturer le surcoût induit par la récupération des ressources non locales dans un réseau homogène. Notre protocole expérimental consiste, pour les différentes expériences, à générer aléatoirement 25 allocations initiales pour des problèmes d'allocation distincts.

Afin d'évaluer notre processus de réallocation indépendamment du processus de consommation des taches, nous considérons $m \in [2; 16]$ nœuds, $l_0 = 4$ jobs, $n = 12 \times m$ tâches avec 10 ressources par tâche. Chaque ressource $\rho_i$ est répliquée 3 fois et $|\rho_i| \in [0; 100]$.

**Hypothèse 1 : la stratégie de réallocation réduit significativement le temps de réordonnancement.** — Nous considérons ici que les allocations initiales sont aléatoires.

La figure 8.1 montre les médianes et les écarts types de nos métriques, le *flowtime* simulé, le temps d'ordonnancement et le taux de disponibilité, en fonction du nombre de nœuds. Nous observons que notre stratégie de réallocation améliore le *flowtime* de l'allocation initiale mais qu'il est supérieur à celui atteint par les méthodes fondées sur des enchères séquentielles. La méthode d'allocation, qui considère le meilleur nœud pour chaque tâche mise aux enchères, permet d'obtenir un *flowtime* simulé meilleur que celui obtenu par les méthodes de réallocation qui sont pénalisées par l'allocation initiale aléatoire à rééquilibrer. Malgré le fait que certaines délégations, susceptibles de réduire le *flowtime*, ne sont pas prises en compte par le processus de négociation, notre stratégie multi-agents s'avère efficace : le *flowtime* simulé atteint par notre stratégie est meilleur que celui de l'allocation initiale, et le surcoût par rapport à une méthode d'allocation basée sur des enchères séquentielles est en moyenne de 40 %. En effet, notre stratégie d'offre sélectionne efficacement les tâches distantes dont la délégation réduit le coût, dans le but d'améliorer le taux de disponibilité locale. Bien que ce taux soit inférieur à celui atteint par la méthode d'allocation, il reste similaire à celui obtenu par la méthode de réallocation basée sur des enchères.

Comparativement aux méthodes basées sur des enchères qui évaluent toutes les délégations possibles, notre stratégie multi-agents présente un temps d'ordonnancement nettement inférieur. Par exemple, ce temps est mille fois plus court pour 8 nœuds. Il est intéressant de noter que l'écart entre le temps de réordonnancement entre une méthode fondée sur des enchères et notre stratégie de négociation croît exponentiellement avec le nombre de nœuds, tandis que l'écart pour le *flowtime* reste globalement constant. Ainsi, même lorsque le nombre de nœuds est limité, le bénéfice obtenu sur le *flowtime* grâce aux enchères séquentielles sera contrebalancé et annulé par le coût supplémentaire lié au temps de réordonnancement. Comme nous l'explor器ons ultérieurement, ce surcoût a un impact négatif sur l'équilibrage continu des charges pendant l'exécution des tâches.
<figure><img src="image_11.png" /><figcaption>(a) Délai moyen de réalisation</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(b) Temps de réordonnancement selon une échelle de temps logarithmique</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(c) Taux de disponibilité</figcaption></figure>

FIGURE 8.1 – Réallocation sans consommation
Afin d'évaluer le processus de réallocation exécuté de manière concurrente à la consommation des taches, nous considérons $m = 8$ nœuds, $l_0 = 4$ jobs, $n \in [40; 320]$ tâches avec 10 ressources par tâche. Chaque ressource $\rho_i$ est répliquée 3 fois et $|\rho_i| \in [0; 500]$. Afin de ne pas déclencher des négociations inutiles dues à l'asynchronisme des opérations de consommations, nous considérons dans nos expérimentations qu'une réallocation bilatérale est socialement rationnelle si elle fait décroître d'au moins une seconde le *flowtime*. Le fait que, dans nos expériences, la différence entre le *flowtime* réalisé et le *flowtime* simulé de l'allocation initiale ($C_{\text{mean}}^{R}(\vec{A}_0) - C_{\text{mean}}^{S}(\vec{A}_0)$), qui mesure le coût de l'infrastructure, est négligeable, conforte ce choix technologique.

**Hypothèse 2 : la stratégie de réallocation améliore le flowtime.** — Nous considérons ici que les allocations initiales sont aléatoires et que les agents ont une connaissance parfaite de l'environnement d'exécution (cf. équation 8.1).

La figure 8.3a montre les médianes et les écarts types des différents *flowtime* en fonction du nombre de tâches. Nous observons que le *flowtime* réalisé atteint par la méthode d'allocation est pire que le *flowtime* réalisé de l'allocation aléatoire initiale. Même si le *flowtime* simulé est très bon, la méthode d'allocation diffère le processus de consommation afin d'obtenir préalablement une allocation équilibrée et donc pénalise le *flowtime* réalisé. À l'inverse, le *flowtime* réalisé des méthodes de réallocation appliquées au cours du processus de consommation, que cela soit notre stratégie ou qu'elle soit fondée sur des enchères, est meilleur que le *flowtime* réalisé de l'allocation initiale aléatoire. De plus, le *flowtime* réalisé des méthodes de réallocation est borné par le *flowtime* simulé de la réallocation (si un oracle calcule la réallocation en temps constant). Ces méthodes améliorent le *flowtime* en réallouant au cours du processus de consommation les tâches non locales dont la délégation réduit le coût. Comme le nombre de délégations de notre stratégie est supérieur au nombre de délégations de la méthode de réallocation fondée sur des enchères, le taux d'amélioration de performance (Γ) de notre stratégie est meilleur (entre 13 % et 23 %) que le taux d'amélioration de performance de la méthode de référence (entre 0 % et 15 %).

La figure 8.2 montre l'évolution des médianes et écarts-types de nos métriques au cours de la consommation de 128 tâches selon une échelle de temps logarithmique. Elle confirme que le meilleur *flowtime* réalisé est celui obtenu par notre stratégie lorsqu'elle est exécutée de manière concurrente au processus de consommation. La réactivité (*responsiveness*) de notre stratégie

**Hypothèse 3 : la stratégie de réallocation ne pénalise pas la consommation.** —
Nous considérons ici uniquement des allocations initiales stables, c'est-à-dire pour lesquelles il n'existe aucune réallocation bilatérale socialement rationnelle.

Dans la figure 8.3b le *flowtime* réalisé des méthodes de réallocation est similaire au *flowtime* réalisé de l'allocation initiale. Le surcoût de la négociation, que cela soit des enchères ou des marchandages bilatéraux, est négligeable car le processus de négociation est concurrent au processus de consommation et, dans le cas de notre stratégie, aucune négociation n'est déclenchée lorsque les agents estiment que l'allocation est stable.
<figure><img src="image_14.png" /><figcaption>FIGURE 8.2 – Au cours de la consommation selon une échelle de temps logarithmique</figcaption></figure>

Hypothèse 4 : la stratégie de réallocation s'adapte aux aléas d'exécution. —
Nous considérons ici le coût qui simule le ralentissement de la moitié des nœuds
(cf. équation 8.2).

Nous observons dans la figure 8.3c que les délais moyens de réalisation ont doublé
à cause des aléas d'exécution. Le flowtime réalisé et le flowtime simulé de la méthode
d'allocation fondée sur des enchères, qui ne prend pas en compte le ralentissement de
la moitié des nœuds, sont supérieurs aux mêmes configurations sans ralentissement
(cf. figure 8.3a). Contrairement à la méthode de réallocation fondée sur des enchères, le
flowtime réalisé de notre stratégie reste meilleur que le flowtime réalisé de l'allocation
initiale aléatoire et ce malgré une connaissance imparfaite de l'environnement d'exécu-
tion des agents. Prendre en compte les temps d'exécution effectifs des tâches déjà réa-
lisées permet au taux d'amélioration de performance Γ de se situer entre 17 % et 29 %.
<figure><img src="image_15.png" /><figcaption>FIGURE 8.3 – Hypothèses 2, 3 et 4 : la stratégie de réallocation améliore le flowtime, ne pénalise pas la consommation et s'adapte aux aléas d'exécution</figcaption></figure>
*Hypothèse 5 : la stratégie de réallocation s'adapte à la libération de jobs.* — Nous considérons ici à nouveau que les allocations initiales sont aléatoires et que les agents ont une connaissance parfaite de l'environnement d'exécution (cf. équation 8.1). Nous examinons la consommation de 3 jobs libérés à $t_0$, chacun constitué de 32 tâches. Un quatrième job, également constitué de 32 tâches, est libéré 10 secondes après le début de la consommation des autres jobs.

La figure 8.4 montre l'évolution des médianes et écarts-types de nos métriques au cours de la consommation selon une échelle de temps logarithmique. La figure 8.4a révèle une nette amélioration du *flowtime* moyen avec notre stratégie. La figure 8.4b met en évidence le nombre plus important de délégations réalisées au cours du processus par notre stratégie. Il est intéressant de noter que, non seulement notre stratégie de réallocation améliore nettement le *flowtime*, mais elle permet aussi d'obtenir un temps total d'exécution (*makespan*) bien meilleur que le temps de consommation sans

<figure><img src="image_16.png" /><figcaption>FIGURE 8.4 – Lors de la libération selon une échelle de temps logarithmique</figcaption></figure>
réallocation ou avec une méthode d'allocation, et du même ordre que le temps d'exécution avec une méthode de réallocation fondée sur des enchères. Contrairement aux méthodes de référence, notre stratégie réaffecte les tâches d'un job dès qu'il est libéré afin d'améliorer le *flowtime* réalisé et de réduire le temps de consommation.

## 9. DISCUSSION

Afin de concevoir des agents autonomes qui réalisent de manière concurrente des opérations de consommation et de réallocation, nous avons proposé une architecture modulaire d'agent composé de trois agents composants : l'exécutant qui exécute les tâches ; le négociateur qui marchande des reallocations avec ses pairs ; et le gestionnaire qui coordonne localement ces opérations en gérant le lot de tâches. Sans pour autant connaître l'état global du système, i.e. l'allocation, ces agents disposent de connaissances locales (e.g. la tâche courante, le lot de tâches) et d'un modèle de leurs homologues qui guident leur comportement dans les interactions.

L'architecture modulaire que nous proposons, en se basant sur la séparation des rôles, permet de réduire la complexité de conception des comportements des agents, comparativement au cas où un seul agent aurait à gérer simultanément l'exécution des tâches et la négociation des reallocations. Cette complexité est mesurée dans la table 9.1 en nombre d'états, de transitions et de lignes de code.

<table><caption>TABLE 9.1 – Mesure de complexité des comportements</caption><thead><tr><td>Agent</td><td>Nb. d'états</td><td>Nb. de transitions</td><td>Nb. de lignes</td></tr></thead><tbody><tr><td>Superviseur</td><td>9</td><td>69</td><td>626</td></tr><tr><td>Exécutant</td><td>2</td><td>7</td><td>173</td></tr><tr><td>Gestionnaire</td><td>5</td><td>23</td><td>465</td></tr><tr><td>Négociateur</td><td>9</td><td>74</td><td>1306</td></tr><tr><td>Total agents composants</td><td>16</td><td>104</td><td>1944</td></tr></tbody></table>

Nos expérimentations montrent que le taux d'amélioration de performance dû à notre stratégie de réallocation, lorsqu'elle est exécutée en continue lors du processus de consommation, peut atteindre 29 %. En sélectionnant efficacement les délégations et les échanges qui atténuent le coût d'exécution des tâches, le marchandage réduit significativement le temps de réordonnancement. De plus, le surcoût lié aux négociations est négligeable car, lorsque l'allocation est stable, elles sont suspendues. Même si un ou plusieurs nœuds sont ralentis, notre stratégie de réallocation s'adapte au contexte d'exécution en distribuant plus de tâches aux nœuds qui ne sont pas ralentis, car elle tient compte du temps d'exécution effectif des tâches déjà réalisées, sans pour autant nécessiter de phase d'apprentissage. Nous avons également évalué notre stratégie face à la libération de jobs au fil de l'eau. La réactivité (*responsiveness*) de notre stratégie, qui se démarque des méthodes d'allocation et de réallocation de référence fondées
sur des enchères, s'explique par la réallocation de lots de tâches grâce à de multiples négociations bilatérales concurrentes entre-elles et avec le processus de consommation.

Une analyse de sensibilité pour étudier l'influence du facteur de réplication, du coût induit par la récupération des ressources non locales (κ) ou du délai d'annulation de la négociation (timeout) va au-delà de la portée de cet article, mais mériterait une étude approfondie.

Plus généralement, nos travaux futurs porteront sur l'intégration de la réallocation des tâches dans un processus d'approvisionnement qui ajoute ou supprime des nœuds de calcul au cours de l'exécution en fonction des besoins des utilisateurs afin de proposer une stratégie multi-agents élastique de passage à l'échelle.

## RÉMERCIEMENTS

Nous adressons nos remerciements aux relecteurs pour leur travail minutieux et leurs précieux conseils qui nous ont permis d'améliorer cet article. Nous tenons égale- ment à remercier le Mésocentre de Calcul Scientifique Intensif de l'Université de Lille pour la mise à disposition des ressources informatiques.

## BIBLIOGRAPHIE

[1] Q. BAERT, « Négociation multi-agents pour la réallocation dynamique de tâches », Thèse de doctorat, Université de Lille, Septembre 2019.

[2] E. BEAUPREZ, L. BIGAND, A.-C. CARON, M. MORGE & J.-C. ROUTIER, « Réaffectation de tâches de la théorie à la pratique : état de l'art et retour d'expérience », in *Actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA)*, Cépaduès, 2021, p. 51-60.

[3] E. BEAUPREZ, A.-C. CARON, M. MORGE & J.-C. ROUTIER, « Échange de tâches pour la réduction de la durée moyenne de réalisation », in *Actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA)*, Cépaduès, 2022, p. 19-28.

[4] ———, « Consommation adaptive par négociation continue », in *Actes des Journées Francophones sur les Systèmes Multi-Agents (JFSMA)*, Cépaduès, 2023, p. 21-30.

[5] ———, « Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation », *ROIA 4* (2023), n° 2, p. 193-221.

[6] E. BEAUPREZ, M. MORGE & A.-C. CARON, « Scala implementation of the Extended Multi-agents Sit-uated Task Allocation », https://gitlab.univ-lille.fr/maxime.morge/smastaplus, 2020.

[7] Y. CHEN, X. MAO, F. HOU, Q. WANG & S. YANG, « Combining re-allocating and re-scheduling for dynamic multi-robot task allocation », in *Proc. of IEEE International Conference on Systems, Man, and Cybernetics (SMC)*, 2016, p. 395-400.

[8] H.-L. CHOI, L. BRUNET & J. P. How, « Consensus-based decentralized auctions for robust task alloca-tion », *IEEE Transactions on Robotics* **25** (2009), n° 4, p. 912-926.

[9] N. CREECH, N. CRIADO PACHECO & S. MILES, « Resource allocation in dynamic multiagent systems », https://arxiv.org/abs/2102.08317, 2021.

[10] A. DAMAMME, A. BEYNIER, Y. CHEVALEYRE & N. MAUDET, « The Power of Swap Deals in Distributed Resource Allocation », in *Proc. of International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*, 2015, p. 625-633.

[11] J. DEAN & S. GHEMAWAT, « MapReduce: Simplified Data Processing on Large Clusters », in *Proc. of The Sixth Symposium on Operating System Design and Implementation*, 2004, p. 137-150.

[12] U. ENDRISS, N. MAUDET, F. SADRI & F. TONI, « Negotiating Socially Optimal Allocations of Resources », *Journal of Artificial Intelligence Research* **25** (2006), p. 315-348.
[13] S. KOENIG, C. TOVEY, M. LAGOUDAKIS, V. MARKAKIS, D. KEMPE, P. KESKINOCAK, A. KLEYWEGT, A. MEYERSON & S. JAIN, « The power of sequential single-item auctions for agent coordination », in *Proc. of The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference (AAAI)*, vol. 2006, 2006, p. 1625-1629.

[14] K. LERMAN, C. JONES, A. GALSTYAN & M. J. MATARIĆ, « Analysis of dynamic task allocation in multi-robot systems », *The International Journal of Robotics Research* **25** (2006), n° 3, p. 225-241.

[15] LIGHTBEND, « Akka is the implementation of the Actor Model on the JVM », http://akka.io, 2020.

[16] S. MAYYA, D. S. D'ANTONIO, D. SALDAÑA & V. KUMAR, « Resilient task allocation in heterogeneous multi-robot systems », *IEEE Robotics and Automation Letters* **6** (2021), n° 2, p. 1327-1334.

[17] G. A. MILLS-TETTEY, A. STENTZ & M. B. DIAS, « The dynamic hungarian algorithm for the assignment problem with changing costs », *Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-07-27 (2007)*, p. 19.

[18] C. NAM & D. A. SHELL, « When to do your own thing: Analysis of cost uncertainties in multi-robot task allocation at run-time », in *Proc. of IEEE International Conference on Robotics and Automation*, 2015, p. 1249-1254.

**ABSTRACT.** — In this paper, we study the problem of continous allocation of concurrent jobs, composed of situated tasks, underlying the distributed deployment of the MapReduce design pattern on a cluster. In order to implement our multi-agent strategy that aims at minimizing the mean flowtime of jobs, we propose a composite agent architecture that allows negotiation and consumption concurrency. Our experiments show that, when executed concurrently with the consumption process, our reallocation strategy: (1) significantly reduces the rescheduling time; (2) improves the flowtime; (3) does not penalise the consumption; (4) is robust to execution hazards; and (5) adapts to the release of jobs.

**KEYWORDS.** — Multi-Agents Systems, Distributed Problem Solving, Agent-based Negotiation, Agent Architecture.