Mateusz Pyzik
email: mateusz.pyzik@pwr.edu.pl

François Coste
email: francois.coste@inria.fr

Witold Dyrka
email: witold.dyrka@pwr.edu.pl

Olgierd Unold

Wojciech Wieczorek

How to measure the topological quality of protein parse trees?

Keywords: context-free grammar, parse tree, contact map, molecular language

Human readability and, consequently, interpretability is often considered a key advantage of grammatical descriptors. Beyond the natural language, this is also true in analyzing biological sequences of RNA, typically modeled by grammars of at least context-free level of expressiveness. However, in protein sequence analysis, the explanatory power of grammatical descriptors beyond regular has never been thoroughly assessed. Since the biological meaning of a protein molecule is directly related to its spatial structure, it is justified to expect that the parse tree of a protein sequence reflects the spatial structure of the protein. In this piece of research, we propose and assess quantitative measures for comparing topology of the parse tree of a context-free grammar with topology of the protein structure succinctly represented by a contact map. Our results are potentially interesting beyond its bioinformatic context wherever a reference matrix of dependencies between sequence constituents is available.

Introduction

Context-free (CF) and context-sensitive (CS) grammars are often regarded as more appropriate to model proteins than regular level models such as finite state automata and Hidden Markov Models (HMM). In theory, the claim is well-founded in the fact that many biologically relevant interactions between residues of protein sequences have a character of nested or crossed dependencies. In practice, there is hardly any evidence that grammars of higher expressiveness have an edge over old good profile HMMs [START_REF] Eddy | Profile hidden Markov models[END_REF][START_REF] Soeding | Protein homology detection by HMM-HMM comparison[END_REF] in classical applications including recognition and classification of protein sequences [START_REF] Eddy | Accelerated profile HMM searches[END_REF][START_REF] Remmert | HHblits: lightning-fast iterative protein sequence searching by HMM-HMM alignment[END_REF][START_REF] Finn | The pfam protein families database: towards a more sustainable future[END_REF]. This is in contrast to RNA modeling, where CFGs power some of the most successful tools [START_REF] Sakakibara | Stochastic context-free grammars for modeling RNA[END_REF][START_REF] Eddy | RNA sequence analysis using covariance models[END_REF][START_REF] Knudsen | RNA secondary structure prediction using stochastic context-free grammars and evolutionary history[END_REF][START_REF] Sükösd | PPfold 3.0: fast RNA secondary structure prediction using phylogeny and auxiliary data[END_REF].

A few explanations of this phenomenon are plausible. On the biology side, one difficulty is that interactions in proteins are often less specific and more collective in comparison to RNA. On the modeling side, a difficulty is the larger alphabet which combined with high complexity of CF and CS grammars imposes considerable trade-offs consisting on information reduction or learning sub-optimal solutions. Indeed, some studies hinted that CF level of expressiveness brought an added value in protein modeling when CF and regular grammars were implemented in the same framework [START_REF] Dyrka | Probabilistic context-free grammar for pattern detection in protein sequences[END_REF][START_REF] Dyrka | Probabilistic grammatical model for helix-helix contact site classification[END_REF].

Explanatory potential of grammatical modeling has not been fully used in studying proteins. A notable example is Protomata [START_REF] Coste | Learning Automata on Protein Sequences[END_REF], which was applied to create a database of motifs for phycobilin lyases [START_REF] Bretaudeau | CyanoLyase: a database of phycobilin lyase sequences, motifs and functions[END_REF]. Several works attempted to build on explanatory power of grammars beyond regular. For example, derivations generated by mildly CSGs were proposed for prediction of secondary structures for protein sequences [START_REF] Mamitsuka | Predicting location and structure of betasheet regions using stochastic tree grammars[END_REF][START_REF] Abe | Predicting protein secondary structure using stochastic tree grammars[END_REF] and their mutual conformation in transmembrane bundles [START_REF] Waldispuehl | Modeling and predicting all-transmembrane proteins including helix-helix pairing[END_REF][START_REF] Waldispuehl | Predicting transmembrane betabarrels and interstrand residue interactions from sequence[END_REF][START_REF] Waldispuehl | Modeling ensembles of transmembrane beta-barrel proteins[END_REF]. Most likely parse trees derived using probabilistic CFGs were suggested to approximate the spatial structure of binding sites [START_REF] Dyrka | A stochastic context free grammar based framework for analysis of protein sequences[END_REF], and to reveal expected amino acid properties at particular positions in helix-helix pairs [START_REF] Dyrka | Probabilistic grammatical model for helix-helix contact site classification[END_REF]. Trees generated with annotated stochastic CFGs were used to investigate relations between conserved regions in sequences [START_REF] Sciacca | Annotated stochastic context free grammars for analysis and synthesis of proteins[END_REF]. However, there have been no systematic study of explanatory power provided by various grammatical models.

The first step to this goal is defining objective criteria of such evaluation. Intuitively, a decent explanatory grammar should generate a topology, encoded in the parse tree, consistent with the topology of the protein, or its secondary and/or tertiary structure. In this piece of research we build on this intuition and propose a set of measures to compare the topology of the parse tree of a grammar with the topology of the protein structure represented by a contact map. The advantage of the parse tree as a grammatical descriptor is that it is a direct outcome of parsing; moreover, it can be obtained for the non-probabilistic and probabilistic grammars (typically the maximum-likelihood tree). The advantage of the contact map as the protein structure representation is its apparent simplicity but also availability of good quality predictions [START_REF] Weigt | Identification of direct residue contacts in protein-protein interaction by message passing[END_REF][START_REF] Wang | Accurate de novo prediction of protein contact map by ultra-deep learning model[END_REF], which can be potentially used in case the actual protein structure has not been solved.

Definitions

Context-free grammar. A context-free grammar is a quadruple G = Σ, V, v 0 , R , where Σ is a finite alphabet of terminal symbols (representing for instance amino acid species), V is a finite alphabet of non-terminal symbols (also called variables

) disjoint from Σ, v 0 ∈ V is a special start symbol and R is a finite set of rewriting rules such that R ⊆ (V → (Σ ∪ V ) * ), where X → Y = {x → y : x ∈ X ∧ y ∈ Y } and XY = {xy : x ∈ X ∧ y ∈ Y }. Chomsky Form with Contacts Consider a context-free grammar G = Σ, V, v 0 , R satisfying V = V l V s and R = R l ∪ R b ∪ R c , where R l ⊆ (V l → Σ), R b ⊆ (V s → V V ) and R c ⊆ (V s → V l V s V l ).
The subsets R l , R b and R c shall be referred to as lexical, branching and contact rules. Set R s = R b ∪R c is later referred to as structural rules. Grammars which satisfy these conditions are hereby defined to be in Chomsky Form with Contacts (CFC). When a CFC grammar satisfies R c = ∅, it happens to be in Chomsky Normal Form (CNF).

Derivations and parse trees

A rule r = (A → α) derives ω 2 from ω 1 , written ω 1 r ⇒ ω 2 ,
if and only if ω 1 = wAβ and ω 2 = wαβ for some w ∈ Σ * , β ∈ (N ∪ Σ) * . Note that only the first non-terminal can be rewritten here, enabling to define a canonical (left-most) derivation by a string of rules: we say that a derivation

d = r 1 . . . r l ∈ R l , l ≥ 0 derives ω l from ω 0 , written ω 0 d ⇒ ω l , if and only if ω 0 r l ⇒ ω 1 . . . r l ⇒ ω l for some ω 1 , . . . , ω l ∈ (N ∪ Σ) * .
A derivation d such that v 0 d ⇒ x, x ∈ Σ * is called a complete derivation for G. We say then that d yields x, denoted yield(d) = x. A complete derivation d structures the sequence x by the associated parse tree y(d), which is a labeled ordered tree whose root is labeled by v 0 and extended iteratively following the derivation rules: at each step of the derivation, by applying rule r i = (v → α 1 . . . α k ) with α 1 , . . . , α k ∈ (Σ ∪ V ), the parse tree is extended by adding edges from the existing left-most node labeled v to new ordered nodes labeled α 1 to α k . As derivation is complete, the result is a (complete) parse tree whose nodes are labeled by variables and leaves by terminals.

Unlabeled derivation tree If we are interested only in the shape of the parse tree (called also the topology of the parse tree), we can consider the unlabeled parse tree or skeleton u obtained by removing the variables that label the nodes of the parse tree y, we write u = u (y) [START_REF] Sakakibara | Efficient learning of context-free grammars from positive structural examples[END_REF]. Each (un)labeled tree has an associated n × n symmetric matrix p = (p i,j ), where p i,j is the length of the path from i-th to j-th leaf.

Contact constraints Let x = x 1 . . . x n be a protein sequence. Most protein sequences fold into complex spatial structures. Let d = (d i,j ) be a matrix of spatial distances between amino acids at positions i and j. The distance is typically calculated between C α or C β atoms from the main backbone [START_REF] Pawel | Characteristics of protein residue-residue contacts and their application in contact prediction[END_REF]. Two amino acids at positions i and j are said to be in contact if d i,j is below a given threshold τ (usually assumed to be 8 Å (Wozniak and Kotulska, 2014)). A (complete) contact map for a protein of length n is a binary symmetric n × n matrix m = (m i,j ) such that m i,j = 1 ⇐⇒ d i,j ≤ τ . In practice, sometimes only a subset of the contact is determined. A partial contact map for a protein of length n is a binary symmetric matrix m such that m i,j = 1 =⇒ d i,j ≤ τ .

The complement of the contact matrix m = (m i,j ) is defined such that m i,j = 1 -m i,j .

Usually contacts between residues very close in the sequence do not carry much information. For a given separation in sequence s, let m (s) = m (s) i,j be a truncation of contact matrix m such that m

(s) i,j = [|i -j| ≥ s] • m i,j
, where [•] is the Iverson bracket. Given a threshold δ, parse tree t is said to be consistent with a contact map m if and only if m i,j = 1 =⇒ p i,j ≤ δ.

A contact map is non-crossing when no contact has one end inside and another outside of interval induced by any other contact. In other words, pairs can stand side by side or be nested one in another.

(m i,j = 1 ∧ m k,l = 1 ∧ i ≤ k ∧ i < j ∧ k < l) =⇒ (i < k ∧ (j < k ∨ l < j))
For example, contacts (1, 6), (2, 5) form a non-crossing contact map, while contacts (1, 6) and (2, 7) are crossing. Interestingly, fixing threshold δ = 4, contact map m is non-crossing if and only if there exists a grammar G in CFC and a parse tree w.r.t. G which is consistent with map m.

