Alice Legru

Federica Verdirosa

Jean-François Hernandez
email: jean-francois.hernandez@umontpellier.fr

Giusi Tassone

Filomena Sannio

Manuela Benvenuti

Pierre-Alexis Conde

Guillaume Bossis

Caitlyn A Thomas

Michael W Crowder

Melissa Dillenberger

Katja Becker

Cecilia Pozzi

Stefano Mangani

Jean-Denis Docquier
email: jddocquier@unisi.it

Laurent Gavara
email: laurent.gavara@umontpellier.fr

à la diffusion de documents scientifiques de niveau

Keywords: Metallo-b-Lactamase inhibitor, 1,2,4-triazole-3-thione, bacterial resistance, blactam antibiotic, thioether

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

Bacterial resistance to antibiotics has reached alarming levels and represents an increasingly important Public Health concern [START_REF] Ventola | The antibiotic resistance crisis: part1: causes and threats[END_REF][START_REF] Reygaert | An overview of the antimicrobial resistance mechanisms of bacteria[END_REF][START_REF] Cassini | Attributable deaths and disability-adjusted life-years caused by infections with antibioticresistant bacteria in the EU and the European Economic Area in 2015: a population-level modelling analysis[END_REF]. Among the bacterial pathogens responsible of nosocomial infections, carbapenem-resistant Gram-negative bacteria such as Enterobacterales,

Acinetobacter baumannii and Pseudomonas aeruginosa have recently been recognized by the World Health Organization as "critical" priorities for the discovery and development of new antibacterial drugs [START_REF]World Health Organization, Global priority list of antibiotic-resistant bacteria to guide research, discovery and development of new antibiotics[END_REF]. Indeed, such organisms are often multi-to extremely-drug-resistant, therefore limiting available treatments to a few therapeutic options [START_REF] Walsh | The emergence of pan-resistant Gram-negative pathogens merits a rapid global political response[END_REF]. One privileged approach is to restore their susceptibility to carbapenems, which are valuable β-lactam antibiotics considered as last resort antibacterial drugs in the clinical setting.

Among the possible mechanisms of carbapenem resistance, which also include decreased porin expression or efflux, the most relevant is the enzymatic inactivation by β-lactamases endowed with carbapenem-hydrolyzing activity, the so-called carbapenemases. They belong to molecular classes A, B and D of β-lactamases [START_REF] Nordmann | Global spread of carbapenemase-producing Enterobacteriaceae[END_REF][START_REF] Bush | Past and present perspectives on b-lactamases[END_REF]. Serine-carbapenemases are active serine enzymes. They are characterized by a broad substrate profile, an efficient hydrolysis of carbapenems and their insensitivity to currently available SBL inhibitors (clavulanate, avibactam, vaborbactam). These enzyme subtypes are typically encoded by mobile genetic elements (transposons, plasmids) disseminating in Gram-negative fermenters and nonfermenters, which initially emerged and spread in the hospital setting. However, because of their present global dissemination, MBL-producing isolates increasingly cause communityacquired infections [START_REF] Gajamer | Escherichia coli encoding blaNDM-5 associated with community-acquired urinary tract infections with unusual MIC creep-like phenomenon against imipenem[END_REF]. New drugs are urgently needed to fight infections due to MBLproducing bacteria.

Combining a b-lactamase inhibitor with a b-lactam antibiotic is a well-known approach to restore the efficacy of the latter. Several b-lactamase inhibitors are currently marketed (clavulanate, sulbactam, tazobactam, avibactam, vaborbactam) [START_REF] Gonzalez-Bello | b-Lactamase inhibitors to restore the efficacy of antibiotics against superbugs[END_REF][START_REF] Vazquez-Ucha | New carbapenemase inhibitors : clearing the way for the b-lactams[END_REF]. However, they only target some SBLs, including the carbapenemases KPC and OXA-48 in the case of the most recently approved inhibitors [START_REF] Docquier | An update on b-lactamase inhibitor discovery and development[END_REF]. Despite many MBL inhibitors have been reported in the literature, none have been approved yet [START_REF] Bahr | Metallo-b-lactamase inhibitors in the age of multidrug resistance: from structure and mechanism to evolution, dissemination, and inhibitor design[END_REF]. The structural and functional heterogeneity of clinically relevant MBLs represents a true challenge for the discovery of a broad-spectrum inhibitor [START_REF] Ju | The continuing challenge of metallo-b-lactamase inhibition: mechanism matters[END_REF][START_REF] Palacios | Metallo-b-lactamase inhibitors inspired on snapshots from the catalytic mechanism[END_REF]. In addition, most reported inhibitors displayed a zinc-coordinating element in their structures. This element is often determining to reach high affinity and it increases the risk of off-target activity, especially on human metallo-enzymes [START_REF] Chen | Targeting metalloenzymes for therapeutic intervention[END_REF]. It is particularly the case of thiol-containing compounds, which represent the most abundant class of MBL inhibitors described to date [START_REF] Docquier | An update on b-lactamase inhibitor discovery and development[END_REF][START_REF] Gonzalez | Bisthiazolidines: a substrate-mimicking scaffold as an inhibitor of the NDM-1 carbapenemase[END_REF][START_REF] Klingler | Approved drugs containing thiols as inhibitors of metallo-β-lactamases: strategy to combat multidrugresistant bacteria[END_REF][START_REF] Tehrani | Thiol-containing metallo-β-lactamase inhibitors resensitize resistant Gram-negative bacteria to meropenem[END_REF][START_REF] Liu | S)-3-Mercapto-2-methylpropanamido)acetic acid derivatives as metallo-β-lactamase inhibitors: synthesis, kinetic and crystallographic studies[END_REF]. This potential drawback might be alleviated with rhodanines, which behave as thiol precursors [START_REF] Brem | Rhodanine hydrolysis leads to potent thioenolate mediated metallo-β-lactamase inhibition[END_REF][START_REF] Xiang | Rhodanine as a potent scaffold for the development of broad-spectrum metallo-β-lactamase inhibitors[END_REF]. The carboxylate group is another well-known Znligand and compounds containing several of these groups as succinates or dipicolinates were reported [START_REF] Ju | The continuing challenge of metallo-b-lactamase inhibition: mechanism matters[END_REF][START_REF] Chen | Dipicolinic acid derivatives as inhibitors of New Delhi Metalloβ-lactamase-1[END_REF]. Inhibitors with metal-stripping effect as the aspergillomarasmine A [START_REF] King | Aspergillomarasmine A overcomes metallo-β-lactamase antibiotic resistance[END_REF] or Zn148 [START_REF] Samuelsen | ZN148 -a modular synthetic metallob-lactamase inhibitor reverses carbapenem-resistance in Gram-negative pathogens in vivo[END_REF] also showed potent activity, but they are expected to be of insufficient selectivity.

