Jorge-Arnulfo Quiané-Ruiz

Philippe Lamarre
email: lamarre@univ-nantes.fr

Patrick Valduriez
email: patrick.valduriez@inria.fr

Un modèle pour caractériser des participants autonomes dans un processus de médiation 1*

Keywords: Autonomie des participants, satisfaction, comportement à long terme Participants' autonomy, satisfaction, long-run behavior

Nous considérons les systèmes d'information distribués dans lesquels les participants sont non seulement libres de quitter le système, mais peuvent aussi manifester différents intérêts. La plupart des travaux dans ce contexte sont centrés sur la performance (répartition de charge, temps de réponse. . . ) sans tenir compte des intérêts des participants. Pourtant, le non respect de leurs intérêts particuliers peut conduire les participants à quitter le système. Nous proposons une nouveau modèle qui aide à caractériser la satisfaction des participants sur le long terme ainsi que leur adéquation.

Introduction

Nous nous intéressons aux systèmes d'information distribués où des participants fournisseurs et clients) hétérogènes et autonomes interagissent. L'autonomie fait ici référence à la possibilité de quitter le système suite à une décision individuelle locale et ce, sans aucune contrainte.

Chaque requête doit être allouée à des fournisseurs peuvant la traiter. De nombreux travaux dans ce domaine ont concentré leurs efforts sur la répartition de charge (QLB) [1, 3, 7]. Cependant, les participants peuvent manifester certaines attentes en dehors des seules performances. Par exemple, un fournisseur représentant une firme pharmaceutique peut souhaiter, à une période donnée, faire la promotion d'une lotion anti-moustique. Il manifestera alors un intérêt plus marqué pour les requêtes relatives à ce type de produits et aura tendance à les privilégier par rapport aux autres requêtes de son domaine.

Intuitivement, dans ces conditions, un environnement est satisfaisant pour les participants s'il leur permet de répondre à leurs attentes. Pour cela, le système d'allocation des requêtes doit tenir compte de leurs intentions. Ces intentions peuvent être le résultat de la combinaison de plusieurs informations comme les préférences, la charge, les stratégies. Les préférences d'un client peuvent leur permettre de faire le choix entre différents fournisseurs (par exemple en utilisant la réputation). Celles d'un fournisseur peuvent être fondées sur leurs centres d'intérêt. Nous considérons ici que les preferences sont plutôt statiques (i.e. peu sujettes à évolution), alors que les les intentions sont plus dynamiques. Dans l'idéal, le système devrait satisfaire tous les participants à chaque allocation.

Cependant, cela n'est pas toujours possible. Par exemple, pour une requête donnée, lorsqu'aucun fournisseur ne souhaite traiter la traiter, il y aura nécessairement des insatisfaits. Ils seront soit du coté "client", si la requête est rejetée par le système, soit du coté "fournisseur", si le traitement de la requête leur est imposé. Une vue à long terme de la satisfaction est donc plus réaliste.

A notre connaissance, il n'existe pas de travaux qui permettent de caractériser la capacité d'un système à satisfaire les intentions des participants sur le long terme. Les systèmes économiques considèrent l'utilité, qui est liée à la notion de satisfaction mais sans lui correspondre exactement. Nous proposons donc un nouveau modèle permettant de déterminer si un système satisfait les participants sur le long terme et s'il est "juste" avec eux.

La suite de cet article est structurée de la manière suivante. La section 2 présente un scénario motivant la démarche. La section 3 présente quelques concepts préliminaires. Le modèle permettant d'évaluer un système du point de vue de la satisfaction est présenté à la section 4. Dans la section 5, nous définissons les propriétés permettant d'évaluer la qualité des méthodes d'allocation. Finalement, les liens avec d'autres travaux sont présentés à la section 6 avant la section 7 qui conclue.

Motivation

Pour illustrer le problème des systèmes d'information distribués avec des participants autonomes, considérons par exemple un système incluant des centaines de scientifiques (biologistes, docteurs en médecine, généticiens. . . ) travaillant sur le génôme humain. Ils sont répartis sur la planête et ils partagent leurs informations. Chaque site, qui représente un scientifique, déclare ses capacités au système et gère localement ses préférences et intentions.

Préliminaires