Measures

The most straightforward approach to assess descriptive performance is to use the unlabeled derivation tree as a predictor of spatial contacts between positions in sequence, parameterized by the cutoff δ on path length between the leaves. Pairs of terminal symbols linked by paths shorter than δ are considered as true (false) positives if actually (not) in contact, while pairs of terminal symbols linked by longer paths are considered as false (true) negatives if actually (not) in contact.

Basic measures

The essential measures of prediction performance are the recall (called also sensitivity), which is the fraction of correctly predicted objects which actually belongs to the class of interest, and the precision (called also positive predictive value), which is the fraction of correctly predicted objects among all predicted to belong to the class of interest. Indeed, they were used, for example, to assess small grammar designs for RNA secondary structure prediction [START_REF] Dowell | Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction[END_REF]. The harmonic mean of recall and precision is usually denoted as the F 1 measure, also known as Czekanowski binary index [START_REF] Czekanowski | Zur differential Diagnose der Neandertalgruppe[END_REF], Dice index (Dice, 1945) and Sørensen index [START_REF] Sørensen | A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons[END_REF]. In the setting of the contact prediction, the measure can be seen as the overlap between a subset of residues close in a protein structure and a subset of residues close in a parse tree. All three measures are parameterized by the fixed cutoff δ.

Aggregated measures While choice of δ can be obvious for some grammars such as a classical probabilistic CFG for RNA modeling [START_REF] Knudsen | RNA secondary structure prediction using stochastic context-free grammars and evolutionary history[END_REF], it is not evident in general. A possible workaround consists in calculating an aggregated measure, such as the area under precision-recall curve (AUPRC) defined by a sequence of recall-precision points over varying thresholds δ. In practice AUPRC is often approximated by the average precision calculated over the thresholds (AP). Another popular aggregated measure of performance of a classifier is the area under the receiver operating characteristic (AUROC) calculated for true positive rates achieved over the thresholds of false positive rate [START_REF] Fawcett | An introduction to ROC analysis[END_REF]. The threshold-independent measures can be used to evaluate the overall topology (global features of the shape) of the parse tree.

Mean path measures

In addition, we propose two novel measures that relate the mean path length in the parse tree between residues in contact p m (s) to the mean path length between residues not in contact p m (s) , where m is the reference contact map, p (a) = p, a / a 1 , •, • stands for the scalar product and • 1 denotes the 1 norm. Then, the overall fitness of the parse tree w.r.t. a given contact map m can be calculated as:

S 1 = p m (s) -p m (s) max p m (s) , p m (s) , and R 1 = p m (s) p m (s) ,
which are respectively the normalized difference, and the ratio of average path lengths between residues in contact and those not in contact. S 1 gives scores from -1 (bad ) to 1 (good ), while R 1 ranges from 0 (bad ) to ∞ (good ). Both measures indicate how much paths to residues in contact are shorter than paths to residues not in contact.

Measures defined above are general enough to cope with weighted contact maps where each pair has a score or probability -input matrix of contacts m can be real-valued. Definition of distances p can be changed as well -variants of measure S 1 for weighted grammars can be defined similarly, for example, by setting distance p i,j to be the sum of negated logarithms of edge weights between i and j.

Local measures w.r.t. residue Local variants of all aforementioned measures can be defined. Intuition behind them is to focus only on residues that are in contact with k-th residue. This effect can be obtained by using only respective row of the contact map m k,• when calculating the value of a measure for amino acid at position k.

Implementation All measures and simulations were implemented in python 3.5 [START_REF] Van Rossum | Interactively testing remote servers using the Python programming language[END_REF] with some help of scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine learning in Python[END_REF]. Charts were plotted with matplotlib [START_REF] Hunter | Matplotlib: A 2d graphics environment[END_REF] and parse trees were plotted with dot [START_REF] Gansner | An open graph visualization system and its applications to software engineering[END_REF].

Data

Simulated data Properties of the proposed measures were first evaluated using a large set of simulated data. It was assumed that parse trees were generated using grammars in the CFC in the form

v 0 → v 0 v 0 |v 0 v 1 |v 1 v 0 |v 1 v 1 |v 1 v 0 v 1 and v 1 → •,
where • denotes a terminal symbol (irrelevant for the shape of the tree). Therefore, the minimum separation between residues in contact s was set to 3 (two residues in between), and the minimal achievable distance between terminals in the tree was 4. Having in mind the goal of assessing topological quality of protein grammars and basing on data from our previous research [START_REF] Dyrka | A stochastic context free grammar based framework for analysis of protein sequences[END_REF][START_REF] Daskalov | Theme and variations: evolutionary diversification of the HET-s functional amyloid motif[END_REF], we assumed the sequence length of 30 residues with 6 or 10 non-crossing contacts.

To build the set, first, one hundred non-crossing maps were generated, and parse trees that matched them perfectly were constructed. Note that ambiguities in generating the unlabeled parse tree with regard to the non-crossing contact map can occur for stretches of non-pairing residues. In such cases, it was arbitrarily chosen to prefer v 0 → v 0 v 1 over v 0 → v 1 v 0 rules. Thus, within each non-pairing stretch of residues, the rightmost leaves were closer to the root of the parse tree. Then contact maps were randomly modified such that from one up to 2/3 of contacts were changed either by deletion, addition, or replacement (combination of deletion and addition). Additions were performed either in non-crossing or in unconstrained manner. The process was repeated 10 times for each setup (initial number of contacts, type and number of modifications). The modified maps were then treated as a reference when computing measures against the parse tree reflecting the original map. This reversal of the natural scenario of modifying parse trees was applied for the sake of simpler generation process.

Generation of non-crossing contact maps was achieved by subdividing the initial interval into smaller ones. Each newly chosen contact pair partitions space into left-hand, righthand and inner part. To pick a contact, it suffices to choose an interval among available and then its endpoints from the interval that was picked. The procedure yields uniform distribution of non-crossing contact maps.

This simple procedure cannot be used for extending an existing non-crossing contact map, since in this case new contacts are not necessarily added in the hierarchical nested order. Thus, we apply a constrain-and-generate approach with a blacklist of choices that failed to produce valid result (desired number of contacts) and a stack of choices that can be undone if contradiction appears. Backtracking guaranteed completeness and the blacklist ensured termination of the procedure. A set of allowed endpoints was maintained for each position in the sequence. The sets were adjusted at every random choice of a pair in contact, effectively pruning the search space. This method was sufficiently efficient, as we were mostly interested in maps which were not large and not dense enough to make such the search procedure prohibitively time-consuming.

RNA Qualitative analysis of the proposed measured was conducted using an example RNA sequence taken from Fig. 2 in [START_REF] Dowell | Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction[END_REF]. The sequence folds into a three-stem structure stabilized by interactions exhibiting only nesting and branching dependencies. A set of parse trees compatible with the CFC was used to model various defects in representing the real RNA structure defined. Specifically, the grammar underlying all the parse trees was in the form

v 0 → v 0 v 0 |v 0 v 1 |v 1 v 0 |v 1 v 1 |v 1 v 0 v 1 and v 1 → A|C|G|U,
where A, C, G and U represented the four bases of the RNA sequence. Scores of the consistency measures were calculated for the minimum separation of 3.

Proteins Eventually, the proposed measures were evaluated on a set of the maximum likelihood parse trees generated for three samples of protein sequences. The parse trees were obtained using probabilistic CFGs with rule probabilities automatically inferred solely from positive training sequences using a genetic algorithm-based framework [START_REF] Dyrka | A stochastic context free grammar based framework for analysis of protein sequences[END_REF][START_REF] Dyrka | Probabilistic grammatical model for helix-helix contact site classification[END_REF], as described in our recent work [START_REF] Dyrka | Estimating probabilistic context-free grammars for proteins using contact map constraints. under review[END_REF]. Two variants of grammars were used: one with rules in CFC, and the other with the subset of rules conforming to CNF (no contact rules). The rule sets included all possible productions which can be generated for 3 lexical and 4 structural non-terminals in these forms

(|R l | = 60, |R b | = 196, |R c | = 144
). The setup of the genetic algorithm is described in [START_REF] Dyrka | Estimating probabilistic context-free grammars for proteins using contact map constraints. under review[END_REF] and is similar to [START_REF] Dyrka | A stochastic context free grammar based framework for analysis of protein sequences[END_REF]. The processing was carried using a variant of the 8-fold Cross-Validation scheme in which 6 parts were used for training, 1 part was used for validation and parameter selection, and 1 part was used for final testing (the scheme resulted in 56 runs for each sample) [START_REF] Dyrka | Estimating probabilistic context-free grammars for proteins using contact map constraints. under review[END_REF]. Within each sample, all sequences shared the same length, and for each sample, one experimentally solved spatial structure from the Protein Data Bank (PDB) [START_REF] Berman | The Protein Data Bank[END_REF] was selected as the representative. The samples were made non-redundant at the level of sequence similarity around 70%. They consisted of:

• CaMn: 24 sequences of a Calcium and Manganese binding site from the legume lectins [START_REF] Sharon | Legume lectins-a large family of homologous proteins[END_REF]) collected according to the PROSITE PS00307 pattern [START_REF] Christian | New and continuing developments at PROSITE[END_REF] true positive and false negative hits, but extended to 27 residues to cover the entire binding site. The motif folds into a stem-like structure with 41 contacts, many of them forming nested dependencies (Fig. 7a based on pdb:2zbj (de Oliveira et al., 2008));

• NAP : 64 sequences of the Nicotinamide Adenine dinucleotide Phosphate binding site fragment from an aldo/keto reductase family [START_REF] K M Bohren | The aldo-keto reductase superfamily. cDNAs and deduced amino acid sequences of human aldehyde and aldose reductases[END_REF] collected according to the PS00063 pattern true positive and false negative hits (four least consistent sequences were excluded). The motif of length of 16 amino acids covers only a part of the binding site of the relatively large ligand. Eleven contacts within the motif seem to be insufficient for fully defining the fold, which depends also on interactions with amino acids outside the motif;

• HET-s: 160 sequences of the HET-s-related motifs r1 and r2 involved in the prion-like signal transduction in fungi [START_REF] Daskalov | Theme and variations: evolutionary diversification of the HET-s functional amyloid motif[END_REF]. The largest subset of motifs with length of 21 amino acids was used to avoid length effects on grammar scores. The beta-hairpin-like fold of the motif partially relies on interactions between hydrophobic amino acids at positions 5, 8, 10, 14, 16 and 18. There is also strong dependency between positions 17 and 21 [START_REF] Daskalov | Theme and variations: evolutionary diversification of the HET-s functional amyloid motif[END_REF]. All 10 intra-motif contacts are shown in Fig. 9a, which is based on pdb:2kj3 (van Melckebeke et al., 2010).

