Edouard Boivin

Jean-Noël Chotard

Michel Ménétrier

Lydie Bourgeois

Tahya Bamine

Dany Carlier

François Fauth

Christian Masquelier

Laurence Croguennec
email: laurence.croguennec@icmcb.cnrs.fr

Oxidation under air of tavorite LiVPO4F : influence of vanadyl-type defects on its electrochemical properties

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The increasing mobility of populations and the need to fight against global warming with the development of sustainable energies are two reasons for which electrochemical energy storage is one of the major issue for scientific researches both at the academic and industrial levels. The Lithium-ion battery technology is already largely used as an energy source for mobile devices such as smartphones, laptops etc. Nevertheless, for applications such as electric and hybrid vehicles, the energy density delivered by these batteries cannot currently compete with fossil energy (cost and limited autonomy in particular). Polyanionic compounds could be promising candidates at the positive electrode of Lithium-ion batteries developed for that kind of applications, due to higher working potential for a given M n+ /M (n-1)+ redox couple than in oxides [START_REF] Manthiram | Lithium Insertion into Fe 2 (MO 4 ) 3 Frameworks: Comparison of M = W with M = MO[END_REF] and, for some of them, higher chemical and thermal stability. Among them, A x MXO 4 Y Tavorite-type compounds (with A = Li, Na, … ; M= Ti, V, Mn, Fe, … ; X = P or S and Y = O, OH, F and mix of them) are of interest [START_REF] Masquelier | Polyanionic (phosphates, Silicates, Sulfates) Frameworks as Electrode Materials for Rechargeable Li (or Na) Batteries[END_REF][START_REF] Whittingham | Quest for Nonaqueous Multivalent Secondary Batteries: Magnesium and Beyond[END_REF][START_REF] Rousse | Sulfate-Based Polyanionic Compounds for Li-Ion Batteries: Synthesis, Crystal Chemistry, and Electrochemistry Aspects[END_REF] . MO 4 Y 2 octahedra are linked by bridging anions Y to form infinite chains [Y-MO 4 -Y] n which are connected by XO 4 polyanionic groups in such way that each oxygen atom belongs to one different octahedron. The three dimensional network thus generated can accommodate alkaline cations which can diffuse easily. The Tavorite framework is tailored according to the inductive effect coming from the bridging anion Y (O, OH or F) in addition to that from the XO 4 polyanionic group. The environment of the transition metal thus greatly influences the potential of the redox couple involved. Typically, for the same redox couple Fe III /Fe II , lithium insertion occurs at a potential of 2.6 and 2.9 V vs Li + /Li in LiFe III PO 4 OH [START_REF] Marx | The Structure of Tavorite LiFePO 4 (OH) from Diffraction and GGA + U Studies and Its Preliminary Electrochemical Characterization[END_REF] and LiFe III PO 4 F 6 , respectively. Indeed, fluorine is more electronegative than the hydroxyl group, inducing the formation of a more ionic metal-ligand bond, a decreasing energy of the antibonding orbital level, and thus an increasing potential difference of the Fe III /Fe II redox couple versus Li + /Li. Vanadium based phosphate Tavorite compounds are very attractive because of their high potential and theoretical energy density, at least competitive with the already commercialized LiFePO 4 2 : 655Wh/Kg of theoretical energy density for LiVPO 4 F vs. 586Wh/Kg for LiFePO 4 . LiVPO 4 F is generally synthesized using a lengthy two steps ceramic synthesis route [START_REF] Barker | Electrochemical Insertion Properties of the Novel Lithium Vanadium Fluorophosphate[END_REF][START_REF] Ateba Mba | Synthesis and Crystallographic Study of Homeotypic LiVPO 4 F and LiVPO 4 O[END_REF] and most of the efforts currently devoted to this material are focused on the development of an easy, eco-friendly and scalable synthesis process maintaining optimal electrochemical properties [START_REF] Kim | Fast-Rate Capable Electrode Material with Higher Energy Density than LiFePO 4 : 4.2V LiVPO 4 F Synthesized by Scalable Single-Step Solid-State Reaction[END_REF] . Nevertheless, among the huge number of articles (over 100) which report on an apparently pure LiVPO 4 F there are significant differences in lattice parameters and unit cell volumes that fluctuate for these latter between V/Z = 87.00 [START_REF] Zheng | Novel Synthesis of LiVPO 4 F Cathode Material by Chemical Lithiation and Postannealing[END_REF] and V/Z = 87.31 Å 3 11 whereas the difference between LiVPO 4 O (V/Z = 85.51 Å 3 8 ) and LiVPO 4 F is around 1.7 Å [START_REF] Whittingham | Quest for Nonaqueous Multivalent Secondary Batteries: Magnesium and Beyond[END_REF] . Indeed, some of us have shown that apparently pure and stoichiometric LiVPO 4 F powders, as determined from Xray and neutron diffraction as well as high resolution transmission electron microscopy, surprisingly contain a series of local defects detected by [START_REF] Barker | Electrochemical Insertion Properties of the Novel Lithium Vanadium Fluorophosphate[END_REF] Li Magic Angle Spinning Nuclear Magnetic Resonance spectroscopy (MAS NMR) [START_REF] Messinger | Revealing Defects in Crystalline Lithium-Ion Battery Electrodes by Solid-State NMR: Applications to LiVPO 4 F[END_REF] . In parallel to the presence of these defects, slightly different electrochemical signatures were observed as revealed by their irreversible capacity, reversible capacity and polarization [START_REF] Messinger | Revealing Defects in Crystalline Lithium-Ion Battery Electrodes by Solid-State NMR: Applications to LiVPO 4 F[END_REF]13 . The amount of these defects varies and could result from a partial oxidation during the synthesis or the storage. The study of LiVPO 4 F thermal stability in air was reported in reference [START_REF] Ma | Effects of Oxidation on Structure and Performance of LiVPO 4 F as Cathode Material for Lithium-Ion Batteries[END_REF] and raised interesting questions concerning the nature of the possible defects formed and their influence on the electrochemical properties.

In the following we will describe the oxidation of LiVPO 4 F performed in similar conditions to those reported by Ma et al. [START_REF] Ma | Effects of Oxidation on Structure and Performance of LiVPO 4 F as Cathode Material for Lithium-Ion Batteries[END_REF] , and its effect on the composition, structure and electrochemical properties. We will show that combination of Synchrotron X-ray powder diffraction with Infra-Red and NMR spectroscopies is essential to identify the nature of the phases and local defects formed, and to understand in-depth the electrochemical behavior observed in lithium batteries.

Experimental part

The pristine material, LiVPO 4 F, was synthetized, according to the reaction (1) through a two steps carbothermal reduction, as described previously ) and NH 4 H 2 PO 4 (Sigma-Aldrich, > 99%) as described in reference [START_REF] Ateba Mba | Synthesis and Crystallographic Study of Homeotypic LiVPO 4 F and LiVPO 4 O[END_REF] and according to the reaction (2).

(1)

Step

1 V V 2 O 5 + 2 NH 4 H 2 PO 4 + 2C + C excess  2 V III PO 4 /C + 2 NH 3 + CO 2 + CO + 2 H 2 O Step 2 V III PO 4 /C + LiF  LiV III PO 4 F/C (2) V III 2 O 3 + 4/3 NH 4 H 2 PO 4 + 2/3 Li 3 PO 4 + ½ O 2  2 LiV IV PO 4 O + 4/3 NH 3 + 2 H 2 O
The thermogravimetric analysis (TGA) of the pristine material LiVPO 4 F was performed on a TA instruments Q600 under air and over a temperature range between 20 and 700°C, with a continuous heating rate of 5°C/min for the first experiment. In order to separate the different weight losses and overpass the kinetics phenomena, then several plateaus were performed during 30 minutes at the characteristic temperatures defined by the first experiment (i.e. 450, 525, 600 and 700°C).

Based on TGA results, a series of oxidized materials were prepared by heating the pristine material LiVPO 4 F at different temperatures (T = 375, 450, 525, 600 and 700°C) during 30 minutes under air in a muffle furnace and then by quenching them under air. In the following, the resulting samples are called as LVPF-T in general or LVPF-375, LVPF-450, ... to specify the inair treatment temperature. Note that the storage of these samples is a key parameter in order to avoid any evolution of the samples over time, we thus kept them in an Argon filled glove box ([H 2 O] < 1 ppm and [O 2 ] < 1 ppm) as much as possible.

In order to confirm the chemical compositions of the samples, the Li, V, and P contents were determined using an Inductively Coupled Plasma / Optical Emission Spectrometry (ICP-OES) spectrometer (Varian 720-ES Optical Emission Spectrometer) after complete dissolution of the powders into a mixture of hydrochloric and nitric acids. Elemental analyses of C and H were performed using a gas chromatography spectrometer, an Elementar Vario Micro Cube CHNS.

The investigation of the morphology was performed by Scanning Electron Microscopy (SEM) using a Hitachi S-4500 microscope. The powders were previously metallized by gold deposition.

High angular resolution Synchrotron X-ray powder diffraction (SXRPD) experiments were performed at the MSPD beamline of the ALBA synchrotron [START_REF] Fauth | The New Material Science Powder Diffraction Beamline at ALBA Synchrotron[END_REF] (Barcelona, Spain). Data were collected using the MYTHEN position sensitive detector in Debye-Scherrer geometry, at 0.9539 Å wavelength, over a 2° -72° angular range (0.006° step) and total integration time of 5 minutes. The samples were sealed in a 0.5 mm diameter capillary. Diffraction data analysis was performed using the FullProf Suite [START_REF] Rodriguez-Carvajal | Recent Advances in Magnetic Structure Determination by Neutron Powder Diffraction[END_REF] . The profile of the diffraction lines of the highly defected materials had to be fitted using a phenomenological anisotropic strain broadening model [START_REF] Stephens | Phenomenological Model of Anisotropic Peak Broadening in Powder Diffraction[END_REF][START_REF] Rodríquez-Carvajal | Line Broadening Analysis Using FullProf: Determination of Microstructural Properties[END_REF] after deconvolution of the instrumental contribution determined from a silicium reference. The structural model is described within a triclinic unit cell with 18 independent atoms, leading hence to a large number of refined parameters: up to 104 for a single phase model, 212 for some of LiVPO 4 F-T compounds exhibiting two coexisting phases. For these reasons, Rietveld refinements were performed applying soft constraints on P-O distances (1.55 Å ± 0.05) and O-P-O angles (109.5° ± 2.50) to describe the covalent {PO 4 } 3-anionic groups.

In order to support the composition and the structure of the different materials studied, magic angle spinning nuclear magnetic resonance (MAS NMR) was performed. [START_REF] Barker | Electrochemical Insertion Properties of the Novel Lithium Vanadium Fluorophosphate[END_REF]

Results and discussion

2a. Samples preparation and their structural study

As illustrated in V/Z = 87.18 Å 3 . The refinement by the Rietveld method of the structure of LiVPO 4 F confirms the description already reported by Ateba Mba et al. [START_REF] Ateba Mba | Synthesis and Crystallographic Study of Homeotypic LiVPO 4 F and LiVPO 4 O[END_REF] , i.e. the formation of a three dimensional network with a single crystallographic site for the Li + ions.

The TGA data obtained for the thermal treatment of LiVPO 4 F under air (Figure 2) pattern is observed though a very narrow solid solution domain seems to be formed. For the high temperatures processed samples, the XRD patterns could appear as a combination of LVPF and LVPO ones. The SEM images associated to LVPF reveals the formation of aggregates made of 300-600 nm primary particles with 20 nm divided carbon at their surface (the latter appearing as bright small particles in Figure 3). The SEM images also highlight the almost complete disappearance of carbon nanoparticles at 450°C, in good agreement with the TGA analysis.

