Lea Lojkova

Lea Lojková

Bořivoj Klejdus

Jitka Moravcová

Vlastimil Kubáň

Supercritical fluid extraction (SFE) of 4(5)-methylimidazole (4MeI) and 2-acetyl-4(5)-1 (1,2,3,4-tetrahydroxybutyl)-imidazole (THI) from ground-coffee with liquid 2 chromatographic-electrospray mass spectrometric quantification (HPLC/ESI-MS) 3 4

Keywords: supercritical fluid extraction, solid phase extraction, 4(5)-methylimidazole, 2-33 acetyl-4(5)-(1, 2, 3, 4-tetrahydroxybutyl

    Supercritical fluid extraction of 4(5)-methylimidazole (4MeI) and 2-acetyl-4(5)-(1,2,3,4)tetrahydrohydroxybutylimidazole (THI) from grounded coffee with liquid chromatographic -electrospray mass spectrometric (HPLC/ESI-MS) quantification

Introduction 35

Coffee is well known as a stimulant of a central nervous system and as a diuretic. Its 36 world production is about 4 millions tons per annum. Small, evergreen woods of Coffea 37 arabica, C. liberica and C. canephora (Rubiaceae) are planted in many varieties in tropic 38 areas all over the world. They bear coffee seeds (Semen Coffeae) containing 0.3 -2.5 % of 39 caffeine and traces of theophylline -important natural drugs -purine derivatives originated 40 from xanthine methylation [START_REF] Tomko | Farmakognózia, Osveta[END_REF][START_REF] Reeve | Suppresive effect of 2-acetyl-4-470 tetrahydroxybutylimidazole on contact hypersensitivity in the SKH-HR hairless mouse[END_REF]. Ripe coffee seeds are rid of the 41 pulp, endocarp and seed coat in so-called wet or dry way. Finally the selected grains are 42 roasted at 200 -250 °C to get typical coffee aroma and taste. 43

During the roasting process, undesirable imidazole compounds -a neurotoxic 4(5)-44 methylimidazole (4MeI) and an immunosuppressive 2-acetyl-4( 5)-(1,2,3,4-45 tetrahydroxybutyl)-imidazole (THI) -are formed by heating saccharides with nitrogenous 46 compounds. THI has a lymphopenic effect and impairs immunity of rats and mice by 47 modifying splenocyte function, in a histamine-like receptor site [START_REF] Vávrová | Caffeine 473 induces a second wave of apoptosis after low dose-rate gamma radiation of HL-60 cells[END_REF]. THI 48 also restrains contact hypersensitivity. Mice fed with THI have less CD4+ and CD8+ T cells -49 THI probably inhibits a contact hypersensitivity response by preventing the recruitment of 50 CD4+ T cells in the draining lymph nodes [START_REF] Gugasyan | The effect of 2-acetyl-4-tetrahydroxybutyl-444 imidazole on lymphocyte subsets during a contact hypersensitivity response in the NOD 445 mouse[END_REF]. 51

It is impossible to avoid completely the THI and 4MeI formation during the coffee 52 roasting and other food industry processes, but the concentration of both compounds should 53 be kept as low as possible in foods and beverages. For example, the European Commission 54 specified the legal limit of 10 and 200 mg.kg -1 for THI and 4MeI, respectively, for Class III 55 caramel colour. 56

Several procedures have been published for separate determination of either 4MeI or 57 THI in 1986 -95 period. They have been based on LC/UV and LC/MS (Thomsen and 58 Willumsen 1995[START_REF] Moravcová | Determination of 4-methylimidazole in 459 couler[END_REF][START_REF] Müller | Ammoniated forage poisoning: 461 Isolation and characterization of alkyl-substituted imidazoles in ammoniated forage and in 462 milk[END_REF][START_REF] Wagner | HPTLC as a reference method in clinical-chemistry -476 Online coupling with spectroscopic methods[END_REF], Lawrence 59 and Charbonneau 1987[START_REF] Ding | Determination of 2-acetyl-4-435 tetrahydroxybutylimidazole in ammonia caramel color by HPLC[END_REF], capillary electrophoresis [START_REF] Ong | Separation of imidazole and its derivatives by 464 capillary electrophoresis[END_REF], and GC 60 with derivatisation (Kröplien 1986, Fernandes and[START_REF] Fernandes | Gas chromatography -mass spectrometric determination 441 of 4(5)-methylimidazole in ammonia caramel colour using ion-pair extraction and 442 derivatisation with isobutylchloroformate[END_REF]. Quantification of 4(5)-61 methylimidazole in coffee was performed via ion-pair extraction with bis-2-62 ethylhexylphosphate (BEHP), isobutylchloroformate derivatisation and GC/MS (Casal et al. 63 2002). These methods are sensitive and precise, but limited to one or the other of the two 64 compounds. The first successful attempt to separate and determine 4MeI and THI in a single 65 run via LC/M) was published in 2003 [START_REF] Klejdus | A Reversed-Phase High-Performance Liquid 447 Chromatographic/Mass Spectrometric (RP-HPLC/MS-SIM) Method for Separation of 4-448 methylimidazole and 2-acetyl-4-(1,2,3,4-tetrahydroxybutyl)imidazole at pg levels. 449[END_REF]. The same research group also 66 investigated solid phase extraction as an instant tool for simultaneous separation of both 67 [START_REF] Klejdus | Solid-Phase Extraction of 4(5)-451 methylimidazole (4MeI) and 2-acetyl-4(5)-(1,2,3,4-tetrahydroxybutyl)-imidazole (THI) 452 from Foods and Beverages with Subsequent Liquid Chromatographic-Electrospray Mass 453 Spectrometric Quantification[END_REF]. Both analytes can be separated and 68 determined in a short time using a single-run analysis. 69 Solid matrices present another challenge in THI/4MeI separation. Roasted coffee can 70 be, of course, turned to liquid "coffee drink" matrix. A set of spike experiments showed, that 71 although the recovery of spiked analytes from liquid solutions is quantitative, spiking the 72 standards to roasted coffee beans and subsequent treatment with hot water brought less 73 favourable results. SPE is able to extract all analytes from the liquid phase, but the hot water 74 soaking seemingly does not remove all spiked analytes from solid coffee matrix (Klejdus et 75 al. 2006). 76 Thus, supercritical fluid extraction was selected as a method for THI and 4MeI 77 isolation from powdered solid coffee matrix. Due to low viscosity and high diffusivity of 78 supercritical fluid, analytes can be extracted from the matrix most effectively. Apart from 79 that, analytes are carried out of the system during the dynamic extraction. The balance in the 80 extraction cell shifts and it causes faster analyte removal from the matrix. Extraction 81 efficiency and precision was validated in a series of spiked sample experiments. Remainders 82 of coffee samples after supercritical fluid extraction were soaked in hot water and extracted 83 with SPE to verify SFE efficiency. Also, several different varieties and consumer coffee 84 mixtures were tested to exclude possible matrix effect. 85

Together with new isolation method, a new LC/MS method was developed for the 86 simultaneous determination of THI and 4MeI. Method used in previous experiments (Klejdus 87 et al. 2003(Klejdus 87 et al. , 2006) ) works well. But it is quite costly, as the pH of analyses is a limiting pH 88 value of the MetaChem Polaris C-18A column applicability. The column is exposed to a 89 series of serious stresses and after a limited number of analyses, separation performance is 90 decreased: retention times are shifted and peak width broadened. Because of that, brand new 91 method for Atlantis TM HILIC Silica column was developed for a mildly acidic mobile phase 92 in pH range 5 -6, with excellent precision and reproducibility. 93 A hydrophilic interaction chromatography (HILIC) is a variant of a normal phase 94 chromatography, where polar stationary phase is used with a mobile phase, which contains 95 high concentration of organic solvent and low concentration of aqueous solvent. In HILIC, 96 organic portion of mobile phase is a weak solvent, the aqueous portion is a strong solvent and 97 the compound elution is in the order of increasing hydrophylicity. HILIC is also referred to as 98 "aqueous normal phase" or "reverse reversed phase", since the elution order is similar to that 99 of normal phase and used solvents are similar to those of reversed phase chromatography. 100

Samples and sample preparation 116

The samples of coffee varieties were obtained from the Oxalis (import comp., Zlín, Czech 117 Republic). The "Brazilia-Santos" was the well-known 100 % brazil Arabica. The "Haiti 5X" 118 contained extra large coffee beans from the Haiti region Pilate. The "Kenya" originated from 119 the Mount Kenya plantations with altitude over 2000 m. The "Mexico Altura" was a high 120 mountain Arabica harvested at mexican coffee plantations in altitude 1000 -1600 m. The 121 "Boncampo" was obtained from Migros-Genossenschafts-Bund (Zürich, Switzerland). It was 122 a commercially available coffee mixture containing Arabica from Central and South America 123 and also from India/Indonesia, and Robusta from Africa and Asia -the most complex mixture 124 available at the market. Except the Boncampo mixture (Arabica/Robusta), all samples were 125 pure Arabica. All samples were used as the whole beans and ground in an analytical grinder 126 IKA Yellow Line A10 (IKA Works Inc., Wilmington, USA) to assure similar size of particles 127 in all samples. 128

In supercritical fluid extraction, sample amount was 1 g. For the solid-phase extraction 129 [START_REF] Klejdus | Solid-Phase Extraction of 4(5)-451 methylimidazole (4MeI) and 2-acetyl-4(5)-(1,2,3,4-tetrahydroxybutyl)-imidazole (THI) 452 from Foods and Beverages with Subsequent Liquid Chromatographic-Electrospray Mass 453 Spectrometric Quantification[END_REF], 5 g of coffee was extracted with hot water (90 ml) at 90 °C for 5 min. 130

The mixture was then cooled and solids were filtered off. The clear filtrate was transferred 131 into a 100 ml volumetric flask and adjusted with water up to the mark. An aliquot (1000 µl) 132 was diluted with water (3000 µl) and extracted. 133 The standard solutions of THI and MeI were prepared by mixing 1 mg of each compound in 135 100 ml of ultra-pure water. A given volume of THI/4MeI solution was injected into the 136 middle of a matrix bed (glass wool). As for real samples, 1.00 g of roasted coffee powder was 137 weighted into the extraction cell. The coffee samples spiked with the THI/4MeI standard 138 solutions were left to equilibrate for at least 10 min (5 days usually) at laboratory conditions. 139

The procedure avoided immediate dissolution of freshly spiked analytes in too soon added in-140 situ modifier. An attempt was made to use higher amounts of in-situ modifier; but at higher 141 temperatures the solvent caused some pressure in the extraction cell, leaved through the 142 All extractions were carried out using an SE-l instrument (SEKO-K, Ltd., Brno, Czech 155 Republic) equipped with a valve for continuous modifier addition (VALCO, Switzerland, 156 loop 500 µl) according to the method described by Ventura [START_REF] Adam | Combination of solid phase extraction 429 with supercritical fluid extraction for the determination of contaminants in water[END_REF], Eisner et al. 157 2002). The extraction cell was pressurized at 50 to 150 °C up to 10 -40 MPa using SFC/SFE 158 grade CO 2 (Siad, Brno, Czech Republic) with 10 % v/v of modifier mixture added via 159 VALCO valve to the instrument piston pump. 160

The modified supercritical fluid went through the extraction cartridge filled with the 161 sample for 45 min (dynamic extraction). The cell was de-pressurized through a fused silica 162 restrictor (12 cm, 50 µm i.d., flow rate of 750 -850 ml.min -1 , Supelco) into a liquid trap -a 163 glass vial containing 30 ml trapping solvent at the laboratory temperature. Much smaller 164 amount of the trapping solvent would be sufficient for the quantitative analyte trapping; but 165 due to 800 ml/min flow rate a 100 ml flask with a flexible foil seal was used as a trapping vial 166 Prior to the analyses, the extracts were evaporated to dryness in a rotary vacuum 169 evaporator IKA RV 05-ST with a water bath HB 4 (all from IKA -Werke GmbH and Co., 170 Staufen, KG, Germany), dissolved in 500 µl of ultra-pure water and injected directly into the 171 HPLC/MS system (spiked samples) or filtered through the 0.45 µm membrane filter 172 (MetaChem) before the injection (real samples, spiked real samples) to protect the HPLC 173 system. 174 175

Solid-phase extraction 176

Ansys SPEC SCX Disc 15mg/3ml (Ansys Technologies, Torrance, USA) SPE cartridges, 177 tried-and-true in previous analyses [START_REF] Klejdus | A Reversed-Phase High-Performance Liquid 447 Chromatographic/Mass Spectrometric (RP-HPLC/MS-SIM) Method for Separation of 4-448 methylimidazole and 2-acetyl-4-(1,2,3,4-tetrahydroxybutyl)imidazole at pg levels. 449[END_REF], were used for all solid-phase 178 extractions. The cartridges were conditioned with 500 µl methanol and 500 µl water. Usually 179 3 ml samples with 20 µl 0.1 mol.l -1 HCl passed through the cartridge. Impurities were washed 180 out with 1000 µl methanol. Retained imidazoles were eluted from discs with 2 ml of methanol 181 acidified with 5 mol.l -1 HCl v/v (3:1) and extracts were evaporated to dryness in the rotary 182 vacuum evaporator at 39 °C. The residues were dissolved in 500 µl of Milli Q water and 10 µl 183 volumes were injected directly onto the reverse phase chromatographic column. 184 185

High-performance liquid chromatography 186

The HPLC chromatographic system HP 1100 (Hewlett Packard, Waldbronn, Germany) 187 equipped with a vacuum degasser (G1322A), a binary pump (G1312A), an autosampler 188 (G1313A), a column thermostat (G1316A) and a diode array detector (model G1315A) was 189 The limit of detection (LOD) was estimated to be around 1.5 pg for 4MeI and at 2.0 pg for 252 THI with calculated S/N = 3 (see Table 1), while the limit of quantification (LOQ) was 4.4 pg 253 for 4MeI and 6.3 ng ml -1 for THI, respectively (S/N = 10). Molecular protonated ions were 254 used for LOD and LOQ determinations. The calibration curves were linear in the 255 concentration ranges 1 -70 ng ml -1 for 4MeI and 1 -60 ng ml -1 for THI with correlation 256 coefficient r > 0.9993 for 4MeI and r > 0.9996 for THI, respectively. Very good results were 257 obtained for run-to-run repeatability of retention times, peak areas and concentrations of 4MeI 258 and THI (see Table 1). The data shown in Table 2 were achieved by injecting the standard 259 solution of 4MeI and THI to the column in six replicates, in order to test the intra-day 260 variation. 261

The inter-day variation of the method was assessed by analysing of the standard 262 mixtures containing 1 and 3 µg.g -1 of both 4MeI and THI injected independently during 6 263 days in six replicates. The inter-day accuracy for the standard solution at the concentration 1 264 µg.g -1 was found to be 101.5 and 100.6 %, for 4MeI and THI, respectively, whereas that of 265 the standard solution at the concentration of 3 µg.g -1 was found to be 99.1 and 100.2 %, 266 respectively. The precision of the inter-day analysis, expressed as RSD%, was calculated as 267 1.66 and 0.60 % for 4MeI and THI, respectively, in the 1 µg.g -1 standard solutions, and 1.57 268 and 0.7 %, respectively, in the 3 µg.g -1 standard solutions (see Table 2). 269

The recovery of the method was verified analysing roasted coffee beans samples after 270 addition of two known amounts of 4MeI and THI standard solution and subjected to the 271 previously described SPE extraction after equilibration (ageing for 5 days). The theoretical 272 concentrations of the spiking 4MeI and THI standards were 1 and 3 µg. g -1 . The mean 273 recovery and the standard deviations for six replicates are given in Table 3. 274

275

Supercritical fluid extraction 276

Optimisation of extraction conditions for imidazoles 277

Both analytes, THI and 4MeI, are quite polar compounds for an SFE context (see Fig. 2). 278

Quantitative extraction of polar molecules requires long extraction time or very high flow-rate 279 to ensure sufficient mass transfer. Also polarity of a supercritical fluid must be shifted by 280 means of a modifier addition, because pure CO 2 has solvation power close to hexane and is an 281 excellent solvent for non-polar compounds. 282

Several sets of spiked sample experiments were performed to find optimal extraction 283 conditions for both analytes. An instrument adaptation for high CO 2 flow-rate, developed for 284 isoflavone extraction [START_REF] Klejdus | A Reversed-Phase High-Performance Liquid 447 Chromatographic/Mass Spectrometric (RP-HPLC/MS-SIM) Method for Separation of 4-448 methylimidazole and 2-acetyl-4-(1,2,3,4-tetrahydroxybutyl)imidazole at pg levels. 449[END_REF]) was used, providing the gaseous phase flow-rate of 285 c. 750 -850 ml.min -1 and using liquid trapping into foil-sealed 100 ml vial with 30 ml of 286 trapping solvent. Trapping efficiency and expected stripping effect was further tested. 287