Results

Simulated data Results of evaluation on simulated data are shown in Fig. 1, 2, and 3.

Values of the basic prediction-related measures such as precision, recall and F 1 score were completely determined by experiment parameters and as such they exhibited the singlepoint distribution (given the threshold δ = 4). For F 1 , it may be noticed that adding a pairing not present in the contact map to the parse tree (resulting in a false positive) and removing a pairing present in the contact map from the parse tree (resulting in a false negative) do not count equally. Indeed, increasing number of false positive pairings (which affects only precision) counts relatively less than increasing number of false negative pairings (which affects only recall).

Among the aggregated measures, both AP and AUPRC were quite sensitive to alterations: distributions for different levels of discrepancy between the contact map and the parse tree were virtually non-overlapping and had a narrow span. Out of these two, distribution of the average precision appeared to be more tight. In both cases, the probability masses tended to concentrate towards the lower bound at each level of discrepancy. In addition, for experiments with only false positives the measures had the single-point distribution as the value was determined by the level of discrepancy. Moreover, AP achieved consistently lower values than AUPRC when false positives were considered.

Characteristics of S 1 , R 1 and AUROC were more complex. For experiments with false negatives, these measures behaved similarly to AP and AUPRC. Their mean value decreased with increasing discrepancy, however, variance was high so distributions for neighboring levels of alterations overlapped, yet were still discernible when comparing with more distant ones (see also next paragraph). For experiments with false positives alone, the measures only very slightly decreased with increasing number of added false positive pairings. Moreover, AUROC had the single-point distribution as the value was determined by the level of discrepancy. Values R 1 (S 1 ) for parse trees perfectly matching their respective contact maps ranged from 2.4 to about 3.0 (from 0.58 to 0.67).

RNA Results of evaluation of perfect and corrupted parse trees of an RNA molecule are shown in Tab. 1. Selected unlabeled parse trees are shown in Fig. 4 and5. For the sake of clarity, edges representing lexical rules were removed.

The perfect tree (Fig. 4a) was one of the possible trees ideally representing contacts found in the RNA molecule. It achieved the perfect score of 1.0 for the thresholded measures (at δ = 4), AP, AUPRC and AUROC, and set the reference level for R 1 and S 1 scores. The first test consisted on removing the four pairings making the outer stem (2-39, 3-38, 4-36, 5-35). Two unlabeled parse trees were created that accounted for this defect: one preserving the overall topology of the original tree (Fig. 4b) and one breaking the topology (Fig. 4c). The thresholded measures, which are based on counts of bases generated by the contact rules, evaluated both corrupted trees equally: the four false negatives resulted in the recall of 0.64 and F 1 of 0.78. The aggregated measures penalized the tree with broken topology more than the tree with preserved topology. Moreover, the latter was practically indistinguishable from the perfect tree in terms of AUROC, R 1 and S 1 . Relatively large difference between R 1 , S 1 scores for the two corrupted trees amounting to 50-55% of the reference was consistent with wide distributions of these measures observed for the simulated data (Fig. 1, 2, and3).

The next test consisted on removing or adding three pairings in different ways. In the first attempt, all three pairings making the left-hand-side stem (7-15, 8-14, 9-13) were taken out. While the unlabeled parse tree created to represent this defect (Fig. 5a) broke the topology, the effect was visually weaker than previously. This is well reflected in intermediate values of virtually all aggregated measures, except AP, which is virtually equal to that of the tree of preserved topology from the previous experiment. Subsequently, a single pairing was removed from each of the three stems (3-38, 8-14, 22-29), which led to the unlabeled parse tree topology only slightly diverging from the origin (Fig. 5b). Again, this topology-preserving discrepancy only marginally affected AUROC, and was within 90%

of R 1 and S 1 scores of the perfect tree. Quite similar was the effect of adding three false positive pairings (18-34, 21-30, 24-27) into the right-hand-side stem (Fig. 5c). Obviously, in this case the recall remained unaffected, while the precision dropped to 0.79 resulting in F 1 of 0.88. Finally, the measures were applied to trees intentionally unrelated to the real structure of the example RNA molecule. The tree made with a chain of rules producing a single terminal at each step, which represented the trivial topology of unfolded strand, achieved zero precision and recall, and slightly less than random scores or AUROC, R 1 and S 1 . Eventually, the tree made with a chain of contact rules, which represented another trivial topology of a single long stem, mostly achieved slightly higher scores because of the two true positive contacts of the outer stem (2-39, 3-38). Interestingly, AUPRC was higher for the tree with unfolded topology (0.23) than for the tree with the single stem topology (0.13), see Discussion.

Proteins Distributions of values of the evaluated measures on protein data are shown in Fig. 6, and the average values are presented in Tab. 2. Sample parse trees are shown in Fig. 7, 8 and 9 with residues annotated with local AP calculated for contacts of each residue separately. The aim of this kind of presentation is to highlight residues correctly/incorrectly positioned in the tree according to the contact map. The results show considerable variation between samples and grammar forms. Grammarwisely, the CFC grammars typically obtained higher scores than the CNF grammars for CaMn and HET-s datasets, apparently because the contact rules are particularly suited to model the stem-like structures of these protein fragments (Fig. 7a,9a).

Sample-wisely, mean scores of the measures were highest for the CaMn dataset. Yet, even in the best scoring cases (CaMn/CFC at Fig. 7d and CaMn/CNF at Fig. 8c), values of the measures were only at the level of the RNA molecule with seriously corrupted topology due to the missing outer pairings (cf. Tab. 1 and Fig. 4c). Indeed, even though the best trees for CaMn correctly represented the main stem-like structure of the binding site, they could not represent many crossing interactions, e.g. between positions 17 and 21 (Fig. 7a). While in the CaMn case the highest scores were similar for the CFC and CNF trees, distributions were shifted towards higher values for CFC in comparison to CNF, especially for AP and the AUC measures (compare middle rank trees for CFC at Fig. 7c Parse trees generated for NAP were on average scored close to the theoretical or experimentally determined random levels (cf. Tab. 1). Similar was the case of parse trees for HET-s generated with the CNF grammars. Interestingly, the CFC parse trees for HET-s achieved relatively low scores of F 1 , precision, recall, AP and AUPRC, but moderate scores of AUROC, R 1 and S 1 . For example, the best scoring (in terms of AP) CFC tree for HET-s had a correct overall topology, which led to a considerable S 1 of 0.39, but it missed out some of the contacts overlapping those involved in the main stem (most notably between positions 17 and 21), and incorrectly added some false contacts (for example between positions 2 and 20), which led to AP as low as 0.31 (Fig. 9b). This inaccuracy in representing contacts despite generally correct topology resulted in AP not much higher than in the case of the best CNF tree with apparently corrupted topology (Fig. 9b).

Figure 6: Distribution of scores of the evaluated measures on protein samples.

Discussion and conclusions

We investigated several quantitative measures of the consistency between the parse tree of context-free grammar and the contact map. Functionally, the measures can be divided into three groups: thresholded, contact-sensitive, topology-sensitive.

The thresholded measures (F 1 , precision and recall) are best suited when a natural meaningful threshold can be easily defined. For the CFC grammars, it is the minimum possible distance between terminal symbols, which is achievable only by using the contact rules (δ=4). In such a case, the thresholded measures directly quantify the relative number of errors (missed and added contacts) in the tree. For this purpose, they were practical only when the overall topology of the parse tree was good enough to accommodate derivations with contact rules for considerable number of pairings (Tab. 1 and 2). Focusing on a single extreme threshold, the measures were agnostic to the overall shape of the tree, whether it was close or distant from the optimum (compare Tab. 1 and Fig. 4).

The contact-sensitive measures group is made of the aggregated precision measures, AP and AUPRC. They are characterized by a tight score distribution for a given number of errors in the tree, and good separation of scores for changing number of errors (Fig. 1). In addition, AP is more sensitive to false positive pairings than to false negative ones (Fig. 2 and3). These features make AP especially suitable for detecting small defects in the trees of generally topologically correct structure (Tab. 1 and Fig. 7). Favorably, AP varied over virtually full range from 0.0 to 1.0 for the sample RNA molecule (Tab. 1), and from 0.1 to 0.7 for sample protein data (Fig. 6). Unexpectedly, the closely related AUPRC often scored the same parse trees considerably higher than AP, for example in the presence of false positive pairings (Fig. 3). Also, it exhibited a peculiar bimodal distribution for some cases (see HET-s in Fig. 6). These are most likely artifacts of the implementation of AUPRC, which uses the linear interpolation and, therefore, can produce overly optimistic approximation of the area under the actual precision-recall curve.

The topology-sensitive measures group is made of AUROC and the mean-path measures, R 1 and S 1 . They are characterized by wide and poorly separated score distributions given a number of errors in the tree (Fig. 1). At the same time, qualitative analysis of the RNA and protein trees suggests that these measures are sensitive to errors breaking the overall topology of the tree (Tab. 1, Fig. 9). Therefore, they seem to be useful for discriminating between mediocre and moderately good parse trees, which are hardly discernible in terms of AP (Tab. 1 and Fig. 5, Fig. 9). The topology-sensitive measures have the interesting property of being hardly (AUROC) or only weakly (R 1 and S 1 ) sensitive to false positive pairings (Fig. 3, Tab. 1), which may be advantageous in situations where only a partial contact map is available as the ground truth. AUROC varied in the range of ca. 0.5 (0.2) to 1.0 (0.9) for the RNA (protein) sample data. The mean-path measures R 1 and S 1 do not admit fixed right value (even though the latter is scaled between -1 and 1), therefore, they have to be calibrated if they are intended to be used as absolute measures (Fig. 1). S 1 exhibited a strong almost linear correlation with AUROC (Pearson's r of 0.989 on the joint CaMn and HET-s protein sets). However, the optimal value of S 1 saturated slightly slower than for AUROC (cf. Tab. 1). R 1 was even more sensitive in the vicinity of optimal solutions. Despite discussed differences, the topology-sensitive measures were highly correlated with AP (Kendall's τ above 0.90 on the joint CaMn and HET-s protein sets).

Overall, our results support the thesis that the context-free parse trees of protein sequences can be robustly evaluated in the quantitative manner with reference to the protein contact map, despite the fact that a large share of protein contacts has the context-sensitive character (crossing and overlapping). Thus, the study provides a solid ground for objective assessment of the explanatory power of the context-free grammars representing protein sequences. Further conclusions can be expected to arise when the proposed approach is applied in practice, for example to assessing inferred grammars against their predictive performance [START_REF] Dyrka | Estimating probabilistic context-free grammars for proteins using contact map constraints. under review[END_REF]. As bioinformatic applications are often powered by the probabilistic CFGs [START_REF] Knudsen | RNA secondary structure prediction using stochastic context-free grammars and evolutionary history[END_REF][START_REF] Dyrka | A stochastic context free grammar based framework for analysis of protein sequences[END_REF][START_REF] Sciacca | Annotated stochastic context free grammars for analysis and synthesis of proteins[END_REF][START_REF] Sükösd | PPfold 3.0: fast RNA secondary structure prediction using phylogeny and auxiliary data[END_REF], the natural next step is to develop measures for assessing them. This may include modified versions of the parse tree measures analyzed in this study, and also measures aimed at assessing the probability distribution over all derivations [START_REF] Knudsen | Pfold: RNA secondary structure prediction using stochastic context-free grammars[END_REF]. The latter would be a desirable complement to the former approach, since the maximum-likelihood trees of probabilistic CFG are not necessarily well approximates of the probability distribution over derivations with the contact rules [START_REF] Dowell | Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction[END_REF]. Another line of research may include using uncertain contact maps [START_REF] Knudsen | Stochastic context-free grammars and RNA secondary structure prediction[END_REF], which is especially tempting in the light of great progress in the protein contact prediction methods [START_REF] Weigt | Identification of direct residue contacts in protein-protein interaction by message passing[END_REF][START_REF] Wang | Accurate de novo prediction of protein contact map by ultra-deep learning model[END_REF].

Contributions WD, FC conceptualized the study and proposed the mean-path measures; MP, WD selected and implemented the measures, designed and conducted computational experiments; WD, MP analyzed the results; WD, MP, FC wrote the manuscript.

Figure 1 :

 1 Figure 1: Parse tree quality measures in function of number of alterations for simulated maps with 10 contacts and the replacement operation (false positive and false negative pairings); non-crossing (up) or unconstrained (down).

Figure 2 :

 2 Figure 2: Parse tree quality measures in function of number of alterations for simulated maps with 10 contacts and the deletion operation (only false negative pairings); non-crossing (up) or unconstrained (down).

Figure 3 :

 3 Figure 3: Parse tree quality measures in function of number of alterations for simulated maps with 10 contacts and the addition operation (only false positive pairings).

  and CNF at Fig 8b). The worst scoring trees for CaMn had virtually no resemblance to the actual structure of the fold (Fig 7b and 8a).

