Université d!Angers, France

« Les jeunes ont trop d!amis qui n!en sont pas, ils surexposent leur vie privée, ils publient sans réflexion, leurs commentaires et leurs statuts démontrent une pauvreté linguistique, relationnelle et réflexive, sans parler des pratiques transgressives telles que le cyberharcèlement » : telles sont les représentations des parents et des enseignants sur les usages par les jeunes des réseaux sociaux qui se sont dégagées d!une enquête menée par Schneider (2014, p. 66). Cette analyse converge avec celle de Papen qui souligne, dans une interview donnée à Collette (Papen et Collette, 2013, p. 147-148) que les professeurs qui ne connaissent pas « ces pratiques de l!écrit et les pratiques médiatiques » des jeunes « ont tendance à penser qu!elles n!ont rien à voir avec les activités qu!on conduit à l!école, comme lire un roman, écrire une discussion sur un roman, etc. » et « ont peut-être tendance à penser que celles-ci ne sont pas sérieuses, qu!elles ne requièrent pas de compétences ou alors que ce sont des pratiques techniques compliquées, mais qui n!ont rien à voir avec ce que l!on doit enseigner et apprendre à l!école ».

Nous souhaitons ici mieux faire connaître les chroniques, récits dont l!écriture, et encore plus la lecture, sont très populaires chez les jeunes filles des quartiers périphériques de grandes villes en France. La connaissance par les enseignants des compétences que cette pratique révèle et développe semble constituer un support très riche pour penser les enjeux didactiques du développement des compétences de littéracie.

Les chroniques sont donc des récits publiés en ligne, sur des réseaux sociaux (Skyblogs, Facebook, Wattpad, et plus rarement Instagram), par des jeunes qui se présentent le plus souvent comme des filles, ayant entre 15 et 25 ans, issues de l•immigration et résidant dans des quartiers périphériques de grandes villes francophones.

L•écriture et la lecture de chroniques sont des pratiques qui peuvent être étudiées à travers les chroniques elles-mêmes (les différents épisodes du récit, généralement une centaine, publiés par une seule et même autrice), ainsi qu•à travers les nombreux discours qu•elles suscitent au sein des communautés qu•elles rassemblent. Même si celles-ci sont importantes (plusieurs de ces chroniques dépassent la barre des 50 000 abonnés sur Facebook), pour autant la pratique des chroniques reste encore largement méconnue, et très peu commentée, que ce soit dans la presse ou dans des travaux universitaires, en regard, par exemple, de l•attention prêtée à d•autres formes d•écritures numérique ou à d•autres pratiques de communication des jeunes sur les réseaux sociaux.

La recherche que nous avons entreprise sur les chroniques depuis 2015 [START_REF] Bigot | Les chroniques : étude exploratoire d•un genre d•écriture (très) populaire sur le net[END_REF]Bigot et Maillard, 2017a;Bigot et Maillard, 2017b) nous a conduites à nous interroger sur ces textes comme traces de l•émergence d•un genre à la fois nouveau et en même temps inscrit dans une histoire de pratiques d•écriture [START_REF] Bigot | Les chroniques : étude exploratoire d•un genre d•écriture (très) populaire sur le net[END_REF]. Nous avons ainsi dégagé quelques-unes de leurs caractéristiques, tant thématiques que formelles, et notre recherche nous a permis notamment de révéler la très grande sensibilité des chroniqueuses et de leurs lectrices aux questions de variations stylistiques (cf. infra). [START_REF] Mori | L•archipel invisible : L•écriture dans les « cultures de banlieue[END_REF][START_REF] Perret | Prendre en compte les pratiques personnelles d"écriture numérique des élèves en lycée professionnel[END_REF][START_REF] Schneider | Y a-t-il une littéracie adolescente? Spirale[END_REF], enquêtes que notre étude vient compléter. La dimension multimodale et littéraire de l•écriture des chroniques nous conduit à mobiliser des concepts développés pour penser l•écriture des récits [START_REF] Genette | Figures III[END_REF], et notamment des récits autobiographiques [START_REF] Lejeune | Signes de vie[END_REF]. Nous nous sommes également appuyées sur des travaux portant sur l•écriture multimodale (Lebrun et Lacelle, 2012), et notamment les usages adolescents [START_REF] Schneider | Y a-t-il une littéracie adolescente? Spirale[END_REF] ou littéraires [START_REF] Mackrous | Écriveuses du Web : abondance et remix[END_REF]

L•écriture de la chronique : au c•ur d•une constellation de pratiques de littéracie

La mise en discours des pratiques d•écriture et de lecture dans les récits

Dans le récit des petits et grands faits du quotidien auquel se livrent les chroniqueuses, les pratiques de lecture et d•écriture occupent une place de choix. Les descriptions et commentaires qui les accompagnent nous renseignent sur les représentations qui y sont associées. À côté des écritures papier, assez circonscrites, ce sont surtout des écrits sur supports numériques qui sont mentionnés.

Le support papier, s

  Didactique des langues, des textes et des cultures -EA 2288 -Nadja Maillard-De La Corte Gomez : CIRPaLL, EA 7457. Recherche conduites dans le cadre du projet Gedi (GEnre et DIscriminations sexistes et homophobes), porté par la SFR Confluences de l!Université d!Angers et financé par la Région Pays de la Loire.

* Affiliations scientifiques :

-Violaine Bigot, DILTEC -

. Les chroniques, une pratique d•écriture complexe et dialogique Rappelons

  brièvement quelques-unes des caractéristiques communes à ces récits autobiographiques, qu!illustre très bien la chronique de Petite Cendrillon. Les récits s!organisent autour d!un certain nombre de thématiques (mais aussi de figures et de situations) récurrentes, circonscrivant assez précisément le genre : importance de l!environnement urbain, celui de la « cité », dans une moindre mesure de l!école ou du Les circonstances précises dans lesquelles elle a renoué avec Hatem restent tues, et elle annonce qu•elles feront l•objet d•une « after chro ». Elle joue aussi avec le pacte de véracité lorsqu•elle livre une partie (104), dont elle annonce ensuite qu•elle est en fait fictive et provoque amicalement ses lectrices en se déclarant affranchie de la nécessité de « plaire à son lectorat » (« Encore "désolée" pour cette petite blague que j•ai beaucoup apprécié mdr. Tant que moi j•apprécie c•est le principal ptdr.»).Cette écriture, dont nous avons aussi montré dans les travaux précédemment mentionnés les caractéristiques communes avec l•écriture des feuilletons (texte très long, publié en épisodes reliés entre eux par

	chroniques peut éclairer la réflexion didactique sur le développement des 2. L•
	compétences de littéracie des élèves.
	de cette multimodalité. Enfin, pour étudier la superposition des situations de communication que génère l•emploi simultané d•échanges numériques et d•échanges verbaux vocaux, et pour mieux comprendre les compétences langagières spécifiques que génèrent ces situations de communication complexe, nous avons mobilisé les outils conceptuels définis initialement par Goffman pour conduire l•analyse des cadres participatifs (Kerbrat-Orecchioni, 1990). L•écriture de chronique, et, plus largement, la participation aux activités langagières numériques autour des chroniques (lecture, critique, inventaire, republication, etc.) constituent des pratiques d•écriture complexes et dialogiques. Dans une première partie de l•article, nous nous interrogerons sur l•intérêt, pour notre étude, de mobiliser la notion de littéracie, dont Hébert et Lépine (2013) indiquent qu•elle permet de penser « un ensemble d•attitudes, de connaissances, d•habiletés et de compétences qui sont [!] à mesurer ou à situer dans une dynamique 1est un
	espace/temps et dans une visée émancipatrice du développement de la touns » part. 1). Les lectrices « entrent » même dans les chroniques
	personne » (p. 25). Dans un deuxième temps, nous nous intéresserons à lorsqu•elles sont remerciées, en début d•épisode, pour les photo-
	l•écriture multimodale qui caractérise les chroniques. Nous nous montages qu•elles ont réalisés (par exemple, partie 42 : « Merci à ma
	focaliserons ensuite sur la place qu•occupent l•écriture et la lecture dans chérie MiiNii PiiZz pour son jolie dessin encore une fois, tu déchires
	ces récits de la vie quotidienne et notamment la manière dont l•écriture hbiba émoticône heart »). Si le texte des chroniques reste l•espace
	et la lecture de chroniques sont mises en abyme dans le récit lui-même. réservé de la chroniqueuse, la multimodalité de ces publications, à
	Enfin, dans un dernier temps, nous nous demanderons dans quelle laquelle nous allons nous intéresser maintenant, crée quant à elle un
	mesure l•étude d•une pratique littéraciée extra-scolaire telle que celle des espace de cocréation avec les lectrices.