highlights
Furthermore, a significant increase of the particles size is observed from 300 -600 nm for the pristine LVPF material to 1000 -5000 nm for LVPF-700. Curiously, this growth of particles is not accompanied by a narrowing of the diffraction lines. In fact, the formation of highly defected materials and/or the separation into phases very close in compositions are likely at the origin of strain induced peaks broadening.

ICP-OES and CHNS analyses of these samples were carried out in order to titrate the Li, P and V contents on one side and the remaining carbon on the other side, and to check for the chemical composition of these materials. Table 1 summarizes the results obtained. As expected by TGA results, a volatilization of remaining carbon as CO 2 is observed mostly between LVPF-450 and LVPF-525. This observation is supported by the change in the color of the different samples, from dark grey for LVPF-375 to brown for LVPF-525 and green for LVPF-700. Raman spectroscopy is one of the most sensitive techniques to characterize carbonated systems and was used to follow the carbon content of LVPF-T materials. As shown in supplementary information (in Figure S1), Raman bands observed in the 1200 -1700 cm -1 range are assigned to sp 2 -hybridized and disorder-induced lines of carbon systems. The evolution of their integrated intensity can be related to that of the carbon amount. Raman measurements reveal a strong decrease of the carbon content with the increasing annealing temperature, but also the presence of residual carbon until 525°C, in agreement with CHNS results. Contrary to the results reported by Ma et al. [START_REF] Ma | Effects of Oxidation on Structure and Performance of LiVPO 4 F as Cathode Material for Lithium-Ion Batteries[END_REF] , no significant variation of the Li/V ratio from 1/1 is observed (neither for the Li/P ratio nor for the V/P ratio) suggesting that the stoichiometry

LiVPO 4 Y (Y = F 1-x O x ) is maintained.
In order to ascertain the nature of the materials formed following our in-air thermal treatment, corresponding XRD patterns were analyzed and structural models were refined by the Rietveld method considering either a single or two Tavorite-type phases : LiVPO and the difference between the short and the long V-X bonds increases along the chains, from 0.04 Å for LVPF to 0.65 Å for LVPF-700 (Table 2 and Figure 5a), in good agreement with the formation of more and more vanadyl-type bonds along the chains. Note that the length of the short bond decreases faster than the long one grows. Furthermore, these changes are not linear with an increasing substitution of oxygen for fluorine. This could be also in relation with the deviation from the Vegard's law, mentioned above.

Due to an inhomogeneous line broadening, all these patterns were refined using an anisotropic strain broadening model, corresponding to a P-1 space group and provided in the Fullprof software [START_REF] Stephens | Phenomenological Model of Anisotropic Peak Broadening in Powder Diffraction[END_REF][START_REF] Rodríquez-Carvajal | Line Broadening Analysis Using FullProf: Determination of Microstructural Properties[END_REF] . By drawing the so called Williamson-Hall plot (i.e. β obs .cosΘ as function of sinΘ), the size and strain effects can be separated. The analysis of the microstructure reveals that the strains along these three directions increase until 525°C and then decrease gradually. Partial oxidation of the pristine material leads to the formation of vanadyl-type defects that would generate strains at the local scale, relaxed then thanks to the phase separation between a fluorine-rich phase and an oxygen(vanadyl)-rich phase. Moreover, the strains appear more extended along the [100] and [010] directions, this latter corresponding to the vanadyl bond propagation direction. Indeed, the substitution of a part of fluorine by oxygen, leads to the formation of vanadyl bonds at the local scale (as dilute defects for small substitution ratios) which may disrupt the antagonist V-F bonds and generates small variations in the lattice parameters from one unit cell to another, especially along the b axis. The coherent diffraction size domains obtained from the microstructure analysis are consistent, from the pristine LVPF to LVPF-450, with the particles sizes observed by SEM and thus with a particles' growth most probably due to the effect of sintering. Then, a decrease of the apparent crystallites sizes is determined from 450°C to 525°C sample treatment, in parallel to a strong increase of microstrains, whereas an obvious particles' growth is observed by SEM.

The intergrowth of different phases (here two, in a ratio close to 40:60 in LVPF-525 as reported in Table 2) inside the particles would induce the formation of multiple domains and boundaries resulting in the lowering of apparent crystallites sizes and in a strong increase of microstrains. At higher treatment temperature the narrowing of the diffraction lines is due to the combined effect of decreasing microstrains and increasing crystallites domain sizes generated by the sintering.

These results demonstrate the possibility to prepare phosphate Tavorite-type materials LiVPO 4 F 1-x O x , being mixed oxy-fluorides and showing thus mixed V 3+ /V 4+ valences. Nevertheless, it appears that, at least by this synthesis method i.e. an oxidation in temperature of LiVPO 4 F, the solid solution domains are limited (with 10% of maximum substitution). The microstructure analysis reveals also the presence of size and strains effects in all these LiVPO 4 F 1-x O x , materials probably due to the large difference in nature between the bond sequences O….V IV =O and F-V III -F that makes difficult to mix them homogeneously/statistically along the chains. In addition to the average structural description given by X-ray diffraction, MAS NMR and IR spectroscopy appear as the most suitable complementary techniques to get an in-depth characterization of the local scale.

2b. Spectroscopic study NMR [START_REF] Barker | Electrochemical Insertion Properties of the Novel Lithium Vanadium Fluorophosphate[END_REF] Li, 31 P, [START_REF] Onoda | Phase Transition and Spin Dynamics of the LiVFPO 4 Insertion Electrode with the S = 1 Linear Chain and the Development of F -O Mixed System[END_REF] F MAS NMR experiments were carried out on LiVPO 4 F, LiVPO 4 O and all the annealed samples. This technique is sensitive to the local environment of the probed atom (nucleus) and proved to be a powerful tool to detect vanadyl-type defects [START_REF] Messinger | Revealing Defects in Crystalline Lithium-Ion Battery Electrodes by Solid-State NMR: Applications to LiVPO 4 F[END_REF] .

Figure 6a shows the [START_REF] Barker | Electrochemical Insertion Properties of the Novel Lithium Vanadium Fluorophosphate[END_REF] Li MAS NMR spectra recorded for all samples. A rather sharp signal centered at 115 ppm is observed for LiVPO 4 F, which is close to that published previously as corresponding to the unique Li site identified by diffraction [START_REF] Messinger | Revealing Defects in Crystalline Lithium-Ion Battery Electrodes by Solid-State NMR: Applications to LiVPO 4 F[END_REF][START_REF] Ellis | Structure and Electrochemistry of Two-Electron Redox Couples in Lithium Metal Fluorophosphates Based on the Tavorite Structure[END_REF] . The spectrum for the LVPF sample also exhibits a weak signal at -1 ppm assigned to the presence of residual LiF and others additional signals at 4, 84 and 186 ppm. 2D dipolar homonuclear correlation NMR experiments recently performed by Messinger et al. [START_REF] Messinger | Revealing Defects in Crystalline Lithium-Ion Battery Electrodes by Solid-State NMR: Applications to LiVPO 4 F[END_REF] have shown that all these additional signals are correlated to the main one, and correspond thus to Li + ions in the same material, that would be located nearby V ions with altered oxidation and/or spin states.. All paramagnetic materials (such as Vanadium based Tavorite-like compounds discussed in this section) lead to NMR spectra dominated by interactions between nuclear and electron spins (hyperfine interactions).

The Fermi contact shift, which governs the position of the NMR signal of such compounds, corresponds to the presence of some density of electron spin at the nucleus probed. Indeed, the value of the Fermi contact shift is proportional to the spin density at the site of the probed nucleus and to the magnetic susceptibility of the compound [START_REF] Bertini | Magnetic Susceptibility in Paramagnetic NMR[END_REF] . Modelling of the defect in LiVPO 4 F considering the presence of oxygen replacing fluorine locally in the structure using DFT calculations, leads to a rather good [START_REF] Barker | Electrochemical Insertion Properties of the Novel Lithium Vanadium Fluorophosphate[END_REF] Li NMR signal assignment [START_REF] Bamine | Understanding the Defect in LiVPO 4 F : A Combined NMR and DFT Calculations Study[END_REF] .

The investigation of the NMR spectrum of LVPO shows a single sharp peak at 79 ppm, less shifted than in LiVPO 4 F (115 ppm) due to the higher oxidation state of vanadium. Indeed, V 4+ (t 2g 1 e g 0 ) provides less spin transfer towards the Li nuclei than V 3+ (t 2g 2 e g 0 ), in the same structural environment. In LiVPO 4 O, there are two crystallographic sites for Lithium [START_REF] Ateba Mba | Synthesis and Crystallographic Study of Homeotypic LiVPO 4 F and LiVPO 4 O[END_REF] . So, two [START_REF] Barker | Electrochemical Insertion Properties of the Novel Lithium Vanadium Fluorophosphate[END_REF] Li MAS NMR peaks would have been expected whereas only one is detected, due to the strong structural and electronic similarity between the two sites as confirmed by the calculated shifts for the Li in the structure (see Table S1 in supplementary information).

The effect of annealing treatment under air is detected as soon as 375°C. Indeed, for this sample a small decrease in intensity of the LiVPO 4 F-type main signal is observed, with the appearance of a tiny peak at 80 ppm. This latter contribution seems to match with an LiVPO 4 O-type environment for Lithium. This trend is confirmed with an increase of the annealing temperature (i.e. 450°C and 525°C). Indeed, the intensity of the LiVPO 4 F-type signal decreases at the benefit of the LiVPO 4 O-type one. The NMR shifts are highly sensitive to the local environment of the probed nuclei and highlights thus here that only one additional environment can be detected for lithium, slightly different from that of LiVPO 4 O with an NMR shift 5 ppm smaller. Note that the LiVPO 4 F-type contribution is slightly more shifted (116 ppm against 115 ppm for the pristine LVPF), that could be accounted for by a shortening of the Li-V distance due to the oxidation of vanadium in the vicinity of LVPF local type environments. Note also that there is a strong modification of the [START_REF] Barker | Electrochemical Insertion Properties of the Novel Lithium Vanadium Fluorophosphate[END_REF] Li MAS NMR spectra between LVPF-450 and LVPF-525, in good agreement with the results obtained by SXRD which highlight a weak substitution level of oxygen for fluorine in LVPF-450 (less than 10%) and a larger one for LVPF-525 with a global composition of LiVPO 4 O 0.65 F 0.35 . For this latter and especially for LVPF-600, several new peaks appear and a significant broadening is observed. This is likely due to the formation of a series of different (V 4+ , V 3+ ) environments for the Li + ions in these materials highly disordered. Note that the appearance of these new contributions is done at the expense of those existing in the pristine material (4 and 186 ppm), the latter being associated with localized vanadyl-type defects [START_REF] Bamine | Understanding the Defect in LiVPO 4 F : A Combined NMR and DFT Calculations Study[END_REF] . Nevertheless, the correlation between these NMR shifts and the nature of the defects formed due to a partial oxidation of LVPF is not trivial and would require DFT calculations.

LVPF sample exhibits a single relatively sharp 31 P MAS NMR signal at 3998 ppm (Figure 6b) in agreement with the unique phosphorous site present in the structure. shown that this material is a biphasic one, with two phases very close to each other, which could not be separated by 31 P MAS NMR. Furthermore, signal corresponding to phosphorus in diamagnetic compound grow at -9 and 52 ppm from 600°C.

The comparison of the [START_REF] Onoda | Phase Transition and Spin Dynamics of the LiVFPO 4 Insertion Electrode with the S = 1 Linear Chain and the Development of F -O Mixed System[END_REF] F MAS NMR spectrum of LVPF with those of the series of samples LVPF-T is given in supplementary information (Figure S3). The isotropic peak is located at -1500 ppm for LVPF. The global intensity of this signal decreases gradually until 700°C due the replacement of oxygen for fluorine and, surprisingly, no others peaks which would be assigned to Fluorine atoms in interaction with V 4+ cations can be detected. The large number of spinning sidebands and the narrow solid solution domains (with less than 10% of oxygen substitution for fluorine (and vice versa) in LiVPO 4 F 1-x O x ) could make difficult the observation of the contributions expected.