Figure 4 :

 4 Figure 4: Unlabeled parse trees of an RNA sequence: (a) fully covering the reference contact map, (b,c) without four outermost pairings. The overall topology of the tree is preserved in (b) but broken in (c) for positions 1-6.

Figure 5 :

 5 Figure 5: Unlabeled parse trees of an RNA sequence: (a) without all three contacts of the left-hand-side stem, (b) without one contact from each of the three stems, (c) with three additional (false positive) contacts in the right-hand-side stem.

Figure 7 :

 7 Figure 7: Unlabeled parse trees obtained using the CFC grammars for CaMn ligand binding sequences (b-d). Leaves are annotated with local AP scores. The schematic representative spatial structure of the binding site is shown in (a). Endings and positions whose contacts are poorly modeled by the best AP tree are marked (see text).

Figure 8 :

 8 Figure 8: Unlabeled parse trees obtained using the CNF grammars for CaMn ligand binding sequences. Leaves are annotated with local AP scores.

Figure 9 :

 9 Figure 9: Unlabeled parse trees obtained for HET-s prion folding domain samples using the (b) CFC and (c) CNF grammars. Leaves are annotated with local AP scores. The schematic representative spatial structure of the domain is shown in (a) with all contacts with separation at least 3 marked using dashed lines.

Table 1 :

 1 Values of the evaluated measures for perfect and corrupted parse trees of a sample RNA molecule from[START_REF] Dowell | Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction[END_REF].

	Tree / defect	Fig. F 1 Prec. Recall AP AUPRC AUROC R 1	S 1
	Perfect	4a 1.00 1.00	1.00	1.00	1.00	1.00	3.2 0.69
	Missing outer pairings
	topology preserved	4b 0.78 1.00	0.64	0.76	0.88	0.99	3.2 0.69
	Missing outer pairings
	topology broken	4c 0.78 1.00	0.64	0.64	0.64	0.76	1.6 0.38
	Missing all pairings
	in a stem	5a 0.81 1.00	0.73	0.74	0.74	0.92	2.4 0.59
	Missing a pairing
	in each stem	5b 0.81 1.00	0.73	0.80	0.84	0.99	3.0 0.67
	Additional pairings
	in a stem	5c 0.88 0.79	1.00	0.79	0.89	0.998	2.9 0.66
	Unfolded strand	-	0.00 0.00	0.00	0.02	0.23	0.48	0.9 -0.11
	All residues
	in one stem	-	0.13 0.11	0.18	0.05	0.13	0.65	1.3 0.22

Acknowledgments