More recently, appeared several families of inhibitors active on both SBLs and MBLs including boronates [START_REF] Burns | b-Lactamase inhibitors[END_REF][START_REF] Wang | Structure-based development of (1-(3'-mercaptopropanamido)methyl)boronic acid derived broad-spectrum, dual-action inhibitors of metallo-and serine-b-lactamases[END_REF][START_REF] Hecker | Discovery of cyclic boronic acid QPX7728, an ultrabroad-spectrum inhibitor of serine and metallo-b-lactamases[END_REF][START_REF] Parkova | Broad spectrum b-lactamase inhibition by a thioether substituted bicyclic boronate[END_REF], phosphonates [START_REF] Pemberton | Heteroaryl phosphonates as non covalent inhibitors of both serine-and metallocarbapenemases[END_REF] and azetidinimines [START_REF] Romero | Azetidinimines, as a novel series of non-covalent broad-spectrum inhibitors of b-lactamases with submicromolar activities against carbapenemases KPC-2 (class A), NDM-1 (class B) and OXA-48 (class D)[END_REF]. Only few compounds are currently promising [START_REF] Reddy | A 2018-2019 patent review of metallo-b-lactamase inhibitors[END_REF]. It includes the thiazole MBL inhibitor ANT2681 [START_REF] Davies | ANT2681: SAR studies leading to the identification of a metallolactamase inhibitor with potential for clinical use in combination with meropenem for the treatment of infections caused by NDM-producing Enterobacteriaceae[END_REF] and the broadspectrum inhibitors of MBLs and SBLs cyclic boronates, such as taniborbactam [START_REF] Burns | b-Lactamase inhibitors[END_REF][START_REF] Liu | Discovery of Taniborbactam (VNRX-5133): a broad spectrum serine-and metallo-b-lactamase inhibitor for carbapenem-resistant bacterial infections[END_REF][START_REF] Brem | Structural basis of metallo-b-lactamase, serine-b-lactamase and penicillin-binding protein inhibition by cyclic boronates[END_REF] and QPX7728 [START_REF] Hecker | Discovery of cyclic boronic acid QPX7728, an ultrabroad-spectrum inhibitor of serine and metallo-b-lactamases[END_REF]. Noteworthily, these two latter compounds are under clinical development.

However, the current absence of approved MBL inhibitors and the intrinsic ability of bacteria to develop resistances necessitate further investigation to offer new treatment options.

We are developing MBL inhibitors containing the promising 1,2,4-triazole-3-thione heterocycle as an original ligand for MBL dizinc active sites [START_REF] Nauton | Structural insights into the design of inhibitiors of the L1 metallo-b-lactamase from Stenotrophomonas maltophilia[END_REF]. Since the first report by Olsen et al. [START_REF] Olsen | New leads of metallo-b-lactamase inhibitors from structure-based pharmacophore design[END_REF] related to the subclass B3 L1 MBL, several random in silico and experimental studies also supported the potential of this heterocycle to inhibit various MBLs of the B1 subclass (i.e.

IMP-1 [START_REF] Vella | The identification of new metallo-b-lactamase inhibitor leads from fragment-based screening[END_REF], VIM-2 [START_REF] Christopeit | Discovery of novel inhibitor scaffolds against the metallo-b-lactamase VIM-2 by surface plasmon resonance (SPR) based fragment screening[END_REF] and NDM-1 [START_REF] Spyrakis | Structure-based virtual screening for the discovery of novel inhibitors of New Delhi Metallo-b-lactamase-1[END_REF]). In addition, several other crystallographic structures of complexes confirmed that the heterocycle was well adapted to bind into the di-zinc active site of these enzymes. Indeed, in all structures, the heterocycle-thione simultaneously bound to the two Zn ions through two atoms, the heterocyclic nitrogen N 2 for Zn1 and the extracyclic sulfur for Zn2 [START_REF] Nauton | Structural insights into the design of inhibitiors of the L1 metallo-b-lactamase from Stenotrophomonas maltophilia[END_REF][START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF][START_REF] Spyrakis | Virtual screening identifies broad-spectrum b-lactamase inhibitors with activity on clinically relevant serine-and metallo-carbapenemases[END_REF]. Finally, its particular mode of binding might be less efficient toward human metallo-enzymes, which are mainly mono-zinc.

The 1,2,4-triazole-3-thione scaffold offers two modifiable substituents at positions 5 and 4

(Figure 1). In a first study, we explored substitution at position 5, while position 4 was not substituted or only by an amino group [START_REF] Sevaille | 1,2,4-Triazole-3-thione compounds as inhibitors of dizinc metallob-lactamase[END_REF]. Some compounds showed significant and broadspectrum inhibition against representative MBLs, but none was able to restore antibiotic activity in MBL-producing resistant bacteria. A second series was that of Schiff base analogues where an aryl substituent was linked to the 4-amino-heterocycle through a hydrazone-like bond (Figure 1A) [START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF]. Although the introduction of an aryl substituent at position 4 led to more potent compounds with a broader spectrum of inhibition, no antibiotic potentiation could be achieved against clinical isolates. Poor penetration of the bacterial outer membrane and the potential instability of the hydrazone-like bond to hydrolysis could explain this strong limitation. To solve the instability issue, we first reduced the hydrazone-like bond of selected Schiff base analogues, yielding a third series of compounds (Figure 1B) [START_REF] Gavara | 4-(N-Alkyl-and -acyl-amino)-1,2,4-triazole-3-thione analogs as metallo-b-lactamase inhibitors: impact of 4-linker on potency and spectrum of inhibition[END_REF]. Unfortunately, this modification led to less promising compounds. In parallel, we further explored substitution at position 4 by introducing alkyl moieties. A first study identified the high potential of alkanoic chains (Figure 1C) [START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]. However, these compounds showed a limited spectrum of activity (no inhibition of NDM-1 and IMP-1) and only modest antibiotic potentiation was observed in microbiological assays. Among these analogues, one possessed an alkanoic chain with a thioether group (compound 1, Figure 1D). Compound 1 was a potent inhibitor of VIM-type enzymes and showed moderate activity toward NDM-1. Based on these results, we further evaluated the presence of a thioether group in the substituent at position 4 (Figure 1E). We found that the addition of an aryl group at the extremity of the thioether-containing alkyl chain led to potent inhibition of VIM-type enzymes, NDM-1 and IMP-1. In addition, several compounds were able to potentiate meropenem antibacterial activity in clinical multidrug resistant isolates of K. pneumoniae.

Finally, the resolution of crystallographic structures of complexes with VIM-2 allowed to study the binding mode of these thioether compounds.

Figure 1. Structure of compounds based on the 1,2,4-triazole-3-thione scaffold and their inhibitory potency toward selected MBLs: (A) Schiff base analogue [START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF]; (B) reduced analogue [START_REF] Gavara | 4-(N-Alkyl-and -acyl-amino)-1,2,4-triazole-3-thione analogs as metallo-b-lactamase inhibitors: impact of 4-linker on potency and spectrum of inhibition[END_REF]; (C) 4-alkanoic analogue; [START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]; (D) 4alkanoic analogue with a thioether group, compound 1 [START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]; (E) general structure of synthesized compounds containing a thioether group. 1,2,4-Triazole-3-thione compounds were prepared from hydrazide and amine precursors in the presence of dipyridylthionocarbonate (DPT) according to Deprez-Poulain et al. [START_REF] Deprez-Poulain | Convenient synthesis of 4H-1,2,4-triazole-3-thiols using di-2-pyridylthionocarbamate[END_REF] and as described [START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]. The hydrazides R 1 -C(O)NHNH2 were first obtained in two steps from the corresponding carboxylic derivative as described in the Supplementary Material part (Scheme S1). The thioether-containing alkylamines R 2 -NH2 were either commercially available or synthesized as Boc-protected derivatives by alkylation of a thiol with a brominated compound, followed by Boc removal in acidic conditions, as described in the Supplementary Material part (Scheme S2). The ether-containing alkylamine precursor of compound 22 was commercially available. Then, the alkylamines were treated with DPT to yield the intermediate isothiocyanates, which were directly reacted with hydrazides to form the thiosemicarbazide derivatives. Finally, basic treatment induced cyclization toward the expected 1,2,4-triazole-3thione compounds 1-30 (Scheme 1).

N N H N S N CO 2 H N N H N S HN CO 2 H N N H N S CO 2 H D Compound 1 N N H N S S R 2 E R 1 m n m = 1,2 n = 0-2

Evaluation of inhibitory potency toward purified MBLs

Compounds were tested against five representative MBLs, the subclass B1 enzymes VIM-1, VIM-2, VIM-4, NDM-1 and IMP-1. After initial testing at 100 µM, Ki values were measured for compounds exhibiting > 75% inhibition.

The results obtained for a first series of 22 compounds are presented in Table 1. Compound 1 was included for comparison. In this series, all compounds possessed a phenyl ring at position 5 with the exception of compound 5, which had a m-biphenyl group. At position 4, they displayed a diversely S-substituted ethyl sulfide group, with the exception of compound 21, which had a S-substituted propyl sulfide group and of compound 22 where the sulfur was replaced by an oxygen. Compared to compound 1, compound 2 possessed a one-methylene longer chain with a S-propanoic substituent and a quite similar activity profile, although it also significantly inhibited IMP-1. Adding a phenyl ring at the a-position of the carboxyl group of compounds 1 and 2 yielded compounds 3 and 4, respectively. Whereas compound 3 showed similar activities as 1, the presence of the aromatic moiety was highly beneficial for compound 4. Indeed, this compound showed submicromolar Ki values against both VIM-type enzymes, was a micromolar inhibitor of NDM-1 and significantly inhibited IMP-1. As we previously found that a m-biphenyl substituent at position 5 was favourable to inhibition, we synthesized the corresponding analogue of 4, i.e. compound 5. However, although 5 was also a potent inhibitor of VIM-type enzymes, this modification did not improve the activity and was slightly detrimental to NDM-1 and IMP-1 inhibition.

N HN N S R 1 R 2 O R 1 H N N H N H S a b H N R 1 O NH 2 + H 2 N R 2 R 2 S * CO 2 H R 2 = X n X = H, phenyl; n = 1,2: 1-5 R 1 =
Because compounds 3 and 4 possessed a chiral center and an a-branched alkanoic chain that could complicate further development of this series, we removed the carboxylic group to check its importance in MBL inhibition, giving compounds 6 and 13, respectively. In fact, this modification was favourable for compound 6 as, in addition to be a slightly better VIM inhibitor, it also inhibited NDM-1 and IMP-1 with Ki values around 20 µM. Compound 13

showed similar activities against all enzymes as 6. These results indicated that the carboxylic group was not essential in this series.

Based on these data, we prepared a small series of 6 analogues where the phenyl group of the 4-substituent was diversely substituted (compounds 7-12). All molecules were potent inhibitors of both VIM-type enzymes as 6, showing Ki values in the low micromolar to submicromolar range. In addition, most compounds (i.e. 7-11) were also moderate to good inhibitors of NDM-1 and IMP-1. Compound 11 showed one of the broadest spectrum of activity in this series.

As the separation of the phenyl ring from the sulfur atom by one [START_REF] Nordmann | Global spread of carbapenemase-producing Enterobacteriaceae[END_REF] or two (13) methylenes gave potent MBL inhibitors, we assessed if its direct attachment was also tolerated (i.e. compound 14). It was indeed the case as compound 14 showed an inhibition profile similar to that of 11. Therefore, we prepared a short series of compounds [START_REF] Palacios | Metallo-b-lactamase inhibitors inspired on snapshots from the catalytic mechanism[END_REF][START_REF] Chen | Targeting metalloenzymes for therapeutic intervention[END_REF][START_REF] Gonzalez | Bisthiazolidines: a substrate-mimicking scaffold as an inhibitor of the NDM-1 carbapenemase[END_REF][START_REF] Klingler | Approved drugs containing thiols as inhibitors of metallo-β-lactamases: strategy to combat multidrugresistant bacteria[END_REF][START_REF] Tehrani | Thiol-containing metallo-β-lactamase inhibitors resensitize resistant Gram-negative bacteria to meropenem[END_REF][START_REF] Liu | S)-3-Mercapto-2-methylpropanamido)acetic acid derivatives as metallo-β-lactamase inhibitors: synthesis, kinetic and crystallographic studies[END_REF] with various aryl and heteroaryl moieties directly attached to the sulfur. Unfortunately, these modifications were generally detrimental for the inhibitory activity, excepted 15 (aniline) with similar profile as 14, and 16 (naphtha-1-yl), which however only inhibited VIM-type enzymes. Increasing the distance between the triazole ring and the sulfur from ethyl to propyl gave compound 21, which was a rather potent inhibitor of VIM-type enzymes although with a lower potency when compared to that of the shorter 14 and compound 6, which possessed a 4-substituent of same size and composition but where the sulfur was shifted by one atom. In addition, 21 only moderately inhibited NDM-1 and IMP-1. This result indicated the importance of the sulfur atom and of its position for MBL inhibition. It was confirmed by replacing the sulfur atom of compound 6 by an oxygen (i.e. compound 22). Indeed, the ether 22 showed a very similar activity profile as 21, and therefore was a less potent inhibitor of both enzymes compared to 6.

It is noteworthy that the thioether moiety exhibits an angle close to 90°, while that of an ether is close to 110°. This difference, which should have an impact in substituent positioning may at least partially explain the difference in activity between the analogues 6 and 22. Overall, the presence of a thioether group in the 4-alkyl chain and a phenyl ring at its extremity was quite favourable to potent and broad-spectrum inhibition of MBLs, while a carboxylic group could be spared. The position of the sulfur relative to the triazole moiety was critical for activity, while its replacement by an oxygen was deleterious.

Based on the results obtained with compounds possessing a phenyl group at the 5-position (with the exception of compound 5), we prepared a series of compounds derived from compound 6, with an ethyl benzyl sulfide substituent and a variable aryl group at positions 4 and 5, respectively (Table 2). The aryl groups were chosen according to inhibition data obtained with our previously reported series of 1,2,4-triazole-3-thione-based MBL inhibitors [START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF][START_REF] Gavara | 4-(N-Alkyl-and -acyl-amino)-1,2,4-triazole-3-thione analogs as metallo-b-lactamase inhibitors: impact of 4-linker on potency and spectrum of inhibition[END_REF][START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF].