Fortunately, non-volatile analytes are trapped quantitatively and stripping effect was not 288 observed in the first 45 min of any extraction. RSDs of all spiked analyte experiment were in 289 the range 1,2 % -4,7 %. 290

The best extraction conditions were examined in several sets of experiments. First, 291 recovery vs. extraction time was examined at 40 MPa and 150 °C (see Figure 3). As can be 292 seen the 55 % of THI and 74 % of 4MeI were extracted in the first 10 min and the 30 min 293 extraction was nearly quantitative (98.4 % and 98.1 % for THI and 4MeI, respectively). 294

Recoveries increased slightly up to 98.9 % and 99.8 % for THI and 4MeI in the 45 th min, 295 respectively (see Figure 3). Fractions were taken also for 60, 75 and 90 min, but they did not 296 bring any measurable improvement of the results. 297 Study of extraction kinetics was repeated with a real sample of roasted coffee powder 298 due to expectation of matrix effects. Courses of extraction kinetic curves were similar. In fact 299 the real sample extractions were faster a little bit, partly due to the lower analyte content in 300 real samples and, mostly, thanks to better-tuned modifier composition. 301 With the optimal extraction time selected, extraction temperature and pressure were 302 optimised (see Figure 3). Series of extraction was performed at 40 MPa for different 303 temperatures and at 150 °C for different pressures. As for THI, the higher the temperature is, 304 the better (150 °C is an instrument limiting value, higher temperatures were not examined). 305

The decrease of extraction efficiency was observed for 4MeI at 75 and 100 °C. The highest 306 recovery was also obtained at 150 °C in this case. Recoveries vary from 86 % to 99 % for 307 THI and from 69 % to 89 % at 150 °C, according to extraction pressure applied (with 308 modifier composition best suitable for both analytes, see Figure 3). The best recovery values 309 were obtained at 40 MPa in both cases. 310 Ultra-pure water, methanol, ethanol, acetonitrile and their combinations were tested in 311 preliminary experiments to find the best modifier composition (2, 5 and 10 % (v/v) of each 312 were added on-line). An aqueous methanol with 10 % (v/v) of water gave the best results thus 313 the concentrations close to that amount were examined more carefully (see Figure 3). The 314 proper modifier composition for THI was aqueous methanol with MeOH/H 2 O 5:1 (v/v) ratio 315 or with higher percentage of water (see Figure 3). Lower percentage of water in aqueous 316 methanol, i.e. MeOH/H 2 O 9:1 (v/v), is favourable for 4MeI. The recovery of the extraction 317 decreased with the higher amount of water. However, the modifier composition MeOH/H 2 O 318 5:1 (v/v) provided recoveries 101.3 % and 89.4 % for THI and 4MeI, respectively. These 319 values could be considered sufficient for their simultaneous extraction (quantitative recoveries 320 of polar analytes are difficult to achieve with SFE and nearly 90 % recovery at conditions 321 optimal for another compound seems to be quite satisfactory). THI is also extractable quite 322 well (with recovery 86.9 %) under the conditions optimised for the 4MeI quantitative 323 extraction (MeOH/H 2 O 9:1 (v/v), recovery of 4MeI 98.9 %). The optimised composition 324

MeOH/H 2 O 5:1 (v/v) was selected for the simultaneous extractions of THI and 4MeI for 325 further experiments due to its higher total recoveries. In experiments, where 4MeI is the more 326 important analyte, 9:1 (v/v) concentration will be more useful. 327 Another set of extractions was performed to find out the best volumes of on-line 328 pump inner space. To avoid this, the modifier addition must be skipped for each n th pump 337 filling (according to the modifier type and its volume). Thus the maximum concentration of a 338 modifier in an extraction fluid is lower. However, the modifier concentration MeOH/H 2 O 5:1 339 (v/v) can be added in 10 % (v/v) amount without any troubles and it is also best composition 340 for 4MeI (see Figure 3). For THI, 5 % (v/v) is sufficient and any higher concentration is 341 suitable. 342

Last but not least was the determination of a suitable trapping solvent (see Figure 3). 343