This research has been funded by National Science Centre, Poland [grant no 2015/17/-D/ST6/04054] and was supported by the E-SCIENCE.PL Infrastructure. Computational experiments have been partially carried out using resources provided by Wroclaw Centre for Networking and Supercomputing (http://wcss.pl) [grant no 98]. The authors would like to thank Olgierd Unold, Lukasz Culer and Agnieszka Kaczmarek for supporting early development of the project.


Roman Le Goff Latimier
email: roman.legoff-latimier@ens-rennes.fr

Bernard Multon
email: bernard.multon@ens-rennes.frhamid.benahmed@ens-rennes.fr

Hamid Ben

DISTRIBUTED OPTIMISATION WITH RESTRICTED EXCHANGS OF INFORMATION: CHARGING OF AN ELECTRIC VEHICLE FLEET

Keywords: Electric vehicle fleet, Alternating Direction Method of Multipliers, Stochastic Dynamic Programming

The multiplication of flexible loads into electrical power systems allows to develop distributed optimisation techniques. The goal is to achieve the best compromise between the individual objectives of each load and the general interest which could be for instance the safety of the grid or the efficiency of the power generation. However the algorithms of distributed optimisation mostly rely on an iterated exchange of information, such as the dual variable and the decision of each agent. This exchange therefore supposes a bidirectional communication which cannot be considered as granted in operational contexts. This paper investigates the utilisation of the Alternating Direction Method of Multipliers under restricted exchanges of information. The case study consists in an electric vehicle fleet which has to comply with a maximum power limit. It is established that a close to optimal behaviour can be achieved using frequent broadcast messages instead of duplex communication.

INTRODUCTION

The diversification of the electrical devices pave the way to a potential increase of the electricity demand, in particular because of the growth of electric vehicles. This increase of the consumption compels to develop a sustainable power generation so as to ensure the relevance of electric mobility from well to wheel. In addition channelling this electricity down to vehicle charging stations may bring a significant overload on the grid. The sizing of the transport and distribution networks have not been done accordingly. In particular the charging of numerous vehicles in residential areas could make the peak consumption unbearable for both production units and distribution systems. However new electricity consumers such as electric vehicle offer some levels of flexibility. Indeed their consumption consists in the charging of a battery which can be shifted in time. This shift has no consequence on the service provided to the user, assuming he announced a departure time when he expects his vehicle to be charged. This characteristic is shared with other flexible consumptions such as heating, but electric vehicles may also be temporary discharged. This discharge could relieve stress on generation units and transport lines. Thus some situations could avoid to strengthen their infrastructures or to delay this adaptation [START_REF] Kempton | Vehicle to grid power implementation : from stabilizing the grid to supporting large scale renewable energy[END_REF]. However it will also bring a greater ageing of the battery in comparison with a charging only focused on the minimisation of the battery losses and ageing. It is therefore mandatory to evaluate this additional decay and to compare it to the service provided to the grid. As the impact of electric vehicles on a grid cannot be significant but if many act jointly, many studies have tackled the distributed control of electric vehicle fleets [START_REF] Vaya | Plug-in electric vehicle charging approaches: centralized versus decentralized and strategic versus cooperative[END_REF][START_REF] Goff Latimier | Stochastic optimisation of an electric vehicle fleet charging with uncertain photovoltaic production[END_REF]. However the distributed optimisation methods widely assume a context where communication is possible, fast and free of charge, between vehicles and/or between vehicles and a central agent. Then an iterative resolution of the problem can be carried out and the solution is enforced once the algorithm converged. However in the operational context of an electric grid, this free and fast communication becomes a very strong hypothesis. It would mean to build a communication network alongside the power network, or to use existing communication infrastructures with inherent risks of delay and loss of information. The scope of this study is to investigate the distributed optimisation of the charging of an electric vehicle fleet. The resolution of this problem is first presented to build a reference case under the assumption of a bidirectional communication between each vehicle and a central agent. Then only broadcast signals are supposed to be possible. Such signal could be for instance send through power line communication within a distribution district which is supplied by a single substation. Next section will introduce the optimal charging problem and the considered case study. The resolution algorithm will also be presented, in a general case and in the restricted communication context. Then the third section will present the resolution of the problem that each vehicle has to solve, as required by distributed optimisation frameworks. The last section will finally present and discuss the results.

OPTIMAL CHARGING PROBLEM UNDER A MAXIMUM POWER CONSTRAINT

Problem Presentation

The case study that is here considered is a distribution district. The substation which supplies the district has a rated power Prated. A non-flexible component of the consumption Pconso(t) is introduced and fluctuates along the day. The remaining available power is then:

𝑃 # (𝑡) = 𝑃 𝑟𝑎𝑡𝑒𝑑 -𝑃 𝑐𝑜𝑛𝑠𝑜 (𝑡) Within this district, electric vehicles are introduced with a flexible consumption and the possibility to be discharged. The goal of the district power management is therefore to respect the power limit while providing the best charging power for the vehicles. That is to say that the battery should be as charged as possible by the departure time of the vehicle. This objective function of each vehicle is named fi(Pi) with Pi the vehicle charging power. The future has to be anticipated because of the temporal coupling introduced by the batteries. Moreover the problem is stochastic as the vehicles are randomly moving. Within this case study, the non-flexible consumption is assumed to be perfectly forecasted and therefore deterministic. This assumption could be cleared by using a stochastic modeling, similar to the one used for the vehicles. The optimal management problem is the minimization of the expected total cost over a time horizon:

min 𝑃 𝑖 𝑡 0 𝐸 ( ∑ ∑ 𝑓 𝑖 (𝑃 𝑖 𝑡 ) 𝑁 𝑛=1 𝑇 𝑡=𝑡 0 ) such that for all t ∑ 𝑃 𝑖 𝑡 𝑁 𝑖=1 ≤ 𝑃 # (𝑡)

Resolution without information constraint

The previous problem is a sharing problem which could be written as: min 𝑥,𝑧 𝑓(𝑥) + 𝑔(𝑧) 𝑠. 𝑡. 𝑥 = 𝑧 where g is the indicator function of the set C = {∑ zi ≤ P # }. Such a problem can then be solved in an efficient way using the Alternating Direction Method of Multipliers ADMM [START_REF] Boyd | Distributed optimisation and statistical learning via the alternating direction method of multiplers[END_REF].

𝑥 𝑖 𝑘+1 ∶= argmin 𝑥 𝑖 𝑓 𝑖 (𝑥 𝑖 ) + 𝜌 2 ‖𝑥 𝑖 -𝑧 𝑖 𝑘 + 𝑢 𝑖 𝑘 ‖ 2 𝑧 𝑘 ∶= ∏ (𝑥 𝑘+1 + 𝑢 𝑘 )
𝐶 𝑢 𝑘+1 ∶= 𝑢 𝑘 + 𝑥 𝑘+1 -𝑧 𝑘+1 Along these iterations, each vehicle first decides its charging power to minimise its own individual cost plus a coordination term. As soon as all the vehicles decisions are gathered, this decision is projected on the feasible set C. Finally the equality constraint between x and z is enforced by updating the scaled dual variable u with a gradient descent.

Resolution with information constraint

On the basis of the previous resolution, the accessible information are reduced to two signals. The total consumption of the district can be measured at the substation level and it is therefore supposed to be accessible at any time. The dual variable value is the second signal that is necessary in the proposed resolution. As soon as the total consumption power is measured, it is possible to project it on the feasible set and to update the dual variable accordingly. Then this scalar value needs to be broadcasted to all the vehicles. This resolution framework meets with operational contexts where messages are sent to all agents at the same time [START_REF] Christakou | Primary voltage control in active distribution networks via broadcast signals: the case of distributed storage[END_REF]. The electrical grid itself can then be used to periodically send a value for instance by power line communication or broadband over powerline. With this limited exchange of information, these two values meet the operational feasibility and a sufficient coordination to carry out a resolution fulfilling the power constraintalthough the performance cannot be as good as in the unrestricted case. The proposed approach consists in substituting the iterations of the optimisation algorithm by real power exchanges with frequent broadcast of the dual variable. First each vehicle decides its optimal charging power on the basis of its own objectives and of the previous dual variable value. The optimal power is applied right away. At the substation level the total power of the district is measured and compared to the rated power. There is no guarantee that the rated power is always fulfilled. If not, a new value for the dual variable is computed and broadcasted. This resolution is similar to the iterations of ADMM algorithm except that real power exchange immediately enforced are used instead of iterated exchanges of information until convergence. The time step must then be much finer than in the unrestricted resolution.

OPTIMAL STRATEGY FOR A VEHICLE CHARGING POWER

The distributed resolution of the fleet charging requires that each vehicle is able to solve the problem of its own optimal charging taking into account the term coming from the coordination at the fleet scale:

min 𝑃 𝑖 𝐸 ( ∑ 𝑓 𝑖 (𝑃 𝑖 𝑡 ) + 𝜌 2 𝑇 𝑡=𝑡 0 ‖𝑃 𝑖 𝑡 -𝑧 𝑖 𝑘,𝑡 + 𝑢 𝑖 𝑘,𝑡 ‖ 2 )
The resolution of this problem has to be performed very often as at each time step, each vehicle must solve it at each iteration. This calls for a resolution using Stochastic Dynamic Programming SDP [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF]. The optimal strategy which will then be computed will contain the best decision for the charging strategy for all configuration of the state vector xi = (E # , SoC, τ, λ), where E # is the capacity of the vehicle battery, SoC is its state of charge, τ is the remaining duration before the vehicle departure, λ gathers the 𝑧 𝑖 𝑘 -𝑢 𝑖 𝑘 quantity. However, such a minimisation means to anticipate the future variations of the own vehiclewhich is possible if the departure time is supposed to be announced by the driverbut also the future values of the dual variable u and of the variable z. These quantities depend on the future state of the fleet which cannot be known as vehicles travels are stochastic. Therefore the evolution of the λ value is considered as a stochastic process which is modelled by an autoregressive model [START_REF] Barty | Decomposition of large scale stochastic optimal control problems[END_REF] The result is then a four dimension matrixas the state space has four dimensionswhich describes the best decision on a discretised grid of the state space. Such a behavior is achieved using extremely negative values of λ so that the coordination term prevails against its individual objectives. Symmetrically the last panel -Figure 1: Cross sectional views of the optimal strategy for the charging power right bottomis the case where the vehicle must consume a power as huge as possible, in the limit of its rated power and current state of charge. The two intermediate panels represent situations where the coordination term and the individual costs of the vehicle have a similar magnitude. The vehicle charging power is then modulated depending on the state of charge and the remaining time before departure: a vehicle with a nearly empty battery which must leave soon will have a greater charging power than a vehicle with a nearly full battery which has a long time before departure. The coordination term still brings a modulation of the charging strategy so as to find a compromise between the individual costs and the global constraint.

RESULTS AND DISCUSSION

Non flexible consumption profile

The case study is built on a distribution district whose substation has a rated power of 𝑃 𝑟𝑎𝑡𝑒𝑑 = 100𝑘𝑊. The temporal profile of Pconso is generated from historical data of electricity consumption in France, freely available from French TSO RTE [START_REF]Eco2mix: data of the 2015 year[END_REF]. These consumption profiles is aggregated at a country scale and gather domestic, industry and services consumption, which are very unlikely to be observed within the same distribution district. Nevertheless it provides a relevant context to assess the adaptation capacity of the proposed resolution.

Vehicle availability scenario

The mobility scenario of each vehicle within the fleet is randomly drawn from probability densities. For the battery capacity, it is built on the market shares of electric vehicles in 2014. The distributions of arrival and departure hours match a fleet which arrives in the morning and leaves in the evening [START_REF]les véhicules électriques en perspective[END_REF]. Finally the probability of the initial state of charge of the battery is deduced from the length of the last trip. These different values are only set from a statistical perspective and a 200 vehicle fleet is simulated over a year. When a vehicle is plugged to a charging station, its state vector is supposed to be known.

Temporal trajectories

Figure 2 presents temporal trajectories of the charging power of the fleet during a week. On the top panel, the maximum power that the vehicles can consume is in red.

In blue is the total power that is actually consumed. The evolution of the dual variable is presented on the middle panel. This dual variable can be seen as the energy price.

It is equal to zero when the constraint is not activated. Its value stands for the restriction that the vehicles undergo on their individual objectives so as to fulfil the global constraint. Because of the chosen mobility scenario, this pressure reaches its maximum during the morning. Finally the last panel shows the individual charging trajectories of each vehicle. It can be noticed that some vehicles can be temporary discharged for the benefit of others to make the most of the fleet interest. Resolution with information constraint When information exchanges are limited, the maximum power constraint cannot be fulfilled at all time. Figure 3 presents the trajectories that can be observed during a winter week and a summer week. In winter vehicle have less available power because of the greater non flexible consumption. The constraint is then more difficult to respect. Although the constraint is regularly violated, it can be noticed that the fleet reacts quickly to these violations and that the general pattern is respected. Moreover the violation amplitude can be significantly lowered by increasing the frequency of the dual variable update as presented in Table 1. The frequency of the violation cannot be set to zero because the possibility of a violation is not anticipated in the presented resolution. But the impact on the mean amplitude is very significant.

CONCLUSION

This study investigated the operational feasibility of a distributed optimisation algorithm for the control of an electric vehicle fleet. First the optimal charging of this fleet has been presented in order to meet a maximum power constraint. This distributed resolution was based on the Alternating Direction Method of Multipliers and Stochastic Dynamic Programming. As in many others distributed scheme, a bidirectional communication between each vehicle and a central agent is necessary. As such a communication may not be possible in a real application, the proposed resolution is then adapted using only two signals. The first one is the measure of the total powerwhich is supposed to be accessible in the district substation. The second one is a broadcast dual variablecomparable to an energy pricewhich is sent to all vehicles for instance through power line communication.

It is shown that the constraint shape is then roughly respected, although some violations may occur. The amplitude of these constraint violations can be put as low as required thanks to a more frequent update of the dual variable. This preliminary results are very hopeful for an operational distributed control of flexible loads.

2 +

 2 . The objective function fi takes into account battery losses, battery ageing and the vehicle mobility: 𝑓 𝑖 (𝑃 𝑖 ) ∶= ∑ (𝑓 𝑙𝑜𝑠𝑠 (𝑡) + 𝑓 𝑎𝑔𝑒 (𝑡) + 1 𝑡=𝑡 𝑑𝑒𝑝 𝑖 𝑓 𝑚𝑜𝑏 (𝑡)) 𝑇 𝑡= 𝑡 0 where floss and fage respectively compute the losses and the ageing of the battery, fmob stands for the user mobility cost and penalize any missing energy in the battery at the departure time tdep. They are computed with the following expressions: 𝑃 𝑙𝑜𝑠𝑠 = 𝛼 𝑙𝑜𝑠𝑠 𝑃(𝑡) 2 𝑑 𝑖 = 𝛼 𝑎𝑔𝑒 𝐷𝑜𝐷 𝛽 𝑎𝑔𝑒 𝐶 𝑚𝑜𝑏 = 𝛼 𝑚𝑜𝑏 (1 -𝑆𝑜𝐶) 2 A quadratic model is used for the losses. The battery ageing is assessed using the depth of discharge of the current cycle DoD and the mobility cost is a quadratic function depending on the state of charge. The resolution by SDP consists in the resolution of the Bellman equation: 𝐽 𝜏=0 * (𝑥) = 𝑓 𝑚𝑜𝑏 (𝑆𝑜𝐶) 𝐽 𝜏 * (𝑥 𝜏 ) = min 𝑃 𝑖 𝑓 𝑙𝑜𝑠𝑠 (𝑃 𝑖 ) + 𝑓 𝑎𝑔𝑒 (𝑃 𝑖 ) + 𝜌 2 ‖𝑃 𝑖 -𝜆‖ 𝐸 (𝐽 𝜏-∆𝑇 * (𝑓 𝑑𝑦𝑛 (𝑥 𝜏 , 𝑃 𝑖 )))

  Figure 1 presents cross sectional views of this strategy depending on the battery state of charge and of the remaining time before departure, for different values of λ and a fixed battery capacity 𝐸 # = 85𝑘𝑊ℎ. Iso-power curves are also plotted. The first panelleft-topstands for the situation when the fleet interest needs the vehicle to discharge at full power, no matter what is its individual situation.

Figure 2 :

 2 Figure 2: Trajectories of a fleet charging under a maximum power constraint

Figure 3 :

 3 Figure 3: Trajectories of a fleet charging when communication is restricted

Table 1 :

 1 Constraint violation depending on the frequency of the dual variable update

	Updates	Violation	Mean violation
	frequency	frequency	amplitude
	10min	34%	9kW
	5min	20%	5kW
	1min	12%	1.5kW
	30s	10%	0.7kW
	10s	9%	0.3kW
	5s	8%	0.1kW


Anaïs Durand

Michel Raynal

Gadi Taubenfeld

k-Set Agreement and Renaming in the Presence of Contention-Related Crash Failures

Keywords: Agreement algorithm, Asynchronous system, Atomic register, Concurrency, Contention, -Mutual exclusion, Participating process, Process crash failure, Read/write register, Renaming, k-Set agreement. 1 Definitions and Motivation 1.1 Processes, Failures, Communication

A new notion of process failure explicitly related to contention has recently been introduced by one of the authors (NETYS 2018). More precisely, given a predefined contention threshold λ, this notion considers the executions in which process crashes are restricted to occur only when process contention is smaller than or equal to λ. If crashes occur after contention bypassed λ, there are no correctness guarantees (e.g., termination is not guaranteed). It was shown that, when λ = n -1, consensus can be solved in an n-process asynchronous read/write system despite the crash of one process, thereby circumventing the well-known FLP impossibility result. Furthermore, it was shown that when λ = n -k and k ≥ 2, k-set agreement can be solved despite the crash of 2k -2 processes.

This paper considers two types of process crash failures: "λ-constrained" crash failures (as previously defined), and classical crash failures (that we call "any time" failures). It presents two algorithms suited to these types of failures. The first algorithm solves k-set agreement, where k = m+f , in the presence of t = 2m + f -1 crash failures, 2m of them being (n -k)-constrained failures, and (f -1) being any time failures. The second algorithm solves (n + f )-renaming in the presence of t = m + f crash failures, m of them being (n -t -1)-constrained failures, and f being any time failures. It follows that the differentiation between λ-constrained crash failures and any time crash failures enlarges the space of executions in which the impossibility of k-set agreement and renaming in the presence of asynchrony and process crashes can be circumvented. In addition to its behavioral properties, both algorithms have a noteworthy first class property, namely, their simplicity.

Let us call contention the current number of processes that started executing. The model parameter λ denotes a predefined contention threshold. So, an execution can be divided into two parts: a prefix in which the contention is ≤ λ and a suffix in which contention is > λ. Hence, we consider a failure model in which there are two types of crashes: the ones that can occur only when contention is ≤ λ that we call "λ-constrained", and the ones that can appear at "any time"; λ-constrained crashes were introduced in [START_REF] Taubenfeld | Weak failures: definition, algorithms, and impossibility results[END_REF] under the name "weak failures".

Motivation for Considering λ-Constrained Failures

As discussed in [START_REF] Taubenfeld | Weak failures: definition, algorithms, and impossibility results[END_REF], the new type of λ-constrained failures enables us to design algorithms that can tolerate several traditional "any time" failures plus several additional λ-constrained failures (i.e., weak failures). More precisely, assume that a problem can be solved in the presence of t traditional failures, but cannot be solved in the presence of t + 1 such failures. Yet, the problem might be solvable in the presence of t 1 ≤ t "any time" failures plus t 2 λ-constrained failures, where t 1 + t 2 > t.

Adding the ability to tolerate λ-constrained failures to algorithms that are already designed to circumvent various impossibility results, such as the Paxos algorithm [START_REF] Lamport | The part-time parliament[END_REF] and indulgent algorithms in general [START_REF] Guerraoui | Indulgent algorithms[END_REF][START_REF] Guerraoui | The information structure of indulgent consensus[END_REF], would make such algorithms even more robust against possible failures. An indulgent algorithm never violates its safety property, and eventually satisfies its liveness property when the synchrony assumptions it relies on are satisfied. An indulgent algorithm which in addition (to being indulgent) tolerates λ-constrained failures may, in many cases, satisfy its liveness property even before the synchrony assumptions it relies on are satisfied.

When facing a failure related impossibility result, such as the impossibility of consensus in the presence of a single faulty process [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF], one is often tempted to use a solution which guarantees no resiliency at all. We point out that there is a middle ground: tolerating λ-constrained (weak) failures enables to tolerate failures some of the time. Also, traditional t-resilient algorithms tolerate failures only some of the time (i.e., as long as the number of failures is at most t). After all, something is better than nothing.

The type of λ-constrained failures which are assumed to occur only before a specific predefined threshold on the level of contention is reached, is in particular useful in systems in which contention is usually low. Another possible type of weak failures, also defined in [START_REF] Taubenfeld | Weak failures: definition, algorithms, and impossibility results[END_REF], in which failures are assumed to occur only after a specific predefined threshold on the level of contention is reached, may correspond to a situation where, when there is high contention, processes are slowed down and as a result give up and abort.

Finally, the new failure model establishes a link between contention and failures, which enables us to better understand various known impossibility results, like the impossibility result for consensus [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF] and its generalizations [START_REF] Borowsky | Generalized FLP impossibility results for t-resilient asynchronous computations[END_REF][START_REF] Herlihy | The topological structure of asynchronous computability[END_REF][START_REF] Saks | Wait-free k-set agreement is impossible: the topology of public knowledge[END_REF].

High Level Objects

To make the presentation of the proposed algorithms easier, the basic read/write system is enriched with two types of objects, namely -mutual exclusion and snapshot. Both can be built on top of a crash-prone asynchronous read/write system. Deadlock-free -mutual exclusion. Such an object, which provides the processes with the operations acquire() and release(), allows up to of them to simultaneously execute their critical section. It is defined by the following properties.

• Mutual exclusion. No more than processes can simultaneously be in their critical section.

• Deadlock-freedom. If less than processes crash, and processes are invoking the operation acquire(), at least one of them will terminate its invocation.

It is shown in [START_REF] Afek | A bounded first-in, first-enabled solution to the -exclusion problem[END_REF][START_REF] Fischer | Resource allocation with immunity to limited process failure (Preliminary Report)[END_REF][START_REF] Taubenfeld | Synchronization algorithms and concurrent programming[END_REF] that -mutual exclusion can be built on top of an asynchronous crash-prone read/write system. In the one-shot version, a process invokes acquire() and release() at most once.

Snapshot.

A snapshot object provides two operations denoted write() and snapshot() [START_REF] Afek | Atomic snapshots of shared memory[END_REF][START_REF] Anderson | Multi-writer composite registers[END_REF]. Such an object can be seen as an array of single-writer multi-reader atomic register SN [1.

.n] such that: (a). when p i invokes write(v), it writes v into SN [i]; and (b). when p i invokes snapshot(), it obtains the value of the array SN [1.

.n] as if it read simultaneously and instantaneously all its entries. Said another way, the operations write() and snapshot() are atomic. Snapshot objects can be implemented on top of asynchronous crash-prone read/write systems [START_REF] Afek | Atomic snapshots of shared memory[END_REF][START_REF] Anderson | Multi-writer composite registers[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF].

2 k-Set Agreement and M -Renaming

k-Set Agreement

A k-set agreement (k-SA) object is a one-shot object introduced by S. Chaudhuri [START_REF] Chaudhuri | More choices allow more faults: set consensus problems in totally asynchronous systems[END_REF] to study the relation linking the number of failures and the agreement degree attainable in a set of crash-prone asynchronous processes. Such an object provides a single operation denoted propose(), which allows the invoking process to propose a value and obtain a result (called decided value). Assuming each correct process proposes a value, each process must decide on a value such that the following properties are satisfied.

• Validity. A decided value is a proposed value.

• Agreement. At most k different values are decided.

• Termination. Every correct process decides a value.

When k = 1, k-set agreement boils down to consensus, whose impossibility in the presence of asynchrony and a single process crashed was proved in [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF] for message-passing systems, and in [START_REF] Loui | Memory requirements for agreement among unreliable asynchronous processes[END_REF] for read/write systems. It was later shown in [START_REF] Borowsky | Generalized FLP impossibility results for t-resilient asynchronous computations[END_REF][START_REF] Herlihy | The topological structure of asynchronous computability[END_REF][START_REF] Saks | Wait-free k-set agreement is impossible: the topology of public knowledge[END_REF] that it is impossible to solve k-set agreement in crash-prone asynchronous read/write systems where t ≥ k. Hence, as the k-set agreement read/write-based algorithm presented in [START_REF] Taubenfeld | Weak failures: definition, algorithms, and impossibility results[END_REF] works despite up to t = 2k -2 λ-constrained failures (where λ = n -k), the introduction of contention-related failures in [START_REF] Taubenfeld | Weak failures: definition, algorithms, and impossibility results[END_REF], is a noteworthy advance in fault-tolerance, which enlarges the space of executions in which k-set agreement can be solved.

M-Renaming

The renaming object was introduced in the context of message-passing system [START_REF] Attiya | Renaming in an asynchronous environment[END_REF]. An introductory survey to renaming in crash-prone asynchronous read/write systems is presented in [START_REF] Castañeda | The renaming problem in shared memory systems: an introduction[END_REF].

An M -renaming object allows n processes with initially distinct names from a large name space to acquire distinct new names from a smaller name space {1, ..., M }, where M is a predefined value known by the processes. A one-shot renaming object allows each process to acquire a distinct new name just once. A long-lived renaming object allows processes to repeatedly acquire distinct names and release them. In this paper, we consider only one-shot renaming objects.

A process p i accesses an M -renaming object R using the operation R.rename(id i ), where id i is its original name, which returns a new name. A process p i knows neither its index i, nor the original names of the other processes. The properties defining such an object are the following.

• Validity. A new name belongs to the set {1, ..., M }.

• Agreement. No two processes obtain the same new name.

• Termination. If a process invokes R.rename(id) and does not crash, it returns from its invocation.

In the classical n-process model (i.e., a model where only any time crash failures are considered), it is known that with t any time failures, there is a tight (n + t) bound on the size of new name space for renaming for infinitely many values of n. We will show how this result can be circumvented. The interested reader will find renaming algorithms in textbooks such as [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF][START_REF] Taubenfeld | Synchronization algorithms and concurrent programming[END_REF].

The Results of the Paper at a Glance

As announced in the abstract, this paper is on k-set agreement and M -renaming in an asynchronous read/write model in which there are two kinds of process crashes:

• the "usual" ones, which are allowed to occur at any time, called "any time" failures in the following;

• the ones (introduced in [START_REF] Taubenfeld | Weak failures: definition, algorithms, and impossibility results[END_REF]) that are restricted to occur only while the contention has not bypassed a predefined threshold λ, called "λ-constrained" failures in the following.

As announced in the Introduction, let us recall that all the algorithms presented in the paper assume that all correct processes participate.

Results Concerning k-Set Agreement

The paper presents a general k-set agreement algorithm that, in addition to the model and problem parameters n, t, k, and

λ = n -k, considers two more integers m ≥ 0 and f ≥ 1, such that m + f = k and t = 2m + f -1 (or, equivalently, t = 2k -f -1)
. The fault-tolerance properties of this algorithm are summarized in Table 1.

The k-set agreement algorithm: Fault-tolerance properties total # of failures tolerated t = 2m + f -1 "λ-constrained" crash failures 2m

"any time" crash failures f -1

Table 1: k-Set agreement: tolerates crash failures with λ = n -k and k = m + f More generally, the parameters m and f , where k = m + f , can be seen as parameters allowing the user to tune the type of crash failures that are dominant in the considered application context. At one extreme, the pair of values m, f = 0, k maximizes the number of any time failures, and allows up to any time k -1 crash failures. At the other extreme, the pair m, f = k -1, 1 maximizes the number of λ-constrained failures: it allows up to 2k -2 λ-constrained failures and no any time failure. Since t = 2m + f -1 we can say that, intuitively, one any time failure "equals" two (n -k)constrained failures. That is, it is possible to trade one strong (any time) failure for two weak (λconstrained) failures and vice versa, as demonstrated in Table 2. Interestingly, the particular instantiation m, f = k -1, 1 boils down to a specific case of the algorithm described in [START_REF] Taubenfeld | Weak failures: definition, algorithms, and impossibility results[END_REF] 1 .

Additionally, as it will become clear in its description, Algorithm 1 presented in Section 4 sheds new light on a relation linking k-set agreement and -mutual exclusion

The k-set agreement algorithm: tradeoffs total # of failures

m = 0 m = k/2 m = k -1 t = 2m + f -1 f = k f = k/2 f = 1 2m "λ-constrained" crash failures 0 k 2k -2 f -1 "any time" crash failures k -1 k/2 -1 0
Table 2: k-Set agreement: tradeoffs "λ-constrained/any time" crash failures, with λ = n -k

Results Concerning M -Renaming

Considering a new name space of size M = n + f , the paper presents a general M -renaming algorithm that, in addition to the model and problem parameters n, t, and λ = n -t -1, as previously, considers two integers m ≥ 0 and f ≥ 0, such that t = m + f . The fault-tolerance properties of this algorithm are summarized in Table 3.

The (n + f )-renaming algorithm: Fault-tolerance properties total # of failures tolerated t = m + f "λ-constrained" crash failures m "any time" crash failures f

Table 3: M -Renaming: tolerated crash failures, with λ = n -t -1

Similarly to the case of k-set agreement, the parameters m and f , where t = m + f , allows the user to tune the type of crash failures and (here) the size of the name space that are dominant in the considered application context. At one extreme, the pair of values m, f = 0, t maximizes the number of any time failures (which is good) but also maximizes the size of the name space (which is bad). At the other extreme, the pair m, f = t, 0 maximizes the number of λ-constrained failures and minimizes the size of the name space (which is good). This is demonstrated in Table 4.

The (n + f )-renaming algorithm: Tradeoffs total # of failures m = 0 m = k/2 m = t t = m + f f = t f = k/2 f = 0 m "λ-constrained" crash failures 0 k/2 t f "any time" crash failures t k/2 0
The size of name space

n + t n + k/2 n
Table 4: M -Renaming: tradeoffs "λ-constrained/any time" crash failures, with λ = n -t -1

4 k-Set Agreement: Algorithm (k ≥ 2)
This section presents a k-set agreement algorithm that allows to circumvent the known impossibility result for solving k-set agreement in crash-prone asynchronous read/write systems where t ≥ k [START_REF] Borowsky | Generalized FLP impossibility results for t-resilient asynchronous computations[END_REF][START_REF] Herlihy | The topological structure of asynchronous computability[END_REF][START_REF] Saks | Wait-free k-set agreement is impossible: the topology of public knowledge[END_REF]. The algorithm considers the contention-related failure model, and assumes all correct processes participate. It is characterized by the following theorem.

Theorem 1. For any n ≥ 1, n -1 ≥ t ≥ 0, m ≥ 0 and f ≥ 1 such that t = 2m + f -1 and k = m + f , it is possible to solve k-set agreement for n processes in the presence of at most t crash failures, 2m of them being λ-constrained failures where λ = n -k, and f -1 of them being any time failures.

In the algorithm described below, it is assumed that the identity of a process p i is its index i.

Shared objects. The processes cooperate through the following objects.

• PART [1.

.n]: snapshot object, initialized to [down, • • • , down], used to indicate participation.

• DEC : atomic register initialized to ⊥ (a value which cannot be proposed). It will contain values (one at a time) that can be decided.

• MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF]: one-shot deadlock-free f -mutex object.

• MUTEX [START_REF] Afek | A bounded first-in, first-enabled solution to the -exclusion problem[END_REF]: one-shot deadlock-free m-mutex object.

For the special case where m = 0 and f = k, in the proposed algorithm no process will ever try to access the MUTEX [2] object. Thus, there is no need to define the notion of a 0-mutex object.

Local variables. Each process p i manages the following local variables: part i is used to locally store a copy of the snapshot object PART ; count i is a local counter; and group i a binary variable whose value belongs to {1, 2}.

Behavior of a process p i . Algorithm 1 describes the behavior of a process p i . When it invokes propose(in i ) (where in i is the value it proposes), p i first indicates it is participating (line 1). Then it invokes the snapshot object until at least n -t processes are participating (lines 2-4). When this occurs, p i enters group 1 or group 2 according to the value of its counter count i (line 5), and launches in parallel two threads T 1 and T 2 (line 6).

In the thread T 1, p i loop forever until DEC contains a proposed value. When this happens p i decides it (line 7). The execution of return() at line 7 or 12 terminates the invocation of propose().

The thread T 2 is the core of the algorithm. Process p i tries to enter the critical section controlled by either the f -mutex or the m-mutex object MUTEX [group i ] (line 9). If it succeeds and DEC has still its initial default value, p i assigns it the value in i it proposed (line 10). Finally, p i releases the critical section (line 11), and decides (line 12). Let us remind that, as far as MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF] (respectively, MUTEX [START_REF] Afek | A bounded first-in, first-enabled solution to the -exclusion problem[END_REF]) is concerned, up to f (respectively, m) processes can simultaneously execute line 10.

Remark. The reader can check that the line 8 (together with line 13) and line 11 can be suppressed without compromising the correctness of the algorithm. This is a side-effect of task T 1. For clarity, we nevertheless keep these lines. Algorithm 1: k-SA despite up to 2m "(n -k)-constrained" and f -1 "any time" failures Proof. Assume by contradiction that more than n -k processes have their counter less or equal to n -k when leaving the repeat loop (2-4). P being this set of processes, we have |P | ≥ n -k + 1. Moreover, let p i be the last process of P that invokes PART .snapshot() (line 1). It follows from the atomicity of the write() and snapshot() operations on the object PART that count i ≥ |P | ≥ n -k + 1, a contradiction. Lemma 2. In the presence of at most t = 2m + f -1 crash failures, 2m of them being (n -k)constrained, if processes participate in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF], at most f -1 of them can fail.