Compounds 23 (o-toluyl), 24 (2-hydroxy-5-methoxy) and 25 (1-methyl-pyrrol-2-yl), were potent inhibitors of both VIM-type enzymes with Ki values in the submicromolar range. NDM-1 and IMP-1 were also significantly inhibited by these compounds, although less potently in the case of 24. However, substituting the phenyl ring at position 5 did not improve the inhibitory profile compared to 6. Based on its potency and broad spectrum of inhibition, compound 25 was subjected to a Dixon plot analysis (Figure 2) with the VIM-1 MBL. The data obtained were compatible with a competitive mechanism of inhibition and confirmed the submicromolar Ki value (0.20 ± 0.02 µM). We also prepared compounds with two aromatic groups at position 5 because these substituents were previously found to be highly favourable to MBL inhibition [START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF][START_REF] Gavara | 4-(N-Alkyl-and -acyl-amino)-1,2,4-triazole-3-thione analogs as metallo-b-lactamase inhibitors: impact of 4-linker on potency and spectrum of inhibition[END_REF][START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]. They displayed an ortho- [START_REF] Burns | b-Lactamase inhibitors[END_REF], meta- [START_REF] Wang | Structure-based development of (1-(3'-mercaptopropanamido)methyl)boronic acid derived broad-spectrum, dual-action inhibitors of metallo-and serine-b-lactamases[END_REF], or para-biphenyl (28) group, a p-benzyloxyphenyl [START_REF] Parkova | Broad spectrum b-lactamase inhibition by a thioether substituted bicyclic boronate[END_REF], or a naphth-2-yl-methyl (30) group. Unfortunately, the inhibitory data obtained with these compounds were quite disappointing as none inhibited VIM-2 and NDM-1 and they were generally only modest

or not inhibitors of the other tested MBLs. In particular, compound 27, which possesses a mbiphenyl group previously shown to be the most favourable substituent at this position, only inhibited VIM-4. In addition, some of these compounds [START_REF] Wang | Structure-based development of (1-(3'-mercaptopropanamido)methyl)boronic acid derived broad-spectrum, dual-action inhibitors of metallo-and serine-b-lactamases[END_REF][START_REF] Hecker | Discovery of cyclic boronic acid QPX7728, an ultrabroad-spectrum inhibitor of serine and metallo-b-lactamases[END_REF][START_REF] Pemberton | Heteroaryl phosphonates as non covalent inhibitors of both serine-and metallocarbapenemases[END_REF] suffered of low solubility.

Crystal structures of the complexes between VIM-2 and compounds 8, 10 and 14

The structure of VIM-2 in complex with three inhibitors, compounds 8, 10, and 14, was determined at resolutions ranging from 1.80 to 1.92 Å (Table S1). We previously reported the characterization of VIM-2 in complex with a 4-amino-1,2,4triazole-3-thione-derived Schiff base (PDB code 6YRP, compound 31 in reference [START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF]). The comparison with the binding modes of the 1,2,4-triazole-3-thione compounds 8, 10, and 14

highlights the conserved interactions formed by the shared triazole-thione core of the inhibitors, involved in the coordination of both Zn1 and Zn2 ions inside the cavity (Figure 4). Analogous interactions are also formed by the shared 5-phenyl moiety of the inhibitors, accommodated in the pocket lined by Phe61, Trp87, and Asp119. At the opposite side of the cavity, the variable molecular functions introduced at position 4 determine peculiar interactions in this area. In compounds 8, 10, and 14, the increased length of the ethyl sulfide group allows to explore a different portion of the active site cavity, lined by Tyr67, Arg228, and His263 (Figure 4).

Equilibrium dialysis and native state electrospray ionization mass spectrometry (native MS)

We further evaluated the mechanism of inhibition of this series of compounds by studying the effect of compound 6 on the metal content of VIM-2 and NDM-1 using equilibrium dialysis followed by metal analysis with atomic absorption spectroscopy [START_REF] Chen | Dipicolinic acid derivatives as inhibitors of New Delhi Metalloβ-lactamase-1[END_REF][START_REF] Thomas | Probing the mechanism of inhibition for various inhibitors of metallo-b-lactamases VIM-2 and NDM-1[END_REF]. At concentrations up to 48 µM, the compound did not remove Zn(II) from either VIM-2 or NDM-1 (Figure S3), suggesting the formation of a ternary complex between the inhibitor and both MBLs in agreement with previous and here presented crystallographic data [START_REF] Nauton | Structural insights into the design of inhibitiors of the L1 metallo-b-lactamase from Stenotrophomonas maltophilia[END_REF][START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF][START_REF] Spyrakis | Virtual screening identifies broad-spectrum b-lactamase inhibitors with activity on clinically relevant serine-and metallo-carbapenemases[END_REF].

Native MS is an efficient technique used to probe the mechanism of inhibition at low enzyme/inhibitor concentrations. The experiment was performed using 10 µM NDM-1 and 5

equivalents of compound 6. The native MS of the MBL with 6 showed two main peaks: a dominant +8 peak at 3,174 m/z, and a non-dominant +8 peak at 3,214 m/z, corresponding to the mass of two Zn(II) bound NDM-1 (25,385 Da) and to that of two Zn(II) bound NDM-1 with one equivalent of compound 6 (25,712 Da), respectively. This result further supports the formation of a ternary complex with NDM-1 (Figure S4).

In vitro antibacterial synergistic activity

Considering the significant potency of several compounds towards all tested MBLs and in particular on VIM-type enzymes, their potential synergistic activity was tested using the broth microdilution method on several MBL-producing multidrug-resistant clinical isolates. First, it was assessed that (a) none of the compounds showed any direct or intrinsic antibacterial activity (MIC > 512 µg/mL) and that (b) the stability of meropenem was not affected by the presence of selected inhibitor for up to 4 hours at 35 °C (measured in both 50 mM HEPES buffer, pH 7.5, and in Mueller-Hinton broth, by following the absorbance at 300 nm, as previously described; data not shown) [START_REF] Huang | Determination of meropenem in bacterial media by LC-MS/MS[END_REF][START_REF] Landini | Effect of high N-acetylcysteine concentrations on antibiotic activity against a large collection of respiratory pathogens[END_REF]. Tested at a fixed concentration of 32 µg/mL (essentially to generate data comparable to that of previous series [START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF][START_REF] Sevaille | 1,2,4-Triazole-3-thione compounds as inhibitors of dizinc metallob-lactamase[END_REF][START_REF] Gavara | 4-(N-Alkyl-and -acyl-amino)-1,2,4-triazole-3-thione analogs as metallo-b-lactamase inhibitors: impact of 4-linker on potency and spectrum of inhibition[END_REF][START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]), most compounds were able to reduce the MIC of meropenem on K. pneumoniae isolates producing VIM-1 or VIM-4 (Table 3). Indeed, in these conditions, several showed up to a remarkable 16-fold potentiation of meropenem (compounds 2, 7, 9-14, 21 and 25). In particular, compound 14 displayed a similar potentiation against both isolates. There was no clear relationship between inhibitory potencies and synergistic antibacterial activities, suggesting that structural modifications would differently impact on enzyme inhibition and the ability of the compound to readily accumulate in the periplasmic space through rapid diffusion across the outer membrane. In particular, the potent VIM inhibitors 16 and 27 were unable to potentiate meropenem in these experiments.

To assess whether the compounds would show a true synergistic activity (rather than an additive effect), a chequerboard analysis was carried out with two potent inhibitors of VIM-4, compounds 13 and 25, and meropenem (the VIM-4-producing K. pneumoniae VA-416/02 strain was used) (Table S2, Figure S2). The inhibitors showed a dose-dependent effect. Overall, compound 25 showed a better activity as it was able to restore a meropenem MIC of 2 µg/mL (16-fold potentiation) already at 8 microg/mL, while compound 13 only achieved a two-fold potentiation at this concentration. Nonetheless, the resulting average FIC index values were 0.459 and 0.347, for compounds 13 and 25 respectively, i.e. below 0.5 in both cases, indicating that the MBL inhibitors act synergistically with meropenem to potentiate its activity [START_REF] Hall | The fractional inhibitory concentration (FIC) index as a measure of synergy[END_REF][START_REF]Terminology relating to methods for the determination of susceptibility of bacteria to antimicrobial agents[END_REF].

Furthermore, since compound 25 exhibited among the most potent in vitro enzyme inhibition and meropenem potentiation on VIM-producing clinical isolates, the bactericidal activity of the combination meropenem:25 was investigated with time-kill curves. This compound alone, at 32 µg/mL, did not minimally affect bacterial growth. However, in combination with 2 µg/mL meropenem (equivalent to the susceptibility breakpoint), 25 proved able to restore the bactericidal activity of the antibiotic (reduction of >3log10 viable bacteria) against the VIM-4producing K. pneumoniae isolate VA-416/02 (starting inoculum, 5 × 10 6 CFU/mL), within 3 hours (bacterial count, 1.1 × 10 3 CFU/mL; reduction fold, ≈ 4,500).

A few compounds were tested on the same clinical isolates in the presence of other carbapenems (i.e. imipenem (IPM), doripenem (DOR) and ertapenem (ETP)) (Table S3). Compared to meropenem, some compounds also showed similar potentiating activity with IPM. This activity was lower with DOR and absent with ETP. In the latter case, this result might be explained by the lower MIC values of ETP (8-to 16-fold) compared to the other carbapenems. In this assay, compound 7 showed the strongest activity toward both clinical isolates and for both IPM and MEM. A similar experiment was performed with compound 9 (Ki = 12.0 ± 1.8 µM against NDM-1) on two NDM-1-and NDM-4-producing clinical isolates (Table S4). Compound 9

showed modest potentiating activity in the presence of DOR only (4-fold reduction of its MIC)

with the NDM-1-producing isolate. 1 and2. c Data from reference [START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]. NI: no inhibition.

Finally, a few compounds were also evaluated on a NDM-1-producing E. coli clinical isolate (SI-004M) in the presence of meropenem but none showed potentiation activity (Table S5).

This result might be due to their 10-to 100-fold lower inhibitory potency against NDM-1 compared to VIM-1 and VIM-4 and/or to insufficient accumulation into the periplasmic space.

To check the latter hypothesis, a sub-inhibitory concentration of colistin (not affecting MIC values alone), a polymyxin antibiotic with known membrane permeabilizing properties [START_REF] Mugnaini | Screen of unfocused libraries identifies compounds with direct or synergistic antibacterial activity[END_REF],

was added to the medium. In these conditions, several compounds (6, 9, 13) showed synergistic activity (Table S5). In particular, compound 13 induced a remarkable 128-fold potentiation of meropenem. However, the reasons why other compounds with higher inhibitory potency were poorly active in microbiological assays are not clear.

Overall, compounds of the present series could restore the susceptibility of MBL-producing clinical isolates to a carbapenem with higher efficiency compared to the recently published alkanoic series, supporting the interest for further medicinal chemistry efforts.

Cytotoxicity assays on mammalian cells

The potential cytotoxic activity of several compounds was evaluated using a membrane integrity assay (CytoTox 96®, Non-Radioactive Cytotoxicity Assay, Promega). They were tested for their ability to induce the lysis of HeLa cells at concentrations up to 250 µM (Table 4). Half of the tested compounds (4, 12, 25) showed IC50 values > 250 µM, indicating that they do not induce cell lysis. Others (i.e. 6, 7, 23) displayed moderate toxicity but with IC50 values greater than 100 µM.

A further evaluation of their potential cytotoxicity was performed using the RealTime-Glo MT Viability Assay, which substantially confirmed these results, showing no additional cytotoxicity upon exposure of HeLa cells to the compound (at the IC50 concentration) for up to 48 hours. Additional cytotoxicity assays were performed using the A549 human cell line (adenocarcinomic human alveolar basal epithelial cells) on selected compounds (12 and 25).

Although compound 12 showed a slightly higher cytotoxic activity after exposure to the compound for up to 48 h towards this cell line (IC50, 125 µM), compound 25 did not inhibit cell viability and proliferation (IC50, >250 µM).

Finally, the toxicity of selected compounds (6, 7, 12, 25) was also assessed on normal human cells, i.e. Peripheral Blood Mononucleated Cells (PBMC) from four donors (Table S6).

Compound 12 showed no toxicity after 24h with IC50 values above 500 µM for all donors while 7 was the most toxic with IC50 values comprised between 175 and 377 µM. Compounds 6 and 25 were not toxic toward the PBMC of two donors (IC50 > 500 µM) but lower IC50 values (about 200-300 µM) were measured for the two other samples. Overall, these compounds showed no or only moderate toxicity in this assay.

Tested in both three assays, 25 appeared to be one of the best compounds in terms of enzyme inhibition, antibiotic potentiation and selectivity.

Selectivity toward human glyoxalase II

The potential inhibitory activity of compound 6 on human glyoxalase II, a di-zinc metallohydrolase belonging to the MBL superfamily was determined. It could inhibit human glyoxalase II but moderately with an IC50 value of 52 µM, showing clear selectivity in favour of MBL enzymes.

Conclusions

Introducing an ethyl alkyl sulfide chain at position 4 of 5-substituted 1,2,4-triazole-3-thione derivatives yielded potent broad-spectrum inhibitors of clinically relevant subclass B1 MBLs with Ki values in the micromolar to submicromolar range against three VIM-type MBLs, NDM-1 and IMP-1. Kinetic and structural data largely support a competitive mechanism of inhibition.

Compared to the previously reported alkanoic series [START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF], these results represented significant progress as VIM-1, NDM-1 and IMP-1 were not or only poorly sensitive to this older series of compounds. The extended inhibition spectrum now including the three MBL enzyme subgroups was largely relying on the introduction of a phenyl moiety. However, the better activity against VIM-1 was also due to the presence of the sulfur atom. Indeed, the carba (i.e.

sulfur replaced by CH2) analogues of compounds 1 and 2 were around 6-and 2-fold less potent against this enzyme, respectively [START_REF] Brem | Structural basis of metallo-b-lactamase, serine-b-lactamase and penicillin-binding protein inhibition by cyclic boronates[END_REF]. Furthermore, it was possible to remove the carboxylic group present in most best compounds identified in previous series [START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF][START_REF] Gavara | 4-(N-Alkyl-and -acyl-amino)-1,2,4-triazole-3-thione analogs as metallo-b-lactamase inhibitors: impact of 4-linker on potency and spectrum of inhibition[END_REF][START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]. It is an interesting result as this ionizable group is generally considered to limit membrane permeation.

Replacing the sulfur of compound 6 by an oxygen [START_REF] Xiang | Rhodanine as a potent scaffold for the development of broad-spectrum metallo-β-lactamase inhibitors[END_REF] yielded less potent compounds, showing again the favorable role of this heteroatom. In addition, its position relative to the triazole ring looked critical. The role played by the sulfur might at least partially come from the nearly right angle of the thioether moiety compared to the 110° angle of an ether or the corresponding alkyl group.

Three crystal structures of VIM-2 complexes were obtained and showed the same binding mode of the triazole-thione moiety in the di-zinc active site of the enzyme, when compared to previously reported structures. The positions of compounds 8, 10 and 14 are largely superimposable, including the flexible thioether chain lying on a hydrophobic region of the VIM-2 binding site, although the phenyl ring present at its extremity was not visible in the case of 10 and 14. Interestingly, the same phenyl ring in compound 8 showed a stable position, thanks to its fluorine substituent, which establishes stabilizing interactions, including with an arginine guanidinium group. This result will be taken into account in the design of future molecules.

Microbiological assays showed that many compounds of this series were able to significantly potentiate the activity of meropenem toward VIM-producing clinical isolates of K. pneumoniae with a reduction of the antibiotic MIC up to 16-fold. Compared to previous series [START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF][START_REF] Gavara | 4-(N-Alkyl-and -acyl-amino)-1,2,4-triazole-3-thione analogs as metallo-b-lactamase inhibitors: impact of 4-linker on potency and spectrum of inhibition[END_REF][START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF],

these inhibitors showed a better ability to accumulate in the periplasm at concentrations compatible with efficient MBL inhibition in the bacterial cell. These favourable results might be due to their higher hydrophobicity compared to best inhibitors of previous series, which often contained a carboxylic group.

Finally, cytotoxicity experiments and the study of a potential off-target (i.e. glyoxalase II) afforded quite favourable results.

These promising results support the interest to continue the development of 1,2,4-triazole-3thione-based compounds. Further modification at position 4 is ongoing to obtain compounds characterized with both better inhibitory activity against NDM-1 and better synergistic antibacterial activity.

Experiment section

Microbiological assays

The minimum inhibitory concentrations (MICs) of carbapenems (meropenem, imipenem, ertapenem and doripenem) were determined in triplicate using Mueller-Hinton broth (MHB) and a bacterial inoculum of 5 × 10 4 CFU/well, as recommended by the CLSI [START_REF]Methods for dilution antimicrobial susceptibility tests for bacteria that grow aerobically[END_REF], in both the absence and presence of a fixed concentration (32 µg/mL) of an inhibitor. The antibiotics and compounds were diluted from a stock solution (1.2 mg/mL meropenem in sterile milliQ water;

3.2 mg/mL inhibitor in DMSO) in MHB. For assessing the activity of the combination, the inhibitor was added at 32 µg/mL to the wells immediately prior to the addition of the antibiotic diluted in MHB containing 32 µg/mL inhibitor and the two-fold serial dilutions. Multidrug resistant VIM-1-or VIM-4-producing K. pneumoniae clinical isolates present in our collection (7023 and VA-416/02, respectively) [START_REF] Cagnacci | Bloodstream infections caused by multidrug-resistant Klebsiella pneumoniae producing the carbapenem-hydrolysing VIM-1 metallo-b-lactamase: first Italian outbreak[END_REF][START_REF] Luzzaro | Emergence in Klebsiella pneumoniae and Enterobacter cloacae clinical isolates of the VIM-4 metallo-b-lactamase encoded by a conjugative plasmid[END_REF] were used and added extemporaneously to each well, prior to incubation of the plates at 35 °C for 24 h. Negative and positive growth controls were also prepared. The residual concentration of DMSO in the assay did not exceed one percent. Results were read following visual inspection of the plates. A multidrug resistant NDM-1-producing E. coli clinical isolate (SI-004M) was also used. In this case, the experiment was also performed in the absence and the presence of a sub-inhibitory concentration of colistin (0.12 µg/mL) [START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]. Chequerboard analysis was carried out with selected inhibitors and meropenem using the VIM-4-producing K. pneumoniae clinical isolate VA-416/02, as previously described [START_REF] Hall | The fractional inhibitory concentration (FIC) index as a measure of synergy[END_REF][START_REF]Terminology relating to methods for the determination of susceptibility of bacteria to antimicrobial agents[END_REF]. Time-dependent bacterial killing of meropenem/inhibitor combination was investigated using established methods [START_REF]Terminology relating to methods for the determination of susceptibility of bacteria to antimicrobial agents[END_REF]. Briefly, a culture medium containing a starting inoculum of 5.0 × 10 6 CFU/mL of strain VA-416/02 was incubated aerobically at 35 °C under orbital agitation (200 rpm) in Mueller-Hinton broth, in the absence and presence of 2 µg/mL meropenem and 32 µg/mL inhibitor. Bacterial count (expressed in CFU/mL) in the control and antibiotic-containing media was determined every hour for up to 6 h of incubation, by serial 10-fold dilution and direct plating of 0.1 mL of the sample on Mueller-Hinton Agar medium (without antibiotic), incubated for 24 h at 35 °C.

Inhibition of human glyoxalase II (hGloII)

The assay was performed as previously described [START_REF] Gavara | 4-Amino-1,2,4-triazole-3-thionederived Schiff bases as metallo-b-lactamase inhibitors[END_REF]. Briefly, the activity of recombinant hGloII [START_REF] Akoachere | Characterization of the glyoxalases of the malarial parasite Plasmodium falciparum and comparison with their human counterparts[END_REF] was measured by following the disappearance of its substrate S-Dlactoylglutathione (Sigma, e240nm = 3.1 mM -1 cm -1 ) at 25 °C in 100 mM 4-morpholinopropane sulfonate (MOPS) buffer, pH 7.2 and with a Thermo Evolution spectrophotometer. The inhibitor, dissolved in DMSO was added to the assay mixture containing the substrate and the reaction was started with enzyme (5-25 nM hGloII). All experiments were carried out in duplicate.

Cell toxicity

The potential cytotoxic activity of compounds was first evaluated using the commercially available integrity assay (CytoTox 96® non-radioactive cytotoxicity assay, Promega). The were then added to the wells containing the cells, in duplicate. The final concentrations of compounds was ranging from 500 µM to 7.8 µM. After 24 hours, cells were analyzed by cytometry using a Novocyte Flow Cytometer. Live cells were identified using a FSC/SSC gating. IC50 values were calculated using GraphPad Prims version 9 (Table S6).

X-ray crystallography section

VIM-2 was expressed and purified following established protocols [START_REF] Docquier | On functional and structural heterogeneity of VIM-type metallo-b-lactamases[END_REF][START_REF] Garcia-Saez | The three-dimensional structure of VIM-2, a Zn-beta-lactamase from Pseudomonas aeruginosa in its reduced and oxidised form[END_REF]. Crystals of the enzyme were grown within a few days using the sitting drop vapor diffusion method [START_REF] Benvenuti | Crystallization of soluble proteins in vapor diffusion for X-ray crystallography[END_REF] at room temperature, as described elsewhere [START_REF] Docquier | On functional and structural heterogeneity of VIM-type metallo-b-lactamases[END_REF][START_REF] Garcia-Saez | The three-dimensional structure of VIM-2, a Zn-beta-lactamase from Pseudomonas aeruginosa in its reduced and oxidised form[END_REF]. Soaking solutions for compounds 8, 10, and 14, formerly dissolved in dimethyl sulfoxide (DMSO), were prepared by dilution in PEG-400 using a 1:9 molar ratio (final concentration 5 mM). Each enzyme-inhibitor complex was obtained by adding 1 µL of soaking solution to the crystallization drop containing preformed crystals and allowing compound diffusion for 30 minutes at room temperature. Crystals were then frozen in liquid nitrogen. Diffraction data were collected at 100 K using synchrotron radiation at the Diamond Light Source (DLS, UK) beamline I04 equipped with an Eiger2 XE 16M detector. Reflections were integrated using XDS [60] and scaled with SCALA [START_REF] Evans | An introduction to data reduction: space-group determination, scaling and intensity statistics[END_REF] from the CCP4 suite [START_REF] Wynn | Overview of the CCP4 suite and current developments[END_REF]. The structures were solved by molecular replacement using MOLREP [START_REF] Vagin | Molecular replacement with MOLREP[END_REF] and the structure of VIM-2 (PDB code 6SP7 [START_REF] Liu | Discovery of Taniborbactam (VNRX-5133): a broad spectrum serine-and metallo-b-lactamase inhibitor for carbapenem-resistant bacterial infections[END_REF]), as search model (excluding non-protein atoms and water molecules). The three structures were refined using REFMAC5 from the CCP4 suite [START_REF] Murshudov | REFMAC5 for the refinement of macromolecular crystal structures[END_REF]. The molecular graphic software Coot [START_REF] Emsley | Features and development of Coot[END_REF] was used for manual rebuilding and modelling of missing atoms in the electron density and to add solvent molecules. In each structure, the inspection of the Fourier difference map clearly evidenced the presence of the inhibitor inside the catalytic cavity that was modelled accordingly. The occupancy of the exogenous ligands was adjusted and refined to values resulting in atomic displacement parameters close to those of neighboring protein atoms in fully occupied sites. The final models were inspected manually and checked with Coot [START_REF] Emsley | Features and development of Coot[END_REF] and PROCHECK [START_REF] Laskowski | PROCHECK: a program to check the stereochemical quality of protein structures[END_REF]. Structural figures were generated using the molecular graphic software CCP4mg [START_REF] Potterton | Developments in the CCP4 molecular-graphics project[END_REF]. Data collection, processing, and refinement statistics are summarized in Table S1. Final coordinates and structure factors were deposited in the Protein Data Bank (PDB) under the codes 7OVF (VIM-2/8), 7OVE (VIM-2/10), and 7OVH (VIM-2/14).

Equilibrium dialysis and native state electrospray ionization mass spectrometry

These studies have been performed on compound 6 following published procedures [START_REF] Thomas | Probing the mechanism of inhibition for various inhibitors of metallo-b-lactamases VIM-2 and NDM-1[END_REF]. The equilibrium dialysis experiment is briefly described in the Supplementary Material part.

1, 2 , 4 -

 24 Triazole-3-thione compounds with a 4-ethyl alkyl/aryl sulfide substituent are broad-spectrum metallo-b-lactamase inhibitors with re-sensitization activity Alice Legru, Federica Verdirosa, Jean-François Hernandez, Giusi Tassone, Filomena Sannio, Manuela Benvenuti, Pierre-Alexis Conde, Guillaume Bossis, Caitlyn A Thomas, Michael W Crowder, et al. To cite this version: Alice Legru, Federica Verdirosa, Jean-François Hernandez, Giusi Tassone, Filomena Sannio, et al.. 1,2,4-Triazole-3-thione compounds with a 4-ethyl alkyl/aryl sulfide substituent are broad-spectrum metallo-b-lactamase inhibitors with re-sensitization activity. European Journal of Medicinal Chemistry, 2021, 226, pp.113873. 10.1016/j.ejmech.2021.113873. hal-03719307

  enzymes (SBLs) mainly represented by the Klebsiella pneumoniae carbapenemases (class A KPC-type enzymes) and the OXA-type class D enzymes such as OXA-48 and OXA-23. Class B β-lactamases have a different catalytic mechanism as they need one or two Zn ion(s) for catalysis, and are further classified into three sub-classes (B1, B2, B3) of so-called metallo-βlactamases (MBLs) [8,9]. Clinically relevant MBLs include the subclass B1 IMP-(imipenemase), VIM-(Verona integron-borne MBL) and NDM-type (New Delhi MBL)

Figure 2 .

 2 Figure 2. Dixon plot analysis of VIM-1 inhibition by compound 25. Imipenem was used as the reporter substrate (VIM-2 Km value, 9 µM). Inhibition data were obtained at 100, 300 and 1000 µM of substrate (red, blue and green, respectively) and in the presence of inhibitor concentrations ranging 1-5 µM.

Figure 3 .

 3 Figure 3. Active-site view of VIM-2 (steel blue cartoon and carbon atoms; residues in sticks) in complex with A) 8 (in sticks, magenta carbons, PDB code 7OVF), B) 10 (in stick, green carbons, PDB code 7OVE), C) 14 (in stick, cyan carbons, PDB code 7OVH). In all figures, Zn ions and water molecules are displayed as grey and red spheres (arbitrary radius), respectively. Hydrogen and coordination bonds are represented as red and black dashed lines. Oxygen atoms are colored red, nitrogen blue, sulfur yellow, and fluorine grey.

Figure 4 .

 4 Figure 4. Active site view of the superimposition between the structures of VIM-2 (steel blue cartoon and carbons, residues in sticks) in complex with 8 (in sticks, magenta carbons; residues in sticks, light magenta carbons) and the Schiff base 31 (PDB code 6YRP, numbering from reference [41]; 31 and residues in sticks, orange and light orange carbons, respectively).

  compounds were tested for their ability to induce the lysis of HeLa cells by measuring the release of lactate dehydrogenase (LDH) after incubating the HeLa cell cultures (20,000 cells/well) for 24h (37 °C, 5% CO2) in DMEM (Dulbecco's Modified Eagle Medium) supplemented with 10% fetal bovine serum, 4.5 mg/mL glucose and 2 mM L-glutamine in the absence and presence of varying concentrations of the compounds (up to 250 µM). Further controls included samples containing the medium only or in which cell lysis was induced by the addition of 9% Triton X-100 (maximum LDH release control). The percentage of cytotoxicity was computed as 100 x (sample LDH release)/(maximum LDH release). The variation of the percentage of cytotoxicity allowed to compute an IC50 value (compound concentration inducing 50% cytoxicity).The cytotoxicity of the compounds was also calculated by measuring the number of viable cells in culture with respect to the control culture (cells treated with DMSO only) using the RealTime-Glo™ MT Cell Viability Assay, in the absence and presence of varying concentrations of the inhibitors. The assay is a nonlytic, homogeneous, bioluminescent method to measure cell viability/proliferation in real time using NanoLuc® luciferase and a cellpermeant prosubstrate (MT Cell Viability Substrate). The potential cytotoxicity was tested by incubating the compounds with Hela cells (1500 cells/well) for up to 48 h in DMEM. Both HeLa and A549 (adenocarcinomic human alveolar basal epithelial cells) human cell lines were used in these experiments.The cytotoxicity of selected compounds was also assessed on normal human cells, Peripheral Blood Mononucleated Cells (PBMC). PBMC were prepared from four buffy coats from individual donors of the « Etablissement Francais du Sang » (EFS). Leukocytes were purified by density-based centrifugation using Histopaque 1077 (Sigma-Aldrich) and frozen. After thawing, PBMC were resuspended at 1.10e6/mL in RPMI medium supplemented with 10% FBS and 50 µL distributed in 96 well plates. The compounds, resuspended at 20 mM in DMSO, were diluted at 1 mM in RPMI before serial dilution in RPMI. 50 µL of the diluted compounds

2. Results and discussion

	2.1. Synthesis
	Scheme 1. Synthesis of 1,2,4-triazole-3-thione derivatives. Reagents and conditions: (a) H2N-R 2 treated with DPT,
	Na2CO3, DMF, 55 °C, 3h; then R 1 -CONHNH2, DMF, 55 °C, 3h; (b) aqueous KOH or NaHCO3, 100 °C, 3h.

Table 1 .

 1 Inhibitory activity of 1,2,4-triazole-3-thione analogues 1-22 against various MBLs.

				R		R 2
					N
				N	H N	S
		R 2		VIM-1	VIM-2	VIM-4	NDM-1	IMP-1
	1 b	S	CO 2 H	2.36 ±	0.81 ±	0.71 ±	(40%)	NI
				0.14	0.04	0.06
	2	S	CO 2 H	1.99 ±	1.91 ±	1.98 ±	(59%)	(67%)
				0.18	0.09	0.12
	3			1.65 ±	0.19 ±	0.21 ±	(40%)	(30%)
		S		0.16	0.01	0.02
		CO 2 H
	4	HO 2 C		0.48 ±	0.60 ±	0.22 ±	6.0 ± 1.0	35.0 ±
		S		0.06	0.04	0.02		11.0
	5 a			1.39 ±	0.37 ±	0.21 ±	20.3 ± 1.7	(56%)
				0.13	0.02	0.01
	6			0.21 ±	0.24 ±	0.31 ±	22.3 ± 1.9 19.6 ± 2.5
		S		0.02	0.36	0.07
	7			0.59 ±	0.28 ±	0.32 ±	11.9 ± 0.4 12.1 ± 1.0
		S		0.03	0.01	0.02
			F

a Cpd Structure Ki (µM) or (% inhibition at 100 µM)

a For all compounds, R = H, excepted compound 5 for which R = phenyl. All kinetic assays were performed in triplicate. NI: no inhibition (< 30% inhibition at 100 µM). b From reference

[START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]

. c Apparent Ki value, not determined due to non linear v0/vi vs [I] plot.

Table 2 .

 2 Inhibitory activity of 1,2,4-triazole-3-thione analogues 23-30 with R 2 = ethyl benzyl sulfide against various MBLs. a All kinetic assays were performed in triplicate. NI: no inhibition (< 30% inhibition at 100 µM or < 15% inhibition at 25 µM). ND: not determined. b Approximate Ki value, not determined due to non-linear v0/vi vs [I] plot. c Tested at 25 µM due to poor solubility in HEPES 50 mM.

		R 1	S
			N
		N
			N H	S
	Cpd	Structure		Ki (µM) or (% inhibition at 100 µM)
		R 1	VIM-1	VIM-2	VIM-4	NDM-1	IMP-1
			0.40 ±	0.80 ±	0.50 ±	13.0 ± 1.0 44.0 ± 8.0
			0.04	0.09	0.04
		OMe	0.18 ±	1.65 ±	0.60 ±	(46%)	(63%)
			0.02	0.16	0.10
		HO
		N	0.23 ±	0.34 ±	0.25 ±	(75%)	9.04 ±
			0.01	0.01	0.01	28 b	1.53
			ND	NI	ND	NI	(35%)
			NI c		NI c	0.89 ±	NI	(21%) c
						0.22
			NI c		NI	NI c	NI	(60%)
		O	2.24 ±	NI	1.04 ±	NI	(60%)
			0.58		0.18
			NI c		NI	(23%) c	NI	(70%)

a

Table 3 .

 3 Antibacterial synergistic activity of compounds on VIM-1-and VIM-4-producing K. pneumoniae clinical isolates with meropenem determined by the broth microdilution method.

	Cpd
	(32
	µg/mL)

Meropenem MIC a (µg/mL) and Ki (µM) values of selected inhibitors

	25	2	0.23 ± 0.01	1	0.25 ± 0.01
	27	16	NI	16	0.89 ± 0.22
		K. pneumoniae 7023	K. pneumoniae VA 416/02
		(blaVIM-1 + )	(blaVIM-4 + )
		MEM MIC	Ki (VIM-1) b	MEM MIC	Ki (VIM-4) b
	None	16	-	16	-
	1 c		2.36 ± 0.14	4	0.71 ± 0.06
	2		1.99 ± 0.18	1	1.98 ± 0.12
	3		1.65 ± 0.16	2	0.21 ± 0.02
	4		0.48 ± 0.06	4	0.22 ± 0.02
	5		1.39 ± 0.13	2	0.21 ± 0.01
	6		0.21 ± 0.02	4	0.31 ± 0.07
	7		0.59 ± 0.03	2	0.32 ± 0.02
	8		2.22 ± 0.16	2	1.11 ± 0.04
	9		1.33 ± 0.10	1	1.18 ± 0.03
	10		0.480 ± 0.004	1	0.56 ± 0.07
	11		0.43 ± 0.02	1	0.88 ± 0.03
	12		0.58 ± 0.03	4	0.25 ± 0.02
	13		0.46 ± 0.02	1	0.43 ± 0.03
	14		1.26 ± 0.07	1	0.54 ± 0.07
	15		0.47 ± 0.04	2	0.41 ± 0.02
	16		0.48 ± 0.05	16	0.25 ± 0.04
	17		2.17 ± 0.15	2	2.95 ± 0.22
	21		2.98 ± 0.25	1	4.85 ± 0.58
	22		1.02 ± 0.10	2	2.06 ± 0.19
	23		0.40 ± 0.04	2	0.50 ± 0.04
	24		0.18 ± 0.02	2	0.60 ± 0.10

a MEM, meropenem. b From Tables

Table 4 .

 4 Cytotoxic activity against HeLa cells.

	Cpd	HeLa cells IC50 (µM)	Cpd	HeLa cells IC50 (µM)
	4	> 250	12	> 250
	6	152 ± 16	23	121 ± 10
	7	165 ± 29	25	> 250

Acknowledgements

Part of this work was supported by Agence Nationale de la Recherche (ANR-14-CE16-0028-01), the Deutsche Forschungsgemeinschaft (BE1540/15-2 within SPP 1710 to K.B.). We thank Mr Pierre Sanchez for mass spectrometry analyses. We also thank the Diamond Light Source for providing us beamtime (BAG proposal MX21741) and the staff of beamline I04 for their assistance with crystal testing and data collection. The Dipartimento di Biotecnologie Mediche and the Dipartimento di Biotecnologie, Chimica e Farmacia, University of Siena, were both awarded "Department of Excellence 2018-2022" by the Italian Ministry of Education, University and Research (MIUR, L. 232/2016).

Mononucleated Cells; RPMI, Roswell Park Memorial Institute medium; SBL, serine-b-lactamase; TFA, trifluoroacetic acid; VIM, Verona Integron-borne Metallo-b-lactamase.

Chemistry section

The compound synthesis was adapted from Deprez-Poulain et al. [START_REF] Deprez-Poulain | Convenient synthesis of 4H-1,2,4-triazole-3-thiols using di-2-pyridylthionocarbamate[END_REF] and performed as previously described [START_REF] Gavara | 4-Alkyl-1,2,4-triazole-3-thione analogues as metallo-blactamase inhibitors[END_REF]. General procedures for the preparation of 1,2,4-triazole-3-thiones as well as of the hydrazide and amine precursors are presented in the Supplementary Material section. The physico-chemical properties of final compounds are also described in the Supplementary Material section. Their purity was determined to be ≥95% by 1 H NMR and reverse phase HPLC.

Biology section 4.2.1. Metallo-b-Lactamase inhibition assays 4.2.1.1 VIM-type enzymes, NDM-1 and IMP-1

The inhibition potency of the compounds has been assessed with a reporter substrate method and specifically by measuring the rate of hydrolysis of 150 µM imipenem or 150 µM meropenem at 30 °C in 50 mM HEPES buffer (pH 7.5) in the absence and presence of several concentrations of the inhibitor (final concentration, 0.5-1,000 µM). Final DMSO concentration in the assays was 0.5%.

The reaction rate was measured as the variation of absorbance observed upon substrate hydrolysis in a UV-Vis spectrophotometer or microplate reader at a wavelength of 300 nm (imipenem, meropenem) and in the presence of a purified MBL enzyme (VIM-1, VIM-2, VIM-4, NDM-1, IMP-1) at a final concentration ranging from 1-70 nM). In some cases (as indicated in Tables), a 10 min pre-incubation of enzyme and compound was done.

The inhibition constants (Ki) were determined on the basis of a model of competitive inhibition by analyzing the dependence of the ratio v0/vi (v0, hydrolysis velocity in the absence of inhibitor; vi, hydrolysis velocity in the presence of inhibitor) as a function of [I] as already described [START_REF] Docquier | On functional and structural heterogeneity of VIM-type metallo-b-lactamases[END_REF].

The slope of the plot of v0/vi vs [I], which corresponds to Km S /( Km S + [S])Ki (where Km S is the Km value of the reporter substrate and [S] its concentration in the reaction mixture) and allowed the calculation of the Ki value. Alternatively, a Dixon plot analysis was carried out by measuring the initial hydrolysis rates in the presence of variable concentrations of inhibitor and substrate.

This allowed Ki values to be determined and supported the hypothesis that the various compounds behaved as competitive inhibitors of the various tested enzymes. All assays were performed in triplicate.

Declaration of competing interest

The authors declare that they have no competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Appendix A. Supplementary data

Supplementary data can be found online at… General synthetic procedures (Schemes S1 and S2). Characterization of final compounds. Xray crystallography (Table S1 and Figure S1). Figure S2 and Tables S2-S5 showing results of microbiological assays. Experimental details for equilibrium dialysis and native state ESI-MS studies (Figures S3 andS4). Cytotoxicity toward PBMC (Table S6). 1 H and 13 C NMR spectra and chromatographic profile of final compounds. X-ray structures of VIM-2/inhibitor complexes: PDB codes 7OVF (cpd 8), 7OVE (cpd 10), 7OVH (cpd 14): Authors will release the atomic coordinates and experimental data upon article publication.


Keywords: data replication, large-scale, database systems réplication, large-échelle, base de données

Introduction

Non-trivial consistency problems e.g. file systems, collaborative environments, and databases. are the major challenge of large-scale systems. Recently some architectures have emerged to scale file systems up to thousands of nodes [START_REF] Kubiatowicz | Oceanstore: An architecture for global-scale persistent storage[END_REF][START_REF] Muthitacharoen | Ivy: A read/write peer-to-peer file system[END_REF][START_REF] Busca | Pastis: A highly-scalable multi-user peer-to-peer file system[END_REF], but no practical solution exists for database systems.

At the cluster level protocols based on group communication primitives [START_REF] Camargos | Sprint: a middleware for high-performance transaction processing[END_REF][START_REF] Kemme | Don't be lazy, be consistent: Postgres-r, a new way to implement database replication[END_REF][START_REF] Pacitti | Preventive replication in a database cluster[END_REF] are the most promising solutions to replicate database systems [22] . In this article we extend the group communication approach to large-scale systems.

Highlights of our protocol:

Replicas do not re-execute transactions, but apply update values only.

We do not compute a total order over of operations. Instead transactions are partially ordered. Two transactions are ordered only over the data where they conflict.

For every transaction T we maintain the graph of T 's dependencies. T commits locally when T is transitively closed in this graph.

The outline of the paper is the following. Section 2 introduces our model and assumptions. Section 3 presents our algorithm. We conclude in Section 4 after a survey of related work. An appendix follows containing a proof of correctness.

System model and assumptions

We consider a finite set of asynchronous processes or sites Π, forming a distributed system. Sites may fail by crashing, and links between sites are asynchronous but reliable. Each site holds a database that we model as some finite set of data items. We left unspecified the granularity of a data item. In the relational model, it can be a column, a table, or even a whole relational database. Given a data item x, the replicas of x, noted replicas(x), are the subset of Π whose databases contain x.

We base our algorithm on the three following primitives: 1Uniform Reliable Multicast takes as input a unique message m and a single group of sites g ⊆ Π . Uniform reliable multicast consists of the two primitives R-multicast(m) and R-deliver(m). With Uniform Reliable Multicast, all sites in g have the following guarantees:

-Uniform Integrity: For every message m, every site in g performs R-deliver(m) at most once, and only if some site performed R-multicast(m) previously.

-Validity: if a correct site in g performs R-multicast(m) then it eventually performs R-deliver(m).

lock held lock requested

R W IW R 1 0 0 W 0 0 0 IW 0 0 1 Table 1: Lock conflict table
-Uniform Agreement: if a site in g performs R-deliver(m), then every correct sites in g eventually performs R-deliver(m).

Uniform Reliable Multicast is solvable in an asynchronous systems with reliable links and crash-prone sites.

Uniform Total Order Multicast takes as input a unique message m and a single group of sites g. Uniform Total Order Multicast consists of the two primitives TO-multicast(m) and TO-deliver(m). This communication primitive ensures Uniform Integrity, Validity, Uniform Agreement and Uniform Total Order in g:

-Uniform Total Order: if a site in g performs TO-deliver(m) and TO-deliver(m ′ ) in this order, then every site in g that performs TO-deliver(m ′ ) has performed previously TO-deliver(m).

Eventual Weak Leader Service Given a group of sites g, a site i ∈ g may call function WLeader (g). WLeader (g) returns a weak leader of g :

-WLeader (g) ∈ g.

-Let ρ be a run of Π such that a non-empty subset c of g is correct in ρ. It exists a site i ∈ c and a time t such that for any calls of WLeader (g) on i after t, WLeader (g) returns i.

This service is strictly weaker than the classical eventual leader service Ω [START_REF] Raynal | Eventual leader service in unreliable asynchronous systems: Why? how? In NCA[END_REF], since we do not require that every correct site eventually outputs the same leader. An algorithm that returns to every process itself, trivially implements the Eventual Weak Leader Service.

In the following we make two assumptions: during any run, (A1) for any data item x, at least one replica of x is correct, and (A2) Uniform Total Order Multicast is solvable in replicas(x).

Operations and locks

Clients of the system (not modeled), access data items using read and write operations. Each operation is uniquely identified, and accesses a single data item. A read operation is INRIA a singleton: the data item read, a write operation is a couple: the data item written, and the update value.

When an operation accesses a data item on a site, it takes a lock. We consider the three following types of locks: read lock (R), write lock (W), and intention to write lock (IW).Table 1 illustrates how locks conflict with each other; when an operation requests a lock to access a data item, if the lock is already taken and cannot be shared, the request is enqueued in a FIFO queue. In Table 1, 0 means that the request is enqueued, and 1 that the lock is granted.

Given an operation o, we note: We say that two operations o and o ′ conflict if they access the same data item and one of them is a write:

item(o),
conflict (o, o ′ ) △ = item(o) = item(o ′ ) isWrite(o) ∨ isWrite(o ′ )

Transactions

Clients group their operations into transactions. A transaction is a uniquely identified set of read and write operations. Once a site i grants a lock to a transaction T , T holds it until i commits T , i aborts T , or we explicitly say that this lock is released.

The algorithm

As replicas execute transactions, it creates precedence constraints between conflicting transactions. Serializability theory tell us that this relation must be acyclic [2].

One solution to this problem, is given a transaction T , (i) to execute T on every replicas of T , (ii) to compute the transitive closure of the precedence constraints linking T to concurrent conflicting transactions, and (iii) if a cycle appears, to abort at least one the transactions involved in this cycle.

Unfortunately as the number of replicas grows, sites may crash, and the network may experience congestion. Consequently to compute (ii) the replicas of T need to agree upon the set of concurrent transactions accessing item(T ).

Our solution is to use a TO-multicast protocol per data item.

Overview

To ease our presentation we consider in the following that a transaction executes initially on a single site. Section 3.9 generalizes our approach to the case where a transaction initially executes on more than one site. We structure our algorithm in five phases:

In the initial execution phase, a transaction T executes at some site i.

In the submission phase, i transmits T to replicas(T ).

In the certification phase, a site j aborts T if T has read an outdated value. If T is not aborted, j computes all the precedence constraints linking T to transactions previously received at site j.

In the closure phase, j completes its knowledge about precedence constraints linking T to others transactions.

Once T is closed at site j, the commitment phase takes place. j decides locally whether to commit or abort T . This decision is deterministic, and identical on every site replicating a data item written by T .

Initial execution phase

A site i executes a transaction T coming from a client according to the two-phases locking rule [2], but without applying write operations2 . When site T reaches a commit statement, it is not committed, instead i releases T 's read locks, converts T 's write locks into intention to write locks, computes T 's update values, and then proceeds to the submission phase.

Submission phase

In this phase i R-multicasts T to replicas(T ). When a site j receives T , j marks all T 's operations as pending using variable pending. Then if it exists an operation o ∈ pending, such that j = WLeader (replicas (o)), j TO-multicasts o to replicas(o). 3

Certification phase

When a site i TO-delivers an operation o for the first time4 ,i removes o from pending, i certifies o.

To certify o, i considers any preceding write operations that conflicts with o. We say that a conflicting operation

o ′ precedes o at site i, o ′ → i o, if i TO-delivers o ′ then i TO-delivers o: o ′ → i o △ = TO-deliver i (o ′ ) ≺ TO-deliver i (o) conflict (o ′ , o)
Where given two events e and e ′ , e ≺ e ′ is the relation e happens-before e ′ , and TO-deliver i (o ′ ) is the event: "site i TO-delivers operation o ′ ".

If o is a read, we check that o did not read an outdated value. It happens when o executes concurrently to a conflicting write operation o ′ that is now committed. Let committed i be the set of transactions committed at site i, the read operation o aborts, if it exists 1); otherwise it means that trans(o ′ ) is still executing at site i, and function forceWriteLock (o) aborts it. 5