Nous considérons un système dans lequel interagissent des clients, des fournisseurs et des médiateurs. Les ensembles de ces participants, non nécessairement disjoints, sont notés respectivement C, P , et M. Les requêtes sont exprimées sous forme d'un triplet q = < c, d, n > où q.c ∈ C est l'identifiant du client ayant émis la requête ; q.d, la description de la tâche demandée ; et q.n ∈ N * , le nombre de fournisseurs demandés. P q dénote l'ensemble des fournisseurs ayant les capacités de traiter une requête q• Les clients envoient leurs requêtes à un médiateur m ∈ M qui, si c'est possible, alloue toute requête q à q.n fournisseurs choisis parmi ceux ayant les capacités de le faire [START_REF] Azar | Balanced Allocations[END_REF] . Un client c (resp. un fournisseur p) peut exprimer ses intentions -→ CI q c [p] (resp. P I p (q)) pour allouer [START_REF] Azar | Balanced Allocations[END_REF] Convention : un médiateur suit les directives des clients dans la mesure où les fournisseurs sont assez nombreux pour cela.

(resp. traiter) une requête q. Ces intentions sont des valeurs réelles dans [-1..1]. Au contraire d'une valeur négative, une intention positive dénote le désir d'allouer (resp. de traiter) la requête

La modélisation

Notre attention s'est portée sur deux caractériques des participants qui permettent de comprendre comment ils peuvent percevoir le système dans lequel ils interagissent.

La première de ces caractéristiques est l'adéquation. En fait, deux adéquations doivent être considérées. a) adéquation du système par rapport à un participant e.g. un système dans lequel un fournisseur ne peut trouver aucune requête correspondant à ses attentes n'est pas adéquat pour ce fournisseur ; b) adéquation d'un participant au système e.g. un client qui émet des requêtes qui n'intéressent aucun fournisseur n'est pas adéquat par rapport au système. A travers ces notions il est possible d'évaluer si un participant a une chance d'atteindre ses objectifs dans un système. À moins d'avoir une connaissance globale du système, un participant ne peut déterminer lui même ce que les autres pensent de lui. Aussi, nous considérons l'adéquation d'un participant au système comme une caractéristique globale (cf. Section 4.3).

La seconde caractéristique est la satisfaction. Comme pour l'adéquation, deux sortes de satisfaction peuvent être consédérées : a) la satisfaction d'un participant vis-à-vis du système e.g. un client qui reçoit des résultats de fournisseurs qu'il ne souhaitait pas solliciter n'est pas satisfait ; et b) la satisfaction d'un participant par rapport au système de médiation e.g. un fournisseur devant traiter des requêtes qu'ils ne désirait pas met en cause le système de médiation lorsqu'il constate qu'il existe des requêtes lui convenant mieux, mais ne lui étant pas allouées. Ces deux notions de satisfaction peuvent avoir un impact important sur le système dans la mesure où elles peuvent fonder une décision de départ d'un participant.

Nous supposons que les participants ont une mémoire limitée et qu'ils ne mémorisent donc que leurs k dernières interactions avec le système [START_REF] Ferguson | Microeconomic Algorithms for Load Balancing in Distributed Computer Systems[END_REF] . Nous allons donc définir les différentes notions présentées ci-dessus par rapport à la mémoire des participants. Deux remarques suppémentaires. Il est évident que ces notions évoluent au cours du temps, mais pour éviter d'alourdir les notations, le temps n'apparaîtra pas. Enfin, ces notions peuvent être définies soit à partir des préférences des participants, soit à partir de leurs intentions. Si les définitions formelles sont similaires, les valeurs obtenues présentent quelques différences. Pour des raisons de place, nous ne pouvons en présenter ici qu'une seule version. Dans la mesure où les préférences sont souvent considérées comme des données privées, ce sont les intentions affichées auprès des médiateurs qui serviront de base à nos définitions.

Caractérisation locale d'un client

Un client est caractérisé à partir des informations qu'il peut obtenir du système. Intuitivement, les caractéristiques présentées ci-après sont utiles pour répondre à des questions de la forme "Dans quelle mesure mes intentions correspondent à celles des fournisseurs pouvant traiter mes requêtes ?" -adéquation d'un client par rapport au sytème -"Dans quelle mesure les fournisseurs ayant traité mes dernières requêtes me satisfont ?" -Satisfaction d'un client -"La méthode d'allocation des requêtes me satisfait-elle ?" -Satisfaction d'un client par rapport à l'allocation -. Ces notions seront basées sur la mémoire d'un client qui sera notée IQ k c .

Adéquation. L'adéquation du système pour un client caractérise la vision du système qu'a le client. Dans le scénario présenté section 2, le système est relativement adéquat pour Emma car bon nombre des fournisseurs lui conviennent. Plus formellement, l'adéquation du système par rapport au client c et pour une requête q, notée δ sca (c, q), est définie comme étant la moyenne des intentions de c par rapport à l'ensemble des fournisseurs pouvant traiter q (P q ). La valeur de cette notion est volontairement amenée dans l'intervalle