Proof. If a process p i participates in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF] it follows from line 5 that count i > n -k when it exited the repeat loop (lines 2-4). Thus, the contention was at least n -k + 1 when p i exited the loop and, due to the definition of "(n -k)-constrained crash failures", there is no more such failures. As t = 2m + f -1, it follows that, if processes participate in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF], at most f -1 of them can fail.

Theorem 2 (Termination). In the presence of at most t = 2m + f -1 crash failures, 2m of them being (n -k)-constrained, every correct process eventually terminates.

Proof. Since there is at most t processes that may fail and participation is required, at least n -t processes set their participating flag to up in the snapshot object PART (line 1). Thus, no correct process remains stuck forever in the repeat loop (lines 2-4).

First, assume m = 0. By Lemma 1, at most n -k processes have a counter less or equal to n -k when they exit the repeat loop (lines 2-4). Thus, at most n -k processes belong to group 2. If m = 0, there is n -t = n -f + 1 correct processes and, since k = f , n -f + 1 > n -k. So, among the processes participating in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF], at least one of them is correct and at most f -1 of them crash before returning from MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF].release() (line 11). Due to the deadlock-freedom property of the one-shot f -mutex object MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF], at least one correct process eventually enters its critical section and, if DEC has not already been written, writes its input into DEC . It then follows from task T 1 that, if it does not terminate at line 11, every other correct process will decide and terminate. Now, assume m > 0. There are two cases.