an operation o ′ such that o ′ → i o ∧ trans(o ′ ) trans(o) ∧ trans(o ′ ) ∈ committed i ,

Precedence graph

Our algorithm decides to commit or abort transactions, according to a precedence graph. A precedence graph G is a directed graph where each node is a transaction T , and each directed edge T →T ′ , models a precedence constraint between an operation of T , and a write operation of T ′ :

T →T ′ △ = ∃(o, o ′ ) ∈ T × T ′ , ∃i ∈ Π, o ′ → i o
A precedence graph contains also for each vertex T a flag indicating whether T is aborted or not: isAborted (T, G), and the subset of T 's operations: op(T, G), which contribute to the relations linking T to others transactions in G.

Given a precedence graph G, we note G.V its vertices set, and G.E its edges set. Let G and G ′ be two precedence graphs, the union between G and G ′ , G ∪ G ′ , is such that:

(G ∪ G ′ ).V = G.V ∪ G ′ .V, (G ∪ G ′ ).E = G.E ∪ G ′ .E, ∀T ∈ (G ∪ G ′ ).V, isAborted (T, (G ∪ G ′ )) = isAborted (T, G) ∨ isAborted (T, G ′ ). ∀T ∈ (G ∪ G ′ ).V, op(T, (G ∪ G ′ )) = op(T, G) ∪ op(T, G ′ ).
Algorithm 1 decide(T, G), code for site i