This MAS NMR study appears fully consistent with the diffraction results discussed just before, and especially with the microstructure analysis that highlighted strong strains effects within the LiVPO 4 F 1-x O x phases. The analysis of the corresponding environments more largely mixed in V 3+ and V 4+ are formed at the local scale. A study using diffuse reflectance infra-red spectroscopy was performed to definitively support the nature of the defects associated to the presence of V 4+ , i.e. the formation of vanadyl-type bonds.

FTIR

The Mid-IR diffuse reflectance spectra recorded between 450 and 4000 cm -1 for all the annealed samples are compared to those of LVPF and LVPO in Figure 7. The assignment of the main vibrational bands is given in In the 3000 -4000 cm -1 region, no contribution was detected in the LVPF spectrum whereas a very broad signal is observed for LVPO. This band is assigned to the adsorbed water stretching vibration in good agreement with the presence of the corresponding H-O-H bending vibration at 1635 cm -1 23 . When the annealing temperature is increased, these two signals appear from 525°C and gradually grow until 700°C. The amount of adsorbed water is thus obviously increased for samples that had been previously treated at higher temperature, despite the decreasing specific surface area of the powder. Actually, this unexpected result can be explained considering the disappearance of the carbon coating with the formation of CO 2 during the annealing in air. That carbon coating would act as a protective layer against the moisture adsorption: without it, the affinity of the material with water is obviously increased.

Otherwise, the vanadyl ({V=O} 2+ ) stretching vibration mode, in LVPO, is located at 915 cm -1 (Table 3). This band is not expected in LVPF which is theoretically a V 3+ -rich fluorophosphate and a vanadyl-free composition. Nevertheless, a tiny peak is observed at 874 cm -1 , shifted versus the vanadyl stretching vibration mode observed in LVPO, which could match with the presence of localized vanadyl-type defect in LVPF as already discussed here but also previously in reference [START_REF] Messinger | Revealing Defects in Crystalline Lithium-Ion Battery Electrodes by Solid-State NMR: Applications to LiVPO 4 F[END_REF] . Moreover, as the temperature is increased, a high wavenumber shift, an increasing intensity and a significant broadening of this vanadyl-type vibration are observed.

As already reported, there is a correlation between the length of the V=O bond and the wavenumber of the associated stretching mode [START_REF] Harrison | Microwave-Assisted Solvothermal Synthesis and Characterization of Various Polymorphs of LiVOPO 4[END_REF] . Basically, the shorter is the V=O bond, the higher is the wavenumber. These results obtained in IR are in very good agreement with the structural descriptions reported before, i.e. the decrease of the V=O bond length whereas the antagonist V-O bond length increases with temperature (see Figure 5a). Furthermore, due to the alternation between shorter and longer V-X distances along the chains with the increasing temperature, the vanadium ions do not occupy anymore the central position of the VO 4 X 2 octahedra leading to an increase of the equatorial V-O bond lengths (between 1.97 Å in average for LVPF and 1.99 Å in average for LVPO).

The PO 4 stretching region is located between 950 and 1200 cm -1 24-26 . A single crystallographic site exists for phosphorus in LiVPO 4 F, whereas two sites are identified in LiVPO 4 O due to the lower symmetry (i.e. doubling of the unit cell). This is shown by the increase in the number of components in the PO 4 stretching region (Table 3). With the increasing temperature, from 375°C, some characteristic vibration bands of LiVPO 4 O-type appear around 950 and 1165 cm -1 and gradually shift and grow in intensity suggesting that LVPF is oxidized to LVPO through the formation of LiVPO 4 F 1-x O x phases.

In short, the combination of Synchrotron X-ray powder diffraction, MAS NMR and FTIR spectroscopy allows to demonstrate the formation of vanadyl-type defects in LVPF through thermal treatment in air. Upon increasing temperature, LiVPO 4 F 1-x O x phases are formed, in limited composition ranges with x either smaller than 0.1 (of LVPF-type) or higher than 0.9 (of LVPO-type). The influence of these defects on the electrochemical properties will be demonstrated in the following part.

2c. Electrochemical properties versus Lithium

In order to investigate separately the high voltage region (involving the V III /V IV /V V redox couples) and low voltage region (involving V IV /V III /V II redox couples), the pristine materials (i.e. here 0.96 Li + ) corresponds to the oxidation of V III to V IV at 4.24 V and then 4.28 V vs Li + /Li. The transition between the first and the second plateaus occurs at the Li 0.67 VPO 4 F composition.

Actually, the charge mechanism is a two steps biphasic process between LiVPO 4 F, Li 0.67 VPO 4 F and VPO 4 F 27 . The following discharge occurs at 4.17 V vs Li + /Li as a biphasic process between the lithium-free and the fully lithiated phases, with a reversible capacity of 140 mAh/g, and does not involve the intermediate phase. Note that this asymmetric charge/discharge process observed for LiVPO 4 F is not fully understood yet. The lithium extraction from the LVPO composition occurs at a lower potential than from LVPF (3.95 V vs Li + /Li) even if the V IV /V V redox couple is the one involved.

Due to the presence of vanadyl bonds the redox couple actually involved is {V=O} 2+ /{V=O} 3+ . As In the low voltage region (i.e. 3.0 -1.5 V vs Li + /Li), the lithium insertion-extraction into/from LVPF occurs at 1.8 V according to a biphasic process between LiVPO 4 F and Li 2 VPO 4 F involving the V III /V II redox couple (Figures 8c andS4c). The lithium insertion into LVPO leads to the reduction of V IV to V III and occurs at 2.48 V, 2.31 V then 2.03 V vs Li + /Li, to reach the Li In our point of view there is a destabilization of V II in an asymmetrical environment (i.e. F-V II -O). Indeed, there are significant structural differences between the phases previously mentioned (i.e. LVPF, LVPO and the corresponding intercalated compositions), especially concerning the V-X bond length along the chains of VO 4 X 2 octahedra. In the V III phases (i.e. LiVPO 4 F and Li 2 VPO 4 O) this V-X bond length are almost homogeneous (1.98 Å and 1.95 Å respectively). In Li 2 V II PO 4 F, the V-F are longer (2.12 Å) and also constant because V 2+ is preferentially stabilized in a symmetrical environment due to its electronic configuration (t 2g 3 ). The insertion of Lithium in a fluorine-rich compound (V (3+ε)+ ) involves theoretically mainly the reduction of V 3+ in V 2+ .

Nevertheless, V 2+ may be destabilized in a distorted environment induced by the presence in its first coordination sphere of oxygen and fluorine along the chain, this could explain why a small amount of oxygen in a LiVPO 4 F-type phase leads to a strong decrease in capacity. Inversely, the lithium insertion in an oxygen-rich phase would be promoted as suggested by the comparison of LiVPO 4 F and Li 2 VPO 4 O. Actually, in the pristine material the average oxidation state of vanadium is V (3+ε)+ and the strains highlighted by SXRD measurement would be relaxed thanks to insertion of lithium involving the reduction of V IV to V III and leading to an overall homogenization of the distances V-X along the chains.

The discrepancies observed between this work and the results reported by Ma et al [START_REF] Ma | Effects of Oxidation on Structure and Performance of LiVPO 4 F as Cathode Material for Lithium-Ion Batteries[END_REF] (Table S2) may come from small differences in composition, structure and/or morphology for the materials studied. Actually the amount of vanadyle-type defects in LiVPO 4 F is a key parameter influencing greatly its electrochemical properties. [START_REF] Messinger | Revealing Defects in Crystalline Lithium-Ion Battery Electrodes by Solid-State NMR: Applications to LiVPO 4 F[END_REF][13] Note for instance that the electrochemical signature given by Ma et al. for the pristine material (Figure 10, reference 14) is significantly different from that expected for a stoichiometric composition of LiVPO 4 F, whereas that reported in this work was fully characterized combining highly sensitive techniques such as NMR IR, and SXRPD and was shown to be stoichiometric.

Conclusion

The oxidation under air at controlled temperature of the promising positive electrode material, LiVPO 4 F, was investigated in order to get a good knowledge of the different types of defects or compositions which can be formed under synthesis conditions not under control. A combination of high resolution synchrotron powder X-ray diffraction, with infrared and MAS NMR spectroscopies was proved to be the tools of choice to characterize the materials thus formed. Their complex composition, microstructure and defects induced by the annealing treatment impact hugely their electrochemical properties in comparison to those of LVPF and LVPO. Below 450°C, solid solutions LiVPO 4 F 1-x O x are formed with less than 10% of oxygen substitution for fluorine and still limited impact on the electrochemical performance at high potential. Above 450°C the effect is drastic, moving from a LVPF-type electrochemical signature to that of LVPO-type, with a decreasing average discharge potential, a larger hysteresis between the charge and the discharge, a decrease of the reversible capacity etc. In the low voltage region, the effect of the oxygen defects is even more pronounced, everything happens as if the presence of vanadyl-type defects would prevent the formation of V 2+ during lithium

Figure 1 ,

 1 LiVPO 4 F was obtained as pure: all the diffraction lines could be indexed in a typical Tavorite unit cell described in the P-1 space group with a = 5.16893(3) Å, b = 5.30867(3) Å c = 7.26212(3) Å, α = 107.591(4)°, β = 107.972(5)°,  = 98.394(4) ° and

Figure 3 ,

 3 Figure 3, with the corresponding SEM images given in inset. A rather continuous evolution of the diffraction patterns is observed. Contrary to the results obtained by Ma et al. 14 , a clear phase separation is observed for samples thermally treated at 525°C and above. For the lower temperature treated samples (i.e. up to 450°C), no obvious significant change of the diffraction