• If at least y ≥ f processes participate in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF], it follows from Lemma 2 that at most f -1 of them crash before returning from MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF].release() (line 11), and consequently all other processes participating in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF] are correct. As y > f -1 and f > 0, there is at least one such correct process, say p x . Due to the deadlock-freedom property of the one-shot f -mutex object MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF], p x eventually enters its critical section and, if DEC has not already been written, writes its input into DEC .

• Otherwise, less than f processes participate in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF]. There are two sub-cases.

-If a correct process p i participates in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF], it follows from this sub-case assumption and the deadlock-freedom property of the one-shot f -mutex object MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF], that p i eventually enters its critical section and, if DEC = ⊥, writes its input in x into this atomic register. -Otherwise, no correct process participates in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF]. By Lemma 1, at most n -k processes have a counter less or equal to n -k when they exit the repeat loop (lines 2-4). So at most n -k processes participate in MUTEX [START_REF] Afek | A bounded first-in, first-enabled solution to the -exclusion problem[END_REF]. Since no correct process participates in MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF], all correct processes (they are at least n -t) participate in MUTEX [START_REF] Afek | A bounded first-in, first-enabled solution to the -exclusion problem[END_REF]. Thus, at most

(n-k)-(n-t) = t-k = 2m+f -1-(m+f ) = m-1 processes that participate in MUTEX [2]
fail. Hence, due to the deadlock-freedom property of the one-shot m-mutex object MUTEX [START_REF] Afek | A bounded first-in, first-enabled solution to the -exclusion problem[END_REF], at least one correct process enters its critical section and, if DEC = ⊥, writes its input into DEC .