1: variable G ′ := (Ø, Ø)
⊲ a directed graph 2:

3: for all C ⊆ cycles(G) do 4:

if ∀T ∈ C, ¬isAborted (T, G) then 5:

G ′ := G ′ ∪ C 6: if T ∈ breakCycles (G ′ ) then 7:
return false 8: else 9:

return true We say that G is a subset of G ′ , noted G ⊆ G ′ , if: G.V ⊆ G ′ .V ∧ G.E ⊆ G ′ .E, ∀T ∈ G.V, isAborted (T, G) ⇒ isAborted (T, G ′ ), ∀T ∈ G.V, op(T, G) ⊆ op(T, G ′ ).
Let G be a precedence graph, in(T, G) (respectively out(T, G)) is the restriction of G.V to the subset of vertices formed by T and its incoming (resp. outgoing) neighbors. The predecessors of T in G: pred (T, G), is the precedence graph representing the transitive closure of the dual of the relation G.E on {T }.

Deciding

Each site i stores its own precedence graph G i , and decides locally to commit or abort a transaction according to it. More precisely i decides according to the graph pred (T, G i ). For any cycle C in the set of cycles in pred (T, G i ) : cycles(pred (T, G i )). i must abort at least one transaction in C. This decision is deterministic, and i tries to minimize the number of transactions aborted.