[0..1]. δ sca (c, q) = 1 ||P q || p∈Pq -→ CI q c [p] + 1 2 (1)
L'adéquation du système par rapport à un client c, est alors définie comme la moyenne des adéquations pour les k dernières requêtes.

Définition 1 Adéquation du système par rapport à un client.

δ sca (c) = 1 ||IQ k c || q∈IQ k c δ sca (c, q)
Plus la valeur est proche de 1, plus le client considère le système comme adéquat.

Satisfaction. La satisfaction d'un client c concernant le traitement d'une de ses requêtes q, notée δ s (c, q) est liée aux fournisseurs auxquels sa requête a été allouée ( P q ). La moyenne semble une technique intuitive. Cependant, elle ne permet pas de prendre en compte le souhait d'un client d'avoir plusieurs résultats de fournisseurs différents. Par exemple, dans le scénario de la section 2, Emma a demandé 2 fournisseurs. Si le système ne lui en alloue qu'un seul la satisfaction d'Emma ne peut être totale, même si ce fournisseur est parfait. L'équation suivante tient compte de ce point.

δ s (c, q) = 1 n p∈ c Pq -→ CI q c [p] + 1 2 (2)
où n abbrège q.n. Les valeurs de δ s (c, q) sont dans l'intervalle [0..1].

La satisfaction d'un client c est alors obtenue en faisant la moyenne des satisfactions par rapport aux k dernières requêtes traitées.

Définition 2 Satisfaction d'un client

δ s (c) = 1 ||IQ k c || q∈IQ k c δ s (c, q)
Cette notion de satisfaction ne tient aucun compte du contexte. Elle ne permet donc pas au client d'évaluer les efforts consentis par le système d'allocation pour le satisfaire. Par exemple, en reprenant le scénario de la section 2, suppose qu'Emma a une intention de 1 (resp. 0.9, 0.

δ as (c) = 1 ||IQ k c || q∈IQ k c δ s (c, q) δ sca (c, q)
Si la valeur ainsi obtenue est supérieure à 1, le client peut en conclure que la méthode d'allocation agit en sa faveur. Par contre, si cette valeur est proche de 0 la méthode défavorise le client.

δ spa (p) = 1 ||P Q k p || q∈P Q k p -→ P I k p [q] + 1 2 0 si P Q k p = ∅
Les valeurs que peut prendre cette adéquation sont dans l'intervalle [0.

δ s (p) = 1 ||SQ k p || q∈SQ k p -→ P I k p [q] + 1 2 0 si SQ k p = ∅ Avec cette
δ csa (c, q) = 1 ||P q || p∈Pq P I p (q) + 1 2 (3)
L'adéquation du client par rapport au système est simplement définie comme la moyenne de ces valeurs.