4 and 5 .

 45 4 F-type or/and LiVPO 4 O-type. The main difference between LiV III PO 4 F and LiV IV PO 4 O lies in the distances observed along the chains of octahedra 8 : they are constant and equal to 1.98 Å in LiVPO 4 F, whereas there is an alternation between a short bond (the vanadyl bond around 1.7 Å) and a longer bond (around 2.2 Å) in LiVPO 4 O. In LiVPO 4 F the vanadium cations are thus sitting at the center of the VO 4 F 2 octahedra, in special positions (0, 0, 0) P-1 and (0, 0, 1/2) P-1 . In order to allow the displacement of the vanadium cations from the center of the octahedra along the chains, and the possible formation of oxy-fluoride LiVPO 4 F 1-x O x solid solutions, the Rietveld refinements were performed considering a LiVPO 4 O-type model, and thus the doubling of the unit cell according to the following matrix: Described in a LiVPO 4 O-type model the cell parameters of LiVPO 4 F are a = 6.84751(3) Å, b = 7.26212(3) Å, c = 7.93166(3) Å, α = 89.931(4) °, β = 91.544(5) °,  = 117.854(4) ° and V/Z = 87.18 Å 3 . The results of the refinements are summarized in Table2and in the Figures The patterns of LVPF-375 and LVPF-450 (as highlighted for the latter in Figure4a) can be refined using a single phase model, close to LVPF but significantly different, revealing thus that a solid solution domain exists below 450°C. For instance, the V/Z values obtained for LVPF-375 and LVPF-450 are 87.12 Å 3 and 87.05 Å 3 respectively, versus 87.18 Å 3 for LVPF. In order to estimate the substitution level in these materials the Vegard's law was applied on their volumes,their vanadium average oxidation states would be 3.02 and 3.05 respectively, versus 3 for LVPF, hence their compositions would be LiVPO 4 F 0.98 O 0.02 and LiVPO 4 F 0.95 O 0.05 . Note that the individual cell parameters don't follow this law and a strong deviation is observed, especially for a and b parameters (see FigureS2in supplementary information). As reported before in[START_REF] Onoda | Phase Transition and Spin Dynamics of the LiVFPO 4 Insertion Electrode with the S = 1 Linear Chain and the Development of F -O Mixed System[END_REF] , single crystals with LiVPO 4 F 1-x O x compositions also doesn't adopt a linear evolution of their cell parameters with the substitution ratio whereas the cell volume does. The formation of the vanadyl bond (along the b axis) may be disrupted by the presence of antagonist fluorine and the resultant distances in these … F--V IV =O--V III -F … sequences would be different to the average of F-V III -F and O-V IV =O bond lengths in end-member phases. In that case, the oxygen-fluorine repartition along the chains may have a strong influence. Nevertheless, diffraction techniques are unable to determine this repartition. From 525°C two phases are observed in each sample, and must be considered for the Rietveld refinement to determine their structure (as highlighted for LVPF-525 in Figure4b

  Figure 5b shows the evolution of the width of the microstrains' distribution (ɛ hkl = Δd hkl /d hkl ) along peculiar directions ([100], [010], [001] and in average along all [hkl] directions) for all samples and Table 2 summarizes the microstructure parameters (D hkl (= the apparent crystallite size) and ɛ hkl ).

  LVPF and LVPO) and all LVPF-T samples were cycled in lithium cells between 3.0 and 1.5 V vs. Li + /Li and between 3.0 and 4.6 V vs Li + /Li at a C/50 rate. The resulting galvanostatic and their derivative curves are given in Figures8a and 8b(for LVPF, LVPO and LVPF-525, and in supplementary information in Figures S4a and S4b for all the samples). The lithium extraction from LiVPO 4 F (i.e.

  synthetized, the reversible capacity of LVPO is about one third of the theoretical one (55 vs. 156 mAh/g). The diffraction and spectroscopic results of this study have highlighted the possibility to substitute partially oxygen for fluorine, and to form partial solid solutions LiVPO 4 F 1-x O x by the annealing in air of LVPF. This oxidation induces the appearance of a redox process at around 4.1 V vs. Li + /Li whose length grows as the annealing temperature is increased. According to the Figures8a and S4a, from 525°C, the annealing affects greatly the reversible capacity that decreases, but below this temperature the reversible capacities observed for the LVPF-T samples remain close to that of the pristine LVPF. This decrease in capacity could be explained by deteriorated transport properties for the oxidized compositions due to the sintering of the particles and to the loss of carbon as conductive additive within the active mass during the annealing, as highlighted by SEM images and Raman spectroscopy results. The evolution of the discharge reversible capacity obtained at a C/10 rate (inset in Figure8a) shows a strong and continuous decrease in capacity as the annealing temperature is increased. Furthermore, as described above, the phase diagram observed during the charge of LiVPO 4 F presents the formation of an intermediate phase corresponding to the Li 0.67 VPO 4 F composition. The derivative curves given in the Figures 8b and S4b show that the presence of this intermediate phase persists at least until the LiVPO 4 F 0.90 O 0.10 composition corresponding to the highly fluorinated phase in LVPF-525.

Figure S4d )

 S4d Figure S4d). For LVPF-450 and LVPF-525 the electrochemical signature of LVPF disappears whereas XRD revealed the persistence of a fluorine-rich phase at these temperatures. Everything happens as if the LiVPO 4 F-type phase does not participate in the insertion-extraction processes involved in the low potential region. The strong decrease in capacity in the low voltage domain when fluorine is partially replaced by oxygen in LiVPO 4 F 1-x O x even for small values of y, may results from the crystal field.

Figure 1 :

 1 Figure 1: Rietveld refinement of the pristine LVPF structure based on Synchrotron powder X-ray diffraction data. The observed intensities are plotted as red points, the theoretical Bragg positions are plotted as blue marks, calculated intensities and the difference between observed and calculated intensities are plotted as black lines.

Figure 2 :

 2 Figure 2: TGA curve obtained under air for the pristine LVPF as function of time and plotted as a blue line and the corresponding temperature vs time curve plotted as a red line. The heating/cooling rate is ± 5°C/min and the temperature plateau is maintained during 30 minutes.

Figure 3 :

 3 Figure 3: Synchrotron XRD patterns of the pristine materials (LVPF and LVPO) and the annealed samples (LVPF-375, LVPF-450, LVPF-525, LVPF-600 and LVPF-700). Corresponding SEM images are shown in inset.

Figure 4 :

 4 Figure 4: Rietveld refinements obtained for the samples LVPF-450 (a) and LVPF-525 (b) taking into account the structural model of LiVPO 4 O. The observed intensities are plotted as red points, the theoretical Bragg positions are plotted as blue (LiVPO 4 F-type phase) or purple (LiVPO 4 O-type phase) marks, calculated intensities and the difference between observed and calculated intensities are plotted as black lines. In inset, a zoom between 11 and 18.5° in which the contribution of each phase is represented.

Figure 5 :

 5 Figure 5: (a) evolution of the shorter and longer V-X distances along the [X-VO 4 -X] n chains as function of the vanadium oxidation state. The empty circles represent the long V-X distances and full circles the short V-X distances. (b) The width of the microstrains' distribution along [100] (square), [010] (triangles) and [001] (circles) directions, and the average on all [hkl] (stars)directions.

Figure 6 :

 6 Figure 6: 7 Li (a) and 31 P (b) normalized (according to the mass of the sample) NMR spectra of LVPF, LVPF-375, LVPF-450, LVPF-525, LVPF-600, LVPF-700 and LVPO. In inset, zooms of the isotropic signals associated to the different contributions. The isotropic peaks are noted by #, their spinning side bands by * and additional contributions by . The contributions which can be assigned to a 31 P in interaction with both V 3+ and V 4+ cations are noted by | .

Figure 7 :

 7 Figure 7: Diffuse reflectance infrared spectra of LVPF, LVPO and the LVPF-T samples in the 475 -3800 cm -1 range and, in inset, the 800 -1200 cm -1 region assigned to the stretching vibrations of PO 4 groups and V=O bonds.

Figure 8 :

 8 Figure 8: Galvanostatic curves obtained versus Lithium at a C/50 rate for LVPF, LVPO and LVPF-525: (a) in the high voltage domain (i.e. between 3.0 and 4.6 V vs Li + /Li) and (c) in the low voltage domain (1.5 -3.0 V vs Li + /Li). The corresponding derivative curves are given in (b) and

  Figure 1

Figure 7 Figure 8 Figure

 78 Figure 7

  Aldrich, > 99%). A thermal treatment at 800°C under argon flow leads to the formation of VPO 4 /C, in which the vanadium phosphate particles are surrounded by residual carbon nanoparticles localized in the grain boundaries. After the addition of a stoichiometric amount of LiF to VPO 4 /C, the mixture is annealed at 800°C under argon flow to form LiVPO 4 F. LiVPO 4 O was

	also synthetized by a solid state reaction from V 2 O 3 (Cerac, ≤ 99.9%), Li 3 PO 4 (Sigma-Aldrich,
	97%

[START_REF] Barker | Electrochemical Insertion Properties of the Novel Lithium Vanadium Fluorophosphate[END_REF][START_REF] Ateba Mba | Synthesis and Crystallographic Study of Homeotypic LiVPO 4 F and LiVPO 4 O[END_REF]

. V 2 O 5 (Sigma-Aldrich, > 98%) is reduced by a small excess of C SP carbon (i.e. a highly divided soot) in the presence of NH 4 H 2 PO 4 (Sigma-

  ). Both Tavorite-type phases belong to the LiVPO 4 F 1-x O x phase diagram, one is close to LVPF whereas the other is close to LVPO. Their compositions are LiVPO 4 F 0.90 O 0.10 and LiVPO 4 F 0.08 O 0.92 respectively. The refinements of LVPF-600 and LVPF-700 confirm the persistence of the phase separation, but at higher treatment temperatures the Tavorite-type phases formed are really close to LVPO (i.e. LiVPO 4 F 0.11 O 0.89 and LiVPO 4 F 0.03 O 0.97 for LVPF-600 and LiVPO 4 F 0.04 O 0.96 and LiVPO 4 F 0.01 O 0.99 for LVPF-700). The global compositions calculated for each sample, taking into account the composition and weight percentage determined for each phase, are continuously enriched in oxygen with the increase in the annealing temperature moving from LiVPO 4 F 0.96 O 0.04 for LVPF-375 to LiVPO 4 F 0.02 O 0.98 for LVPF-700. Moreover, as the substitution of oxygen for fluorine increases, the average oxidation state of vanadium increases

  and 1580 ppm against 1593 and 1418 ppm for LVPO). In this sample, the shift of the LVPF-type contribution is also affected, it increases from 3868 ppm for the pristine phase LVPF to 3911 ppm for LVPF-450. At 525°C, in the LVPO region, a new broad signal is observed around 2100 ppm. The shift of this peak is very different from those of LVPO and may correspond to a strongly disordered LVPO-type phase. This trend is amplified with the increase of the annealing temperature, indeed at 600°C this new contribution is even more intense: two components can be identified at 1930 and 2185 ppm, but a large contribution is also observed on the left. These signals are probably due to phosphorus nuclei in interaction with several distribution of V 3+ and V 4+ cations in their environment. The 31 P NMR spectrum of the sample annealed at 700°C is very close to that of LVPO, but it differs slightly in the shift (1413 and 1493 ppm versus 1443 and 1614 ppm for LVPO) and in the relative intensity of each signal. The diffraction analysis has

	The two signals at
	1593 ppm and 1418 ppm observed for LiVPO 4 O confirm the existence of two different types of
	phosphorus, in agreement with the two crystallographic sites. Based on the theoretical
	calculated shifts, the 1593 ppm shift is assigned to P1 and the 1418 ppm to P2 site (see Table S1
	in supplementary information). Furthermore, due to the smaller number of electrons in V 4+ t2g
	orbitals of LVPO compared to that in V 3+ t2g orbitals of LVPF, the isotropic signals in LVPO are
	less shifted than in LVPF. The effects of annealing on the 31 P MAS NMR spectra of the different
	samples is detected from 375°C with a slight decrease of the LiVPO 4 F-type signal without any

modification of its shift. At this temperature no new signal is observed. A small LiVPO 4 O-type contribution is detected only from 450°C, with an NMR shift smaller than those observed for LVPO (1365

  phases) as local defects around the probed nuclei. It is also interesting to mention the case of LVPF-600 which revealed intermediate NMR signals between those typical of LVPF and those typical of LVPO, suggesting that for this sample (i.e. in these synthesis conditions)

	7 Li and 31 P MAS NMR spectra
	supports the formation of solid solutions in narrow compositions domains (i.e. close in
	compositions either to LVPF or to LVPO), as NMR signals close but different from those of LVPF