Formally speaking i solves the minimum feedback vertex set problem over the union of all cycles in pred (T, G i ) containing only non-aborted transactions The minimum feedback vertex set problem is an NP-complete optimization problem, and the literature about this problem is vast [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. We consequently postulate the existence of an heuristic: breakCycles(). breakCycles() takes as input a directed graph G, and returns a vertex set S such that G \ S is acyclic. Now considering a transaction T ∈ G i such that G = pred (T, G i ), Algorithm 1 returns false if i aborts T , or true otherwise.

Closure phase

In our model sites replicate data partially, and consequently maintain an incomplete view of the precedence constraints linking transactions in the system. Consequently they need to complete their view by exchanging parts of their graphs. This is our closure phase:

INRIA

When i TO-delivers an operation o ∈ T , i adds T to its precedence graph, and adds o to op(T, G i ). Then i sends pred (T, G i ) to replicas(out (T, G i )) (line 29).

When i receives a precedence graph G, if G ⊆ G i , for every transaction T in G i , such that pred (T, G) ⊆ pred (T, G i ), i sends pred (T, G ∪ G i ) to replicas(out (T, G i )). Then i merges G to G i (lines 31 to 35).
Once i knows all the precedence constraints linking T to others transactions, we say that T is closed at site i. Formally T is closed at site i when the following fixed-point equation is true at site i:

closed (T, G i ) = op(T, G) = T ∀T ′ ∈ in(T, G i ).V, closed (T ′ , G i )
Our closure phase ensures that during every run ρ, for every correct site i, and every transaction T which is eventually in G i , T is eventually closed at site i.

Commitment phase

If T is a read-only transaction: wo(T ) = Ø, i commits T as soon as T is executed (line 9).

If T is an update, i waits that T is closed and holds all its IW locks: function holdIWLocks () (line 35). Once these two conditions hold, i computes decide(T, pred (T, G i )). If this call returns true, i commits T : for each write operation o ∈ wo(T ), with i ∈ replicas (o), i considers any write operation

o ′ such that T →trans(o ′ ) ∈ G i ∧ conflict (o, o ′ ). If trans(o ′
) is already committed at site i, i does nothing; otherwise i applies o to its database.

Algorithm 2 describes our algorithm. This protocol provides serializability for partially replicated database systems: any run of this protocol is equivalent to a run on a single site [2]. The proof of correctness appears in Appendix.

Initial execution on more than one site

When initial execution phase does not take place on a single site we compute the read-from dependencies. More precisely when a site i receives a read o accessing a data item it does not replicate, i sends o to some replica j ∈ replicas(o). Upon reception j executes o. At the end of execution j sends back to i the transitive closure containing read-from dependencies and starting from T .

Once i has executed locally or remotely all the read operations in T , i checks if the resulting graph contains cycles in which T is involved. If this is the case, T will be aborted, and instead of submitting it, i re-executes at least one of T 's read operations Otherwise i computes the write set and the update values, and sends T with its read-from dependencies by Uniform Reliable Multicast. The dependencies are merged to precedence graph when a site receives an operation by Total Order Multicast. The rest of the algorithm remains the same. Gi.V := Gi.V ∪ {T }

Performance analysis

We consider Paxos [START_REF] Lamport | Fast paxos[END_REF] as a solution to Uniform Total Order Multicast. Since precedence constraints in a cycle are not causally related, Algorithm 2 achieves a message delay of 5: 2 for Uniform Reliable Multicast, and 3 for Uniform Total Order Multicast. It reduces to 4, if in each replica group the leader of Paxos is also the weak leader of g.

Let o be the number of operations per transaction, and d be the replication degree, the message complexity of Algorithm 2 is 5od + (od) 2 : 2od for Uniform Reliable Multicast, o Uniform Total Order Multicasts, each costing 2d messages, and od replicas execute line 29, each site sending od messages. Again, if in each replica group, the leader of Paxos is also the weak leader of g, the message complexity of our protocol reduces to 4od + (od) 2 4 Concluding remarks

Related work

Gray et al. [START_REF] Gray | The dangers of replication and a solution[END_REF] prove that scale traditional eager and lazy replications does not scale: the deadlock rate increase as the cube of the number of sites, and the reconciliation rate increases as the square. Wiesmann and Schiper confirm practically this result [22]. Fritzke et al. [START_REF] Fritzke | Transactions on partially replicated data based on reliable and atomic multicasts[END_REF] propose a replication scheme where sites TO-multicast each operations and execute them upon reception. However they do not prevent global deadlocks with a priority rule; it increases abort rate. Preventive replication [START_REF] Pacitti | Preventive replication in a database cluster[END_REF] considers that a bound on processor speed, and network delay is known. Such assumptions do not hold in a large-scale system. The epidemic algorithm of Holiday et al [START_REF] Holliday | Partial database replication using epidemic communication[END_REF] aborts concurrent conflicting transactions and their protocol is not live in spite of one fault. In all of these replication schemes, each replica execute all the operations accessing the data items it replicates. Alonso proves analytically that it reduces the scale-up of the system [START_REF] Alonso | Partial database replication and group communication primitives in 2nd European Research Seminar on Advances in Distributed Systems[END_REF].

The DataBase State Machine approach [START_REF] Pedone | The database state machine approach[END_REF] applies update values only but in a fully replicated environment. Its extensions [START_REF] Schiper | Optimistic algorithms for partial database replication[END_REF]21] to partial replication require a total order over transactions.