δ psa (p) = 1 ||P Q k p || q∈P Q k p -→ CI q c [p] + 1 2 0 if P Q k p = ∅

  TAB. 1 -Fournisseur ayant les capacités de traiter la requête d'Emma.

	sions pourraient conduire ces participants à quitter le système. Ici la seule réponse correcte du point de vue des intentions est Mary. Malheureusement, cette allocation n'est pas satisfaisante du point de vue de la répartition de charge. De plus, Emma a demandé à ce que la requête soit envoyée à deux scientifiques. C'est donc un cas qui génèrera du mécontentement d'un coté ou de l'autre.	Fournisseurs Charge Mark 15% Robert 43% Johnson 78% William 85% Mary 100%	Intention Oui Non Oui Non Oui	Cons. Int. Non Oui Non Oui Oui
	Plusieurs questions restent donc ouvertes : Que doit faire le système dans ce cas ? Doit-il privilégier les intentions du client (ici Emma) ? les intentions des four-	Considérons un scénario simple. Emma (Dr. en médecine) vient de découvrir un lègues, disons 2 pour simplifier l'exemple. haite avoir des réponses de plusieurs col-dies. Pour une vue plus générale, elle sou-ver des liens éventuels avec d'autres mala-peau. Elle interroge le système pour trou-gène responsable d'une maladie de la
		Dans un premier temps, le système doit identifier les fournisseurs capables de trai-ter la requête. Un algorithme de match-making [10] permet de résoudre ce pre-mier problème. Supposons que pour cet exemple, il y en ait 5. La seconde étape consiste à obtenir les intentions de ces fournisseurs par rapport à cette requête (supposées binaires dans cet exemple). Le tableau 1 regroupe les différentes données de cet exemple.
		Mary est la plus chargée (elle n'a plus de ressource disponible). Robert et William ne désirent pas traiter cette requête pour des raisons qui leurs sont propres. D'un autre coté, pour des raisons de confiance envers leurs résultats, Emma ne souhaite pas que Mark ou Johnson traitent sa re-quête.
		Quoi qu'il en soit, à la demande d'Emma, le système doit choisir deux fournisseurs pour leur allouer la requête. Mark et Ro-bert sont les moins chargés. C'est donc à eux que les méthode basées sur la réparti-tion de charge alloueraient la requête. Cela aurait pour conséquence de mécontenter Robert et Emma. Répétées, de telles déci-

nisseurs ? Doit-il prendre en compte la charge des fournisseurs ? Dans cet article, nous ne répondons pas à ces questions, mais nous proposons un modèle qui permet d'analyser le comportement d'un système de ce type. Les notions présentées peuvent aussi servir à une méthode de médiation dans ses prises de décisions.

  0 > 0 est une constante positive prédéfinie, il mesure l'écart maximal entre les valeurs, et donc il qualifie la balance entre les différents éléments. Plus la valeur obtenue est grande meilleure est la balance. Cet article est centré sur les systèmes d'information distribués où les participants (fournisseurs comme clients) sont libres de quitter le système quand ils le souhaitent et ont des intérêts particuliers. Nous avons proposé un modèle de répartition des requêtes dont les principales caractéristiques sont 1) prise en compte des intentions des participants sur le long terme ; 2) indépendance par rapport à la stratégie utilisée pour obtenir les intentions et par rapport à la technique utilisée pour effectuer la répartition des requêtes ; d'où, 3) applicablilité à tous les systèmes existants pour mesurer leurs capacités à respecter les intentions des participants et donc à les satisfaire ; et, 4) présentation de notions pouvant guider la conception de nouvelles techniques d'allocation de requêtes. En utilisant les différentes mesures proposées, nous pensons qu'il est possible de prévoir les départs des participants d'un système et d'en déterminer les raisons. Dans de futurs travaux, nous allons analyser des méthodes d'allocations existantes en utilisant ce modèle et vérifier concrètement s'il permet d'effectuer des prévisions correctes.

	7 Conclusion
		σ(g, S) =	min s∈S max s ∈S	g(s) + c 0 g(s ) + c 0	(6)
		6 Travaux connexes
	5 Mesures Les mesures proposées sont identiques pour les clients et les fournisseurs, et sont applicables aux différentes notions présen-tées plus haut. Pour éviter les redites, la fonction g dénotera l'une ou l'autre des no-tions présentées, et S un ensemble de four-nisseurs ou de clients. La moyenne (µ) permet de mesurer correc-tement l'efficacité. µ(g, S) = 1 ||S|| s∈S g(s) (4) L'indice d'équité proposé par [5] (Equa-tion 5) apporte quant à lui des informa-tions sur la répartition des valeurs. Il est toujours compris entre 0 et 1. Plus la va-leur est proche de 1, plus le mécanisme est équitable. f(g, S) = s∈S g(s) 2 ||S|| s∈S g(s) 2 (5)	Il existe une litérature substantielle rela-tive au problème de "query load balan-ce". Dans le contexte des systèmes large-ment distribués, la plupart des travaux al-louent la requête aux fournisseurs qui sont les moins chargés. Azar et al. [1] explorent le problème d'allouer n tâches en choi-sissant le serveur le moins chargé parmi d serveurs choisis aléatoirement. Vöcking [11] a montré que l'usage de l'a-symétrie améliore les résultats. Mitzenmacher et al. [6] améliorent les deux propositions pré-cédentes en introduisant une mémoire des m derniers serveurs utilisés. Cependant, tous ces travaux font l'hypothèse que les fournisseurs (et les requêtes) sont homo-gènes et ne se généralisent pas aux sys-tèmes hétérogènes. Des travaux ont consi-déré d'autres notions comme le CPU [4], ou la combinaison de plusieurs notions I/O, mémoire, CPU [9], ou encore des scé-narii avec plusieurs ressources [7]. Cepen-dant, aucun ne considère les intentions que ce soient celles des fournisseurs ou des clients. Plusieurs approches [2, 8] s'ap-prochent de la notion d'intention en pré-sentant des modèles économiques, mais l'économie introduit d'autres aspects (liés à l'auto-régulation des systèmes écono-miques) qui ne sont pas directement liées aux intentions. De plus, l'étude sur le long terme (k requêtes) n'est pas toujours claire.

Lorsque l'on s'intéresse à la répartition de charge, le ratio Min/Max est aussi largement utilisé. Tel que défini par l'équation 6 où c

Notons que k peut être différent d'un participant à l'autre. Cependant, dans un souci de simplification, nous supposerons ici que ce paramètre est identique pour tous les participants.

Travail en partie financé par ARA "Massive Data" of the French ministry of research (projects MDP2P and Respire) and the European Strep Grid4All project.

† Cet auteur est supporté par