and LVPO were observed. These signals are often slightly shifted (of few ppm) but broadened, suggesting a distribution of environments containing either V 4+ (in LVPF-type phases) or V 3+ (in LVPO-type

Table 3 .

 3 The spectra obtained for all the intermediate phases cannot be explained by a simple linear combination of the spectra recorded for the extreme phases LiVPO 4 F and LiVPO 4 O, in good agreement with the results obtained by XRD and NMR which reveal the formation of solid solution type phases LiVPO 4 F 1-x O x which are significantly different from LiVPO 4 F and LiVPO 4 O.

  2 V III PO 4 O composition at the end of the discharge with a reversible capacity close to the theoretical one (143 vs. 159 mAh/g). This mechanism involves several intermediate phases Li 1.5 VPO 4 O and Li 1.75 VPO 4 Oaccording to a three steps biphasic mechanism[START_REF] Bianchini | Multiple Phases in the Ε-VPO4O-LiVPO4O-Li2VPO4O System: A Combined Solid State Electrochemistry and Diffraction Structural Study[END_REF] . Coming back to the LVPF-T samples, the electrochemical signature of LVPO appears and grows with the temperature. At 375°C several shoulders appear at 2.45, 2.20 and 2.00 V vs Li + /Li and the length of the plateau at 1.8 V, related to LiVPO 4 F-type phase, strongly decreases (as clearly shown by the derivative curves given in the

Table captions Table 1 :

 captions1 Results of CHNS and ICP-OES chemical analyses carried out on all samples. Their color varies according to the weight percentage of carbon and to the oxidation state of vanadium. The average particle sizes are obtained thanks to SEM images given in inset at the figure3.

Table 2 :

 2 Summary of the parameters determined for each sample from the Rietveld refinement of its Synchrotron powder X-ray diffraction pattern. The weight percentage associated to each phase contained in the samples (1 or 2), their V/Z unit cell volumes and the corresponding R Bragg reliability factor are listed in the first three columns. The vanadium average oxidation state in each phase and the global composition of each sample were obtained taking into account the Vegard's law applied to the unit cell volume. The shorter V-X bond and the antagonist longer V-X bond along the chains [X-VO 4 -X]

n are also listed. The four last columns summarize the microstructure analysis. The width of microstrains' distribution along the [100], [010], [001] directions and in average for all [hkl] directions (ε = Δd hkl /d hkl ) and the crystallites domain sizes are given (* means no size effect induced broadening detected).

Table 3 :

 3 Wavenumbers and assignment of the main vibration bands observed by diffuse reflectance IR spectroscopy.

Table 1 :

 1

	Samples	colors	CHNS C (w%)	Li/V	ICP-OES Li/P	V/P	Particle Sizes (nm)
	LVPF	Black	5.65	0.98	1.02 1.04	300 -600
	LVPF-375	Black	4.29	1.02	1.01 0.99	300 -600
	LVPF-450 Dark grey	1.09	0.99	1.01 1.02	300 -600
	LVPF-525	Brown	0.22	0.97	0.99 1.03 500 -1000
	LVPF-600	Brown	/	1.03	1.06 1.03 500 -2000
	LVPF-700 Dark green	/	1.05	1.04 0.99 1000 -5000
	LVPO	Green	/	0.99	1.02	1.03 500 -1000

Table 2 :

 2

		# phase	R (%) Bragg	wt.%	V/Z (Å	3 )	Vanadium average oxidation state	Global composition	Distances along the chains (Å) the longer V-X the shorter V-X	Width of microstrains distribution ε along [100] [010] [001] average, (%) hkl In <hkl>	Crystallites' domain size D (nm)
	LVPF	1	3.72	100 87.18(1)	3	LiVPO	4 F	2.00(3)	1.96(3)	0.12	0.09	0.07	0.13	256.2
	LVPF-375	1	2.53	100 87.12(1)	3.04	LiVPO	4 O	0.04 F 0.96	2.00(3)	1.96(3)	0.16	0.19	0.17	0.20	466.1
	LVPF-450	1	2.61	100 87.05(1)	3.08	LiVPO	4 O	0.08 F 0.92	2.02(3)	1.93(3)	0.20	0.20	0.18	0.24	607.4
	LVPF-525	1 2	3.34 35(1) 87.01(2) 2.14 65(1) 85.63(2)	3.10 3.92	LiVPO	4 O	0.65 F 0.35	2.04(3) 2.08 (3)	1.85(3) 1.78(3)	0.23 0.64	0.31 0.72	0.25 0.40	0.33 0.53	173.8 227.1
	LVPF-600	1 2	3.14 47(2) 85.69(2) 2.64 53(2) 85.56(2)	3.89 3.97	LiVPO	4 O	0.93 F 0.07	2.04(3) 2.08(3)	1.84(3) 1.73(3)	0.32 0.33	0.27 0.40	0.24 0.33	0.27 0.35	* 767.6
	LVPF-700	1 2	3.21 41(2) 85.58(1) 2.15 59(2) 85.52(2)	3.96 3.99	LiVPO	4 O	0.98 F 0.02	2.15(3) 2.25(3)	1.72(3) 1.60(3)	0.23 0.24	0.19 0.23	0.23 0.24	0.21 0.23	* 1276.0
	LVPO	1	2.07	100 85.51(1)	4	LiVPO	4 O	2.24(3)	1.63(3)	/	/	/	/	/

Table 3 :

 3

	LVPF	LVPF-375	wavenumber (cm LVPF-450 LVPF-525	-1 ) LVPF-600	LVPF-700	LVPO	assignment	ref
	/	/	/	3400	3400	3400	3400	ν H-O-H	23
	/	/	/	1650	1650	1650	1650	δ H-O-H	23
	/	/	1163	1165	1166	1165	1165	ν PO4	24,26
	1120	1121	1113	1104	1104	1104	1103	ν PO4	24-26
	1051	1048	1051	1050	1055	1056	1056	ν PO4	24-26
	1007	1007	1006	1006	1001	998	998	ν PO4	24-26
	/	/	953	953	951	952	953	ν PO4	24,26
	874	877	889	896	895	912	915	ν V=O	26,29

Acknowledgment

The authors thank Philippe Dagault, Cathy Denage, Laetitia Etienne, and Eric Lebraud at ICMCB and Matthieu Courty at LRCS for technical assistance, François Weill and Sonia Buffière at ICMCB for the microscopy experiments, as well as ALBA (Barcelona, Spain) for Synchrotron X-ray diffraction experiments on MSPD beamline (proposal number 2015021236). The authors also acknowledge FEDER, the Région Haut-de-France and the RS2E Network for the funding of EB's PhD thesis, as well as the financial support of Région Nouvelle Aquitaine and of the French National Research Agency (STORE-EX Labex Project ANR-10-LABX-76-01 and HIPOLITE Progelec project ANR-12-PRGE-0005-02).

intercalation in the mixed valence V III /V IV pristine materials, LiVPO 4 F 1-x O x : very rapidly, already with a small amount of oxygen substitution for fluorine, only the LiVPO 4 O's electrochemical signature is detected. This work allows providing a description of the nature of the defects or of the derived compositions which can be obtained when the synthesis conditions of LiVPO 4 F are not perfectly controlled, versus the oxygen content during the thermal treatment or the cooling.

Furthermore, this study reveals that the versatility of the vanadium chemistry with a large number of stable oxidations states (from V 2+ to V 5+ ), but stabilized in very different environments (from very regular to very distorted ones), opens the road to the formation of new materials, whose structures and electrochemical activity can be complex to control due to the strains imposed by the crystal field.


Ellie Beauprez
email: ellie.beauprez@univ-lille.fr

Anne-Cécile Caron
email: anne-cecile.caron@univ-lille.fr

Maxime Morge
email: maxime.morge@univ-lille.fr

Jean-Christophe Routier
email: jean-christophe.routier@univ-lille.fr

A Multi-Agent Negotiation Strategy for Reducing the Flowtime

Keywords: Multi-Agent Systems, Distributed Problem Solving, Negotiation and Interaction Protocols

In this paper, we study the problem of task reallocation for load-balancing in distributed data processing models that tackle vast amount of data. In this context, we propose a novel strategy based on cooperative agents used to optimize the rescheduling of tasks for multiple jobs submitted by users in order to be executed as soon as possible. It allows an agent to determine locally the next task to process and the next task to delegate according to its knowledge, its own belief base and its peer modelling. The novelty of our strategy lies in the ability of agents to identify opportunities and bottleneck agents, and afterwards to reallocate some of the tasks. Our contribution is that, thanks to concurrent bilateral negotiations, tasks are continuously reallocated according to the local perception and the peer modelling of agents. In order to evaluate the responsiveness of our approach, we implement a prototype testbed and our experimentation reveals that our strategy reaches a flowtime which is close to the one reached by the classical heuristic approach and significantly reduces the rescheduling time.

INTRODUCTION

Data science involves the processing of large volumes of data which requires distributed file system and parallel programming. This emerging distributed computing topic brings new challenges related to task allocation and loadbalancing. This paper is concerned with a class of practical applications where (a) some jobs, i.e. sets of tasks, are concurrently submitted by users in order to be executed as soon as possible, and (b) some of the resources, e.g. data, required to successfully execute a task are distributed at different network nodes.

In this class of applications, we consider here MapReduce [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] which is the most prominent distributed data processing model for tackling vast amount of data on commodity clusters as with Hadoop (The Apache Software Foundation, 2020) or Spark [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF]. MapReduce jobs are divided into a set of tasks that are distributed on nodes ; the division labour should capitalize upon the way resources are distributed in the system. Indeed, as several resources are necessary to perform a task, any initial allocation inevitably requires fetching some of these resources from other nodes, thus incurring an extra time cost for task execution.

In order to tackle the problem of loadbalancing and task reallocation in applications such as those that motivate this work, multiagent technologies have received a lot of attention [START_REF] Jiang | A survey of task allocation and load balancing in distributed systems[END_REF]. Most of the existing works adopting the market-based approach [START_REF] Walsh | A market protocol for decentralized task allocation[END_REF][START_REF] Shehory | Methods for task allocation via agent coalition formation[END_REF][START_REF] An | Automated negotiation with decommitment for dynamic resource allocation in cloud computing[END_REF][START_REF] Turner | Distributed Strategy Adaptation with a Prediction Function in Multi-Agent Task Allocation[END_REF] model the loadbalancing problem as a non-cooperative game. By contrast, in line with [START_REF] Baert | A Location-Aware Strategy for Agents Negotiating Load-balancing[END_REF], we assume that agents are cooperative, viz.: they share the same objective and there is no shared knowledge, including any knowledge about the whole task allocation. Beyond [START_REF] Baert | A Location-Aware Strategy for Agents Negotiating Load-balancing[END_REF], we consider here several jobs which are divided into a set of tasks that can be performed by any multi-task agent. The agents aim at minimizing the mean flowtime of several concurrent jobs, i.e. the average completion time of these jobs. The main difficulty lies in the fact that task reallocation does not only change the workload of each agent but also their own scheduling. For this purpose, we propose a negotiation strategy which is composed of a consumption strategy and a delegation strategy. While the consumption strategy allows agents to decide the next tasks to execute, the delegation strategy decides which deal is suggested or accepted. The latter is based on peer modelling and determines the agent behaviour at each point of choice for the negotiation protocol: (a) the offer strategy selects a potential delegation, i.e. a task and a receiver; (b) the acceptability rule determines whether the agent accepts or declines a delegation. Inspired by our practical application, the experiments on our testbed evaluate the responsiveness of our approach.

Specifically, our contributions are as follows:

• We formalize the multi-agent situated task allocation problem with concurrent jobs where tasks have different costs for different agents due to the resource locality.

• We design a multi-agent strategy which allows the agents to continuously identify opportunities and bottleneck agents within a current unbalanced allocation. Afterwards, concurrent and bilateral negotiations amongst agents are triggered to locally delegate some of the tasks. Tasks reallocations occur continuoulsy according to the local perception and the peer modelling of agents.

• We conduct extensive experiments which

show that our method reaches a flowtime which is close to the one reached by the classical heuristic approach and significantly reduces the rescheduling time.

The paper is structured as follows. After an overview of the related work in Sec. 2, we formalize the multi-agent situated task allocation problem with concurrent jobs in Sec. 3. Sec. 4 describes the operations of consumption/delegation and the negotiation process. Sec. 5 specifies the consumption strategy, i.e. how agents choose the scheduling order of their own bundle. Sec. 6 details the delegation strategy, i.e. how agents choose which task to negotiate with whom. Our empirical evaluation is described in Sec. 7. Finally, Sec. 8 summarizes our contribution and outlines our future work.

RELATED WORK

Classical scheduling problems are constrained optimization problems that can be approximated by different heuristics such as hill climbing or simulated annealing (See [START_REF] Pinedo | Scheduling. Theory, Algorithms, and Systems[END_REF] for a survey). The limitations of these approaches for task reallocation in distributed systems are due to the following aspects:

• Decentralization: global control causes a performance bottleneck as it must collect status information of the entire system in real time. By contrast, agents can take local decisions over an existing allocation in order to improve the load-balancing.

• Adaptation: classical scheduling problems are static. The inaccurate estimation of tasks execution time and the disruptive phenomena (task consumption, job release, etc.), may require major modifications in the existing allocation to stay optimal. Agents can act in dynamic environments that evolve over time.

These are the reasons why multi-agent scheduling has received significant attention for load-balancing problems in distributed systems (See [START_REF] Jiang | A survey of task allocation and load balancing in distributed systems[END_REF] for a recent survey). Banerjee and Hecker propose in [START_REF] Banerjee | A Multi-agent System Approach to Load-Balancing and Resource Allocation for Distributed Computing[END_REF] a general distributed resource allocation protocol for load-balancing coarse-grained jobs on a massively distributed system. They emphasize that the local interactions between agents lead to some complex high-level emergent properties. By contrast, Selvitopi et al. investigate in (Selvitopi et al., 2019) the simultaneous scheduling of fine-grained tasks in order to improve the data locality and balance the workloads. Their approach is based on graph and hypergraph models which make use of applicationspecific knowledge. Our study aims at bridging this granularity gap by the reassignment of independent tasks within multiple jobs in an application-agnostic way. Schaerf et al. investigate in (Schaerf et al., 1995) the adaptive behaviour of agents for efficient load-balancing using multi-agent reinforcement learning. Turner et al. combine in (Turner et al., 2018) supervised classification learning with an internal decision-making process for task assignments. Conversely, we do not assume any prior model of the data/environment since it is not relevant considering the class of practical applications we are concerned with.

In [START_REF] Jiang | Locality-sensitive task allocation and load balancing in networked multiagent systems: Talent versus centrality[END_REF], the authors distinguish two kinds of vicinity: the locality of the resources which are needed to perform the tasks, and the neighbourhood of the agents. On this latter point, we assume a fully connected social network with uniform communication costs. In [START_REF] Zaharia | Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling[END_REF], the authors are concerned with data locality. In the context of the scheduling problem of MapReduce jobs composed of multiple tasks, they try to place computations near their input data in order to maximize the system throughput. In this paper, we abstract away from the practical applications, but we address a similar challenging problem by considering task consumption, job release and slowing down nodes as unexpected events in a dynamic environment.

On one hand, most of the existing works adopting the market-based approach model the load-balancing problem as a non-cooperative game. For instance, An et al. propose in [START_REF] An | Automated negotiation with decommitment for dynamic resource allocation in cloud computing[END_REF] a distributed negotiation mechanism where selfish agents negotiate over resources both a contract price and a decommitment penalty. On the other hand, most of the solving algorithms for the distributed constraint optimization problems (See [START_REF] Fioretto | Distributed constraint optimization problems and applications: A survey[END_REF] for a recent survey) try to optimize a singleobjective function which is assumed to be utilitarian (a sum of costs to be minimized). More recently, [START_REF] Baert | A Location-Aware Strategy for Agents Negotiating Load-balancing[END_REF] targets an egalitarian objective which is the minimization of the maximum completion time of the tasks to perform (i.e. the makespan). In this paper, we consider the problem of coordinating agent decisions to find a globally optimal solution for multi-objective functions. The agents try to minimize the mean flowtime of several concurrent jobs, i.e. the mean of the maximum completion times of the tasks in these jobs.

SITUATED TASKS

We formalize here the multi-agent situated task allocation problem with concurrent jobs.

A job is a set of independent, non divisible and non preemptive tasks without precedence order. The execution of each task requires resources which are distributed at different nodes. We consider that the resources are transferable and non consumable.

Definition 1 (Distributed system). A system is a triple D = N, E, R where: For simplicity, we assume that there is exactly one agent per node (the set of agents is N) and all the resources are accessible by any agent.

• N = {ν 1 , . . . ,
The execution of a job (without deadline) consists of the performance of a set of independent tasks which require resources to produce an outcome.

Definition 2 (Job/Task). Let D be a distributed system and Outcome be the space of outcomes. We consider the set of jobs J = {J 1 , . . . , J }. Each job J i is a set of k i tasks J i = {τ 1 , . . . , τ k i } associated to the release date t 0 J i where each task τ is a function which links a set of resources to an outcome: τ : 2 R → Outcome.

T = 1≤i≤ J i denotes the set of the n tasks of J and R τ ⊆ R is the set of the resources required for the task τ. For the sake of brevity, we denote job(τ) the job containing the task τ. We assume that the number of jobs is negligible with respect to the number of tasks, |J| << |T|.

The task cost estimates its runtime on a node.

Definition 3 (Task cost). Let D be a distributed system and T be a set of tasks. the cost function is s.t.:

c : T × N → R * + (2)
The cost of the task τ i for the node ν j is a strict positive real number denoted c(τ i , ν j ).

The difficulty lies in the specification of this function in order to have a good estimation of the runtime. As the fetching time of resources is supposed to be significant, the cost function must verify that the task τ is cheaper for ν i than for ν j (c(τ, ν i ) ≤ c(τ, ν j )) if the required resources are "more local" to ν i than to ν j . We postpone the full specification of the task cost function to the experimental setup (Sec. 7).

A multi-agent situated task allocation problem with concurrent jobs consists of assigning several jobs to some nodes according to the underlying task costs.

Definition 4 (MASTA+).

A multi-agent situated task allocation problem is a quadruple MASTA+ = D, T, J, c where:

• D = N, E, R is a distributed system with m nodes; • T = {τ 1 , . . . , τ n } is a set of n tasks; • J = {J 1 , . . . , J } is a set of jobs, i.e. a partition of tasks s.t. (T = 1≤i≤ J i ) ∧ (J i ∩ J i = ∅ with 1 ≤ i = j ≤ ) (3) • c : T × N → R *
+ is the task cost function. A task allocation is a distribution of sorted bundles at different nodes.

Definition 5 (Allocation). Let MASTA+ be a task allocation problem. An allocation is a vector of m sorted task bundles. A = ((B 1 , ≺ 1 ), . . . , (B m , ≺ m )) where each bundle (B i , ≺ i ) is the set of tasks (B i ⊆ T) assigned to the node ν i associated with a scheduling order, i.e. a strict and total order (

≺ i ⊆ T × T) s.t. τ j ≺ i τ k means that if τ j , τ k ∈ B i then τ j is performed before τ k by ν i . The allocation A is s.t.: ∀τ ∈ T, ∃ν i ∈ N, τ ∈ B i (4) ∀ν i ∈ N, ∀ν j ∈ N \ {ν i }, B i ∩ B j = ∅ (5)
All the tasks are assigned (Eq. 4) and each task is assigned to a single node (Eq. 5). For brevity, we denote:

• B i = (B i , ≺ i ), the sorted bundle of ν i ; • min ≺ i B i ,
the next task to perform by ν i :

• jobs(B i ), the set of jobs assigned to ν i , i.e. the jobs having at least one task in B i ;

• ν(τ, A), the node responsible for τ in A.

The sum of the task costs in a bundle estimates its runtime. Formally, The workload of ν i for A is:

w i ( A) = ∑ τ∈B i c(τ , ν i ) (6)
In order to evaluate a task allocation, we consider the flowtime, which measures the time between the release date of the jobs and their completion dates, and the makespan which is the completion time of all the jobs. Definition 6 (Flowtime/Makespan). Let MASTA+ be a task allocation problem and A be an allocation. We define:

• the delay of τ for ν i ,

t(τ, ν i ) = ∑ τ ∈B i |τ ≺ i τ c(τ , ν i ) (7) • the completion time of τ ∈ T for A, C τ ( A) = t(τ, ν(τ, A)) + c(τ, ν(τ, A)) (8)
• the completion time of J ∈ J for A,

C J ( A) = max τ∈J {C τ ( A)} (9)
• the completion date of J ∈ J for A,

t E J ( A) = t 0 J + C J ( A) (10)
• the mean flowtime of J for A,

C( A) = 1 ∑ J∈J C J ( A) (11)
• the makespan of J for A,

C max ( A) = max J∈J t E J ( A) (12)
• the local availability ratio of A,

L( A) = ∑ τ∈T ∑ ρ∈R τ , ν(τ, A)∈l(ρ) |ρ| ∑ ρ∈R τ |ρ| (13)
The delay of a task for a node estimates the runtimes (costs) of the previous tasks in the bundle (Eq. 7) since we assume the nodes are never inactive. The completion time of a task is the sum of the delay before the task is started plus its runtime (Eq. 8). Contrary to the cost of the task, its delay and its completion time depend on the scheduling order over the bundle. According to Eq. 9, a job is finished for all the agents when they have performed all the tasks in this job. The completion date of a job is the finishing date (Eq. 10). The mean flowtime is the mean completion time of the jobs (Eq. 11). Since the makespan measures the maximum completion time of the jobs (Eq. 12), it is the maximum workload of the nodes:

C max ( A) = max ν i ∈N {w i ( A)} (14)
Contrary to the makespan, the flowtime depends on the scheduling order. The local availability ratio measures the proportion of locally processed resources (Eq. 13).

Example 1 (MASTA+). We consider D = N, E, R where:

• 3 nodes N = {ν 1 , ν 2 , ν 3 } are fully connected E = {(ν 1 , ν 2 ), (ν 1 , ν 3 ), (ν 2 , ν 3 )}; • 9 resources R = {ρ 1 , ρ 2 , ρ 3 , ρ 4 , ρ 5 , ρ 6 , ρ 7 , ρ 8 , ρ 9 }
are replicated over 2 nodes (Fig. 1a). For instance, ρ 1 , with |ρ 1 | = 6, is over ν 1 and ν 2 but not over ν 3 .

ρ 2 ρ 3 ρ 4 ρ 5 ρ 6 ρ 7 ρ 8 ρ 9 ρ 1 ρ 2 ρ 3 ρ 4 ρ 5 ρ 6 ρ 7 ρ 8 ρ 9 ρ 1 ρ 2 ρ 3 ρ 4 ρ 5 ρ 6 ρ 7 ρ 8 ρ 9 J 1 J 2 J 3 Jobs ν 1 ν 2 ν 3 Nodes (a) Resource distribution ν1 ν2 ν3 Nodes 0 2 4 6 8 10 Workload τ 1 τ 4 τ 7 τ 5 τ 8 τ 2 τ 3 τ 9 τ 6 J 1 J 2 J 3 Jobs (b) Allocation
τ 1 τ 2 τ 3 τ 4 τ 5 τ 6 τ 7 τ 8 τ 9 c(τ, ν 1 ) 3 5 0.5 3 2 6 4 2 1 c(τ, ν 2 ) 3 5 0.5 3 1 12 4 1 2 c(τ, ν 3 ) 6 10 1 6 1 6 8 1 1
Table 1: The cost of the tasks for the nodes

We also consider MASTA+ = D, T, J, c with:

• 9 tasks T = {τ 1 , τ 2 , τ 3 , τ 4 , τ 5 , τ 6 , τ 7 , τ 8 , τ 9 }. Each one requires the corresponding resource, e.g.

ρ 1 is required for τ 1 ; • 3 jobs J = {J 1 , J 2 , J 3 }, s.t. J 1 = {τ 1 , τ 2 , τ 3 }, J 2 = {τ 4 , τ 5 , τ 6 } and J 3 = {τ 7 , τ 8 , τ 9 }. • the cost function which is represented in Tab. 1.
We assume that the cost of a task is proportional to the resource size and two times more important if the resource is remote.

The allocation represented in Fig. 1b is s.t. B 1 = (τ 1 , τ 4 , τ 7 ), B 2 = (τ 5 , τ 8 , τ 2 ) and B 3 = (τ 3 , τ 9 , τ 6 ).

The makespan and the mean flowtime are C max ( A) = 10 and C( A) = 8.33, respectively. In summary, we consider heterogeneous nodes because the cost of tasks depend on the processing nodes due to the locality of the underlying resources. Our objective is to minimize the mean flowtime of the concurrent jobs containing several tasks:

R m |Σ J∈J max τ∈J C τ ( A)

CONSUMPTION AND DELEGATION PROCESS

We describe here the operations of consumption/delegation and we sketch the negotiation protocol.

The addition/removal of the task τ in the bundle B i modifies not only the set of tasks but also the scheduling order over the bundle. Formally,

• if τ / ∈ B i then ---→ B i ⊕ τ denotes the bundle which contains the set of tasks B i ∪ {τ} sorted with ≺ i ; • if τ ∈ B i then ---→ B i τ denotes the bundle which contains B i \ {τ} sorted with ≺ i .
These operations imply a rescheduling of the bundle. As we will see in Sec. 5, the consumption strategy specify the scheduling order.

A task consumption is a disruptive event which modifies not only the allocation of tasks but also the underlying problem. Definition 7 (Consumption). Let MASTA+ = D, T, J, c be a task allocation problem and A be an allocation. The consumption of τ by ν i with a nonempty bundle (B i = ∅) leads to the allocation A = γ(ν i , A) for the problem MASTA = D, T , J , c where:

T = T \ {min ≺ i B i } (15) J =      J \ {job(min ≺ i B i )} if job(min ≺ i B i ) = {min ≺ i B i } J else (16)
In the latter case:

J j = J j \ {min ≺ i B i } if job(min ≺ i B i ) = J j J j else (17)
and

B j = --------→ B i min ≺ i B i if j = i B j else ( 18
)
The task is removed from the set of tasks (Eq. 15) and from the corresponding job (Eq. 17). The latter is removed if it only contains τ (Eq. 16). The task is removed from the allocation (Eq. 18). Obviously, a task consumption can increase neither the makespan nor the flowtime but it decreases the local makespan (w i (γ(ν i , A)) < w i ( A)) and the local flowtime

(Σ J∈jobs(B i ) C J (γ(ν i , B i )) < Σ J∈jobs(B i ) C J ( B i ))
. The sequence of consumptions, which consists of an iteration of MASTA+ problems, removes one by one all the tasks from the initial allocation to the empty one.

A task delegation is a disruptive event which changes the current allocation, i.e. a reallocation.

Definition 8 (Delegation). Let MASTA+ = D, T, J, c be a task allocation problem and A = ( B 1 , . . . , B m ) be an allocation. If the task τ is assigned to the donor ν i (τ ∈ B i ), then the delegation to the recipient ν j leads to the allocation δ(τ, ν i , ν j , A) with the m bundles δ(τ, ν i , ν j , B k ) such as:

δ(τ, ν i , ν j , B k ) =      ---→ B i τ if k = i ---→ B j ⊕ τ if k = j B k else (19)
A task delegation must reduce the local makespan and the local flowtime.

Definition 9 (Socially rational delegation). Let MASTA+ = D, T, J, c be a task allocation problem, A be an allocation and δ(τ, ν i , ν j , A) the allocation after the delegation of τ by ν i to ν j . This delegation is socially rational:

• with respect to the makespan if and only if the local makespan decreases

w j ( A) + c(τ, ν j ) < w i ( A) (20)
• with respect to the flowtime if and only if the local flowtime decreases

Σ J∈jobs(B i ∪B j ) max(C J ( ---→ B i τ), C J ( ---→ B j ⊕ τ)) < Σ J∈jobs(B i ∪B j ) max(C J ( B i ), C J ( B j )) ( 21
)
An allocation is stable if none of the agents have socially rational delegations. In a stable allocation with respect to the makespan, agents cannot locally improve the makespan.

Property 1 (Termination). Let MASTA+ = D, T, J, c be a task allocation problem and A be a non-stable allocation with respect to the makespan.

There is always a finite path of socially rational delegations with respect to this criterion, which leads to a stable allocation with respect to makespan.

The property derives from Theo. 7 in [START_REF] Endriss | Negotiating Socially Optimal Allocations of Resources[END_REF]. By contrast, a sequence of socially rational delegations with respect to the flowtime does not necessarily lead to a stable allocation for this criterion.

Agents operate in multiple bilateral singleround negotiations for task delegations. Each negotiation, which is based on the alternating offers protocol [START_REF] Rubinstein | Perfect equilibrium in a bargaining model[END_REF], includes three decision steps: (a) the offer strategy of the proposer (Sec. 6) which selects a potential delegation, i.e. a task in its bundle and a recipient, (b) the acceptability rule (Sec. 6) allows the responder to determine whether it rejects or accepts such a delegation, and (c) in the latter case, the delegation is confirmed or withdrawn by the proposer depending on the interleaved consumptions.

CONSUMPTION STRATEGY

We describe here the consumption strategy adopted by an agent to select the next task to perform, i.e. a scheduling order over its bundle based on its local knowledge.

We consider a task allocation problem MASTA+ = D, T, J, c and an allocation A. Each agent ν i ∈ N which knows the problem and has a local perception of the allocation, i.e. its bundle B i , can deduce the following metrics: • its workload (Eq. 6);

• the delay of the tasks in its bundle (Eq. 7);

• the completion time of these tasks (Eq. 8);

• the completion time of the jobs for the node,

C J ( B i ) = max τ∈J∩B i {C τ ( B i )} if J ∈ jobs(B i ) 0 else (22)
• the job costs for the node,

c(J , ν i ) = Σ τ∈J∩B i c(τ , ν i ) (23)
It is worth noticing that the mean completion time of the jobs for an agent depends on the scheduling order over its bundle.

A consumption strategy is defined by a scheduling order, i.e. a strict total order over the bundle. Since we aim at minimizing the completion time of jobs rather than tasks we focus on job-oriented consumption strategies. Such a strategy is a lexicographic order which consists of sorting first jobs, and then the tasks inside the same job.

Definition 10 (Job-oriented strategy). Let i and i two strict total order relations over T and J, respectively. A job sorting strategy based on ( i , i ) sorts the bundle B i according to the strict total order relation ≺ i defined by:

∀τ j , τ k ∈ B i τ j ≺ i τ k ⇔ job(τ j ) i job(τ k ) ∨ (job(τ j ) = job(τ k ) ∧ τ j i τ k ) (24)
J 1 i J 2 means that the tasks in J 1 are prior to the tasks in J 2 . The tasks in the same job are consecutive in the bundle.

The job-oriented consumption strategy we consider in this paper aims at minimizing the completion times of jobs by sorting them according to their costs.

Definition 11 (LCJF). Let i a strict total order on T. A job sorting strategy based on ( i , i ) is said "Locally Cheapest Job First" (LCJF) if and only if the relation i over the jobs satisfies :

∀J j , J k ∈ J, J j i J k ⇔ c(J j , ν i ) < c(J k , ν i ) ∨ (c(J j , ) = c(J k , ν i ) ∧ J j < J k ) ( 25
)
where < denotes the order over the jobs induced by the natural order over their identifiers.

This strategy executes the tasks in the cheapest jobs before the tasks in the expensive ones.

The relation over the jobs i is based on the knowledge of the agent about the MASTA+ problem and its own bundle. This scheduling order is strict and total since < discriminates the ties. Since we assume a strict total order over the tasks i (e.g. arbitrary the natural order over the task identifiers), ≺ i is also strict and total.

A LCJF strategy allows ν i to locally minimize the completion time of jobs. None permutation of jobs in the bundle can strictly decrease the local flowtime.

Lemma 1 (LCJF). Let ≺ i be a LCJF strategy based on ( i , i ).

∀σ ∈ S(jobs(B

i )), Σ J∈jobs(B i ) C J ( B i ) ≤ Σ J∈jobs(B i ) C J (σ( B i )) ( 26
)
where S(jobs(B i )) denotes the set of all the permutations of the jobs assigned to ν i .

The lemma derives from Theo. 3.1.1 in Chap. 3 of [START_REF] Pinedo | Scheduling. Theory, Algorithms, and Systems[END_REF].

Example 2 (LCJF). Let us consider Ex. 1. If the bundles are B 1 = {τ 1 , τ 4 , τ 7 }, B 2 = {τ 2 , τ 5 , τ 8 } and, B 3 = {τ 3 , τ 6 , τ 9 }, the allocation sorted with the LCJF strategy (Fig. 1b) is s.t.:

• B 1 = (τ 1 , τ 4 , τ 7 ) since (c(J 1 , ν 1 ) = c(τ 1 , ν 1 )) < (c(J 2 , ν 1 ) = c(τ 4 , ν 1 )) < (c(J 3 , ν 1 ) = c(τ 7 , ν 1 )); • B 2 = (τ 5 , τ 8 , τ 2 ) since (c(J 2 , ν 2 ) = c(τ 5 , ν 2 )) = (c(J 3 , ν 2 ) = c(τ 8 , ν 2 )) < (c(J 1 , ν 2 ) = c(τ 2 , ν 2 )) and J 2 < J 3 ; • B 3 = (τ 3 , τ 9 , τ 6 ) since (c(J 1 , ν 3 ) = c(τ 3 , ν 3 )) = (c(J 3 , ν 3 ) = c(τ 9 , ν 3 )) < (c(J 2 , ν 3 ) = c(τ 6 , ν 3 ))
and J 1 < J 3 .

DELEGATION STRATEGY

We describe here the different parts of the delegation strategy (peer modelling, acceptability rule, offer strategy) and we sketch the agent behaviour.

The peer modelling is built upon the information exchanged by the agents through messages. In particular, the agent ν i informs its peers about the job costs for it (c(J , ν i ), ∀J ∈ J) before the negotiation process and after each delegation in which it is involved. Since the number of jobs is much smaller than the number of tasks, the size of theses messages (O(|J|)) is negligible wrt the task bundle descriptions (O(|T|)). The peer modelling of the target ν j by the subject ν i is based on:

• the belief base of the subject, eventually partial or obsolete, which contains the belief about the job costs for ν j (c i (J, ν j ) ∀J ∈ J) and the belief about the workload of ν j (w i j ( A) = Σ J∈J c i (J, ν j ));

• the consumption strategy of the target assumed by the subject which boils down to the relation over the jobs adopted by the target, denoted i j .

For readability, we denote c i (J,

ν i ) = c(J, ν i ) and w i i ( A) = w i ( A).
From its beliefs about the target and the assumed consumption strategy, the subject can deduce the completion time of the job J for the target, eventually after the addition/removal of τ : C

i J ( B j ), C i J ( ---→ B j ⊕ τ) and C i J ( ---→ B j τ).
Then, the subject can deduce the completion time of a job for the allocation:

C i J ( A) = max ν j ∈N C i J ( B j ) where C i J ( B i ) = C J ( B i ) (27)
The subject considers the target as a bottleneck for the job J (ν j = nodeMax i ( A, J)) if the completion time of this job for the target is the completion time for the allocation, i.e. C i J ( A) = C i J ( B j ). The acceptability rule is a local decision by the recipient of a delegation, which is based on its knowledge and its peer modelling, to determine whether a delegation is accepted or declined depending on its perception of the social rationality of the delegation.

Definition 12 (Acceptability criterion). Let δ(τ, ν i , ν j , A) be the delegation of τ from ν i to ν j in A. This delegation is acceptable by the recipient :

• with respect to the makespan if and only if the recipient believes that the delegation decreases the local makespan,

w j ( A) + c(τ, ν j ) < w j i ( A) (28)
• with respect to the flowtime if and only if the recipient believes that the delegation decreases the local flowtime,

Σ J∈J max(C j J ( ---→ B i τ), C J ( ---→ B j ⊕ τ)) < Σ J∈J max(C j J ( B i ), C J ( B j )) (29)
While the first criterion is built upon the belief about the workload of the donor (Eq. 28), the second one is built upon the knowledge about the completion times of the jobs for the recipient before/after the delegation and its belief about the completion times of the jobs for the donor before/after the delegation (Eq. 29).

In order to reduce the flowtime, the acceptability rule consists in checking not only the acceptability criterion wrt the flowtime but also the acceptability criterion wrt the makespan which guarantees the convergence of the negotiation process (Prop. 1).

The offer strategy of a possible donor ν i , which is based on its knowledge and its peer modelling, selects a potential delegation: a recipient, a task and so a job. The strategy is divided in 4 steps:

1. Job selection. According to the principle of subsidiarity, the goal of the donor is to reduce the completion time of the jobs it is responsible for. In order to reduce not only the completion time of one job for the donor but also the completion time of the next jobs in B i , our heuristic selects the prior job for which the donor is a bottleneck,

∀J ⊆ J, J * = σ i (J ) = min i {J ∈ jobs(B i ) ∩ J | ν i = nodeMax i ( A, J)} (30)
2. Recipient selection. The jobs assigned to the recipient which are impacted by the delegation are those after J * according to i j . Not to increase the completion times of these jobs, our heuristic selects the recipient for whom the sum of the differences between the completion time for the allocation and the completion time for this agent is the greatest one, 31) where < denotes the order over the nodes induced by the natural order over their identifiers.

∀N ⊆ N, ν * = σ i (N , J * ) = min < {argmax ν j ∈N ∑ J * i j J (C i J ( A) -C i J ( B j ))} (
3. Task selection. In order to reduce the completion times, the donor selects a distant task whose delegation reduces its cost since it is locally executed. For this purpose, our heuristic selects the task in the job J * or in the prior jobs in B i with the highest payoff. In case of tie, the prior task is chosen,

∀T ⊆ T, τ * = σ i (T , ν * , J * ) = min i { argmax τ∈T ∩B i ∩{J|J=J * ∨(J i J * )} c(τ, ν i ) -c(τ, ν * )} (32)
4. Validation. By symmetry with the acceptability criterion (Def. 12), the trigger criterion is a local decision by the donor to determine whether a delegation is perceived as socially rational. In order to warranty the convergence of the negotiation process, the trigger rule is a conjunction of the trigger criterion wrt the makespan and the trigger criterion wrt the flowtime. If the trigger rule is not satisfied, then another task (T = T \ {τ * } in step 3) or another recipient (N = N \ {ν * } in step 2), eventually another job (J = J \ {J * } in step 1) is chosen. In case of failure, no delegation is proposed and the agent enters in pause until its belief base is updated and a new opportunity (i.e. a potential delegation) is found.

In our approach, the task reallocation is the outcome of negotiations between agents adopting the same behaviour: they alternatively play the roles of proposer, responder and contractor. The agents execute this behaviour according to their knowledge and beliefs. The agent behavior is specified in [START_REF] Beauprez | Scala implementation of the Extended Multi-agents Situated Task Allocation[END_REF]) by a deterministic finite state automaton 1 . In order to avoid deadlock, the proposals are associated with deadlines.

It is worth noticing the reception of the message from the peers updates the belief base of the agent and none proposal is sent when the agents believes that the allocation is stable.

Example 3 (Delegation strategy). Let us consider the MASTA+ instance and the allocation A of Ex. 1. We assume that the agents have up-to-date beliefs and that they know that all of them adopt the LCJF strategy. Contrary to ν 1 and ν 2 , the agent ν 3 can make a proposal since it selects: 1. the job for which it is a limiting factor (Eq. 30), J * = J 2 ; 2. the less bottleneck agent for the impacted jobs (Eq. 31) which are the jobs J 3 for ν 1 and the jobs J 1 and J 3 for ν 2 :

∑ J * 3 1 J (C 3 J ( A) -C 3 J ( B 1 = 0 (33) ∑ J * 3 2 J (C 3 J ( A) -C 3 J ( B 2 )) = 8 (34)
Therefore, ν * = ν 2 ; 3. the prior task with the highest payoff (Eq. 32) in J 2 or in the prior jobs, i.e. J 1 and J 3 :

(c(τ 6 , ν 3 ) -c(τ 6 , ν 2 )) = 6 -12 = -6 (c(τ 9 , ν 3 ) -c(τ 9 , ν 2 )) = 1 -2 = -1 (c(τ 3 , ν 3 ) -c(τ 3 , ν 2 )) = 1 -0.5 = 0.5 (35)
Therefore, τ * = τ 3 ; 4. the delegation is triggerable since the trigger criterion wrt the flowtime is satisfied,

Σ J∈J max(C J ( ----→ B 3 τ 3 ), C 3 J ( ----→ B 2 ⊕ τ 3 )) = 16.5 < Σ J∈J max(C J (B 3 ), C 3 J (B 2 )) = 17.0 (36)
and the trigger criterion wrt the makespan is satisfied, w 3 2 ( A) + c(τ, ν 2 ) = 7.5 < w 3 ( A) = 8.0 (37)

1 https://gitlab.univ-lille.fr/maxime.morge/ smastaplus/-/tree/master/doc/specification

The donor ν 3 delegates the task τ 3 to the agent ν 2 to reach A = δ(τ 3 , ν 3 , ν 2 , A) s.t. B 1 = {τ 1 , τ 4 , τ 7 }, B 2 = {τ 5 , τ 8 , τ 3 , τ 2 } and B 3 = {τ 9 , τ 6 }. The allocation is stable.

EMPIRICAL EVALUATION

We consider as a practical application the distributed deployment of the MapReduce design pattern in order to process large datasets on a cluster, as with Hadoop (The Apache Software Foundation, 2020) or Spark [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF]. We focus here on the reduce stage of MapReduce jobs. This can be formalized by a MASTA+ problem where several jobs are concurrently submitted and the cost function is s.t.:

c i (τ, ν j ) = ∑ ρ j ∈R τ c i (ρ j , ν j ) with c i (ρ j , ν i ) = |ρ j | if ν i ∈ l(ρ j ) κ × |ρ j | else ( 38
)
where we empirically calibrate κ = 2 as a realistic value.

To our best knowledge, no alive project of agent platforms provides a logic-based agent programming language, allowing a direct implementation of concepts such as beliefs and goals, that supports the development of cognitive agents for large-scale, distributed applications and services. That is the reason why our testbed [START_REF] Beauprez | Scala implementation of the Extended Multi-agents Situated Task Allocation[END_REF] is implemented with the general purpose programming language Scala and Akka [START_REF] Lightbend | Akka is the implementation of the actor model on the JVM[END_REF] for highly concurrent, distributed, and resilient message-driven applications. We assume that: (a) the message transmission delay is arbitrary but not negligible, (b) the message order per sender-receiver pair is preserved, and (c) the delivery of messages is guaranteed. Experiments have been conducted on a blade with 20 CPUs and 512Go RAM.

We consider three metrics: (1) the mean flowtime (Eq. 11), (2) the local availability ratio (Eq. 13), and (3) the scheduling time. We aim at (i) comparing the allocation reached by our negociation process with the classical approach, and (ii) evaluating the acceleration thanks to the decentralization.

The outcome reached by the general-purpose solver IBM® ILOG® CPLEX® tackling the underlying non-linear discrete mathematical optimization problem is poor. This is the reason why our baseline is a hill climbing algorithm. The latter and our method both start with the same randomly generated initial allocation sorted according to the LCJF strategy. At each step, the hill climbing algorithm iteratively selects among all the possible delegations, the one which minimizes the flowtime after the application of the LCJF strategy.

The MASTA+ problem instances we consider are such that m ∈ [2; 12] nodes/agents, ∈ [2; 5] jobs and n = 3 × × m tasks. We consider one resource per task. Each resource ρ i is replicated 3 times and |ρ i | ∈ [0; 100]. We generate 10 MASTA+ problem instances, and for each we randomly generate 10 initial allocations.

The hypothesis we want to test are: (1) the flowtime reached from our strategy is close to the one reached by the classical approach and (2) the decentralization significantly reduces the scheduling time.

Figures 2a and2b present the medians of the flowtime and the scheduling time exhibited by the methods depending on the number of nodes and the number of jobs. Figures 2c, 2d and 3 focus on the medians and the standard deviations of all the metrics depending on the number of nodes with = 4 jobs. It is worth noticing that the hill climbing algorithm has been used with small MASTA+ instances due to its prohibitive scheduling time. At each step, the hill climbing algorithm considers all the possible delegations, thus it reaches an allocation with a better flowtime than our strategy. Since the overhead of our strategy is 25%, our delegation strategy seems to be efficient even if the acceptability criterion wrt the makespan, which is required to guarantee the convergence, may lead to discard some delegations which may reduce the flowtime (Sec. 4). This is due to the fact that the delegation strategy selects the distant tasks whose delegations reduce their cost in order to improve local availability ratio which is slightly better than the one reached by the hill climbing algorithm. Moreover, since the latter evaluates at each step all the possible delegations, its scheduling time is much higher than the one of our negociation strategy. For instance, it is six times higher for 9 agents and 4 jobs.

It is worth noticing that the gap between the scheduling times of the two methods increases exponentially with the number of agents, while the gap between the flowtimes is roughly constant. We can expect a higher scheduling time if we adopt a local search method such as the simu-lated annealing without any warranty about the optimality of the outcome.

As a result, even if the number of agents is small, the gain realized on the flowtime by the hill climbing algorithm will be penalized and cancelled by the overhead of its scheduling time. This overhead penalized the time-extented assignment in a distributed system which should be adaptive to disruptive phenomena (task consumption, job release, slowing down nodes).

Finally, we observe that, when it is decentralized on several cores, the acceleration of our algorithm increases with the number of agents and jobs. For instance, with a similar flowtime neglecting the observable nondeterminism of their executions, the decentralized version runs 3 times faster than the centralized one for 12 agents and 4 jobs.

CONCLUSION

In this paper, we have proposed a multi-agent system for task reallocation among distributed nodes based on the location of the required resources in order to minimize the mean flowtime of concurrent jobs. Our prototype has been empirically evaluated. Our experiments show that the flowtime reached by our strategy is close to the one reached by the classical heuristic approach and it significantly reduces the rescheduling time. This is due to the fact that our negotiation process continuously adapts the allocation in order to improve the load-balancing by reducing the completion times of the jobs for the bottleneck agents. On one hand, the consumption strategy performs the tasks of the cheapest jobs before the most expensive ones. On the other hand, the delegation strategy selects a job which can reduce the completion times of the donor by choosing a receiver which is not a bottleneck for the impacted jobs and by choosing a task whose delegation reduces its cost since it is locally executed. A sensitivity analysis to study the influence of the replication factor has been beyond the scope of this work, but it is certainly worth of further investigation. Obviously, our approach is scalable since it tackles a large number of tasks due to the local decisions of agents about the next task to delegate/execute. Moreover, the overhead of the negotiation is negligible with respect to the benefit of the load-balancing since no negotiation is triggered when the agents believe that the allocation is stable.

A comparative study of our strategy with different distributed resolution methods algorithms is beyond the scope of this paper, but it is certainly worth of further investigation. Some of our experiments suggest that we need to extend our negotiation framework to consider (a) task swaps to improve the mean flowtime of stable allocations, and (b) a less restrictive acceptability rule which currently discards some task delegations which may reduce the flowtime. Gener-ally, future work must extend the task reallocation toward an iterated, dynamic and on-going process, which takes place concurrently with the task execution, allowing the distributed system to be adaptive to disruptive phenomena (task consumption, job release, slowing down nodes).

Figure 1 :

 1 Figure 1: The resource distribution and the allocation sorted by the LCJF strategy

Figure 2 :Figure 3 :

 23 Figure 2: The mean flowtime and the scheduling time for our (centralized and decentralized) negociation strategy and the hill climbing algorithm.

ACKNOWLEDGMENTS

We thank the anonymous reviewers for their stimulating comments which help us to improve the paper.