Committing transactions using a distributed serialization graph is a well-known technique [START_REF] Shih | Survey of deadlock detection in distributed concurrent programming environments and its application to real-time systems[END_REF]. Recently Haller et al. have proposed to apply it [START_REF] Haller | Decentralized coordination of transactional processes in peer-topeer environments[END_REF] to large-scale systems, but their solution does not handle replication, nor faults.

Conclusion

We present an algorithm for replicating database systems in a large-scale system. Our solution is live and safe in presence of non-byzantine faults. Our key idea is to order conflicting transaction per data item, then to break cycles between transactions. Compared to previous existing solutions, ours either achieves lower latency and message cost, or does not unnecessarily abort concurrent conflicting transactions.

The closure of constraints graphs is a classical idea in distributed systems. We may find it in the very first algorithm about State Machine Replication [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF], or in a well-known algorithm to solve Total Order Multicast [START_REF] Defago | Totally ordered broadcast and multicast algorithms: a comprehensive survey[END_REF]. 6 We believe that the closure generalizes to a wider context, where a constraint is a temporal logic formula over sequences of concurrent operations.

.

Additionnal notations

We note D the universal set of data item, T the universal set of transactions, and G the universal set of precedence graphs constructed upon D.

Let ρ be a run of Algorithm 2, given a site i we note event i when the event event happens at site i during ρ ; moreover if value is the result of this event we note it: event i = value.

Let ρ be a run of Algorithm 2, we note: faulty(ρ) the set of sites that crashes during ρ, correct (ρ) the set Π \ faulty(ρ).

committed (ρ) the transactions committed during ρ, i.e. {T ∈ T, ∃i ∈ Π, T ∈ committed i }, and aborted (ρ) the transactions aborted during ρ, i.e. {T ∈ T, ∃i ∈ Π, T ∈ aborted i }.

Given a site i and a time t, we note G i,t the value of G i at time t.

.

Proof of correctness

Since the serializability theory is over a finite set of transactions, we suppose hereafter that during ρ a finite subset of T is sent to the system. Let ρ be a run of Algorithm 2, we now proove a series of propositions leading to the fact that ρ is serializable.

£ ¢ ¡ P1 ∀T ∈ T, (∃j ∈ Π, R-deliver j (T ) ∈ ρ) ⇒ (∀o ∈ T, ∀i ∈ replicas(o) ∩ correct (ρ), TO-deliver i (o) ∈ ρ)

Proof

Let T be a transaction and j a site that R-delivers T during ρ.

F1.1 ∀i ∈ replicas(T ) ∩ correct (ρ), R-deliver i (T )
By the Uniform Agreement property of Uniform Reliable Multicast.

F1.2 ∀o ∈ T, ∃k ∈ correct(ρ) ∩ replicas(o), TO-multicast k (o) ∈ ρ F1.2.1 ∃l ∈ correct (ρ) ∩ replicas (o), WLeader l (replicas(o)) = l ∧ R-deliver l (o)
By fact F.1.1, assumption A1 and the properties of the Eventual Weak Leader Service. By fact F1.2.1 eventually a correct site executes line 16 in Algorithm 2.

INRIA

Fact F1.2 and the Validity and the Agreement properties of Total Order Multicast conclude our claim.

In the following we say that a transaction T is submitted to the system:

T ∈ submitted(ρ), if a site i R-delivers T during ρ. £ ¢ ¡ P2 ∀T ∈ submitted (ρ), ∀i ∈ replicas(T ), ∀o ∈ T, ∃G ∈ G, o ∈ op(T, G) ∧ receive i (G) Proof F2.1 ∀i ∈ Π, ∀t, t ′ , t > t ′ ⇒ G i,t ⊆ G i,t ′ F2.2 ∀G ∈ G, ∀T ∈ T, T ∈ G ⇒ T ∈ pred (T, G)
By definition of pred (T, G).

By proposition P1, facts F2.1 and F2.2, and since links are reliable.

£ ¢ ¡ P3 ∀T, T ′ ∈ submitted(ρ), T →T ′ ⇒ (∃o, o ′ ∈ T × T ′ , ∃i ∈ correct (ρ), o→ i o ′ ) Proof By definition of T →T ′ , let o, o ′ ∈ T × T ′
and let j be a site such that o→ j o ′ . Since conflict (o, o ′ ) and an operation applies on a single data item, we note x the unique data item such that x = item(o) = item(o ′ ).

F3.1 j ∈ replicas (x) Site j TO-delivers o during ρ and links are reliable.

F3.2 ∃i ∈ replicas(x) ∩ correct(ρ), TO-deliver i (o) ∧ TO-deliver i (o ′ ) RR n 6440
By assumption A1 ∃i ∈ replicas(x) ∩ correct(ρ), and by the Uniform Agreement property of Total Order Multicast, since i is correct during ρ, i TO-delivers both o and o ′ . Fact F3.2 and the Total Order property of Total Order Multicast concludes our claim.

£ ¢ ¡ P4 ∀T ∈ submitted (ρ), ∀i ∈ Π (∃t, T ∈ G i,t ) ⇒ (∃T 1 , . . . , T m≥0 ∈ submitted(ρ), i ∈ replicas(T m ) ∧ T → T 1 → . . . → T m )

Proof

Since G i,0 = (Ø, Ø), let us consider the first time t 0 at which T ∈ G i,t . According to Algorithm 2 either: i TO-delivers an operation o ∈ T at t 0 , and thus i ∈ replicas(T ). QED or i receives a precedence graph G ′ from a site j such that T ∈ G ′ . Now since links are reliable, note t 1 the time at which j send G ′ to i. According to lines 29 and 34, it exists a transactions T ′ such that T ∈ pred (T ′ , G j,t1 ), and a transaction T ′′ such that T ′′ ∈ out (T ′ , G j,t1 ) and i ∈ replicas(T ′′ ).