In both cases, every other correct process will decide and terminate.

Theorem 3 (Agreement and validity). At most k different values are decided, and each of them is the input of some process.

Proof. If a process decides (line 7 or line 12), it decides on the current value of DEC , which -due to the predicates of line 7 or line 10-has previously been set -at line 10-to the value proposed by a process. Due to the predicate and the assignment of DEC at line 10, and the fact that MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF] is a f -mutex object, it follows that at most f processes assign a value to DEC in the critical section controlled by MUTEX [START_REF] Afek | Atomic snapshots of shared memory[END_REF]. Due to a similar argument, at most m processes assign a value to DEC in the critical section controlled by MUTEX [START_REF] Afek | A bounded first-in, first-enabled solution to the -exclusion problem[END_REF]. Thus, at most m + f = k different values can be written into DEC , and each of them is a proposed value.

As its proof involves neither the timing nor the number of failures, Theorem 3 gives rise to the following property (called indulgence [START_REF] Guerraoui | Indulgent algorithms[END_REF][START_REF] Guerraoui | The information structure of indulgent consensus[END_REF]).

Corollary 1. Whatever the time occurrence and the number of crash failures, the k-set agreement and validity properties are never violated.

M -Renaming: Algorithm

This section presents a renaming algorithm that allows to circumvent the (n + t) tight bound on the size of name space for renaming for infinitely many values of n. This algorithm considers the contentionrelated failure model, and assumes all correct processes participate. It is characterized by the following theorem.

operation rename(id i ) is (1) PART .write(up);

(2) repeat part i ← PART .snapshot();

(3)

count i ← |{x such that part i [x] = up}| (4) until count i ≥ n -t end repeat; (5) new_name i ← RENAMING f .rename(id i ); (6) return(new_name i ).
Algorithm 2: (n + f )-renaming despite up to m "(n -t -1)-constrained" and f "any time" failures, where t = m + f Theorem 4. For any n ≥ 1, n -1 ≥ t ≥ 0, m ≥ 0 and f ≥ 0 such that t = m + f , it possible to solve (n + f )-renaming for n processes in the presence of at most t crash failures, m of them being λ-constrained failures where λ = n -t -1, and f of them being any time failures. Shared objects. The processes cooperate through the following objects.

• PART [1..n]: snapshot object, initialized to [down, • • • , down], used to indicate participation.

• RENAMING f : (n + f )-renaming object which can tolerate up to f any time crash failures for a model where participation is not required. The fact that participation is not required means that a process that does not participate is not consider faulty. The object is not assumed to tolerate any additional λ-constrained failures. An example of such an algorithm is described in [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] (pages 359-360).

Local variables. Each process p i manages the following local variables: part i is used to locally store a copy of the snapshot object PART ; count i is a local counter; id i and new_name i are used to store the original and new names, respectively.

Behavior of a process p i . Algorithm 2 describes the behavior of a process p i . Every process p i keeps on taking snapshots until it notices that n -t processes (including itself) are participating. Then, the process invokes a rename operation of a RENAMING f object, stores the value of its new name in new_name i , and returns this value.

7 M -Renaming: Proof Lemma 3. In the presence of at most t = m+f crash failures, m of them being (n-t-1)-constrained, if processes participate in RENAMING f , at most f of them can fail.

Proof. If a process p i participates in RENAMING f it follows from line 4 that the predicate count i ≥ n -t is satisfied when it exited the repeat loop (lines 2-4). Thus, the contention was at least n -t when p i exited the loop and, due to the definition of "(n -t -1)-constrained crash failures", there is no more such failures. As t = m + f , it follows that, if processes participate in RENAMING f , at most f of them can fail.

Theorem 5 (Termination). In the presence of at most t = m + f crash failures, m of them being (n -t -1)-constrained, every correct process eventually terminates.

Proof. Since there is at most t processes that may fail and participation is required, at least n -t processes set their participating flag to up in the snapshot object PART (line 1). Thus, no correct process remains stuck forever in the repeat loop (lines 2-4). By Lemma 3, if processes participate in RENAMING f , at most f of them can fail. Since, by definition, (1) RENAMING f can tolerate f any time failures, and (2) in RENAMING f participation is not required, it follows that every operation invoked by a correct processes on RENAMING f must return a value. Thus, every correct process eventually terminates.

Theorem 6 (Agreement and validity). In the presence of at most t = m + f crash failures, m of them being (n -t -1)-constrained, (1) no two processes decide on the same new name, and (2) the new names are in the range [1..n + f ].

Proof. By Lemma 3, at most f processes can fail while executing RENAMING f . Since, RENAMING f is an (n + f )-renaming object which can tolerate up to f crash failures for a model where participation is not required, any correct process that participates in RENAMING f must acquire a unique new name in the range [1..n + f ].

From M-Renaming to One-shot Concurrent Objects

Let us consider any one-shot concurrent object OB , which provides a single operation op(), and tolerate up to x any time crash failures in a model where participation is not required.

This section presents an algorithm that transforms OB in an object OB where, assuming all processes participate (i.e., invoke op()), allows to withstand additional λ-constrained crash failures. As in the previous sections, the transformation considers the parameters n, t, λ = n -t -1, m ≥ 0, and 0 ≤ f ≤ x -1. The fault-tolerance properties of the resulting object OB are summarized in Table 5 (where, let us remind, x is the number of any time crash failures tolerated by the underlying object OB ). total # of failures tolerated t = m + f "λ-constrained" crash failures m "any time" crash failures f ≤ x -1

Table 5: Crash failures tolerated by OB , where λ = n -t -1

As before, the parameters m and f are parameters that allow the user to tune the type of crash failures that are dominant in the considered application context. At one extreme, the pair of values m, f = t -x + 1, x -1 maximizes the number of any time failures, and allows up to x -1 any time crash failures. At the other extreme, the pair m, f = t, 0 maximizes the number of λ-constrained failures: it allows up to t λ-constrained failures and no any time failure. This is described in Table 6.

total # of failures

t = m + f m "λ-constrained" crash failures t -x + 1 t -x 2 t
f "any time" crash failures x -1

x 2 0 Table 6: Tradeoffs "λ-constrained/any time" crash failures (λ = n -t -1)

Algorithm 3 transforms of OB into OB . It is the same as Algorithm 2, which implements an Mrenaming object coping with both λ-constrained failures and any time failures. The meaning of the underlying shared objects and local variables are the same as in Algorithm 2. In addition, res i contains the result of the underlying invocation OB .op(in) (line 5), where in is the input parameter of op(). The proof, which is the same as the one given in Section 7, is left to the reader.

operation op(in) is % applied to OB (1) PART .write(up);

(2) repeat part i ← PART .snapshot();

(3) count i ← |{x such that part i [x] = up}| (4) until count i ≥ n -t end repeat;

(5) res i ← OB .op(in); (6) return(res i ).

Algorithm 3: Transformation of the operation op of a one-shot object tolerating up to m "(n -t -1)constrained" failures and f "any time" failures, where t = m + f

Conclusion

This paper addressed a process crash failure model in which some number of processes may crash only when process contention has not bypassed a predefined threshold λ, while another number of processes may crash at any time. It has been shown that this failure model allows impossibility results to be circumvented. To this end, the paper has presented algorithms building k-set agreement and renaming objects in such a model. So, it extends the set of possible executions in which k-set agreement and renaming can be solved despite asynchrony and process crashes. The proposed algorithms allow their users to tune them to specific failure-prone environments. This can be done by appropriately defining the pair of integers m, f . As an example, considering k-set agreement, these parameters control the number of crashes allowed to occur before the contention threshold λ = n -k is bypassed, namely 2m = 2(k -f ), and the number of failures which can occur at any time, namely, f -1. That is, it is possible to trade one strong "any time" failure for two weak "(n -k)-constrained" failures, and vice versa.

Finally, some issues remain challenging on the open problem side. More specifically, on the complexity/computability side of k-set agreement, it would be interesting to find out whether the upper bound we have proved on the number of failures t = 2m + f -1 (where 2m failures are (n -k)constrained and f -1 failures are any time failures) is tight for k ≥ 2. On the algorithm design side, as there is an algorithm (and a tight bound) for 1-agreement (see [START_REF] Taubenfeld | Weak failures: definition, algorithms, and impossibility results[END_REF]), it would be interesting to find a more general algorithm, i.e., an algorithm which works for k ≥ 1 (and not only for k ≥ 2).

  At most n -k processes have a counter less or equal to n -k when leaving the repeat loop (lines 2-4).operation propose(in i ) is (1) PART .write(up); (2) repeat part i ← PART .snapshot(); (3) count i ← |{x such that part i [x] = up}|; (4) until count i ≥ n -t end repeat; (5) if count i ≤ n -k then group i ← 2 else group i ← 1 end if;(6) launch in parallel the threads T 1 and T 2. % Both threads and the operation terminate when p i invokes return() (line 7 or 12).

	5 k-Set Agreement: Proof (7) loop forever if DEC = ⊥ then return(DEC ) end if end loop. thread T 2 is (8) if group i = 1 ∨ m > 0 then (9) MUTEX [group i ].acquire(); (10) if DEC = ⊥ then DEC ← in i end if; (11) MUTEX [group i ].release(); (12) return(DEC ). Lemma 1. thread T 1 is (13) end if;

It is proved in[START_REF] Taubenfeld | Weak failures: definition, algorithms, and impossibility results[END_REF] that for every two positive integers and k, there is a k-set agreement algorithm for n processes, using registers, that can tolerate + k -2 λ-constrained crash failures, where λ = n -. So, for the special case where = k, the algorithm can be tolerated

2k -2 (n -k)-constrained failures.

Acknowledgments

We thank Armando Castañeda for helpful discussions on the renaming problem. This work has been partially supported by the Franco-German DFG-ANR Project 40300781 DISCMAT (devoted to connections between mathematics and distributed computing), and the French ANR project ANR-16-CE40-0023-03 DESCARTES (devoted to layered and modular structures in distributed computing). Last but not least, the authors also thank the referees for their constructive comments.