travail; des relations familiales, amicales et amoureuses (notamment les amours empêchées entre la chroniqueuse et un mauvais garçon, un « thug »); de la religion; de la mixité culturelle et linguistique. L!incipit, dont le format se retrouve de chronique en chronique et semble particulièrement routinisé, vise à nouer le contact avec les lectrices (il débute souvent par des salutations) et à présenter la chroniqueuse et son entourage; s!y noue aussi, dans le cas des chroniques « réelles », un « pacte autobiographique »

(Lejeune, 2005, p. 31)

.

Dans le cas de Petite Cendrillon, le récit s!ouvre alors que Souad (la chroniqueuse) a « dans les 15 ans » (« J!venais de quitter le collège et j!partais en seconde au lycée. c!était donc les vacances d!été ») et se clôt sept ans après alors qu!elle vient de terminer ses études (« Je vous ai raconté 7 ans de ma vie »). Souad se présente dans l!incipit comme une « jeune fille musulmane d!origine tunisienne » et retrace ses amours tumultueuses avec Hatem, finalement devenu " au moment où elle écrit la chronique " son mari et le père de ses enfants. À l!exemple des autres chroniques que nous avons pu étudier, le récit suit pas à pas la chronologie des évènements, sous une forme, classique, de narration que l!on pourrait qualifier avec G.

[START_REF] Genette | Figures III[END_REF]