From T ∈ pred (T ′ ,), by definition of the predecessors, we obtain T → . . . → T ′ , and from T ′′ ∈ out(T ′ , G j,t1 ) we obtain T ′ →T ′′ . Thus T → . . . → T ′ → T ′′ , with i ∈ replicas (T ′′ ).

£ ¢ ¡ P5 ∀T ∈ submitted (ρ), ∀i ∈ correct (ρ), (∃t, T ∈ G i,t ) ⇒ (∃t, op(T, G i,t ) = T )
Proof Let T 0 be a transaction submitted during ρ and let i be a site that eventually hold T 0 in G i .

By proposition P4 it exists T 1 , . . . , T m≥0 ∈ submitted(ρ) such that i ∈ replicasT m and T → T 1 → . . . → T m .

Let k ∈ 0, m , we note P(k) the following property:

INRIA P(k) △ = ∀j ∈ correct (ρ) ∩ replicas(T k ), ∃t ∈ op(T 0 , G j,t0 ) = T 0
Observe that by proposition P2 P(0) is true. We now proove that P(k) is true for all the k by induction:

Let o, o ′ ∈ T k × T k+1 , and j ∈ correct (ρ) such that o→ j o ′ . Let t 0 be the first time at which j TO-delivers o during ρ. Let t 2 be the first time at which op(T k , G j,t ) = T k (since G j,0 = (Ø, Ø), and P(k) is true).

Let t 1 be the first time at which j To-delivers o ′ during ρ.

Observe that since o→ j o ′ , t O < t 1 . It follow that we have three cases to consider: cases t 2 < t 0 < t 1 and t 0 < t 2 < t 1

In these cases when j To-delivers o ′ , we have:

T k →T k+1 ∈ G j,t1 ∧ op(T k , G j,t1 = T k ) Thus, T k ∈ pred (T k+1 , G j,t1 ) ∧ op(T k , pred (T k , G j,t1 )) = T k
and according to Algorithm 2, j sends pred (T k+1 , G j,t1 ) to replicas(out(T k+1 , ))G j,t1 . Now since replicas(T k+1 ) ⊆ replicas(out (T k+1 , ))G j,t1 , given a site j ∈ replicas(T k+1 ), eventually j receives pred (T k+1 , G j,t1 ), and merges it into its own precedence graph. case t 0 < t 1 < t 2

We consider two-subcases:

-At t 2 j delivers an operation of T k , and this operation is different from o ′ . Now since T k →T k+1 ∈ G j,t2 , P(k + 1) is true.

-If now j receives a graph G such that op(T k , G) = T k , by definition of t 2 , G ⊆ G j,t2 , and more precisely, pred (T k , G) ⊆ pred (T k , G j,t2 ). It follows that j sends pred (T k , G∪G j,t2 ) to replicas (out(T k , G∪∪G j,t2 )). Finally since by definition of t

1 , T k →T k+1 ∈ G j,t2 , we obtain T k+1 ∈ out (T k , G ∪ G j,t2
), from which we conclude that P(k + 1) is true.

To conclude observe that since i ∈ replicas(T m ) and

P(m) is true, eventually op(T 0 , G i,t0 ) = T 0 . £ ¢ ¡ P6 ∀T ∈ submitted (ρ), ∀i ∈ correct (ρ), (∃t, T ∈ G i,t ) ⇒ (∃t, ∀T ′ ∈ submitted (ρ), T ′ →T ⇒ (T ′ , T ) ∈ G i,t ) Proof F6.1 ∀T, T ′ ∈ submittedρ, ∀o, o ′ ∈ T × T ′ , (∃i ∈ Π, o ′ → ⇒ o∀j ∈ replicas(o), o→ j o ′
By the Uniform Agreement and Total Order properties of Total Order MBroadcast

F6.2 ∀T ∈ submitted (ρ), ∀o ∈ T, ∀i ∈ correct (ρ), (∃t, oop(T, G i,t )) ⇒ (∀T ′ submitted(ρ), T ′ →T ⇒ ∃t, (T, T ′ ) ∈ G i,t )
Since o ∈ op(T, G i,t ) and G i,0 = (Ø, Ø), either:

1. i ∈ replicas (T ) ∧ TO-deliver o (i)
First observe that since links are reliable i ∈ replicas(o). Let T ′ be a a transaction, o ′ ∈ T ′ an operation, and k a site such that o

′ → k o. By fact F6.1 since i, j ∈ replicas (o), o ′ → i o. 2. ∃G ∈ G, receive T (G) ∧ o ∈ op(T, G)
According to Algorithm 2 it exists k 0 , . . . , k m sites sucht that: Consequently pred (T, G k0 ) ⊆ G i,t , and according to our reasonning in item 1, we conclude that fact F6.2 is true.

Fact F6.2 and proposition P5 conclude.

We are now able to proove our central theorem: every transaction is eventually closed at a correct site.

INRIA £ ¢ ¡ T1 ∀T ∈ submitted (ρ), ∀i ∈ correct (ρ), (∃t, T ∈ G i,t ) ⇒ (∃t, closed (T, G i,t ))

Proof

We consider that a finite subset of T are sent to the system, consequently submitted(ρ) is also finite. Let C T be the graph resulting from the transitive closure of the relation → on {T }. According to proposition P6, C T is eventually in G i,t , and thus according to proposition P5, T is eventually closed at site i.

£ ¢ ¡ P7

∀T ∈ submitted (ρ), ∀i, j ∈ Π, ∀t, t ′ , (T ∈ G i,t ∧ T ∈ G j,t ′ ∧ closed (T, G i,t ) ∧ closed (T, G j,t ′ )) ⇒ (pred (T, G i,t ) = pred (T, G j,t ′ )) Proof F7.1 pred (T, G i ).V = pred (T, G j ).V Let T ′ ∈ pred (T, G i ). By definition it exists T 1 , . . . , T m such that T ′ → T 1 → . . . → T m → T ⊆ G i . By an obious induction on m using proposition P6 we conclude that T ′ is also in pred (T, G j ). Let T ′ ∈ pred (T, G i ) such that isAborted (T ′ , pred (T, G i )). According to Algorithm 2, it exists a site k and a read operation r ∈ T ′ such that k TO-delivers r during ρ, and then k set the aborted flag of T ′ in its precedence graph. Now let k ′ be a replica of r, by the Uniform Agreement and the Total Order Property of Total Order Multicast, when k ′ TO-delivers r, it also set the aborted flag of T ′ in its precedence graph.

By the conjunction of facts F7.1 to F7.4.

We proove now that ρ is serializable [2]. Let O(x, ρ) be the set of write operation over the data item x during ρ, we define the relation ≪ as follows:

∀x ∈ D, ∀o 1 , o 2 ∈ O(x, ρ), x 1 ≪ x 2 △ = ∃i ∈ replicas(x), o→ i o ′ £ ¢ ¡ P8
≪ is a version order for ρ.

Proof

Let O(x, ρ) be the set of write operation over the data item x during ρ ; and let i ∈ replicas(x) ∩ correct (ρ) (assumption A1).

According to Algorithm 2 o is executed only if trans(o) is committed during ρ consequently i commits during ρ any transaction T such that ∃o ∈ wo(T ), O(x, ρ). Consequently ≪ is total over O(x, ρ), and by the Total Order and Uniform Agreement properties of Total Order Multicast, ≪ is an order over O(x, ρ). Let t and t ′ be respectively the times at which these two events occured; according to Algorithm 2 :

F9.1.1 TO-deliver i (o) < ρ t < ρ t ′ INRIA

  the data item operation o accesses, isRead (o) (resp. isWrite(o)) a boolean indicating whether o is a read (resp. a write), and replicas(o) △ = replicas (item(o));

  Given a transaction T , for any operation o ∈ T , function trans(o) returns T , ro(T ) (respectively wo(T )) is the subset of read (resp. write) operations, item(T ) is the set of data items transaction T accesses: item(T ) △ = o∈T item(o). and replicas(T ) △ = replicas(item(T )).

Algorithm 2 code for site i 1 : 12 : 18 : 19 :

 1121819 variables Gi := (Ø, Ø); pending := Ø for all o ∈ T : i ∈ replicas(o) do 13: pending := pending ∪ {o} 14: 15: when ∃o ∈ pending ∧ i = WLeader (replicas(o)) 16: TO-multicast(o) to replicas(o) 17: when TO-deliver(o) for the first time ⊲ Certification pending := pending \ {o} 20: let T = trans (o) 21:

22 :

 22 op(T, Gi) := op(T, Gi) ∪ {o}23: if isRead (o) ∧ (∃o ′ , o ′ →io ∧ trans(o ′ ) trans(o) ∧ trans(o ′ ) ∈ committedi)then for all o ′ : o ′ →io do 28: Gi.E := Gi.E ∪ {(trans (o ′ ), T )} 29: send(pred (T, Gi)) to replicas(out (T, Gi)) 30: 31: when receive(T, G) ⊲ Closure 32: for all T ∈ Gi do 33:if pred (T, G) ⊆ pred (T, Gi) then 34:send(pred (T, Gi ∪ G)) to replicas(out (T, Gi))if ¬ isAborted (T, Gi) ∧ decide(T, pred (T, Gi)) then

k 0

 0 TO-delivers o during ρ, and execute line 29 sending pred (T, G k0 ) with o ∈ op(T, predecessorsT G k0 ) and k 1 ∈ replicas(out (T, G k0 )). k 1 receives pred (T, G k0 ) during ρ and then execute line 29 or line 34, sending a precedence graph G such that pred (T, G k0 ) ⊆ G to a set of replicas containinig k 2 . etc ... until i receives it.

F7. 2

 2 pred (T, G i ).E = pred (T, G j ).E Identical to the reasonning proposed for fact F7.1.F7.2 ∀T ′ ∈ pred (T, G i ), op(T ′ , pred (T, G i )) = op(T ′ , pred (T, G j ))By fact F7.1 and since T is closed at both sites i and j.

F7. 4

 4 {T ′ |isAborted (T, G i )} = {T ′ |isAborted (T, pgraphSitej)}

  ′ ∈ MVSG(ρ, ≪),((T, T ′ ) ∈ MVSG(ρ, ≪) ∧ wo(T ) = Ø ∧ wo(T ′ ) = Ø) ⇒ T →T ′ Proof F9.1 If (T, T ′) is a read-from edge, then T →T ′ Let (T, T ′ ) be a read-from relation. By definition it exists a site i, a write w[x] ∈ T , and a read r[x] ∈ T ′ such that during ρ at site i w write x then r reads the value written by w.

  where trans(o ′ ) trans(o) means that the transactions trans(o ′ ) and trans(o) were executed concurrently during the initial execution phase.

If now o is a write, i gives an IW lock to o: function forceWriteLock (o). If an operation o ′ holds a conflicting IW lock, o and o ′ share the lock (see Table

Our taxonomy comes from[START_REF] Defago | Totally ordered broadcast and multicast algorithms: a comprehensive survey[END_REF].RR n 6440

RR n 6440

If T writes a data item x then reads it, we suppose some internals to ensure that T sees a consistent value.

If instead of this procedure, i TO-multicasts all the operations, then the system blocks if i crashes. We use a weak leader and a reliable multicast to preserve liveness.INRIA

Recall that the leader is eventual, consequently i may receive o more than one time.

This operation prevents local deadlocks. RR n

In[START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] Lamport closes the ≪ relation for every request to the critical section. In[START_REF] Defago | Totally ordered broadcast and multicast algorithms: a comprehensive survey[END_REF] the total order multicast protocol attributed to Skeen, closes the order over natural numbers to TO-multicast a message.INRIA