Methanol is not good for THI trapping (recovery 85.6 %); acetonitrile is an excellent solvent 344 for both analytes (99.4 % and 98.2 %, for THI and 4MeI, respectively). Ultra-pure water is 345 very good solvent for 4MeI (100.2 %), but poor for THI (38. MeOH/H 2 O 5:1 (v/v) for THI and MeOH/H 2 O 9:1 (v/v) for 4MeI. All the other studies were 353 performed together only with MeOH/H 2 O 5:1 (v/v) modifier. The composition was used also 354 for all the real sample extractions. Recovery verification of SFE was also performed for the 355 both modifier concentrations to authenticate the best conditions for both compounds. The 356 values for 4MeI extracted with MeOH/H 2 O 5:1 (v/v) modifier were also calculated and found 357 out to be satisfactory. 358

359

Real samples extraction and method validation 360 SFE is a matrix-dependable method, where every new procedure must be verified also by 361 application to a set of different real samples. The optimised extraction conditions were 362 applied to the samples of roasted coffee powder, containing THI and 4MeI. A solid phase 363 extraction was used as a comparative method for the neurotoxins determination (Klejdus et al. 364 2003(Klejdus et al. 364 , 2006)). The both analytes were isolated and quantified in the concentrations high above 365 their detection limits. Despite the expected matrix effects the method seems to work well with 366 the acceptable reproducibility. The samples of fine-grained coffee (1.00 g) were homogeneous 367 enough to avoid measurable differences between individual SFE samples. Any differences in 368 their extractability from various matrices were not observed. 369

The efficiency of the supercritical fluid extraction was tested in two ways: via 370 comparison with validated SPE extraction and via post-SFE liquid extraction of the 371 "extracted" samples. Comparison of the results of SFE and SPE is presented in Table 4. 372 Noteworthy, the results of both extraction methods are in the good coincidence for THI, 373 although SPE was reported non-quantitative with spiked solid samples. For post-SFE tests, 374 five used samples of coffee matrix (c. 5 g) were combined in one beaker and "coffee" was 375 prepared in the same way like for the classical SPE. No traces of the analytes were found in 376 any test solution. 377

For validation purposes, the coffee samples were spiked with the standard solution 378 adding 0.5, 1, 2 and 3 µg of the analytes per 1 g of the sample (details given in experimental 379 . All the samples were extracted under the optimised conditions for both analytes. The 380 values obtained for the more suitable modifier are given for each substance (see Table 5). 381 Slightly higher selectivity was achieved with SFE, but the conditions necessary for the 382 quantitative extraction of the analytes are quite hard, and many ballast compounds were co-383 extracted. Because of that, quick test of available clean-up procedures was performed. Finally, 384 0.45 µm Teflon filter was selected for the extracts clean up, as it didn't hold part of analytes. 385

Although the goal to avoid any extract clean up was not achieved, viable method was found 386 that can also be usable for SPE extracts. Thus, both SFE and SPE can be used for the 387 quantitative extraction of THI/4MeI from roasted coffee solid samples (SFE) and lixiviates 388 (SPE). 389 390 Conclusions 391

The SFE method was optimised for the THI and 4-MeI separation from solid coffee 392 samples. Both analytes are quantitatively extracted and it is also possible to co-extract one 393 analyte together with the other with acceptable recovery (101.3 % THI and 89.4 % 4MeI or 394 98.9 % 4MeI and 86.9 % THI). Extraction time is moderate -45 min -and both, the precision 395 and the recovery of analytical method are sufficient. The method is suitable for all matrices 396 and the spiked analytes recovery is quantitative. 397 Thus, an alternative method exists now for THI and 4MeI determination from real 398 coffee samples. Although the method lacks some merits of a standard "low flow-rate" SFE -399 30 ml extracts must be pre-concentrated and even a clean-up procedure is necessary in the 400 case of real samples -it is relatively fast, reliable and works well with spiked solid samples. 401

An attempt was made to enhance environmental friendliness of the method by using 402 ultra-pure water as a trapping solvent, but acetonitrile proved to be the only quantitative 403 14 nitrogen containing compounds. Thus, all baked products could contain some imidazoles in 414 their dark parts [START_REF] Casal | Gas chromatography -mass 432 spectrometric quantification of 4(5)-methylimidazole in roasted coffee after ion-pair 433 extraction[END_REF]. In some cases, baking tins are sprinkled with flour or 415 desiccated coconut (although probably not because of this reason) and the burned 416 flour/coconut layer, containing most of harmful compounds, should stay in the baking tin. In 417 addition to coffee, baked pastries, caramel sweets, and dark beers participate in the puzzle 418 partly while cola-drinks quite seriously, because of both, larger concentrations of imidazoles 419 and lower respect of producers to standard concentration limits (40-times higher than limits 420 for imidazoles were found in several cola-drinks in our lab). Thus, each source of imidazoles 421 should be carefully examined.

  highly polar analytes with volatile mobile phases that are ideal for 101 compound ionization by ESI -MS. This leads to good sensitivity and low limits of detection. -methylimidazole (4MeI) was purchased from Sigma-Aldrich (St Louis, USA). The 107standard of 2-acetyl-4(5)-(1,2,3,4-tetrahydroxybutyl)-imidazole (THI) was obtained from Dr. 108 D. V. Myers (Coca Cola Co., USA). HPLC grade methanol and ammonium formate were 109 from Merck (Darmstadt, Germany). Standards were prepared by dissolution in reverse-110 osmosis Milli-Q water (Millipore, Bedford, USA) at a stock concentration of 10 µg.ml -1 . The 111 solutions were stable for at least one week when stored in dark at 4 °C. All solutions were 112 filtered through a 0.45 µm Teflon membrane filters (MetaChem, Torrance, USA) prior to 113 HPLC analysis. All other chemicals were of analytical grade. 114 115

  restrictor and caused slow extraction of ballast compounds, impending the restrictor plugging. 143 When 200 µl of the in-situ modifier was added to the 0.7 ml cartridge, it was immediately 144 sealed and closed in the extraction cell of a heating block to avoid evaporation of the in-situ 145 modifier. 146 The extraction cells were cleaned in ultra-pure H 2 O in sonication bath and rinsed with 147 MeOH. Inner space of extraction cell of the heating block was also washed with water and 148 methanol, since not all experiments had quantitative recovery during the extraction conditions 149 optimisation. This eliminated or minimised cross-contamination dragged by the extraction 150 phase modifier during de-pressurization after the extraction step. Blank samples were 151 prepared by extracting the same amounts of the matrix. Neither the analytes were found in 152 blank matrices, nor THI/4MeI residues were found in the instrument after the extraction cell 153 heating block cleaning. 154

  solvent splashing out of a vial. Thus a larger volume was needed to achieve 167 sufficient solvent column height. 168

  coupled on-line to a mass selective HP MSD detector(G 1946A, Hewlett Packard, Palo Alto, 190 USA). The ChemStation software (Rev. A 07.01) controlled the whole liquid 191 chromatographic system. A hydrophilic interaction chromatographic column AtlantisHILIC 192 Silica (150 x 2.1 mm, 3 µm) was employed. The mobile phase was methanol (80 %) and 0.01 193 mol.l -1 ammonium formate in Milli-Q water (20 %). Isocratic mode was used for the 194 separation. The flow rate was 0.2 mL.min -1 and the temperature of the column oven was set at 195 25 °C. The column effluent was monitored with the diode array detector at 290 nm for THI 196 and at 215 nm for 4MeI. the liquid chromatograph was directly introduced into the quadruple mass 200 spectrometer operated in the positive ESI mode. The nebulizer gas pressure was 50 psi, the 201 drying gas was nitrogen at the 12 L.min -1 and at the temperature of 350 °C. The capillary 202 voltage was 1 500 V. The gain was 1. The spectra were recorded from m/z 50 to 250 for full 203 scan mode. All experiments were performed at the fragmentor voltage 35 eV for molecular 204 ions. For qualitative analysis, ion ratio experiments were performed for standard solutions and 205 real samples at the fragmentor voltage 65 eV for parent ions and m/z 231/213, m/z 231/195 206 and 231/153 for THI and at the fragmentor voltage 100 eV for the parent ion and m/z 83/56 207 for 4MeI. The dwell time for each analyte was 199 ms. The mass spectrometer was calibrated 208 with an ESI tuning solution obtained from Hewlett Packard (Palo Alto, CA, USA). 209 A sequence 231 -213 -195 appears in the mass spectrum of both THI tautomers that 210 corresponds to stepwise liberation of a single molecule of water from the side chain. The 211 fragment 195 liberates ketene from the double bond of the acetyl group forming an ion 153 as 212 can be seen in both spectra. The sequence is the same for both isomers. In addition the 213 tautomer liberates another water molecule from the fragment 195 forming an ion 176. 214 Because of the water liberated preferentially through six-member cyclic intermediate, it looks 215 like tautomer depicted in Figure 1 (right side). 216 217 Accuracy, precision and recovery 218 Accuracy, precision and recovery of the determination of imidazole analytes were evaluated 219 with the powdered coffee beans spiked with THI/4MeI standards (concentrations varying 220 from 0.5 µg.g -1 to 3 µg.g -1 ). Coefficients of variation % C.V. of intra-day assay were 221 performed in 6 spiked extracts. Inter-day precision was determined by analysing six spiked 222 extracts during a 6-day period. Analyte concentrations were calculated from calibration 223 curves. Accuracy (in %) was evaluated by comparing the estimated concentration with the 224 known concentrations of the individual imidazoles. 225 226 Results and discussion 227 228 High-performance liquid chromatography -mass spectrometry 229 A new LC/ESI/MS analytical method, using Atlantis HILIC Silica column and mildly acidic 230 medium (pH 5 -6) was developed for unambiguous identification and determination of THI 231 and 4MeI. Inherent pH and thermal instability of silica-based column, like MetaChem Polaris 232C-18A used in previous paper[START_REF] Klejdus | A Reversed-Phase High-Performance Liquid 447 Chromatographic/Mass Spectrometric (RP-HPLC/MS-SIM) Method for Separation of 4-448 methylimidazole and 2-acetyl-4-(1,2,3,4-tetrahydroxybutyl)imidazole at pg levels. 449[END_REF] significantly limits the range of 233 under which such columns can be used, especially under 234 reversed phase conditions. In the THI/4MeI analyses, the column was operated at edge 235 conditions of pH applicability that decreased it's lifetime and led to retention times shift and 236 peak width broadening. 237The optimisation was carried out by flow injection analysis (FIA) injecting several 238 solutions containing the individual compounds at the concentration of 1 ng.µl -1 . The analytes 239 produced protonated molecules [M+H] + at m/z 231 for THI and at m/z 83 for 4MeI. The 240 tandem mass spectrometry was therefore used in order to obtain additional structural 241 information by detecting diagnostic product-ions obtained by in-source collision-induced 242 dissociation (CID) of the precursor ion. Three qualifying fragment ions (m/z 231/213, m/z 243 231/195 and m/z 231/153) for THI and one qualifying fragment ion (m/z 83/56) for 4MeI 244 were used, according to the selected-ion monitoring (SIM) technique. 245 246 Validation of the LC/ESI-MS method 247 Several experimental parameters such as limit of detection (LOD), limit of quantification 248 (LOQ), linearity, recovery, stability and repeatability were evaluated for validation of the 249 HPLC/ESI-MS method. The separated HPLC zones were detected by the selected ion-250 monitoring (SIM) mode (m/z 231/213, m/z 231/195 and m/z 231/153 for THI and m/z 83/56). 251

  modifier. The initial amount of the modifier added to the extraction cartridge was 200 µl. The 329 higher volumes caused troubles during the extraction cell heating and leaved the cell trough 330 the restrictor together with some ballast compounds. The concentration of a modifier in the 331 extraction fluid depends on the amount of a liquid modifier added to the extraction phase 332 during every filling of the extractor pump. Up to 1 ml of modifier can be added through the 333 Valco valve loop. That is c. 10 % of the piston micro-pump volume. The modifier percentage 334 is viable only for some substances and their combinations. Ultra-pure water, for example 335 in the piston micro pump. It is accumulated there and decreases piston micro 336

  imidazoles are extractable very well with the modified supercritical fluids 347 with sufficient recoveries in an acceptable extraction time. Of course, all the optimised 348 parameters were not known at the beginning of this study. Most of the experiments were 349 repeated in a "second run" under the "optimised conditions". In Figure3, only the results of 350 the optimised experiments are given. Temperature optimisation, trapping solvent selection 351 and the study of extraction kinetics were performed separately for the modifier composition 352

  trapping solvent. THI trapping in water is insufficient. 404 Still, the solid phase extraction represents, in fact, an instant separation, while SFE 405 takes at least 30 min for extraction and some extra time for pre-concentration. Our results 406 indicate, that SPE of real samples is as efficient as SFE. However, SFE was successfully 407 validated for spiked solid samples now. With Teflon filter clean up, both SFE and SPE are 408 viable methods. Perhaps, SFE present an advantage for small amount extractions and for 409 samples, from which quantitative lixiviation of analytes with common solvents would be 410 difficult. 411 Although imidazole concentrations in coffee are very low, coffee imidazoles are one 412 part of a total food imidazole puzzle. They are formed when sugars are heated together with 413

Fig. 1 Fig. 2 Fig. 3

 123 Fig. 1 Probable chemical structures of THI tautomers 481 482 Fig. 2 HPLC/MS chromatograms (SIM mode for m/z 231 THI, for m/z 83 4MeI) of real 483 samples A, standards B. Peak identification 1 -THI, 2 -4MeI. For chromatographic 484 conditions see text. 485 486 Fig. 3 Optimisation of extraction parameters. All extraction performed from spike samples 487 under following conditions: T = 150 °C, p = 40 MPa, t = 45 min, c (modifier) = 10 % 488 (v/v), in situ modifier: 200 µl, trapping: 30 ml acetonitrile, ACF: modifier THI -489 MeOH/H 2 O 5:1 (v/v), 4MeI MeOH/H 2 O 9:1(v/v), BDE: modifier MeOH/H 2 O 5:1 (v/v) 490 for both analytes. RSDs were in the range 1,2 % -4,7 %. 491

  Figure1

manuscriptcentral.com/tfac Email: fac@tandf.co.uk Food Additives and Contaminants

	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	18

Table 1 :

 1 Retention time (R.T.), peak area (P.A.) and their repeatabilities (RSDs given in 492 brackets, n = 6) and calibration data and LODs for 4MeI and THI obtained under optimised 493

	494	separation conditions using UV and MS detection (injection volume 5 µl)
	495
			4MeI		THI
			UV a	SIM	UV a	SIM
		R.T. (min) b	11.25(0.09) b	6.94(0.14) c
		P.A. (x 10 5 ) c	4.45(1.12) d	2.23(2.24) e
		Concentration range (ng.ml -1 )	40 -650	1 -70	22 -850	1 -60
		Correlation coefficient (n = 6)	0.9998	0.9993	0.9999	0.9996
		LOD (ng.ml -1 )	14.5 f	0.1	8.2 g	0.2
		LOQ (ng.ml -1 )	48.3 f	0.4	27.4 g	0.6
	496	a cit. Moravcová et al. 1999, b range 6.94 -6.95, c range 2.12 -2.30, d range 11.23 -11.26, e
	497	range 4.39 -4.53, f 215 nm, g 290 nm
	498

Table 2 :

 2 HPLC-MS validation: determination of THI and 4MeI in real coffee extracts,

	499
	500 501	standard solutions and coffee extracts spiked with known concentrations of analytes (n=6)
		Compound THI 4MeI THI 4MeI THI 4MeI THI 4MeI
		C [µg/g]	0.5	1	2		3
			Standard solutions of known analyte concentration
		C [µg/g] 0.505 0.498 0.993 0.991 1.973 2.021 3.048 3.030
		SD [µg/g] 0.009 0.006 0.015 0.020 0.027 0.054 0.078 0.062
		RSD [%] 1.76	1.19 1.51 2.04	1.38	2.69	2.55	2.05
		R [%]	100.93 99.67 99.32 99.12 98.67 101.03 101.59 101.00
		Ground roasted coffee extract spiked with known analyte concentration
		C [µg/g] 0.536 1.662 1.014 2.156 2.034 3.150 3.017 4.138
		SD [µg/g] 0.005 0.019 0.012 0.024 0.010 0.005 0.032 0.026
		RSD [%] 0.91	1.15 1.18 1.13	0.47	0.16	1.05	0.63
		R [%]	100.48 101.06 98.14 100.50 100.04 100.17 99.44 99.83
				Real sample (coffee Mexico)
		C [µg/g] 0.034 1.145
		SD [µg/g] 0.0005 0.0073
		RSD [%] 1.57	0.64

Table 3 :

 3 HPLC/MS within-day and interday repeatability of THI and 4MeI determination for standard solution and spiked coffee extracts (n

	502 503 504	= 6, n = 30)
	505 506 507
		Compound	THI	4MeI	THI	4MeI	THI	4MeI	THI	4MeI
			1 (intraday)	1 (interday)	3 (intraday)	3 (interday)
					Standard solution
		C [µg/g]	0.994	1.013	1.006	1.015	3.000	2.985	3.01	2.97
		SD [µg/g] 0.010	0.011	0.006	0.012	0.022	0.029	0.02	0.05
		RSD [%]	1.01	1.04	0.60	1.16	0.72	0.98	0.60	1.57
		R [%]	99.40	101.28 100.60 101.46	99.99	99.51	100.17	99.08
					Spiked coffee extract
		C [µg/g]	1.343	2.087	1.329	2.099	3.318	4.157	3.377	4.138
		SD [µg/g] 0.008	0.014	0.007	0.027	0.046	0.032	0.039	0.053
		RSD [%]	0.59	0.69	0.52	1.28	1.39	0.76	1.16	1.29
		R [%]	100.33	99.21	99.28	99.76	99.39	101.29 101.17 100.85
					Extract of coffee
		C [µg/g]	0.338	1.104
		SD [µg/g] 0.002	0.015
		RSD [%]	0.48	1.33

Table 4 :

 4 Quantification of imidazoles in real sample (ground roasted coffee).

	508
	509 510
		THI [µg/g] (RSD [%])	4MeI [µg/g] (RSD [%])
	COFFEE	SFE (

solid sample) SPE (liquid coffee) SFE (solid sample) SPE (liquid coffee)

	Brazil	0.0165 (4.29)	0.0154 (1.72)	1.34 (2.41)	0.60 (3.22)
	Kenya	0.0025 (3.82)	0.0021 (2.25)	0.77 (3.65)	0.41 (2.59)
	Haiti	0.0262 (3.04)	0.0250 (2.61)	1.45 (4.47)	0.77 (1.66)
	Mexico	0.0337 (2.32)	0.0332 (1.63)	1.11 (3.70)	0.39 (2.48)
	Boncampo	0.0088 (2.66)	0.0086 (2.08)	1.01 (4.29)	0.35 (2.70)
		F o r
			P
			e
			e r
				R
				e
				v i e
					w
					O n l
					y
					22

Table 5 :

 5 SFE validation: the extraction of THI and 4MeI from real coffee sample, sea sand 511 model matrix and real coffee sample spiked with known concentrations of analytes (n=5)

	512
	513
	514
	Compound		THI			4MeI
	C [µg/g]	0.05	0.10	0.15	0.20	1	2	3	4
		Sea sand (p.a.) matrix spiked with known analyte concentration
	C [µg/g]	0.0509	0.103	0.147	0.199	0.992	2.038	2.949	4.088
	SD [µg/g] 0.0019	0.005	0.005	0.009	0.047	0.105	0.132	0.230
	RSD [%]	3.78	4.57	3.35	4.73	4.75	5.14	4.48	5.62
	R [%]	101.71 102.55	98.19	99.30	99.17	101.92	98.30	102.19
		Ground roasted coffee matrix spiked with known analyte concentration
	C [µg/g]	0.085	0.131	0.184	0.231	2.076	3.033	4.065	4.975
	SD [µg/g] 0.004	0.006	0.008	0.011	0.064	0.096	0.176	0.195
	RSD [%]	4.71	4.81	4.43	4.90	3.09	3.18	4.32	3.91
	R [%]	101.97	97.78	100.07 100.23	98.61	97.51	98.92	97.36
				Real sample (coffee Mexico)
	C [µg/g]	0.034	1.110
	SD [µg/g] 0.001	0.041
	RSD [%]	2.32	3.70
	515

http://mc.manuscriptcentral.com/tfac Email: fac@tandf.co.ukFood Additives and Contaminants

Acknowledgements 425

This work was supported by the Grant Agency of the Czech Republic (GA ČR 521/02/1367) 426 and the Grant Agency of the MŠMT (grant No. MSM 432100001 and MSM 6046137305). 427


Swan Dubois
email: swan.dubois@lip6.fr

Toshimitsu Masuzawa
email: masuzawa@ist.osaka-u.ac.jp

Sébastien Tixeuil
email: sebastien.tixeuil@lip6.fr

Self-Stabilization, Byzantine Containment, and Maximizable Metrics: Necessary Conditions

Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors.

We consider the well known problem of constructing a maximum metric tree in this context. Combining these two properties is known to induce many impossibility results. In this paper, we provide two necessary conditions to construct maximum metric tree in presence of transients and (permanent) Byzantine faults.

Introduction

The advent of ubiquitous large-scale distributed systems advocates that tolerance to various kinds of faults and hazards must be included from the very early design of such systems. Selfstabilization [START_REF] Edsger | Self-stabilizing systems in spite of distributed control[END_REF][START_REF] Shlomi | Self-stabilization[END_REF][START_REF] Tixeuil | Algorithms and Theory of Computation Handbook, Second Edition, chapter Self-stabilizing Algorithms[END_REF] is a versatile technique that permits forward recovery from any kind of transient faults, while Byzantine Fault-tolerance [START_REF] Lamport | The byzantine generals problem[END_REF] is traditionally used to mask the effect of a limited number of malicious faults. Making distributed systems tolerant to both transient and malicious faults is appealing yet proved difficult [START_REF] Dolev | Self-stabilizing clock synchronization in the presence of byzantine faults[END_REF][START_REF] Daliot | Self-stabilization of byzantine protocols[END_REF][START_REF] Nesterenko | Tolerance to unbounded byzantine faults[END_REF] as impossibility results are expected in many cases.

Related Works A promizing path towards multitolerance to both transient and Byzantine faults is Byzantine containment. For local tasks (i.e. tasks whose correctness can be checked locally, such as vertex coloring, link coloring, or dining philosophers), the notion of strict stabilization was proposed [START_REF] Nesterenko | Tolerance to unbounded byzantine faults[END_REF][START_REF] Masuzawa | Stabilizing link-coloration of arbitrary networks with unbounded byzantine faults[END_REF]. Strict stabilization guarantees that there exists a containment radius outside which the effect of permanent faults is masked, provided that the problem specification makes it possible to break the causality chain that is caused by the faults. As many problems are not local, it turns out that it is impossible to provide strict stabilization for those. To circumvent impossibility results, the weaker notion of strong stabilization was proposed [START_REF] Masuzawa | Bounding the impact of unbounded attacks in stabilization[END_REF]7]: here, correct nodes outside the containment radius may be perturbated by the actions of Byzantine node, but only a finite number of times.

Recently, the idea of generalizing strict and strong stabilization to an area that depends on the graph topology and the problem to be solved rather than an arbitrary fixed containment radius was proposed [START_REF] Dubois | The impact of topology on byzantine containment in stabilization[END_REF][START_REF] Dubois | On byzantine containment properties of the min+1 protocol[END_REF] and denoted by topology aware strict (and strong) stabilization. When maximizable metric trees are considered, [START_REF] Dubois | The impact of topology on byzantine containment in stabilization[END_REF] proposed an optimal (with respect to impossibility results) protocol for topology-aware strict stabilization, and for the simpler case of breathfirst-search metric trees, [START_REF] Dubois | On byzantine containment properties of the min+1 protocol[END_REF] presented a protocol that is optimal both with respect to strict and strong variants of topology-aware stabilization. The case of optimality for topology-aware strong stabilization in the general maximal metric case remains open.

Our Contribution In this paper, we investigate the possibility of topology-aware strong stabilization for tasks that are global (i.e. for with there exists a causality chain of size r, where r depends on n the size of the network), and focus on the maximum metric tree problem. In more details, we provide two necessary conditions to perform Byzantine containment for maximum metric tree construction. First, we characterize a specific class of maximizable metrics (which includes breath-first-search and shortest path metrics) that prevents the exitence of strong stabilizing solutions. Then, we generalize an impossibilty result of [START_REF] Dubois | On byzantine containment properties of the min+1 protocol[END_REF] that provides a lower bound on the containmemt area for topology-aware strong stabilization.

Model and Definitions

State Model

A distributed system S = (P, L) consists of a set P = {v 1 , v 2 , . . . , v n } of processes and a set L of bidirectional communication links (simply called links). A link is an unordered pair of distinct processes. A distributed system S can be regarded as a graph whose vertex set is P and whose link set is L, so we use graph terminology to describe a distributed system S. We use the following notations: n = |P |, m = |L| and d(u, v) denotes the shortest path between two processes u and v (i.e the length of the shortest path between u and v).

Processes u and v are called neighbors if (u, v) ∈ L. The set of neighbors of a process v is denoted by N v . We do not assume existence of a unique identifier for each process. Instead we assume each process can distinguish its neighbors from each other by locally labelling them.

In this paper, we consider distributed systems of arbitrary topology. We assume that a single process is distinguished as a root, and all the other processes are identical. We adopt the shared state model as a communication model in this paper, where each process can directly read the states of its neighbors.

The variables that are maintained by processes denote process states. A process may take actions during the execution of the system. An action is simply a function that is executed in an atomic manner by the process. The action executed by each process is described by a finite set of guarded actions of the form guard -→ statement . Each guard of process u is a boolean expression involving the variables of u and its neighbors.

A global state of a distributed system is called a configuration and is specified by a product of states of all processes. We define C to be the set of all possible configurations of a distributed system S. For a process set R ⊆ P and two configurations ρ and ρ ′ , we denote ρ R → ρ ′ when ρ changes to ρ ′ by executing an action of each process in R simultaneously. Notice that ρ and ρ ′ can be different only in the states of processes in R. For completeness of execution semantics, we should clarify the configuration resulting from simultaneous actions of neighboring processes. The action of a process depends only on its state at ρ and the states of its neighbors at ρ, and the result of the action reflects on the state of the process at ρ ′ .

We say that a process is enabled in a configuration ρ if the guard of at least one of its actions is evaluated as true in ρ.

A schedule of a distributed system is an infinite sequence of process sets. Let Q = R 1 , R 2 , . . . be a schedule, where R i ⊆ P holds for each i (i ≥ 1). An infinite sequence of configurations e = ρ 0 , ρ 1 , . . . is called an execution from an initial configuration ρ 0 by a schedule Q, if e satisfies

ρ i-1 R i → ρ i for each i (i ≥ 1)
. Process actions are executed atomically, and we distinguish some properties on the scheduler (or daemon). A distributed daemon schedules the actions of processes such that any subset of processes can simultaneously execute their actions. We say that the daemon is central if it schedules action of only one process at any step. The set of all possible executions from ρ 0 ∈ C is denoted by E ρ 0 . The set of all possible executions is denoted by E, that is, E = ρ∈C E ρ . We consider asynchronous distributed systems where we can make no assumption on schedules.

In this paper, we consider (permanent) Byzantine faults: a Byzantine process (i.e. a Byzantine-faulty process) can make arbitrary behavior independently from its actions. If v is a Byzantine process, v can repeatedly change its variables arbitrarily. For a given execution, the number of faulty processes is arbitrary but we assume that the root process is never faulty.

Self-Stabilizing Protocols Resilient to Byzantine Faults

Problems considered in this paper are so-called static problems, i.e. they require the system to find static solutions. For example, the spanning-tree construction problem is a static problem, while the mutual exclusion problem is not. Some static problems can be defined by a specification predicate (shortly, specification), spec(v), for each process v: a configuration is a desired one (with a solution) if every process satisfies spec(v). A specification spec(v) is a boolean expression on variables of P v (⊆ P ) where P v is the set of processes whose variables appear in spec(v).

The variables appearing in the specification are called output variables (shortly, O-variables).

In what follows, we consider a static problem defined by specification spec(v).

A self-stabilizing protocol ( [START_REF] Edsger | Self-stabilizing systems in spite of distributed control[END_REF]) is a protocol that eventually reaches a legitimate configuration, where spec(v) holds at every process v, regardless of the initial configuration. Once it reaches a legitimate configuration, every process never changes its O-variables and always satisfies spec(v). From this definition, a self-stabilizing protocol is expected to tolerate any number and any type of transient faults since it can eventually recover from any configuration affected by the transient faults. However, the recovery from any configuration is guaranteed only when every process correctly executes its action from the configuration, i.e., we do not consider existence of permanently faulty processes.

When (permanent) Byzantine processes exist, Byzantine processes may not satisfy spec(v). In addition, correct processes near the Byzantine processes can be influenced and may be unable to satisfy spec(v). Nesterenko and Arora [START_REF] Nesterenko | Tolerance to unbounded byzantine faults[END_REF] define a strictly stabilizing protocol as a self-stabilizing protocol resilient to unbounded number of Byzantine processes.

Given an integer c, a c-correct process is a process defined as follows.

Definition 1 (c-correct process) A process is c-correct if it is correct ( i.e. not Byzantine) and located at distance more than c from any Byzantine process.

Definition 2 ((c, f )-containment) A configuration ρ is (c, f )-contained for specification spec if, given at most f Byzantine processes, in any execution starting from ρ, every c-correct process v always satisfies spec(v) and never changes its O-variables.

The parameter c of Definition 2 refers to the containment radius defined in [START_REF] Nesterenko | Tolerance to unbounded byzantine faults[END_REF]. The parameter f refers explicitly to the number of Byzantine processes, while [START_REF] Nesterenko | Tolerance to unbounded byzantine faults[END_REF] dealt with unbounded number of Byzantine faults (that is f ∈ {0 . . . n}).

Definition 3 ((c, f )-strict stabilization) A protocol is (c, f )-strictly stabilizing for specification spec if, given at most f Byzantine processes, any execution e = ρ 0 , ρ 1 , . . . contains a configuration ρ i that is (c, f )-contained for spec.

An important limitation of the model of [START_REF] Nesterenko | Tolerance to unbounded byzantine faults[END_REF] is the notion of r-restrictive specifications. Intuitively, a specification is r-restrictive if it prevents combinations of states that belong to two processes u and v that are at least r hops away. An important consequence related to Byzantine tolerance is that the containment radius of protocols solving those specifications is at least r. For some (global) problems r can not be bounded by a constant. In consequence, we can show that there exists no (c, 1)-strictly stabilizing protocol for such a problem for any (finite) integer c.

Strong stabilization

To circumvent such impossibility results, [7] defines a weaker notion than the strict stabilization. Here, the requirement to the containment radius is relaxed, i.e. there may exist processes outside the containment radius that invalidate the specification predicate, due to Byzantine actions. However, the impact of Byzantine triggered action is limited in times: the set of Byzantine processes may only impact processes outside the containment radius a bounded number of times, even if Byzantine processes execute an infinite number of actions.

In the following of this section, we recall the formal definition of strong stabilization adopted in [7]. From the states of c-correct processes, c-legitimate configurations and c-stable configurations are defined as follows.

Definition 4 (c-legitimate configuration) A configuration ρ is c-legitimate for spec if every c-correct process v satisfies spec(v).

Definition 5 (c-stable configuration) A configuration ρ is c-stable if every c-correct process never changes the values of its O-variables as long as Byzantine processes make no action.

Roughly speaking, the aim of self-stabilization is to guarantee that a distributed system eventually reaches a c-legitimate and c-stable configuration. However, a self-stabilizing system can be disturbed by Byzantine processes after reaching a c-legitimate and c-stable configuration. The c-disruption represents the period where c-correct processes are disturbed by Byzantine processes and is defined as follows Definition 6 (c-disruption) A portion of execution e = ρ 0 , ρ 1 , . . . , ρ t (t > 1) is a c-disruption if and only if the following holds:

1. e is finite,

e contains at least one action of a c-correct process for changing the value of an O-variable,

3. ρ 0 is c-legitimate for spec and c-stable, and 4. ρ t is the first configuration after ρ 0 such that ρ t is c-legitimate for spec and c-stable. Now we can define a self-stabilizing protocol such that Byzantine processes may only impact processes outside the containment radius a bounded number of times, even if Byzantine processes execute an infinite number of actions.

Definition 7 ((t, k, c, f )-time contained configuration) A configuration ρ 0 is (t, k, c, f )-time contained for spec if given at most f Byzantine processes, the following properties are satisfied:

1. ρ 0 is c-legitimate for spec and c-stable,

every execution starting from ρ 0 contains a c-legitimate configuration for spec after which the values of all the O-variables of c-correct processes remain unchanged (even when

Byzantine processes make actions repeatedly and forever), 3. every execution starting from ρ 0 contains at most t c-disruptions, and 4. every execution starting from ρ 0 contains at most k actions of changing the values of O-variables for each c-correct process.

Definition 8 ((t, c, f )-strongly stabilizing protocol) A protocol A is (t, c, f )-strongly stabilizing if and only if starting from any arbitrary configuration, every execution involving at most f Byzantine processes contains a (t, k, c, f )-time contained configuration that is reached after at most l rounds. Parameters l and k are respectively the (t, c, f )-stabilization time and the (t, c, f )-process-disruption times of A.

Note that a (t, k, c, f )-time contained configuration is a (c, f )-contained configuration when t = k = 0, and thus, (t, k, c, f )-time contained configuration is a generalization (relaxation) of a (c, f )-contained configuration. Thus, a strongly stabilizing protocol is weaker than a strictly stabilizing one (as processes outside the containment radius may take incorrect actions due to Byzantine influence). However, a strongly stabilizing protocol is stronger than a classical selfstabilizing one (that may never meet their specification in the presence of Byzantine processes).

The parameters t, k and c are introduced to quantify the strength of fault containment, we do not require each process to know the values of the parameters.

Topology-aware Byzantine resilience We saw previously that there exist a number of impossibility results on strict stabilization due to the notion of r-restrictives specifications.

To circumvent this impossibility result, we describe here another weaker notion than the strict stabilization: the topology-aware strict stabilization (denoted by TA strict stabilization for short) introduced by [START_REF] Dubois | The impact of topology on byzantine containment in stabilization[END_REF]. Here, the requirement to the containment radius is relaxed, i.e. the set of processes which may be disturbed by Byzantine ones is not reduced to the union of cneighborhood of Byzantine processes (i.e. the set of processes at distance at most c from a Byzantine process) but can be defined depending on the graph topology and Byzantine processes location.

In the following, we give formal definition of this new kind of Byzantine containment. From now, B denotes the set of Byzantine processes and S B (which is function of B) denotes a subset of V (intuitively, this set gathers all processes which may be disturbed by Byzantine processes).

Definition 9 (S B -correct node) A node is S B -correct if it is a correct node ( i.e. not Byzan- tine) which not belongs to S B .
Definition 10 (S B -legitimate configuration) A configuration ρ is S B -legitimate for spec if every S B -correct node v is legitimate for spec ( i.e. if spec(v) holds).

Definition 11 ((S B , f )-topology-aware containment) A configuration ρ 0 is (S B , f )-topologyaware contained for specification spec if, given at most f Byzantine processes, in any execution e = ρ 0 , ρ 1 , . . ., every configuration is S B -legitimate and every S B -correct process never changes its O-variables.

The parameter S B of Definition 11 refers to the containment area. Any process which belongs to this set may be infinitely disturbed by Byzantine processes. The parameter f refers explicitly to the number of Byzantine processes.

Definition 12 ((S B , f )-topology-aware strict stabilization) A protocol is (S B , f )-topologyaware strictly stabilizing for specification spec if, given at most f Byzantine processes, any execution e = ρ 0 , ρ 1 , . . . contains a configuration ρ i that is (S B , f )-topology-aware contained for spec.

Note that, if B denotes the set of Byzantine processes and S

B = v ∈ V |min b∈B (d(v, b)) ≤ c ,
then a (S B , f )-topology-aware strictly stabilizing protocol is a (c, f )-strictly stabilizing protocol. Then, the concept of topology-aware strict stabilization is a generalization of the strict stabilization. However, note that a TA strictly stabilizing protocol is stronger than a classical self-stabilizing protocol (that may never meet their specification in the presence of Byzantine processes). The parameter S B is introduced to quantify the strength of fault containment, we do not require each process to know the actual definition of the set.

Similarly to topology-aware strict stabilization, we can weaken the notion of strong stabilization using the notion of containment area. This idea was introduced by [START_REF] Dubois | On byzantine containment properties of the min+1 protocol[END_REF]. We recall in the following the formal definition of this concept.

Definition 13 (S B -stable configuration) A configuration ρ is S B -stable if every S B -correct process never changes the values of its O-variables as long as Byzantine processes make no action.

Definition 14 (S B -TA-disruption) A portion of execution e = ρ 0 , ρ 3 Maximum Metric Tree Construction

Definition and Specification

In this work, we deal with maximum (routing) metric trees as defined in [START_REF] Gouda | Maximizable routing metrics[END_REF]. Informally, the goal of a routing protocol is to construct a tree that simultaneously maximizes the metric values of all of the nodes with respect to some total ordering ≺. In the following, we recall all definitions and notations introduced in [START_REF] Gouda | Maximizable routing metrics[END_REF].

Definition 17 (Routing metric) A routing metric (or just metric) is a five-tuple (M, W, met, mr, ≺) where:

1. M is a set of metric values, 2.
W is a set of edge weights, 3. met is a metric function whose domain is M × W and whose range is M , 4. mr is the maximum metric value in M with respect to ≺ and is assigned to the root of the system, For instance, we provide the definition of four classical metrics with this model: the shortest path metric (SP), the flow metric (F), and the reliability metric (R). Note also that we can modelise the construction of a spanning tree with no particular constraints in this model using the metric N C described below and the construction of a BFS spanning tree using the shortest path metric (SP) with W 1 = {1} (we denoted this metric by BFS in the following).

SP = (M 1 , W 1 , met 1 , mr 1 , ≺ 1 ) F = (M 2 , W 2 , met 2 , mr 2 , ≺ 2 ) where M 1 = N where mr 2 ∈ N W 1 = N M 2 = {0, . . . , mr 2 } met 1 (m, w) = m + w W 2 = {0, . . . , mr 2 } mr 1 = 0 met 2 (m, w) = min{m, w} ≺ 1 is the classical > relation ≺ 2 is the classical < relation R = (M 3 , W 3 , met 3 , mr 3 , ≺ 3 ) N C = (M 4 , W 4 , met 4 , mr 4 , ≺ 4 ) where M 3 = [0, 1] where M 4 = {0} W 3 = [0, 1] W 4 = {0} met 3 (m, w) = m * w met 4 (m, w) = 0 mr 3 = 1 mr 4 = 0 ≺ 3 is the classical < relation ≺ 4 is the classical < relation
Definition 18 (Assigned metric) An assigned metric over a system S is a six-tuple (M, W, met, mr, ≺, wf ) where (M, W, met, mr, ≺) is a metric and wf is a function that assigns to each edge of S a weight in W .

Let a rooted path (from v) be a simple path from a process v to the root r. The next set of definitions are with respect to an assigned metric (M, W, met, mr, ≺, wf ) over a given system S.

Definition 19 (Metric of a rooted path) The metric of a rooted path in S is the prefix sum of met over the edge weights in the path and mr.

For example, if a rooted path p in S is v k , . . . , v 0 with v 0 = r, then the metric of p is

m k = met(m k-1 , wf ({v k , v k-1 }) with ∀i ∈ {1, . . . , k -1}, m i = met(m i-1 , wf ({v i , v i-1 }) and m 0 = mr.
Definition 20 (Maximum metric path) A rooted path p from v in S is called a maximum metric path with respect to an assigned metric if and only if for every other rooted path q from v in S, the metric of p is greater than or equal to the metric of q with respect to the total order ≺.

Definition 21 (Maximum metric of a node) The maximum metric of a node v = r (or simply metric value of v) in S is defined by the metric of a maximum metric path from v. The maximum metric of r is mr.

Definition 22 (Maximum metric tree) A spanning tree T of S is a maximum metric tree with respect to an assigned metric over S if and only if every rooted path in T is a maximum metric path in S with respect to the assigned metric.

The goal of the work of [START_REF] Gouda | Maximizable routing metrics[END_REF] is the study of metrics that always allow the construction of a maximum metric tree. More formally, the definition follows.

Definition 23 (Maximizable metric) A metric is maximizable if and only if for any assignment of this metric over any system S, there is a maximum metric tree for S with respect to the assigned metric.

Given a maximizable metric M = (M, W, mr, met, ≺), the aim of this work is to study the construction of a maximum metric tree with respect to M which spans the system in a selfstabilizing way in a system subject to permanent Byzantine failures. It is obvious that these Byzantine processes may disturb some correct processes. It is why, we relax the problem in the following way: we want to construct a maximum metric forest with respect to M. The root of any tree of this forest must be either the real root or a Byzantine process.

Each process v has two O-variables: a pointer to its parent in its tree (prnt v ∈ N v ∪ {⊥}) and a level which stores its current metric value (level v ∈ M ). Obviously, Byzantine process may disturb (at least) their neighbors. We use the following specification of the problem.

We introduce new notations as follows. Given an assigned metric (M, W, met, mr, ≺, wf ) over the system S and two processes u and v, we denote by µ(u, v) the maximum metric of node u when v plays the role of the root of the system. If u and v are neighbors, we denote by w u,v the weight of the edge {u, v} (that is, the value of wf ({u, v})).

Definition 24 (M-path) Given an assigned metric M = (M, W, mr, met, ≺, wf ) over a system S, a path (v 0 , . . . , v k ) (k ≥ 1) of S is a M-path if and only if:

1. prnt v 0 = ⊥, level v 0 = 0, and v 0 ∈ B ∪ {r}, 2. ∀i ∈ {1, . . . , k}, prnt v i = v i-1 and level v i = met(level v i-1 , w v i ,v i-1 ), 3. ∀i ∈ {1, . . . , k}, met(level v i-1 , w v i ,v i-1 ) = max ≺ u∈Nv {met(level u , w v i ,u )}, and 4. level v k = µ(v k , v 0 ).
We define the specification predicate spec(v) of the maximum metric tree construction with respect to a maximizable metric M as follows.

spec(v)

:

prnt v = ⊥ and level v = 0 if v is the root r there exists a M-path (v 0 , . . . , v k ) such that v k = v otherwise

Previous results

In this section, we summarize known results about maximum metric tree construction. The first interesting result about maximizable metrics is due to [START_REF] Gouda | Maximizable routing metrics[END_REF] that provides a fully characterization of maximizable metrics as follow.

∀(m, m ′ ) ∈ M 2 , ∀w ∈ W, m ≺ m ′ ⇒ (met(m, w) ≺ met(m ′ , w) or met(m, w) = met(m ′ , w))
Theorem 1 (Characterization of maximizable metrics [START_REF] Gouda | Maximizable routing metrics[END_REF]) A metric is maximizable if and only if this metric is bounded and monotonic.

Secondly, [START_REF] Gouda | Stabilization of maximal metric trees[END_REF] provides a self-stabilizing protocol to construct a maximum metric tree with respect to any maximizable metric. Now, we focus on self-stabilizating solutions resilient to Byzantine faults. Following discussion of Section 2, it is obvious that there exists no strictly stabilizing protocol for this problem. If we consider the weaker notion of topology-aware strict stabilization, [START_REF] Dubois | The impact of topology on byzantine containment in stabilization[END_REF] defines the best containment area as:

S B = {v ∈ V \ B |µ(v, r) max ≺ {µ(v, b), b ∈ B} } \ {r}
Intuitively, S B gathers correct processes that are closer (or at equal distance) from a Byzantine process than the root according to the metric. Moreover, [START_REF] Dubois | The impact of topology on byzantine containment in stabilization[END_REF] proves that the algorithm introduced for the maximum metric spanning tree construction in [START_REF] Gouda | Stabilization of maximal metric trees[END_REF] performed this optimal containment area. More formally, [START_REF] Dubois | The impact of topology on byzantine containment in stabilization[END_REF] proves the following results.

Theorem 2 ([5]

) Given a maximizable metric M = (M, W, mr, met, ≺), even under the central daemon, there exists no (A B , 1)-TA-strictly stabilizing protocol for maximum metric spanning tree construction with respect to M where A B S B .

Theorem 3 ([5]

) Given a maximizable metric M = (M, W, mr, met, ≺), the protocol of [START_REF] Gouda | Stabilization of maximal metric trees[END_REF] is a (S B , n -1)-TA strictly stabilizing protocol for maximum metric spanning tree construction with respect to M. Some others works try to circumvent the impossibility result of strict stabilization using the concept ot strong stabilization but do not provide results for any maximizable metric. Indeed, [7] proves the following result about spanning tree.

Theorem 4 ([7]

) There exists a (t, 0, n -1)-strongly stabilizing protocol for maximum metric spanning tree construction with respect to N C (that is, for a spanning tree with no particular constraints) with a finite t.

On the other hand, regarding BFS spanning tree construction, [START_REF] Dubois | On byzantine containment properties of the min+1 protocol[END_REF] proved the following impossibility result.

Theorem 5 ([6]) Even under the central daemon, there exists no (t, c, 1)-strongly stabilizing protocol for maximum metric spanning tree construction with respect to BFS where t and c are two finite integers.

These two results motivate our result related to strong stabilization in the general case (see Section 4.1) that proves a necessary condition on the maximizable metric to allow strong stabilization.

Now, if we focus on topology-aware strong stabilization, [START_REF] Dubois | On byzantine containment properties of the min+1 protocol[END_REF] proved the following results.

Theorem 6 ([6]

) Even under the central daemon, there exists no (t, A * B , 1)-TA strongly stabilizing protocol for maximum metric spanning tree construction with respect to BFS where

A * B {v ∈ V |min b∈B (d(v, b)) < d(r, v)} and t is a finite integer.
Theorem 7 ( [START_REF] Dubois | On byzantine containment properties of the min+1 protocol[END_REF]) The protocol of [START_REF] Huang | A self-stabilizing algorithm for constructing breadth-first trees[END_REF] is a (t, S * B , n -1)-TA strongly stabilizing protocol for maximum metric spanning tree construction with respect to BFS where t is a finite integer and

S * B = {v ∈ V |min b∈B (d(v, b)) < d(r, v)}.
In the following, we generalize the Theorem 6 to any maximizable metric (see Section 4.2).

Necessary conditions

In this section, we provide our necessary conditions about containment radius (respectively area) of any strongly stabilizing (respectively TA strongly stabilizing) protocol for the maximum metric tree construction.

Strong Stabilization

We introduce here some new definitions to characterize some important properties of maximizable metrics that are used in the following.

Definition 27 (Strictly decreasing metric) A metric M = (M, W, mr, met, ≺) is strictly decreasing if, for any metric value m ∈ M , the following property holds: either ∀w ∈ W, met(m, w) ≺ m or ∀w ∈ W, met(m, w) = m.

Definition 28 (Fixed point) A metric value m is a fixed point of a metric M = (M, W, mr, met, ≺ ) if m ∈ M and if for any value w ∈ W , we have: met(m, w) = m.

Then, we define a specific class of maximizable metrics and we prove that it is possible to construct a maximum metric tree in a strongly-stabilizing way only if we consider such a metric.

Definition 29 (Strongly maximizable metric) A maximizable metric M = (M, W, mr, met, ≺ ) is strongly maximizable if and only if |M | = 1 or if the following properties holds:

• |M | ≥ 2,
• M is strictly decreasing, and

• M has one and only one fixed point.

Note that N C is a strongly maximizable metric (since |M 4 | = 1) whereas BFS or SP are not (since the first one has no fixed point, the second is not strictly decreasing). If we consider the metric MET defined below, we can show that MET is a strongly maximizable metric such that |M | ≥ 2.

MET = (M 5 , W 5 , met 5 , mr 5 , ≺ 5 ) where

M 5 = {0, 1, 2, 3} W 5 = {1} met 5 (m, w) = max{0, m -w} mr 5 = 3 ≺ 5 is the classical < relation
Now, we can state our first necessary condition.

Theorem 8 Given a maximizable metric M = (M, W, mr, met, ≺), even under the central daemon, there exists no (t, c, 1)-strongly stabilizing protocol for maximum metric spanning tree construction with respect to M for any finite integer t if:

   M is not a strongly maximizable metric or c < |M | -2
Proof We prove this result by contradiction. We assume so that M = (M, W, mr, met, ≺) is a maximizable metric such that there exist a finite integer t and a protocol P that is a (t, c, 1)strongly stabilizing protocol for maximum metric spanning tree construction with respect to M. We distinguish the following cases (note that they are exhaustive):

ρ 0 p 0 = r p 1 p c p c+1 p c+2 p c+3 p 2c+2 . . . . . . . . . . . . p 2c+3 = b w 0 w 0 w c w c w c+1 E E ' ' ' ' E ρ 1 . . . . . . E ' ' ' ' ' ' ' ' ' ρ 2 . . . . . . ' ' ' ' ' ' ' ' ' ρ 3 . . . . . . mr mr ?
? ? ? ? ? As c ≥ 0, we know that |M | ≥ 2 and by definition of a strongly stabilizing metric, M is strictly decreasing, and M has one and only one fixed point.

mr mr µ(p 1 , r) µ(p c , r) µ(p c+1 , r) µ(p c+2 , b) µ(p c+3 , b) µ(p 2c+2 , b) mr µ(p 1 , r) µ(p c , r) µ(p c+1 , r) µ(p c+2 , r) µ(p c+3 , r) µ(p 2c+2 , r) µ(p b , r) mr µ(p 1 , r) µ(p c , r) µ(p c+1 , r) µ(p c+2 , r) µ(p c+3 , r) µ(p 2c+2 , r) mr
By assumption on M, we know that there exist c + 3 distinct metric values m 0 = mr, m 1 , . . . , m c+2 in M and w 0 , w 1 , . . . , w c+1 in W such that: ∀i ∈ {1, . . . , c + 2}, m i = met(m i-1 , w i-1 ) ≺ m i-1 .

Let S = (V, E, W) be the following weighted system V = {p 0 = r, p 1 , . . . , p 2c+2 , p 2c+3 = b}, E = {{p i , p i+1 }, i ∈ {0, . . . , 2c + 2}} and ∀i ∈ {0, c + 1}, w p i ,p i+1 = w p 2c+3-i ,p 2c+2-i = w i . Note that the choice w p c+1 ,p c+2 = w c+1 ensures us the following property when level Assume that the initial configuration ρ 0 of S satisfies: prnt r = prnt b = ⊥, level r = level b = mr, and other variables of b (if any) are identical to those of r (see Figure 1, variables of other processes may be arbitrary). Assume now that b takes exactly the same actions as r (if any) immediately after r. Then, by symmetry of the execution and by convergence of P to spec, we can deduce that the system reaches in a finite time a configuration ρ 1 (see Figure 1) in which: ∀i ∈ {1, . . . , c + 1}, prnt p i = p i-1 , level p i = µ(p i , r) = m i and ∀i ∈ {c + 2, . . . , 2c + 2}, prnt p i = p i+1 and level p i = µ(p i , b) = m 2c+3-i (because this configuration is the only one in which all correct process v satisfies spec(v) Assume now that the Byzantine process acts as a correct process and executes correctly its algorithm. Then, by convergence of P in fault-free systems (remember that a stronglystabilizing algorithm is a special case of self-stabilizing algorithm), we can deduce that the system reach in a finite time a configuration ρ 2 (see Figure 1) in which: ∀i ∈ {1, . . . , 2c + 3}, prnt p i = p i-1 and level p i = µ(p i , r) (because this configuration is the only one in which all process v satisfies spec(v)). Note that the portion of execution between ρ 1 and ρ 2 contains at least one c-perturbation (p c+2 is a c-correct process and modifies at least once its O-variables) and that ρ 2 is c-legitimate and c-stable.

p k p k-1 p k+1 p k+2 w w w w w w k-1 S 2 w w ′ 0 w ′ k ′ -1 p 2c+3-k ′ p 2c+2-k ′ p 2c+4-k ′ p 2c+1-k ′ . . . . . . . . . . . .
Assume now that the Byzantine process b takes the following state: prnt b = ⊥ and level b = mr. This step brings the system into configuration ρ 3 (see Figure 1). From this configuration, we can repeat the execution we constructed from ρ 0 . By the same token, we obtain an execution of P which contains c-legitimate and c-stable configurations (see ρ 1 ) and an infinite number of c-perturbation which contradicts the (t, c, 1)-strong stabilization of P.

Case 2: M is not strictly decreasing.

By definition, we know that M is not a strongly maximizable metric. Hence, we have |M | ≥ 2. Then, the definition of a strictly decreasing metric implies that there exists a metric value m ∈ M such that: ∃w ∈ W, met(m, w) = m and ∃w ′ ∈ W, m ′ = met(m, w ′ ) ≺ m (and thus m is not a fixed point of M). By the utility condition on M , we know that there exists a sequence of metric values m 0 = mr, m 1 , . . . , m l = m in M and w 0 , w 1 , . . . , w l-1 in W such that ∀i ∈ {1, . . . , l}, m i = met(m i-1 , w i-1 ). Denote by k the length of the shortest such sequence. Note that this implies that ∀i ∈ {1, . . . , k}, m i ≺ m i-1 (otherwise we can remove m i from the sequence and this is contradictory with the construction of k). We distinguish the following cases: Intuitively, S * B gathers the set of corrects processes that are strictly closer (according to M) to a Byzantine process than the root. Figures from 3 to 5 provide some examples of containment areas with respect to several maximizable metrics and compare it to S B , the optimal containment area for TA strict stabilization. Now, we can state our generalization of Theorem 6.

Theorem 9 Given a maximizable metric M = (M, W, mr, met, ≺), even under the central daemon, there exists no (t, A * B , 1)-TA-strongly stabilizing protocol for maximum metric spanning tree construction with respect to M where A * B S * B and t is a given finite integer.

Proof Let M = (M, W, mr, met, ≺) be a maximizable metric and P be a (t, A * B , 1)-TA-strongly stabilizing protocol for maximum metric spanning tree construction protocol with respect to M where A * B S * B and t is a finite integer. We must distinguish the following cases: This implies that there exists w ′ ∈ W such that: met(m, w ′ ) ≺ m (remember that M is bounded). Consider the following system:

V = {r, u, u ′ , v, v ′ , b}, E =
′ }, {u, v}, {u ′ , v ′ }, {v, b}, {v ′ , b}}, w r,u = w r,u ′ = w v,b = w v ′ ,b = w, and w u,v = w u ′ ,v ′ = w ′ (b is a Byzantine process). We can see that S * B = {v, v ′ }. Since A * B S B , we have: v / ∈ A * B or v ′ / ∈ A * B .
Consider now the following configuration ρ 0 : prnt r = prnt b = ⊥, level r = level b = mr, and prnt, level variables of other processes are arbitrary (see Figure 6, other variables may have arbitrary values but other variables of b are identical to those of r). Assume now that b takes exactly the same actions as r (if any) immediately after r (note that r / ∈ A * B and hence prnt r = ⊥ and level r = mr still hold by closure and then prnt b = ⊥ and level b = mr still hold too). Then, by symmetry of the execution and by convergence of P to spec, we can deduce that the system reaches in a finite time a configuration ρ 1 (see Figure 6) in which: prnt r = prnt b = ⊥, prnt u = prnt u ′ = r, prnt v = prnt v ′ = b, level r = level b = mr, and level u = level u ′ = level v = level v ′ = m (because this configuration is the only one in which all correct process v satisfies spec(v) when prnt r = prnt b = ⊥ and level r = level b = mr since met(m, w ′ ) ≺ m). Note that ρ 1 is A * B -legitimate for spec and A * B -stable (whatever A * B is). Assume now that b behaves as a correct processor with respect to P. Then, by convergence of P in a fault-free system starting from ρ 1 which is not legitimate (remember that a TA-strongly stabilizing algorithm is a special case of self-stabilizing algorithm), we can deduce that the system reach in a finite time a configuration ρ 2 (see Figure 6) in which: prnt r = ⊥, prnt u = prnt u ′ = r, prnt v = u, prnt v ′ = u ′ , prnt b = v (or prnt b = v ′ ), level r = mr, level u = level u ′ = m level v = level v ′ = met(m, w ′ ) = m ′ , and level b = met(m ′ , w) = m ′′ . Note that processes v and v ′ modify their O-variables in the portion of execution between ρ 1 and ρ 2 and that ρ 2 is A * B -legitimate for spec and A * B -stable (whatever A * B is). Consequently, this portion of execution contains at least one A * B -TA-disruption (whatever A * B is). Assume now that the Byzantine process b takes the following state: prnt b = ⊥ and level b = mr. This step brings the system into configuration ρ 3 (see Figure 6). From this configuration, we can repeat the execution we constructed from ρ 0 . By the same token, we obtain an execution of P which contains c-legitimate and c-stable configurations (see ρ 1 ) and an infinite number of A * B -TA-disruption (whatever A * B is) which contradicts the (t, A * B , 1)-TA-strong stabilization of P.

Conclusion

In this paper, we presented two necessary conditions to achieve strong stabilization and topologyaware strong stabilization in maximum metric tree construction. Our work obviously leads to the following open question: is there a topology-aware strongly stabilizing protocol that ensures a containmemt area equal to S * B ? We conjecture that it is the case.

5 .

 5 ≺ is a less-than total order relation over M that satisfies the following three conditions for arbitrary metric values m, m ′ , and m ′′ in M :(a) irreflexivity: m ≺ m, (b) transitivity : if m ≺ m ′ and m ′ ≺ m ′′ then m ≺ m ′′ , (c) totality: m ≺ m ′ or m ′ ≺ m or m = m ′ .Any metric value m ∈ M \{mr} satisfies the utility condition (that is, there exist w 0 , . . . , w k-1 in W and m 0 = mr, m 1 , . . . , m k-1 , m k = m in M such that ∀i ∈ {1, . . . , k}, m i = met(m i-1 , w i-1 )).

Figure 1 :

 1 Figure 1: Configurations used in proof of Theorem 8, case 1.

  r = level b = mr: µ(p c+1 , b) ≺ µ(p c+1 , r) (and by symmetry, µ(p c+2 , r) ≺ µ(p c+2 , b)). Process p 0 is the real root and process b is a Byzantine one. Note that the construction of W ensures the following properties when level r = level b = mr: ∀i ∈ {1, . . . , c + 1}, µ(p i , r) = µ(p 2c+3-i , b), µ(p i , b) ≺ µ(p i , r) and µ(p 2c+3-i , r) ≺ µ(p 2c+3-i , b).

Figure 2 :

 2 Figure 2: Configurations used in proof of Theorem 8, cases 2 and 3.

Figure 3 :

 3 Figure 3: Examples of containment areas for SP spanning tree construction.

Case 1 :Case 2 :

 12 |M | = 1. Denote by m the metric value such that M = {m}. For any system and for any process v, we have µ(v, r) = min ≺ b∈B {µ(v, b)} = m. Consequently, S * B = ∅ for any system. Then, it is absurd to have A * B S * B . |M | ≥ 2. By definition of a bounded metric, we can deduce that there exists m ∈ M and w ∈ W such that m = met(mr, w) ≺ mr. Then, we must distinguish the following cases: Case 2.1: m is a fixed point of M. Let S be a system such that any edge incident to the root or a Byzantine process has a weight equals to w. Then, we can deduce that we have: m = max ≺ b∈B {µ(r, b)} ≺ µ(r, r) = mr and for any correct process v = r, µ(v, r) = max ≺ b∈B {µ(v, b)} = m. Hence, S * B = ∅ for any such system. Then, it is absurd to have A * B S * B . Case 2.2: m is not a fixed point of M.

Figure 4 :

 4 Figure 4: Examples of containment areas for flow spanning tree construction.

Figure 5 :

 5 Figure 5: Examples of containment areas for reliability spanning tree construction.

Figure 6 :

 6 Figure 6: Configurations used in proof of Theorem 9.

  1 , . . . , ρ t (t > 1) is a S B -TA-disruption if and only if the followings hold: 1. e is finite, 2. e contains at least one action of a S B -correct process for changing the value of an Ovariable, 3. ρ 0 is S B -legitimate for spec and S B -stable, and 4. ρ t is the first configuration after ρ 0 such that ρ t is S B -legitimate for spec and S B -stable. Definition 15 ((t, k, S B , f )-TA time contained configuration) A configuration ρ 0 is (t, k, S B , f )-TA time contained for spec if given at most f Byzantine processes, the following properties are satisfied:

1. ρ 0 is S B -legitimate for spec and S B -stable, 2. every execution starting from ρ 0 contains a S B -legitimate configuration for spec after which the values of all the O-variables of S B -correct processes remain unchanged (even when Byzantine processes make actions repeatedly and forever),

[START_REF] Shlomi | Self-stabilization[END_REF]

. every execution starting from ρ 0 contains at most t S B -TA-disruptions, and 4. every execution starting from ρ 0 contains at most k actions of changing the values of O-variables for each S B -correct process.

Definition 16 ((t, S B , f )-TA strongly stabilizing protocol) A protocol A is (t, S B , f )-TA strongly stabilizing if and only if starting from any arbitrary configuration, every execution involving at most f Byzantine processes contains a (t, k, S B , f )-TA-time contained configuration that is reached after at most l actions of each S B -correct node. Parameters l and k are respectively the (t, S B , f )-stabilization time and the (t, S B , f )-process-disruption time of A.

Case 2.1: k ≥ c + 2.

We can use the same token as case 1 above by using w ′ instead of w c+1 in the case where k = c + 2 (since we know that met(m, w ′ ) ≺ m).

Case 2.2: k < c + 2.

Let S 1 = (V, E, W) be the following weighted system V = {p 0 = r, p 1 , . . . , p 2c+2 , p 2c+3 = b}, E = {{p i , p i+1 }, i ∈ {0, . . . , 2c+2}}, ∀i ∈ {0, . . . , k-1}, w p i ,p i+1 = w p 2c+3-i ,p 2c+2-i = w i , ∀i ∈ {k, . . . , c}, w p i ,p i+1 = w p 2c+3-i ,p 2c+2-i = w and w p c+1 ,p c+2 = w ′ (see Figure 2). Note that this choice ensures us the following property when level r = level b = mr: µ(p c+1 , b) ≺ µ(p c+1 , r) (and by symmetry, µ(p c+2 , r) ≺ µ(p c+2 , b)). Process p 0 is the real root and process b is a Byzantine one. Note that the construction of W ensures the following properties when level r = level b = mr: ∀i ∈ {1, . . . , c

This construction allows us to follow the same proof as in case 1 above.

Case 3: M has no or more than two fixed point, and is strictly decreasing.

If M has no fixed point and is strictly decreasing, then |M | is not finite and then, we can apply the result of case 1 above since c is a finite integer.

If M has two or more fixed points and is strictly decreasing, denote by Υ and Υ ′ two fixed points of M. Without loss of generality, assume that Υ ≺ Υ ′ . By the utility condition on M , we know that there exists sequences of metric values m 0 = mr, m 1 , . . . , m l = Υ and

). Denote by k and k ′ the length of shortest such sequences. Note that this implies that ∀i ∈ {1, . . . , k}, m i ≺ m i-1 and ∀i ∈ {1, . . . , k ′ }, m ′ i ≺ m ′ i-1 (otherwise we can remove m i or m ′ i from the corresponding sequence). We distinguish the following cases:

Without loss of generality, assume that k > c + 2 (the second case is similar). We can use the same token as case 1 above.

Let w be an arbitrary value of W . Let S 2 = (V, E, W) be the following weighted system 2). Note that this choice ensures us the following property when level r = level b = mr: µ(p c+1 , r) = Υ ≺ Υ ′ = µ(p c+1 , b) and µ(p c+2 , r) = Υ ≺ Υ ′ = µ(p c+2 , b). Process p 0 is the real root and process b is a Byzantine one. This construction allows us to follow a similar proof as in case 1 above (note that any process u which satisfies µ(u, r) ≺ Υ ′ will be disturb infinitely often, in particular at least p c+1 and p c+2 which contradicts the (t, c, 1)-strong stabilization of P).

In any case, we show that there exists a system which contradicts the (t, c, 1)-strong stabilization of P that ends the proof.

Topology Aware Strong Stabilization

First, we generalize the set S * B previously defined for the BFS metric in [START_REF] Dubois | On byzantine containment properties of the min+1 protocol[END_REF] to any maximizable metric M = (M, W, mr, met, ≺).