d!ultérieure : le narrateur y raconte ce qui lui est arrivé, dans un passé proche ou plus lointain. Néanmoins, dans les derniers épisodes, elle joue avec les codes, notamment en opérant une ellipse entre les parties 122 et 123. Dans la partie 122, elle se décrit très déprimée par ses échecs sentimentaux et raconte son entrée dans l!écriture de la chronique qui l!aide à mieux comprendre ce qu!elle a vécu. Après une ellipse, qui inclut donc les mois d!écriture de la chronique, elle nous apprend dans la partie 123 qu!elle est mariée puis révèle le nom de l!élu dans la partie 124 (« Hatem, à ce qu!il parait c!était mon évidence, c!était écrit d!avance /#/ c!est lui mon mari, c!est lui qui me rend heureuse. »). La question posée dès l!épisode 1 (« Et oui oui oui, toute la ptite famille et mariée, et moi? vous le saurez dans la suite# ») trouve sa réponse après 123 épisodes. des effets de suspens), présente des qualités attendues et commentées par les lectrices qui constituent des caractéristiques du « genre ». Parmi celles-ci, nous nous sommes notamment intéressées à la capacité des chroniqueuses à faire entendre la voix de leurs personnages, dont elles mettent en évidence des traits saillants (accent, lexique, tics langagiers, etc.). De manière générale, la « justesse » des dialogues fait partie des critères le plus souvent mis en avant par les lectrices lorsqu•elles commentent les chroniques. L•analyse des chroniques elle-même montre que la variation stylistique et le parler plurilingue (translanguaging)

(Garcia, 2009)

comptent parmi les ressources d•écriture des chroniqueuses et révèlent leur capacité à utiliser la diversité de leur propre répertoire langagier comme ressource stylistique pour créer des situations humoristiques, faire avancer la narration ou « camper » les personnages

(Bigot et Maillard, 2017a)

. L•écriture des chroniques se caractérise aussi par sa forte interactivité avec le lectorat, évidemment étroitement liée aux finalités et aux fonctionnalités des réseaux sociaux sur lesquels elles s•inscrivent. Les chroniqueuses maintiennent étroitement le contact avec leurs lectrices, en animant régulièrement la page de la chronique et en répondant aux commentaires qu•elles postent. Mais ce dialogue se retrouve aussi dans l•écriture même des épisodes. Les lectrices sont systématiquement invitées à « lire et faire tourner » et sont interpellées dans des jeux d•écriture dialogique (« Comme vous l•avez compris, Hatem c•

écriture multimodale des chroniques : un espace de cocréation?

  Trois des drapeaux du Maghreb. À partir de la partie 38 sont publiées, de plus en plus fréquemment, des photos (dans lesquelles est incrusté du texte, dont le titre de la chronique) envoyées par les lectrices. Ces dernières, dès la partie 41, sont systématiquement remerciées au début de la partie lorsqu•un de leurs montages est publié. De la partie 63 à la partie 111, toutes les photos qui servent de support à l•épisode sont un envoi de lectrice. De la partie 111 à la partie 123 la chroniqueuse multiplie le nombre de photos associées à son texte (de 2 à 7 selon les parties) probablement pour pouvoir intégrer plus de « montages » de lectrices. Onze de ces montages sont en fait des photos d•affichettes manuscrites sur lesquelles les lectrices ont repris le titre de la chronique, ajouté un sous-titre de leur choix, un dessin, un slogan (par exemple « l•amour avec un grand A »), le nom des personnages. Ces photos d•affichettes réalisées sur papier (parfois des feuilles dont le format scolaire est reconnaissable par le quadrillage Seyès et la perforation) font toutes écho à la photo de la première partie, qui sert de « couverture » à l•album où la chronique est rangée dans la page Facebook : une feuille sur laquelle est écrit à la main « Salamaleikum », en alphabet latin, avec une graphie de type « graffiti », et souligné d•une volute évoquant la calligraphie arabe. Les premiers mots de cette première partie « salut, salam, shalom, namasté etc etc. » reprennent et développent cette « salutation » de la photo d•accueil. Cette photo de couverture offre un écho graphique à la pratique de translanguaging présente dans l•ensemble de la chronique et posée dès les salutations initiales, montrant la capacité des chroniqueuses à mobiliser des ressources plurilingues et plurilittéraciques pour construire linguistiquement un contexte de communication marqué par l•interculturalité. Elle donne aussi à voir, tout comme les fréquentes photos de pages écrites manuellement, Si dans de nombreuses chroniques, les illustrations sont simplement « copiées-collées » d•un autre site, ce n•est pas le cas dans Petite Cendrillon. La chroniqueuse effectue un travail graphique sur les clichés : passés en noir et blanc, le bord du cadre flouté, pour certains recadrés. Les textes insérés dans les photographies témoignent de ce travail de réutilisation et de réappropriation des sources existantes, que l•on peut rapprocher de la culture « remix », que Mackrous identifie comme l•une des caractéristiques des écritures du Web : Le rôle central du texte, tout au moins pour les lectrices, apparaît de manière encore plus évidente dans les « republications » des récits qu•elles font (cf. infra). Il n•est pas rare en effet que les illustrations initialement choisies par la chroniqueuse soient modifiées ou supprimées.

	De manière générale, le remix consiste à combiner ou à éditer du matériau Les chroniques pourraient être envisagées comme un « iconotexte », « un
	Les chroniques peuvent sans conteste être mises au rang des littéracies multimodales. préexistant pour créer quelque chose de nouveau (Navas, 2010) /•/ Le message mixte, un ensemble formant une unité signifiante à part entière, numérique permet plus que jamais à tous de s•approprier des éléments de sa dans laquelle le linguistique et l•iconique se donnent comme une totalité culture pour les transformer, les interpréter, les partager. On peut insécable, mais dans laquelle ils conservent chacun leur spécificité littéralement écrire avec les images, les sons, les vidéos. (2014) propre » (Lugrin, 2006, p. 65). Néanmoins, cette catégori-sation serait à La multimodalité se caractérise [•] par la présence de différents modes La fonction de ces illustrations par rapport aux épisodes de la chronique nuancer, dans la mesure où texte et illustration ne sont, justement, pas iconiques, linguistiques et auditifs. Elle est toujours au moins à deux est variable. Ce sont indéniablement des « produits d•appel » puisque complètement « insécables » et n•ont pas vraiment le même statut. Si les niveaux : premièrement, on a une juxtaposition ou combinaison de c•est en cliquant sur la photographie que l•on accède au texte. On photos constituent un espace de cocréation potentiellement « alimenté » différents modes et, deuxièmement, ces mêmes modes ont une nature retrouve deux des trois modes de juxtaposition des photos et des textes par les lectrices, le récit lui-même reste un espace absolument réservé à multimodale (une séquence vidéo, par exemple, comprend images animées et sons, les deux étant livrés conjointement). (Lebrun et Lacelle, 2012, § 6) que distingue Van der Linden. Les photos peuvent être parfois chroniqueuse.
	redondantes par rapport au texte qui les accompagne (« les contenus Comme toutes les pages Facebook, les pages « d•accueil » des sémantiques se trouvent • totalement ou partiellement • superposés »),
	mais elles sont plus souvent complémentaires (« texte et image
	participent conjointement à l•élaboration du sens »). Elles ne sont jamais
	dissociées (« sens du texte et de l•image divergent ») (Van der Linden,
	2008, p. 53). Les « décors » des scènes sont rarement décrits dans les
	linguistique,
	religieuse, de parcours migratoire familial•), caractéristique des cités
	dont les chroniqueuses font souvent l•éloge, peut constituer un fil de
	lecture des photographies de Petite Cendrillon. Si les photos d•hommes
	et de femmes de types méditerranéens dominent, on trouve aussi un
	couple asiatique, plusieurs couples de type nord-européen et les jeunes
	femmes voilées alternent avec des jeunes femmes dont les cheveux et le
	corps sont montrés (larges décolletés, jupes courtes•).

chroniques entremêlent photos et texte pour donner la « tonalité » de la page. Ainsi, sur la page Petite Cendrillon amoureuse du Prince du Ghetto (chronique), le titre de la chronique, incrusté dans la photo de profil (le pied d•un bébé embrassé par une bouche d•homme), est également superposé à la photo de couverture (un homme et une femme voilée de dos dans une voiture) où il apparaît avec trois typographies différentes, dont une où se mêlent des signes diacritiques évoquant l•écriture de l•arabe. Les posts du journal, qui permettent à la chroniqueuse d•animer sa page, s•agrémentent eux aussi régulièrement de photographies, d•illustrations, de liens vers des vidéos 3 . La chronique stricto sensu se compose quant à elle de 126 « parties » (ou épisodes), qui associent systématiquement un texte et une image. Publiée sur le journal de la page entre octobre 2011 et mars 2012, elle est aussi accessible sous la forme d•un « album » placé dans la rubrique « photo » de la page.

Ces illustrations sont en majeure partie des photographies de jeunes hommes et de jeunes femmes (le plus souvent un sujet en plan moyen ou américain, quelquefois un groupe). Sept clichés représentent uniquement un paysage urbain (barre d•immeubles), deux autres un paysage méditerranéen. Sept reprennent des personnages de dessins animés (notamment Cendrillon). la « pâte manuscrite ». À l•instar des écrivains numériques plus « légitimes », étudiés par Bonnet, les chroniqueuses révèlent ainsi leur sensibilité à la « matérialité originelle » de l•écriture (2015, p. 138).

Les photographies ont quasiment toutes été prélevées sur le Web sans mention de source. À une lectrice qui lui demande où elle a trouvé la photo de la partie 35, la chroniqueuse répond : « je l•ai pu la photo en original lol je l•avais trouvé sur google mais sa fait longtemps et je sais pu ce que j•avais écri ». La seule photo dont la source soit indiquée est celle de la partie 60 (Soprano sur une scène de concert) : « Il s•agit d•une tof perso donc piquez la pas mdr, le coeur que fait Sopra il m•était destiné car j•étais dans le public mdrrrrr /!/ c•est moi qui est prise la photo a l•un de leur concert ». chroniques, mais les nombreuses photos de sites évoquent des lieux dans lesquels se déroule l•action (photographie de grands ensembles urbains, de paysages tunisiens, de cellules de prison). Toutefois, puisque l•anonymat est de rigueur dans la chronique

[START_REF] Bigot | Les chroniques : étude exploratoire d•un genre d•écriture (très) populaire sur le net[END_REF]

, les lieux ne sont pas identifiés dans les récits ni identifiables dans les photos. Les portraits ne représentent pas non plus les « vraies » personnes mentionnées dans les chroniques autobiographiques, mais sont pris sur Internet en raison d•une ressemblance ou de traits partagés avec les personnes décrites dans la chronique (Part 38 : « j•ai mis cette photo parce qu•en sah elle ressemble trop trop trop à Farah lol »). Le lecteur connaît le code et le rapport avec les photographies n•est donc jamais celui d•une redondance absolue. Des stars du rap et du rythm•n•blues, français et américain (Kayna Samet, Tyssem, Kayliah, Usher, etc.), sont sollicitées à titre d•icônes et leur nom n•apparaît qu•occasionnellement dans les commentaires des lectrices. De nombreuses illustrations renvoient, plus largement, aux thématiques privilégiées par la chronique : l•amour, le couple, l•univers des cités, la religion, certains pays d•où sont originaires les familles... La diversité (

  •il n•est pas absent d•une chronique comme Petite Cendrillon, reste cependant cantonné à des usages précis : documents administratifs, communication avec des pairs emprisonnés, travail scolaire. Ce dernier usage du papier est le plus présent, et le lien entre papier et travail scolaire apparaît comme particulièrement fort. Lorsque Souad veut faire croire à son frère qui l•interroge sur son emploi du temps qu•elle a révisé tout l•après-midi, elle lui tend un « vieux brouillon », comme preuve du travail accompli. Lorsqu•Hatem lui donne son nouveau numéro de téléphone, c•est sur un petit bout de papier qui lui fait penser à une « antisèche ». Dans une difficile période de révision avant examens, « ouvrir les cahiers », se mettre « devant les cahiers » devient synonyme de « se mettre à réviser », même si la référence aux objets emblématiques de l•école et aux gestes qui marquent l•intention de « réviser » est aussi une manière de dire en creux que l•activité cognitive de révision ne « suit » pas. Et si son rapport de stage est finalement rédigé sur l•ordinateur, son impression, les « ramettes de papier » et « l•encre » nécessaires pour imprimer les trois exemplaires qui lui sont demandés occupent tout un paragraphe de la chronique.Les réseaux sociaux, dans lesquels les chroniqueuses communiquent, au début des années 2010, essentiellement par des messages écrits, sont en revanche très présents dans une chronique comme Petite Cendrillon; ils y sont décrits comme des espaces parallèles de communication. Dès que Kamel, un garçon dont Souad fait la connaissance, obtient son adresseMSN, il l•ajoute et « vient [lui] parler ». Souad va ensuite « sur l•ordi en espérant y trouver Kamel » qu•elle surnomme ensuite à plusieurs reprises « le skoiteur », parce que lorsqu•elle se connecte sur MSN, elle est toujours sûre de l•y retrouver. Après une période où elle n•a plus échangé avec ses amis (sur MSN ou par SMS), elle refait « un petit tour » et ses amis se réjouissent de son « retour ». On voit donc se tisser une métaphore filée (et partiellement usée dans le langage des utilisateurs?) du déplacement pour désigner les différentes pratiques qui ont cours dans ces espaces numériques. Et les traces plus ou moins pérennes que laissent les messages écrits envoyés par les uns et les autres contribuent à construire cet « espace » où l•on retrouve ses amis. La chronique de Souad témoigne d•une pratique observée par Schneider (2014) dans son étude ethnographique : la relecture des messages reçus, qui permet de « revivre » des émotions provoquées au moment de l•échange initial, mais aussi de « dépasser » ces émotions. Dans la partie 12, ayant reçu un message de Hatem qui la touche, elle explique qu•elle relit « au moins 100 fois le message avant de lui répondre ». Dans la partie 25, elle en reçoit un autre : « passe une bonne nuit hbiba! ». Dans la bouche de celui qu•elle aime mais avec lequel les relations sont compliquées, l•emploi de l•appellatif affectueux « hbiba » suspend momentanément le récit : « naaaaaaaaaaaaaaaaaaa il m•a dit hbiba, atta atta, faut j•relise ohhh boule de chit il m•a dit hbiba ». Avec la transcription ortho-graphique de l•allongement vocalique du « na », les effets de répétition de « il m•a dit hbiba » et de « atta », la chroniqueuse fait partager au lecteur le temps qui s•arrête sous l•effet d•une forte émotion et révèle l•importance de ce message en apparence anodin. On est loin de la communication phatique, inutile, perdue dans la quantité des messages, à laquelle les échanges pléthoriques par SMS des adolescents sont souvent assimilés(Schneider, 2014, p. 64). modes de communication écrite renouvellent donc les modes de construction des relations et de réflexivité par rapport à la construction de la relation. Si dans les chroniques, la réflexion métalinguistique sur l•écriture des messages est généralement assez limitée à des commentaires du type « j•vais faire simple » (quand elle doit répondre au message où il a dit hbiba), le fait d•écrire ou de ne pas écrire est souvent mûrement réfléchi, et peut même faire l•objet de longs échanges entre amis, sur le thème « je lui réponds ou non? » (Partie 50 : « J•hésite pendant une bonne heure, j•écris le message et j•l•efface aussitôt. Donc au bout d•une bonne heure, j•me lance et j•lui envoie le message. »).Outre la possibilité de créer des espaces de communication parallèles à celui de la communication en coprésence dans lesquels il est possible de revenir se promener à loisir, la communication instantanée écrite permet, dans le cadre même de la coprésence en un lieu, de jouer subtilement sur les différents statuts que peut occuper un participant. Goffman (dans Kerbrat-Orecchioni, 1990, p. 86) proposait, pour construire l•analyse du cadre participatif d•une interaction verbale, de distinguer participants ratifiés, qui peuvent être alternativement « addressed » ou « nonaddressed » et participants non ratifiés dont la présence peut être connue des participants ratifiés à l•échange (par exemple la foule qui entoure deux personnes en train d•échanger dans un lieu public) ou non connue (lorsque des personnes entendent sans être vues, et donc à l•insu des participants à l•échange). Lorsqu•à une table pendant un repas (Petite Cendrillon, partie 15), des personnes s•envoient des SMS, elles créent de facto un deuxième cadre participatif puisque les convives exclus de la « conversation sms » sont non seulement « non-adressed » mais qu•ils perdent également leur statut de participant ratifié à cet échange, et que le recours à l•écrit et à l•outil technologique permet qu•ils n•en soient même pas les récipiendaires non ratifiés. On a ainsi quasiment le procédé inverse du témoin caché (dissimulé derrière un paravent par exemple) qui sur une scène de théâtre entend les dialogues sans être vu, mais dans une forme de connivence avec le public (qui le voit). Avec ce procédé, les chroniqueuses mettent les lecteurs dans la connivence de leurs échanges écrits et lus, « à la barbe » des autres convives. Les chroniqueuses et leurs pairs sont donc dépeints dans les chroniques comme des communicants exploitant pleinement les ressources des outils numériques de la communication écrite, et ces superpositions d•espaces de communication constituent une ressource d•écriture que les chroniqueuses savent mettre au service de leur récit. L•annonce, en fin d•épisode, d•un SMS reçu ou lu par un des protagonistes constitue un ressort de suspens très classique dont elles jouent. Il arrive aussi que les chroniqueuses mettent leurs propres pratiques de littéracie en abyme, se racontant en train d•écrire leur chronique ou d•en lire. Ainsi, lorsque Souad explique combien elle est perturbée de se découvrir amoureuse de deux garçons, situation qu•elle qualifie à deux reprises de « chelou », elle se sort du difficile travail d•introspection par une pirouette d•écriture : « C•est vrai j•les aime pas d•la même façon mais j•sais pas c•est chelou. Hassilou, j•vais pas en faire une partie, j•ai une chronique à écrire » (Partie 33). Plus tard, dans la partie 114, elle revient sur sa découverte de l•univers des chroniques, comme lectrice, en 2011. Elle raconte son intérêt croissant pour les chroniques qu•elle lit à partir d•un « faux » compte créé uniquement pour cela. Rapidement passionnée par cette lecture, elle explique sa difficulté à démarrer l•écriture de son rapport de stage par le fait qu• « il passait après [sa] lecture de chronique ». Elle termine ensuite l•épisode 121 en racontant comment, désespérée par sa situation amoureuse, elle s•est mise « à écrire ». L•épisode suivant commence par un commentaire amusé sur les doutes qu•a pu susciter son emploi intransitif du verbe « écrire » : « En sah, [•] j•pensais pas que ça aller vous créez un suspense mdr. Quand j•ai fini par j•ai écris, dans ma tête c•était tellement logique que j•parlais de la chronique que j•ai pas précisé lol. Après j•ai vu certaine cogiter, zehma elle a écrit quoi? Une lettre? Quoi? Donc volontairement j•vous ai laissé réfléchir lol. » une résistance aux pratiques d•écriture dans ce qu•elles supposent de rapport au monde, de valeurs » (Bautier, 1997, p. 10). Que l•explosion de la communication sur les réseaux sociaux ait révélé des pratiques d•écriture jusque-là cachées, ou qu•elle soit la cause de leur développement, il semblerait difficile aujourd•hui de parler de manière aussi radicale de « résistance aux pratiques d•écriture », d•incapacité à sortir d•une écriture brève « parce qu•ils font par écrit ce qu•ils ont l•habitude de faire oralement en termes de pratiques socio-cognitives et langagières » (1997, p. 12). Si tous les élèves n•écrivent pas de chroniques, l•étude de Perret et Massart-Laluc (2013) sur les pratiques d•écriture de jeunes de lycées professionnels montre « la variété et la quantité d•écrits produits par des élèves qui affichent à l•école de faibles performances à l•écrit et continuent d•affirmer, contre toutes données objectives, ne pas écrire » (p. 116). Or, si l•on veut que les enseignants puissent « réconcilier l•élève avec le sujet scripteur [•] en prenant en compte, dans la construction du rapport à l•écriture toutes les dimensions psychologiques, sociales et cognitives interagissant dans l•acte d•écrire » (Perret et Massart-Laluc, 2013, p. 105), il semble indispensable d•apprendre à connaître les pratiques de lecture et d•écriture dont les élèves sont familiers, car c•est à partir de ces pratiques et des modes de transmission horizontale qu•elles nous révèlent que l•école pourra refonder et développer sa didactique de la littéracie.On peut dès lors estimer que les chroniques permettront de penser les enjeux didactiques du développement des compétences de littéracie dans une perspective qui n•aborde pas l•élève dans la logique pédagogique de la tabula rasa. La découverte, par les enseignants, du phénomène des chroniques, peut fonctionner comme une « alerte » pour leur faire prendre conscience de l•écart entre leurs représentations des activités langagières de leurs élèves et la « réalité ». Papen, dans l•échange qu•elle mène avec Collette sur la question des New Literacy Studies, souligne l•intérêt pour les enseignants d•engager leurs élèves dans une approche réflexive de leurs pratiques de littéracie, et de tenir compte des « ressources que constituent leurs expériences avec ces pratiques » : « Ils ont déjà des compétences et je crois que l•enseignant devrait si possible développer des activités sur la base de ces compétences et expériences, pour pouvoir établir des liens entre ce que les élèves savent déjà, leurs expériences et les contenus enseignés à l•école »(Papen et Collette, 2013, p. 150). L•étude des chroniques comme un genre d•écriture à part entière est ainsi susceptible d•aider des enseignants à dépasser des oppositions clivantes et peu productives sur le plan didactique, que ce soit l•opposition oral-écrit déjà évoquée, ou celle entre écriture « ordinaire » et littéraire. Sans survaloriser, ni dévaloriser, ces formes d•écritures populaires (comme le recommande Prévost, 2011, à la suitede Reuter, 1998), il pourra être intéressant de solliciter tant les chroniques que les échanges qui les accompagnent en ligne (commentaires des lectrices notamment), par exemple pour faire le lien avec des grandes thématiques classiquement traitées dans les programmes du secondaire, comme « l•écriture de soi et l•autoportrait » (programme français de 2016, classe de 3 e ), ou plus largement pour engager une réflexion sur les compétences à mettre en !uvre pour écrire un récit. La confrontation, dans le cadre scolaire, à des textes dont l•orthographe est peu respectueuse des normes « académiques » du français attendu à l•école risque certes de soulever des réticences importantes, mais il est possible d•engager avec les élèves une réflexion métalinguistique stimulante sur la question (dimension arbitraire d•un certain nombre de normes orthographiques versus nécessaire respect d•une norme pour l•intelligibilité de la communication, typologie des « erreurs » du point de vue de leurs formes et de leurs possibles sources, etc.) nourrie éventuellement par les nombreuses discussions des lectrices et des autrices dans leurs échanges sur les textes des chroniques.

	l•univers de banlieue associées à l•oral s•oppose à un autre univers, celui de « l•écrit », de « la réflexivité, de norme maîtrisée et d•élaboration conceptuelle satisfaisante » (2012, p. 72). Des travaux, qui, en France, font référence pour la réflexion sur les inégalités scolaires, s•inscrivent, en un certain sens, dans cette perspective. Par exemple, Bautier, réfléchissant sur les difficultés rencontrées par les nouveaux lycéens dans les quartiers « de banlieue », soulignait, en 1997, que l• « "aisance" à l•oral » de ces jeunes, leur facilité, voire leur « revendication » à prendre la parole s•accompagnent Ces 5. Ouverture d• «
	Les chroniques, en tant que pratique d•écriture et de lecture, mais aussi
	par ce qu•elles nous donnent à voir de ces pratiques (dans la mise en
	récit des actions du quotidien liées à l•écriture-lecture et dans les
	dialogues rapportés), constituent donc une riche source d•information
	pour mettre au jour « la complexité de la place de l•écriture dans la vie
	adolescente » (Schneider, 2014, p. 69).
	Elles offrent notamment l•opportunité de déconstruire les représentations
	stigmatisantes et figées qui ont souvent cours lorsqu•il s•agit d•évoquer
	le rapport des jeunes des classes populaires au langage en général, et à
	l•écrit en particulier. En effet, les discours médiatiques et politiques !
	voire certains travaux universitaires ! tendent à présenter la banlieue
	comme « territoire de la tchatche ». Comme le note Mori : « les
	pratiques d•écriture des jeunes en banlieue sont le plus souvent évoquées
	! quand elles le sont ! d•un point de vue normatif et sous l•angle d•une
	non-écriture ou d•une sous-écriture. » (2012, p. 71). Elle montre en outre
	que cette construction s•inscrit dans un système de représentations plus
	large, où la « spontanéité, la vivacité et parfois même [la] brutalité » de

Petite Cendrillon ne propose qu•un seul lien musical dans le texte de la chronique contrairement à d•autres chroniques qui renvoient régulièrement le lecteur vers les musiques citées. En revanche, la page de Petite Cendrillon, comme les autres chroniques, renvoie, à différents moments (dans les parties, dans les messages postés sur le fil d•actualité, etc.) vers d•autres chroniques dont elle recommande la lecture.

En ce sens, il semble pertinent, lorsqu•on s•interroge sur le rôle joué par la notion de littéracie en didactique du français, de prendre en compte « le changement de point de vue qui s•est opéré dans la pensée des relations entre oralité et écriture dès lors que les cultures écrites ont cessé d•être minoritaires » (Chiss, 2012, p. 223). Dans une société où les pratiques de littéracie sont omniprésentes, l•illettrisme ou tout au moins les difficultés de l•école à développer les compétences de littéracie prévues par les programmes, ne peuvent plus simplement s•expliquer par le « fossé qui sépare la tradition littératienne prévalant à l•école publique des traditions orales, très différentes, souvent en pleine contradiction avec les précédentes, propres à la famille de l•élève et à ses pairs » (Goody, 1968, cité par Chiss, 2012, p. 223).


Arnold Maestre

Christian Bessiere

Improving Asynchronous Backtracking for Dealing with Complex Local Problems

Distributed constraint satisfaction, in its most general acceptation, involves a collection of agents solving local constraint satisfaction subproblems, and a communication protocol between agents, in order to allow the distributed system converge to a global solution. The literature, however, often concentrates on the reduction where each agent owns exactly one variable, under the rationale that the corresponding algorithms are easily extended to the most general case. While this is mostly true, the specificities of agents handling local CSPs give way to numerous improvements, since a tradeoff becomes possible between local and distributed search effort. In this paper, we seek to improve nogood learning and solver cooperation in multi-variables distributed constraint satisfaction problems. We propose incremental improvements to be implemented on top of an ABT-like algorithm, and make experimental evaluations of the performance improvement they bring.

INTRODUCTION

Constraint satisfaction is a powerful paradigm for solving combinatorial problems. It has been widely used for modeling problems in artificial intelligence and solve real world problems. The increasing interest in distributed computing has led to distributed approaches of the constraint satisfaction problem (DisCSP), where the global problem is naturally distributed among a set of agents, which then have to communicate in order to match their local solutions.

Those approaches can be classified following a set of characteristics: search control (centralized or distributed), communication protocol (shared memory or message passing), memory requirements (polynomial or not), completeness and agent or variable ordering (static or dynamic). Additionally, DisCSP solvers are said to be variable-based when each agents cares for a given subset of the variables, or constraint-based if the focus is put on constraints being distributed among agents.

In the following, we will focus on complete, statically ordered, variable-based, message passing distributed CSP algorithms with decentralized control. This field is dominated by the algorithms of Yokoo and colleagues, asynchronous backtracking (ABT) [START_REF] Yokoo | Distributed constraint satisfaction for formalizing distributed problem solving[END_REF], asynchronous weak commitment (AWC) [START_REF] Yokoo | Asynchronous weak-commitment search for solving distributed constraint satisfaction problems[END_REF] and distributed break-out (DB) [START_REF] Yokoo | Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems[END_REF]. A pioneer algorithm in the field, ABT is a statically ordered, asynchronous protocol in which high priority agents propose values to lower priority ones, that can refute them with a nogood in case of inconsistency. It has been shown to be complete under polynomial space constraints.

In AWC, agents communicate with all their neighbors and reorder themselves dynamically in order to soften the influence of a bad 1 LIRMM-CNRS 161, rue Ada, 34392 Montpellier Cedex 5, France.

Email: maestre|bessiere@lirmm.fr choice from a high priority agent. Although AWC is incomplete unless agents can store a potentially exponential number of nogoods, Silaghi et al have shown in [START_REF] Silaghi | Abt with asynchronous reordering[END_REF] that it is possible to build a polynomial space algorithm with dynamic reordering as soon as one accepts to bound the maximum time from start during which an agent can be reordered.

Finally, DB works in synchronous phases, where agents in a neighborhood agree on the local move bringing the best improvement to the current state of the system and increase the weight of violated constraints in order to escape local minima.

All these protocols are applied to variable-based distributed problems. Although the generic framework for such problems makes it possible for one agent to own several variables, few works explore the specificities of complex local subproblems, namely the complexity of agent instantiation, which can no longer be seen as a quasiinstantaneous operation, the increasing necessity of agent collaboration, and the generation of meaningful nogoods. Instead, most of these works focus on the ordering of agents and/or variables, which is typically even more important when the granularity of local agents increases, and is indeed a good way to improve performance. In [START_REF] Armstrong | Dynamic priorization of complex agents in distributed constraint satisfaction problems[END_REF] the authors use different heuristics to statically order or dynamically re-order complex agents running a specialized hybridation of ABT and AWC. In [START_REF] Yokoo | Distributed constraint satisfaction algorithm for complex local problems[END_REF] this concept is pushed further with the multi-AWC algorithm, based on AWC, and individual variables, rather than agents, are re-ordered to improve search efficiency. Likewise in [START_REF] Hirayama | Local search for distributed sat with complex local problems[END_REF], multi-DB, a multi-variable variant of the distributed break-out algorithm is proposed, which performs well compared to multi-AWC on 3-SAT benchmarks.

In [START_REF] Hirayama | The phase transition in distributed constraint satisfaction problems: First results[END_REF], the authors evaluate the computational effort and network load needed to solve distributed 3-coloring problems with varying numbers of intra-agent and inter-agent constraints. The algorithm used is a clever extension of ABT, which minimizes the number of messages sent by avoiding those that are trivially unnecessary, but doesn't take into account the issues inherently linked to the complexity of local problems. Silaghi addresses some of these issues in [START_REF] Silaghi | Asynchronously solving distributed problems with privacy requirements[END_REF], where he proposes various solutions: interruptible backtracking, message queues processed by compactors in order to reduce the number of messages effectively handed to the core agent, and communication policies in order to cool down message bursts.

None of these works, however, insist on producing interesting nogoods from conflicting multi-variable agents, nor do they explore the collaboration between complex agents when a new instantiation is to be chosen. Actually, each new instantiation, if different from the previous one, produces a new batch of messages to be sent to lower priority agents, which in turn may have to change their instantiation. In the multi-variable case, the problem is a bit different, since a carefully chosen instantiation may allow the agent to inform only a subset of its lower priority neighbors. The cost of message passing being (in the most general case) prohibitively higher than the cost of local computation, it seems interesting to make a bit more local computation to save some messages (aka stay and play) rather than going with the first feasible local solution (aka scoop and run). In particular, if a solution exists which allows the agent to satisfy all constraints while minimizing the number of changes to variables linked to lower priority agents, it should be preferred over a more disturbing one.

In the following, we will explore those issues, and provide ways to produce high quality nogoods and cooperative instantiations in a distributed constraint satisfaction problem with multiple variables per agent. We will then present an experimental framework, as well as an empirical evaluation of our work.

PRELIMINARIES

In a centralized setting, a constraint network is defined by a triple (X , D, C), where X is a set of n variables, D is the set of their respective finite domains whose size is at most d, and C is a set of constraints. A constraint is a relation over a subset of variables, which defines the combinations of values deemed acceptable for those variables. In the following, we will restrict our attention to constraints involving two variables, namely binary constraints. A constraint among the variables xi and xj will be denoted by cij. A solution is an assignment of values to variables which satisfies every constraint. The constraint satisfaction problem (CSP) is generally formulated as finding a solution to the constraint network. This is usually done by a combination of tree-search with backtracking, look-ahead and backjumping techniques.

A distributed constraint satisfaction problem (DisCSP) is a CSP where the variables, domains and constraints of the network are distributed over a set of autonomous agents. Formally, a variable-based distributed constraint network is defined by a 5-tuple (X , D, C, A, ϕ), where X , D and C are as before. A is a set of p agents, and ϕ : X → A is a function that maps each variable to its agent. Each variable belongs to one agent. The distribution of variables divides C in two disjoint subsets, Cintra = {cij|ϕ(xi) = ϕ(xj)}, and Cinter = {cij|ϕ(xi) = ϕ(xj)}, called intra-agent and inter-agent constraint sets, respectively. An intra-agent constraint cij is known by the agent owner of xi and xj, and it is unknown by other agents. Usually, it is considered that an inter-agent constraint cij is known by the agents ϕ(xi) and ϕ(xj) [START_REF] Yokoo | The distributed constraint satisfaction problem: Formalization and algorithms[END_REF][START_REF] Hamadi | Backtracking in distributed constraint networks[END_REF]. As in the centralized case, a solution of a DisCSP is an assignment of values to variables satisfying every constraint. The agents are ordered, as it is the case in ABT. An agent A k before A l in the ordering is said to have higher priority than A l . We suppose the variable ordering is consistent with the agent ordering: if xi belongs to agent A k and xj belongs to

A l , xi is before xj in the ordering if A k is before A l . Γ -(k) (resp γ -(k))
is the set of agents (resp. variables) constrained with variables belonging to agent A k and appearing before it in the agent ordering. Conversely, Γ + (k) (resp. γ + (k)) is the set of agents (resp. variables) constrained with variables in A k and appearing after it in the agent ordering. In the case of non-trivial, ordered agents, the subproblem Π k to be solved by A k is composed of all variables belonging to A k , its intra-agent constraints as well as inter-agent constraints linking it to higher priority agents.

DisCSPs are solved by the collective action of agents in A, which asynchronously run a process of distributed constraint satisfaction, and send messages to other agents in the system in order to have all local solutions converge to a global one. Considering message passing, it is currently assumed that the delay in delivering a message is finite but random. For a given pair of agents, messages are delivered in the order they were sent.

Let us denote S(k) the set of variables belonging to agent A k . S(k) can be partitioned in two disjoint subsets,

Si(k) = {xj ∈ A k |∀cjm, xm ∈ A k } and So(k) = {xi ∈ A k |∃cij, xj / ∈ A k }.
In a nutshell, Si(k) is a set of private variables, which only share constraints with variables inside A k . Conversely, So(k) is a set of variables linked to the outside world and sometimes referred to as negotiation variables. Moreover So(k) can be seen as the union of two (not necessarily disjoint) sets,

S + o (k) = {xi ∈ A k |∃cij, xj ∈ A l , l > k} and S - o (k) = {xi ∈ A k |∃cij, xj ∈ A l , l < k}. S + o (k)
is the set of variables constrained with variables belonging to agents lower than A k in the ordering, similarly S - o (k) is the set of variables constrained with variables belonging to higher priority agents. Finally, we will denote S j o (k) the set of variables in A k constrained with variables in Aj.

The instantiation of variables in S(k) will be denoted I(k), and the instantiation of a subset u thereof, I(k) |u .

Some distributed constraint satisfaction algorithms make heavy use of nogoods to exchange data about unfeasible partial assignments. A directed nogood for a value c of variable x k is an expression of the form,

(xi = a) ∧ (xj = b) ∧ . . . ⇒ (x k = c) mean-
ing that the assignment of c to x k is inconsistent with the assignments of a, b, . . . to xi, xj, . . .. This nogood explains the deletion of value c, and is relevant as long as values a, b, . . . are assigned to variables xi, xj, . . ., and is equivalent to its non-directed counterpart,

¬((xi = a) ∧ (xj = b) ∧ . . . ∧ (x k = c)).
The left-hand and righthand sides (abbreviated as lhs and rhs respectively) of the directed nogood are defined from the position of the "⇒" symbol.

When together several nogoods yield an inconsistency, they are resolved into a new nogood, following the method exposed in [START_REF] Ginsberg | Dynamic backtracking[END_REF]. Let (xj = b) be the lowest priority assignment in the left-hand sides. The lhs of the resolvent will have the conjunction of the left-hand sides of all inconsistent nogoods, barring references to xj. The righthand side is then (xj = b). The new nogood should be stored by the process owning xj to explain the deletion of (xj, b), while all nogoods referring to (xj = b) become irrelevant and can be deleted.

BASE ALGORITHM

Asynchronous Backtracking

ABT is one of the first complete algorithms proposed to solve DisC-SPs [START_REF] Yokoo | Distributed constraint satisfaction for formalizing distributed problem solving[END_REF]. Although early publications focus on agents owning exactly one variable, [START_REF] Hirayama | The phase transition in distributed constraint satisfaction problems: First results[END_REF] extends its purpose to complex local agents. We will use this algorithm as a base for our work.

In this protocol, agents are ordered statically and inter-agent constraints are directed from high priority agents to low priority ones to build an acyclic graph. Each agent runs a similar process, and stores information about the outside world, in the form of an agent view and a nogood store. The agent view of an agent Aj is the set of values that it believes to be assigned to variables belonging to higher priority agents and constrained with a variable in Aj. The nogood store is a list of nogoods which are either generated locally to reflect the impact of some higher priority agent's decision on the local problem, or received from lower priority agents to forbid some unfeasible value combination. A choice has been made to store at most one nogood per value, in order to keep the storage space requirements reasonable.

Each agent Aj solves its own subproblem and communicates asynchronously with neighboring agents to build a global solution by matching local ones. Agents generally exchange assignments from top to bottom using info messages and nogoods (from the bottom up) using back messages. When receiving an assignment, an agent has to check its local solution for consistency and, if it is not consistent, it must find a new feasible assignment. When receiving a relevant nogood (that is, one that is not obsolete considering the local agent view), Aj has to remove the corresponding value, store the nogood as a justification of this deletion and again find a new assignment. If the lhs of the nogood received includes a variable x k yet unconstrained with Aj, a request is sent via a third type of message, addlink, to the higher priority agent Ai owning x k . Ai must then add a communication link between Ai and Aj regarding x k and inform Aj if the value of x k changes in the future.

Finding a solution to the local subproblem is done the same way as in the centralized case, with a tree search. Whenever an agent Ai cannot find a consistent assignment to one of its variables x k , either because of the original constraints or because of the stored nogoods, a new nogood is generated from those emptying the domain for x k . Let xj be the lowest priority variable in the nogood. If xj belongs to Ai, it is a local back-jump, otherwise the nogood is sent to the agent owning xj. If an empty nogood is produced, the problem is unsolvable. In fact, no superset of a nogood can be part of solution. The agent exits after sending a stop message to all its neighbors.

Yokoo, Sycara and Hirayama propose a number of enhancements for their algorithm. First, the agent and variable orderings follow a max-degree heuristic. Second, as explained above, they use nogood learning inside the agent in order to be able to backjump instead of simply backtracking on the local subproblem. Additionally, they try as much as possible to keep the internal variables to their previous values. Finally, an agent keeps all external nogoods generated during its instantiation phase in a stack, and sends them all at once when done. It also sends the values of changed variables to its neighbors when the instantiation is complete.

Discussion

In order to keep internal and external knowledge separated, and free ourselves from considering the algorithm to be used for solving internal subproblems, we will not derive nogoods inside agents. Thus, the nogood store for a given agent A k will contain nogoods derived from the values of variables in γ -(k), concerning variables in S - o (k), and nogoods received from agents in Γ + (k), concerning variables in S + o (k). This way, the local solver can be completely independent from the communication protocol, since it will be called after the necessary domain reductions have been operated. This allows the use of ad hoc solvers, including local propagation and consistency maintenance.

Moreover, when an agent Ai is successfully instantiated, it is not necessary to send all changed values to all neighbors, since only agents of Γ + (i) need to be informed, and the only noteworthy changes are those occurring in S + o (i). Let Ip(i) be the previous instantiation, and Ic(i) the current one. Then, for each agent

A k in Γ + (i), if {Ic(i) |S k o (i) -Ip(i) |S k o (i) } = ∅,
this set difference should be sent to A k . This allows Ai to avoid sending useless messages to agents on which its new instantiation has no impact, while keeping the actual messages as terse as possible.

IMPROVED NOGOOD LEARNING

Nogood Selection

In a perfect world, each agent would be able to store an arbitrary number of nogoods, and select the best resolvent when failing to find a consistent set of assignments for its variables. Unfortunately, in the most general case, storage space is in limited quantity, and selecting the most suitable nogood with respect to one particular criterion (or set thereof) means generating all possible candidates in order to extract the best one, which could be prohibitively costly.

The nogood store keeps at most one nogood per value, that is, even if there are several relevant justifications to the deletion of one particular value in So, only one is stored. This behavior defaults to storing the first justification met during the search, and discarding all subsequent justifications, since only one is stored. Hence, only one nogood can be generated upon failure, and it mostly depends on the timing of events during search (different timings yielding different resolvents).

However, if several justifications are valid for some values, actively selecting the one to store could allow agents to see past the randomness of message delivery. When comparing two nogoods eliminating the same value, a heuristic criterion could be to select the nogood with the highest possible lowest variable involved. This way, the resolvent nogood would be sent as high as possible in the agent ordering, thus saving unnecessary search effort [START_REF] Bessiere | The ABT Family[END_REF].

As seen in section 2, agents store two types of nogoods: those generated locally, which are the consequences of inf o messages on the domains of variables belonging to S - o , and those received through back messages to forbid values on variables in S + o . ABT accepts a back message if the incoming nogood is consistent with its whole agent view, including its own assignment. Once this nogood is stored, the local value it refers to is eliminated, which makes the nogood consistent with the whole agent view except for the local assignment. Following the definitions in [START_REF] Bayardo | A complexity analysis of spacebounded learning algorithms for the constraint satisfaction problem[END_REF][START_REF] Dechter | Constraint networks[END_REF] the nogood is 1-relevant. If this agent receives a 1-relevant nogood for the same variable in a back message, where the only discrepancy with this variable's assignment, this nogood deserves to be considered because it brings interesting information: it gives a valid justification to discard a value, even though that value may already have been discarded. As a matter of fact, given a different timing, this very nogood could be the one stored, and the other one would be in the incoming message list. Thus, both have to be compared from a heuristic point of view, and the best one should be selected.

Considering inf o messages, the situation is a bit different, since the information they are derived from is stored locally. Actually, each agent is supposed to know the inter-agent constraints relevant to its subproblem, as well as the values of variables in γ -, which are stored in its agent view. So there is no need to aggressively challenge stored nogoods each time the agent view is updated with a new inf o message. Instead, the agent can wait until it really needs an optimal nogood store -that is, when a failure is detected and a back message must be sent -and then only, check each value in S - o against each variable in γ -, replacing existing nogoods with potentially better ones in the process. As a result, the resolvent nogood should be more efficient.

Nogood minimization

It has been hinted in [START_REF] Hirayama | The effect of nogood learning in distributed constraint satisfaction[END_REF], following [START_REF] Mammen | Problem structure and subproblem sharing in multi-agent systems[END_REF], that it is possible to minimize the nogoods resolved upon failure, in order to improve their efficiency, this process being in the most general case a very timeconsuming one. This issue is even more dramatic in the case of complex local problems. Indeed, inconsistency becomes harder to prove as local problems grow bigger, and in the same time, it becomes harder to sort out which of the stored nogoods really cause said inconsistency. Checking whether a subset of the resolved nogood is a conflict set or not was a linear test in the single variable setting. With multiple variables per agent, it becomes full-fledged coNP-complete. If we want to be able to minimize our resolvent-based nogoods, we should at least find a way to optimize the subset exploration.

To this end, when the failure is detected, we will resolve a nogood N g as shown above. Then, we will try and determine which external assignments, if any, are redundant in N g, by repeatedly solving the local problem while activating only a subset of stored nogoods, corresponding to a subset of assignments in N g.

Let N be the set of nogoods selected by Ai upon failure, and K the resolvent of N (the set of assignments appearing in the lefthand sides). Nogoods, as well as assignments, can be seen as additional constraints. Let then ΠK,N (i) be Π(k) + N + K. Since A k failed to instantiate, we know that ΠK,N (i) is inconsistent. Hence, Solve(ΠK,N (i)) returns false. We are now looking for a smaller set κ ⊂ K, such that Πκ,N (i) is still inconsistent. We can easily build such a set by ordering the assignments in K. Starting from κ = ∅, we just have to add assignments from K into κ until Πκ,N (i) returns false. This function is called ShortenResolvent.

De Siqueira and Puget propose a polynomial algorithm to reduce a conflict-set (in the sense of arc-inconsistent subset of constraints) until it is minimal wrt inclusion in [START_REF] De Siqueira | Explanation-based generalisation of failures[END_REF]. Although we won't be able to claim polynomial performance in the case of resolvent minimization, we can propose an adaptation of their algorithm.

The first step involves generating a subset of K that renders the subproblem inconsistent, if such a subset exists. The ShortenResolvent algorithm is then called recursively with the previous list of assignment in which the last assignment becomes the first. This process is repeated until the last element of the new list is equal to the last element of the initial list. The list now contains the assignments of a minimal resolvent nogood.

AGENT COOPERATION

In [START_REF] Petcu | Applying interchangeability techniques to the distributed breakout algorithm[END_REF], Petcu and Faltings evaluate the usefulness of local contention techniques to avoid spreading conflicts among agents running the distributed breakout algorithm. Using interchangeability techniques, they manage to repair conflicts with a number of neighboring agents without involving other, still non-conflicting, nodes.

Solution stability

A similar idea can be applied in ABT-like algorithms, by avoiding unnecessary flips, or value changes, during the instantiation phase. Since a satisfied agent only propagates its flips, keeping the new solution to the subproblem as close as possible to the previous one looks like a valid heuristic.

Each local subproblem can be seen as a dynamic CSP, with each incoming message adding or removing constraints dynamically. If we consider it so, we can benefit from the conclusions of [START_REF] Verfaillie | Maintien de solution dans les problèmes dynamiques de satisfaction de contraintes: bilan de quelques approches[END_REF]. In this paper, Verfaillie and Schiex analyze the respective benefits of various methods for maintaining an existing solution in a CSP subject to dynamic changes. To this end, they measure the number of constraints checks needed by each type of algorithm in function of the size of the change, for various types of problems (under-constrained, critically constrained and over-constrained). Among these methods are a nogood recording algorithm very similar to the one used in [START_REF] Hirayama | The phase transition in distributed constraint satisfaction problems: First results[END_REF], and a simple backtracking, restarting from scratch with a simple value ordering heuristic: use the latest successful assignment first if available. Noticeably, they show that there is no significant difference between nogood recording and backtracking on under-constrained and critically constrained problems, neither in terms of performance nor in terms of solution stability. This is interesting, because in the case of distributed CSPs, local subproblems are likely to be under-constrained. An over-constrained subproblem is indeed fatal to the system, while a critically constrained one probably means that the global problem is unsolvable, since it can only add constraints to this already critical instance.

When trying to preserve the internal solution across search, it is important to notice that not all flips deserve the same attention, because not all of them will be propagated. In fact, only value changes occurring in S + o need to be disclosed to lower priority agents. So instead of trying to preserve the former value of every single internal node, it should be more rewarding to concentrate on the variables constrained with lower priority agents. To this end, and keeping in mind the idea of a black-box, independent internal solver, we decided to prioritize variables of S + o in the variable ordering.

Value selection heuristics

It has been noted in [START_REF] Yokoo | Asynchronous weak-commitment search for solving distributed constraint satisfaction problems[END_REF] that one of the main differences between ABT and AWC is that AWC uses the min-conflict metric as a value ordering heuristic. That is, when selecting a value, if there exist multiple values satisfying all constraints with higher priority variables, the one that minimizes the number of constraint violations with lower priority ones should be preferred. Contrary to the claim that this feature is easily introduced into ABT, this is only possible because AWC agents send their values to all neighbors (not just lower priority ones).

In ABT, agents are not aware of lower priority agents' values, so min-conflict is not an option. To improve inter-agent cooperation, we chose to use a variant of Geelen's Promise heuristic [START_REF] Geelen | Dual viewpoint heuristics for binary constraint satisfaction problems[END_REF]. This heuristic selects a value that least reduces the possible assignments for the remaining uninstantiated variables, by preferring the value v that maximizes the product of the number of supports for v in all neighboring variables. Our value ordering will be a bit different, in that we only want to maximize the choice for extra-agent, lower priority neighboring variables, so we'll only have to use the heuristic on variables in S + o , whenever those variables cannot keep their latest successful assignment, without considering intra-agent neighboring variables. Moreover, the effects of the heuristic will be empowered when used in conjunction with our variable ordering heuristic, which selects variables in S + o first.

EXPERIMENTS

Experimental Setting

Experiments in the distributed constraint satisfaction framework differ mainly on two parameters: the way in which the distribution is achieved or simulated, and the problems to solve. We chose to have each agent be an independent process, all agents running on a single machine and communicating through a loop-back interface. Thus, agent activity is asynchronous, and the scheduling process is handled by the OS kernel, which is supposed to be fair and efficient. We evaluated the different algorithms detailed above on binary random CSPs. A binary random DisCSP class is characterized by #A, n, d, C, T, iC, iT where #A is the number of agents, n is the number of variables, d the number of values per variable, C (resp. iC) the network connectivity defined as the number of interagent constraints (resp. the number of intra-agent constraints on each agent), and T (resp. iT ) the constraint tightness defined as the number of forbidden value pairs on inter-agent or intra-agent constraints, respectively. The constrained variables and the forbidden value pairs are chosen at random. Each agent is assigned all its variables, and the constraints binding them to the neighboring agents.

The problems generated all had 60 variables with a domain of size 10 and 180 constraints of tightness 50. In the centralized case, this problem is situated at the phase transition, with an equivalent number of solvable and unsolvable instances. We then proceeded to generate random binary DisCSPs by choosing a number of agents among which to distribute the problem. When varying the number of agents, we split variables evenly between agents (i.e., n/#A variables per agent), and we modified the relevant parameters in order to keep an equal number of inter-agent and intra-agent constraints (i.e., #A • iC = C/2) whenever it was possible. For example, with 15 agents, we used the class 15, 60, 10, 90, 50, 6, 51 . Notice we adjusted iT in order to keep the problem at the complexity peak. Using this scheme, the more agents we generate, the more uniform the problem structure becomes. With 60 agents, it is a simple mapping of the uniform random binary CSP to the agents.

Results

Considering performance evaluation, we report the number of sequential messages (#msgs), and sequential constraint checks (#ccks). The former represents the length of the longest chain of sequential messages needed to solve the problem, and is a good evaluation of the distributed performance of the algorithm, while the latter can be seen as a measure of computational requirement across search.

We compared 4 different protocols. Results are summarized in Table 1 The nogood minimization scheme (ABT nl ) is a very effective way to decrease the number of sequential messages, but it incurs a significant overhead in terms of constraint checks. Happily, local subproblems are less constrained than the global one, thus they fall in the under-constrained region for problems at the peak, otherwise, repeatedly solving the problem in order to minimize a nogood could prove counter-productive; in that case, using an anytime approach should help balance the penalty. Strikingly, the agent cooperation improvement (ABTac) offers comparable savings in #msgs at a fraction of the #ccks cost. Of course, the penalty for the support counting heuristic is clear on big agents (small number of agents), as well as the burden of using a locally less than optimal variable ordering. Still there is a significant payoff, and ABTac ends up making less constraint checks than plain ABT on problems with lots of small agents.

Unsurprisingly, ABTm improves over all other methods in terms of message passing, but needs a powerful CPU in order to do so. Like its brethren ABT nl , it would be best used if message passing is very slow and/or very costly when compared to CPU cycles (which we believe is often the case).

CONCLUSION

In this paper, we presented incremental enhancements for solving distributed CSPs with complex local problems using ABT-like procedures. Those enhancements are in the fields of nogood learning, through careful selection of stored nogoods and minimization of locally generated resolvents, and agent cooperation, through helpful attitude towards lower priority agents and increased stability of local solutions. The experimental results show consistent performance improvements in terms of sequential message passing and global network load, with various agent granularity, although this comes at the cost of local computation.

Table 1 .

 1 . Algorithms in the right-hand side of the table use improved nogood learning, while algorithms at the bottom of the table try and cooperate with lower priority agents. Hence, ABT is our implementation of Yokoo's ABT, shown as a base for comparison. On top of ABT , ABT nl puts our nogood selection and minimization strategies to good use, ABTac implements our agent cooperation schemes and ABTm implements all of this. Results on problems with various agent granularity.

	ABT	#ccks	#msgs	ABT nl	#ccks	#msgs
	#A=5	39,901	1,697	#A=5	91,244	1,512
	#A=10	51,954	2,074	#A=10	106,517	2,050
	#A=15	57,931	5,637	#A=15	118,742	4,587
	#A=20	88,841	8,517	#A=20	179,238	7,351
	#A=30	135,614 12,204	#A=30	257,411 10,621
	ABTac	#ccks	#msgs	ABTm	#ccks	#msgs
	#A=5	42,217	1,544	#A=5	107,807	1,442
	#A=10	53,954	2,051	#A=10	114,240	1,979
	#A=15	60,663	4,687	#A=15	127,621	4,509
	#A=20	85,006	7,423	#A=20	162,642	7,123
	#A=30	119,754 10,948	#A=30	242,981 10,143