Adam Shimi
email: adam.shimi@irit.fr

Aurélie Hurault
email: aurelie.hurault@irit.fr

Philippe Queinnec
email: philippe.queinnec@irit.fr

Derivation of Heard-of Predicates from Elementary Behavioral Patterns

Keywords: Message-passing, Asynchronous rounds, Failures

There are many models of distributed computing, and no unifying mathematical framework for considering them all. One way to sidestep this issue is to start with simple communication and fault models, and use them as building blocks to derive the complex models studied in the field. We thus define operations like union, succession or repetition, which makes it easier to build complex models from simple ones while retaining expressivity.

To formalize this approach, we abstract away the complex models and operations in the Heard-Of model. This model relies on (possibly asynchronous) rounds; sequence of digraphs, one for each round, capture which messages sent at a given round are received before the receiver goes to the next round. A set of sequences, called a heard-of predicate, defines the legal communication behaviors -that is to say, a model of communication. Because the proposed operations behave well with this transformation of operational models into heard-of predicates, we can derive bounds, characterizations, and implementations of the heard-of predicates for the constructions.

Introduction

Motivation

Let us start with a round-based distributed algorithm; such an algorithm is quite common in the literature, especially in fault-tolerant settings. We want to formally verify this algorithm using the methods of our choice: proof-assistant, model-checking, inductive invariants, abstract interpretation. . . But how are we supposed to model the context in which the algorithm will run? Even a passing glance at the distributed computing literature shows a plethora of models defined in the mixture of english and mathematics.

Thankfully, there are formalisms for abstracting round-based models of distributed computing. One of these is the Heard-Of model of Charron-Bost and Schiper [START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF]; it boils down the communication model to a description of all accepted combinations of received messages. Formally, this is done by considering communications graphs, one for each round, and taking the sets of infinite sequences of graphs that are allowed by the model. Such a set is called a heard-of predicate, and captures a communication model.

An angle of attack for verification is therefore to find the heard-of predicate corresponding to a real-world environment, and use the techniques from the literature to verify an algorithm for this heard-of predicate. But which heard-of predicate should be used? What is the "right" predicate for a given environment? For some cases, the predicates are given in Charron-Bost and Schiper [START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF]; but this does not solve the general case.

Actually, the answer is quite subtle. This follows from a fundamental part of the Heard-Of model: communication-closedness [START_REF] Elrad | Decomposition of distributed programs into communicationclosedlayers[END_REF]. This means that for p to use a message from q at round r, p must receive it before or during its own round r. And thus, knowing whether p receives the message from q at the right round or not depends on how p waits for messages. That is, it depends on the specifics of how rounds are implemented on top of it.

Once again, the literature offers a solution: Shimi et al. [START_REF] Shimi | Characterizing asynchronous message-passing models through rounds[END_REF] propose to first find a delivered predicate -a description of which messages will eventually be delivered, without caring about rounds -, and then to derive the heard-of predicate from it. This derivation explicitly studies strategies, the aforementioned rules for how processes waits for messages before changing round.

But this brings us back to square one: now we are looking for the delivered predicate corresponding to a real-world model, instead of the heard-of predicate. Basic delivered predicates for elementary failures are easy to find, but delivered predicates corresponding to combinations of failures are often not intuitive.

In this paper, we propose a solution to this problem: building a complex delivered predicate from simpler ones we already know. For example, consider a system where one process can crash and may recover later, and another process can definitively crash. The delivered predicate for at most one crash is P Del crash 1 , and the predicate where all the messages are delivered is P Del total . Intuitively, a process that can crash and necessarily recover is described by the behavior of P Del crash 1 followed by the behavior of P Del total . We call this the succession of these predicates, and write it P Del recover 1 P Del crash 1 P Del total . In our system, the crashed process may never recover: hence we have either the behavior of P Del recover 1 or the behavior of P Del crash

1

. This amounts to a union (or a disjunction); we write it P Del canrecover

1 P Del recover 1 ∪ P Del crash 1 .
Finally, we consider a potential irremediable crash, additionally to the previous predicate. Thus we want the behavior of P Del crash ). In the following, we will also introduce an operator ω to express repetition. For example, a system where, repeatedly, a process can crash and recover is (P Del crash

1 P Del total ) ω .
Lastly, the analysis of the resulting delivered predicate can be bypassed: its heard-of predicate arises from our operations applied to the heard-of predicates of the elementary building blocks.

Related Work

The heard-of model was proposed by Charron-Bost and Schiper [START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF] as a combination of the ideas of two previous work. First, the concept of a fault model where the only information is which message arrives, from Santoro and Widmayer [START_REF] Santoro | Time is not a healer[END_REF]; and second, the idea of abstracting failures in a round per round fashion, from Gafni [START_REF] Gafni | Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony[END_REF]. Replacing the operational fault detectors of Gafni with the fault model of Santoro and Widmayer gives the heard-of model.

This model was put to use in many ways. Obviously computability and complexity results were proven: new algorithms for consensus in the original paper by Charron-Bost and Schiper [START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF]; characterizations for consensus solvability by Coulouma et al. [START_REF] Coulouma | A characterization of oblivious message adversaries for which consensus is solvable[END_REF] and Nowak et al. [START_REF] Nowak | Topological characterization of consensus under general message adversaries[END_REF]; a characterization for approximate consensus solvability by Charron-Bost et al. [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: the role of averaging algorithms[END_REF]; a study of k set-agreement by Biely et al. [START_REF] Biely | Gracefully degrading consensus and k-set agreement in directed dynamic networks[END_REF]; and more.

The clean mathematical abstraction of the heard-of model also works well with formal verification. The rounds provide structure, and the reasoning can be less operational than in many distributed computing abstractions. We thus have a proof assistant verification of consensus algorithms in Charron-Bost et al. [START_REF] Charron-Bost | Formal verification of consensus algorithms tolerating malicious faults[END_REF]; cutoff bounds for the model checking of consensus algorithms by Marić et al. [START_REF] Marić | Cutoff bounds for consensus algorithms[END_REF]; a DSL to write code following the structure of the heard-of model and verify it with inductive invariants by Drȃgoi et al. [START_REF] Drȃgoi | PSync: a partially synchronous language for fault-tolerant distributed algorithms[END_REF]; and more.

Contributions

The contributions of the paper are:

-A definition of operations on delivered predicates and strategies, as well as examples using them in Sect. 2. -The study of oblivious strategies, the strategies only looking at messages for the current round, in Sect. 3. We provide a technique to extract a strategy dominating the oblivious strategies of the built predicate from the strategies of the initial predicates; exact computations of the generated heard-of predicates; and a sufficient condition on the building blocks for the result of operations to be dominated by an oblivious strategy. -The study of conservative strategies, the strategies looking at everything but messages from future rounds, in Sect. 4. We provide a technique to extract a strategy dominating the conservative strategies of the build predicate from the strategies of the initial predicates; upper bounds on the generated heardof predicates; and a sufficient condition on the building blocks for the result of operations to be dominated by a conservative strategy.

Due to size constraints, many of the complete proofs are not in the paper itself, and can be found in the full paper [START_REF] Shimi | Derivation of heard-of predicates from elementary behavioral patterns[END_REF].

Basic Concepts

We start by providing basic definitions and intuitions. The model we consider proceed by rounds, where processes send messages tagged with a round number, wait for some messages with this round number, and then compute the next state and increment the round number. N * denotes the non-zero naturals.

Definition 1 (Collections and Predicates). Let Π a set of processes. An element of (N * × Π) → P(Π) is either a Delivered collection c or a Heard-Of collection h for Π, depending on the context. c tot is the total collection such that ∀r > 0, ∀p ∈ Π : c tot (r, p) = Π.

An element of P((N * × Π) → P(Π)) is either a Delivered predicate P Del or a Heard-Of predicate P HO for Π. P tot = {c tot } is the total delivered predicate.

For a heard-of collection h, h(r, p) are the senders of messages for round r that p has received at or before its round r, and thus has known while at round r. For a delivered collection c, c(r, p) are the senders of messages for round r that p has received, at any point in time. Some of these messages may have arrived early, before p was at r, or too late, after p has left round r. c gives an operational point of view (which messages arrive), and h gives a logical point of view (which messages are used).

Remark 1. We also regularly use the "graph-sequence" notation for a collection c. Let Graphs Π be the set of graphs whose nodes are the elements of Π. A collection gr is an element of (Graphs Π ) ω . We say that c and gr represent the same collection when ∀r > 0, ∀p ∈ Π : c(r, p) = In gr[r] (p), where In(p) is the incoming vertices of p. We will usually not define two collections but use one collection as both kind of objects; the actual type being used in a particular expression can be deduced from the operations on the collection. For example c[r] makes sense for a sequence of graphs, while c(r, p) makes sense for a function.

In an execution, the local state of a process is the pair of its current round and all the received messages up to this point. We disregard any local variable, since our focus is on which messages to wait for. A message is represented by a pair round, sender . For a state q, and a round r > 0, q(r) is the set of peers from which the process has received a message for round r.

Definition 2 (Local State). Let Q = N * × P(N * × Π). Then q ∈ Q is a local state.
For q = r, mes , we write q.round for r, q.mes for mes and ∀i > 0 :

q(i) {k ∈ Π | i, k ∈ q.mes}.
We then define strategies, which constrain the behavior of processes. A strategy is a set of states from which a process is allowed to change round. It captures rules like "wait for at least F messages from the current round", or "wait for these specific messages". Strategies give a mean to constrain executions. Definition 3 (Strategy). f ∈ P(Q) is a strategy.

Definition of Operations

We can now define operations on predicates and their corresponding strategies. The intuition behind these operations is the following:

-The union of two delivered predicates is equivalent to an OR on the two communication behaviors. For example, the union of the delivered predicate for one crash at round r and of the one for one crash at round r + 1 gives a predicate where there is either a crash at round r or a crash at round r + 1. -The combination of two behaviors takes every pair of collections, one from each predicate, and computes the intersection of the graphs at each round. Meaning, it adds the loss of messages from both, to get both behaviors at once. For example, combining P Del crash 1 with itself gives P Del crash 2 , the predicate with at most two crashes. Although combination intersects graphs round by round in a local fashion, it actually combines two collections globally, and thus can combine several global predicates like hearing from a given number of process during the whole execution.

-For succession, the system starts with one behavior, then switch to another.

The definition is such that the first behavior might never happen, but the second one must appear. -Repetition is the next logical step after succession: instead of following one behavior with another, the same behavior is repeated again and again. For example, taking the repetition of at most one crash results in a potential infinite number of crash-and-restart, with the constraint of having at most one crashed process at any time.

Definition 4 (Operations on predicates). Let P 1 , P 2 be two delivered or heard-of predicates.

-The union of P 1 and P 2 is P 1 ∪ P 2 .

-The combination

P 1 P 2 {c 1 c 2 | c 1 ∈ P 1 , c 2 ∈ P 2 }, where for c 1 and c 2 two collections, ∀r > 0, ∀p ∈ Π : (c 1 c 2 )(r, p) = c 1 (r, p) ∩ c 2 (r, p). -The succession P 1 P 2 c 1 ∈P 1 ,c 2 ∈P 2 c 1 c 2 , with c 1 c 2 {c | ∃r ≥ 0 : c = c 1 [1, r].c 2 }. -The repetition of P 1 , (P 1 ) ω {c | ∃(c i ) i∈N * , ∃(r i ) i∈N * : r 1 = 0 ∧ ∀i ∈ N * : (c i ∈ P 1 ∧ r i < r i+1 ∧ c[r i + 1, r i+1 ] = c i [1, r i+1 -r i ])}.
For all operations on predicates, we provide an analogous one for strategies. We show later that strategies for the delivered predicates, when combined by the analogous operation, retain important properties on the result of the operation on the predicates. Definition 5 (Operations on strategies). Let f 1 , f 2 be two strategies.

-Their union f 1 ∪ f 2 the strategy such that ∀q a local state:

(f 1 ∪ f 2 )(q) f 1 (q) ∨ f 2 (q). -Their combination f 1 f 2 {q 1 q 2 | q 1 ∈ f 1 ∧ q 2 ∈ f 2 ∧ q 1 .round = q 2 .
round}, where for q 1 and q 2 at the same round r, q

1 q 2 r{ r ′ , k | r ′ > 0 ∧ k ∈ q 1 (r ′ ) ∩ q 2 (r ′ )} -Their succession f 1 f 2 f 1 ∪ f 2 ∪ {q 1 q 2 | q 1 ∈ f 1 ∧ q 2 ∈ f 2 } where q 1 q 2 q 1 .round + q 2 .round, r, k | r > 0 ∧ k ∈ q 1 (r) if r ≤ q 1 .round k ∈ q 2 (r -q 1 .round) if r > q 1 .round -The repetition of f 1 , f ω 1 {q 1 q 2 ... q k | k ≥ 1 ∧ q 1 , q 2 , ..., q k ∈ f 1 }.
The goal is to derive new strategies for the resulting model by applying operations on strategies for the starting models. This allows, in some cases, to bypass strategies, and deduce the Heard-Of predicate for a given Delivered predicate from the Heard-Of predicates of its building blocks.

Executions and Domination

Before manipulating predicates and strategies, we need to define what is an execution: a specific ordering of events corresponding to a delivered collection. An execution is an infinite sequence of either delivery of messages (deliver(r, p, q)), change to the next round (next j ), or a deadlock (stop). Message sending is implicit after every change of round. An execution must satisfy three rules: no message is delivered before it is sent, no message is delivered twice, and once there is a stop, the rest of the sequence can only be stop. Definition 6 (Execution). Let Π be a set of n processes. Let the set of transitions T = {next j | j ∈ Π} ∪ {deliver(r, k, j) | r ∈ N * ∧ k, j ∈ Π} ∪ {stop}. next j is the transition for j changing round, deliver(r, k, j) is the transition for the delivery to j of the message sent by k in round r, stop models a deadlock. Then, t ∈ T ω is an execution

-(Delivery after sending) ∀i ∈ N : t[i] = deliver(r, k, j) =⇒ card({l ∈ [0, i[| t[l] = next k }) ≥ r -1 -(Unique delivery) ∀ r, k, j ∈ (N * × Π × Π) : card({i ∈ N | t[i] = deliver(r, k, j)}) ≤ 1 -(Once stopped, forever stopped) ∀i ∈ N : t[i] = stop =⇒ ∀j ≥ i : t[j] = stop
Let c be a delivered collection. Then, execs(c), the executions of c

       t an execution ∀ r, k, j ∈ N * × Π × Π : (k ∈ c(r, j) ∧ card({i ∈ N | t[i] = next k }) ≥ r -1) ⇐⇒ (∃i ∈ N : t[i] = deliver(r, k, j))       
For a delivered predicate PDel, execs(P Del) {execs(c) | c ∈ P Del}. Let t be an execution, p ∈ Π and i ∈ N. The state of p in t after i transitions is

q t p [i] card({l < i | t[l] = next p }) + 1, { r, k | ∃l < i : t[l] = deliver(r, k, p)} )
Notice that such executions do not allow process to "jump" from say round 5 to round 9 without passing by the rounds in-between. The reason is that the Heard-Of model does not give processes access to the decision to change rounds: processes specify only which messages to send depending on the state, and what is the next state depending on the current state and the received messages.

Also, the only information considered here is the round number and the received messages. This definition of execution disregards the message contents and the internal states of processes, as they are irrelevant to the implementation of Heard-Of predicates.

Recall that strategies constrain when processes can change round. Thus, the executions that conform to a strategy change rounds only when allowed by it, and do it infinitely often if possible.

Definition 7 (Executions of a Strategy). Let f be a strategy and t an execution. t is an execution of f t satisfies:

-(All nexts allowed) ∀i ∈ N, ∀p ∈ Π : (t[i] = next p =⇒ q t p [i] ∈ f ) -(Fairness) ∀p ∈ Π : card({i ∈ N | t[i] = next p }) < ℵ 0 =⇒ card({i ∈ N | q t p [i] / ∈ f }) = ℵ 0 For a delivered predicate PDel, execs f (PDel) {t ∈ execs(PDel) | t is an execution of f }.
The fairness property can approximately be expressed in LTL as ∀p ∈ Π : ♦ (q t p ∈ f ) ⇒ ♦next p . Note however that executions are here defined as sequences of transitions, whereas LTL models are sequences of states.

An important part of this definition considers executions where processes cannot necessarily change round after each delivery. That is, in the case of "waiting for at most F messages", an execution where more messages are delivered than F at some round is still an execution of the strategy. This hypothesis captures the asynchrony of processes, which are not always scheduled right after deliveries. It is compensated by a weak fairness assumption: if a strategy forever allows the change of round, it must eventually happen.

Going back to strategies, not all of them are equally valuable. In general, strategies that block forever at some round are less useful than strategies that don't -they forbid termination in some cases. The validity of a strategy captures the absence of such an infinite wait.

Definition 8 (Validity).

An execution t is valid ∀p ∈ Π : card({i ∈ N | t[i] = next p }) = ℵ 0 .
Let PDel a delivered predicate and f a strategy. f is a valid strategy for PDel ∀t ∈ execs f (P Del) : t is a valid execution.

Because in a valid execution no process is ever blocked at a given round, there are infinitely many rounds. Hence, the messages delivered before the changes of round uniquely define a heard-of collection.

Definition 9 (Heard-Of Collection of Executions and Heard-Of Predicate of Strategies). Let t be a valid execution. h

t is the heard-of collection of t ∀r ∈ N * , ∀p ∈ Π : h t (r, p) =    k ∈ Π ∃i ∈ N :   q t p [i].round = r ∧ t[i] = next p ∧ r, k ∈ q t p [i].mes    



Let P Del be a delivered predicate, and f be a valid strategy for P Del. We write P HO f (PDel) for the heard-of predicate composed of the collections of the executions of f on PDel:

P HO f (PDel) {h t | t ∈ execs f (PDel)}.
Lastly, the heard-of predicate of most interest is the strongest one that can be generated by a valid strategy on the delivered predicate. Here strongest means the one that implies all the other heard-of predicates that can be generated on the same delivered predicate. The intuition boils down to two ideas:

-The strongest predicate implies all the heard-of predicates generated on the same P Del, and thus it characterizes them completely. -When seeing predicates as sets, implication is the reverse inclusion. Hence the strongest predicate is the one included in all the others. Less collections means more constrained communication, which means a more powerful model.

This notion of strongest predicate is formalized through an order on strategies and their heard-of predicates.

Definition 10 (Domination). Let PDel be a delivered predicate and let f and f ′ be two valid strategies for PDel. f dominates f ′ for PDel, written f ′ ≺ PDel f , P HO f ′ (PDel) ⊇ P HO f (PDel).

A greatest element for ≺ PDel is called a dominating strategy for PDel. Given such a strategy f , the dominating predicate for PDel is P HO f (PDel).

Examples

We now show the variety of models that can be constructed from basic building blocks. Our basic blocks are the model P Del total with only the collection c total where all the messages are delivered, and the model P Del crash 1,r with at most one crash that can happen at round r.

Definition 11 (At most 1 crash at round r). P crash

1,r        c a delivered collection ∃Σ ⊆ Π : |Σ| ≥ n -1 ∧ ∀j ∈ Π   ∀r ′ ∈ [1, r[: c(r ′ , j) = Π ∧ c(r, j) ⊇ Σ ∧ ∀r ′ ≥ r : c(r ′ , j) = Σ          .
From this family of predicates, various predicates can be built. Table 1 show some of them, as well as the Heard-Of predicates computed for these predicates based on the results from Sect. 3.3 and Sect. 3.4. For example the predicate with at most one crash P crash 1 If a crash happens, it happens at one specific round r. We can thus build P crash 1 from a disjunction for all values of r of the predicate with at most one crash at round r; that is, by the union of P crash 1,r for all r.

Table 1. A list of delivered predicate built using our operations, and their corresponding heard-of predicate. The HOProduct operator is defined in Definition 16.

Description Expression HO Proof

At most 1 crash

P crash 1 = ∞ i=1 P crash 1,i HOProd({T ⊆ Π | |T | ≥ n -1}) [12]
At most

F crashes P crash F = F j=1 P crash 1 HOProd({T ⊆ Π | |T | ≥ n -F }) [12]
At most 1 crash, which will restart

P recover 1 = P crash 1 P total HOProd({T ⊆ Π | |T | ≥ n -1}) Theorem 4
At most F crashes, which will restart

P recover F = F j=1 P recover 1 HOProd({T ⊆ Π | |T | ≥ n -F }) Theorem 4
At most 1 crash, which can restart

P canrecover 1 = P recover 1 ∪ P crash 1 HOProd({T ⊆ Π | |T | ≥ n -1}) Theorem 4
At most F crashes, which can restart

P canrecover F = F j=1 P canrecover 1 HOProd({T ⊆ Π | |T | ≥ n -F }) Theorem 4
No bound on crashes and restart, with only 1 crash at a time

P recovery 1 = (P crash 1 ) ω HOProd({T ⊆ Π | |T | ≥ n -1}) Theorem 4
No bound on crashes and restart, with max F crashes at a time

P recovery F = F j=1 P recovery 1 HOProd({T ⊆ Π | |T | ≥ n -F }) Theorem 4
At most 1 crash, after round r

P crash 1,≥r = ∞ i=r P crash 1,i ⊆ HOProd({T ⊆ Π | |T | ≥ n -1}) Theorem 10
At most F crashes, after round r

P crash F,≥r = ∞ i=r P crash F,i ⊆ HOProd({T ⊆ Π | |T | ≥ n -F }) Theorem 10
At most F crashes with no more than one per round

P crash = F = i 1 =i 2 ... =i F F j=1 P crash 1,i j ⊆ HOProd({T ⊆ Π | |T | ≥ n -F }) Theorem 10

Families of Strategies

Strategies as defined above are predicates on states. This makes them incredibly expressive; on the other hand, this expressivity creates difficulty in reasoning about them. To address this problem, we define families of strategies. Intuitively, strategies in a same family depend on a specific part of the state -for example the messages of the current round. Equality of these parts of the state defines an equivalence relation; the strategies of a family are strategies on the equivalence classes of this relation.

Definition 12 (Families of strategies). Let ≈: Q × Q → bool. The family of strategies defined by ≈, f amily(≈) {f a strategy | ∀q 1 , q 2 ∈ Π :

q 1 ≈ q 2 =⇒ (q 1 ∈ f ⇐⇒ q 2 ∈ f )}.

Oblivious Strategies

The simplest non-trivial strategies use only information from the messages of the current round. These strategies that do not remember messages from previous rounds, do not use messages in advance from future rounds, and do not use the round number itself. These strategies are called oblivious. They are simple, the Heard-Of predicates they implement are relatively easy to compute, and they require little computing power and memory to implement. Moreover, many examples above are dominated by such a strategy. Of course, there is a price to pay: oblivious strategies tend to be coarser than general ones.

Minimal Oblivious Strategy

An oblivious strategy is defined by the different subsets of Π from which it has to receive a message before allowing a change of round.

Definition 13 (Oblivious Strategy). Let obliv be the function such that ∀q ∈ Q : obliv(q) = {k ∈ Π | q.round, k ∈ q.mes}. Let ≈ obliv the equivalence relation defined by q 1 ≈ obliv q 2 obliv(q 1 ) = obliv(q 2 ). The family of oblivious strategies is f amily(≈ obliv ). For f an oblivious strategy, let Nexts f {obliv(q) | q ∈ f }. It uniquely defines f . We will focus on a specific strategy, that dominates the oblivious strategies for a predicate. This follows from the fact that it waits less than any other valid oblivious strategy for this predicate.

Definition 14 (Minimal Oblivious Strategy). Let P Del be a delivered predicate. The minimal oblivious strategy for P Del is f min {q | ∃c ∈ P Del, ∃p ∈ Π, ∃r > 0 : obliv(q) = c(r, p)}.

Lemma 1 (Domination of Minimal Oblivious Strategy). Let P Del be a PDel and f min be its minimal oblivious strategy. Then f min is a dominating oblivious strategy for P Del.

Proof (Proof idea). f min is valid, because for every possible set of received messages in a collection of P Del, it accepts the corresponding oblivious state by definition of minimal oblivious strategy. It is dominating among oblivious strategies because any other valid oblivious strategy must allow the change of round when f min does it: it contains f min . If an oblivious strategy does not contain f min , then there is a collection of P Del in which at a given round, a certain process might receive exactly the messages for the oblivious state accepted by f min and not by f . This entails that f is not valid.

Operations Maintain Minimal Oblivious Strategy

As teased above, minimal oblivious strategies behave nicely under the proposed operations. That is, they give minimal oblivious strategies of resulting delivered predicates. One specificity of minimal oblivious strategies is that there is no need for the succession operation on strategies, nor for the repetition. An oblivious strategy has no knowledge about anything but the messages of the current round, and not even its round number, so it is impossible to distinguish a union from a succession, or a repetition from the initial predicate itself.

Theorem 1 (Minimal Oblivious Strategy for Union and Succession).

Let P Del 1 , P Del 2 be two delivered predicates, f 1 and f 2 the minimal oblivious strategies for, respectively, P Del 1 and P Del 2 . Then f 1 ∪ f 2 is the minimal oblivious strategy for P Del 1 ∪ P Del 2 and P Del 1 P Del 2 .

Proof (Proof idea). Structurally, all proofs in this section consist in showing equality between the strategies resulting from the operations and the minimal oblivious strategy for the delivered predicate. For a union, the messages that can be received at each round are the messages that can be received at each round in the first predicate or in the second. This is also true for succession. Given that f 1 and f 2 are the minimal oblivious strategies of P Del 1 and P Del 2 , they accept exactly the states with one of these sets of current messages. And thus f 1 ∪ f 2 is the minimal oblivious strategy for P Del 1 ∪ P Del 2 and P Del 1 P Del 2 .

Theorem 2 (Minimal Oblivious Strategy for Repetition). Let P Del be a delivered predicate, and f be its minimal oblivious strategy. Then f is the minimal oblivious strategy for P Del ω .

Proof (Proof idea). The intuition is the same as for union and succession. Since repetition involves only one PDel, the sets of received messages do not change and f is the minimal oblivious strategy.

For combination, a special symmetry hypothesis is needed.

Definition 15 (Totally Symmetric PDel). Let P Del be a delivered predicate. P Del is totally symmetric ∀c ∈ P Del, ∀r > 0, ∀p ∈ Π, ∀r ′ > 0, ∀q ∈ Π, ∃c ′ ∈ P Del : c(r, p) = c ′ (r ′ , q)

Combination is different because combining collections is done round by round. As oblivious strategies do not depend on the round, the combination of oblivious strategies creates the same combination of received messages for each round. We thus need these combinations to be independent of the roundto be possible at each round -to reconcile those two elements.

Theorem 3 (Minimal Oblivious Strategy for Combination). Let P Del 1 , P Del 2 be two totally symmetric delivered predicates, f 1 and f 2 the minimal oblivious strategies for, respectively, P Del 1 and P Del 2 . Then f 1 f 2 is the minimal oblivious strategy for P Del 1 P Del 2 .

Proof (Proof idea). The oblivious states of P Del 1 P Del 2 are the combination of an oblivious state of P Del 1 and of one of P Del 2 at the same round, for the same process. Thanks to total symmetry, this translates into the intersection of any oblivious state of P Del 1 with any oblivious state of P Del 2 . Since f 1 and f 2 are the minimal oblivious strategy, they both accept exactly the oblivious states of P Del 1 and P Del 2 respectively. Thus, f 1 f 2 accept all combinations of oblivious states of P Del 1 and P Del 2 , and thus is the minimal oblivious strategy of P Del 1 P Del 2 .

1 and the behavior of P Del canrecover 1 . 1 P Del canrecover 1 1 ((P Del crash 1 P

 111111 We call it the combination (or conjunction) of these predicates, and write it P Del crashThe complete system is thus described by P Del crash Del total ) ∪ P Del crash 1

Computing Heard-of Predicates

The computation of the heard-of predicate generated by an oblivious strategy is easy thanks to a characteristic of this HO: it is a product of sets of possible messages.

Definition 16 (Heard-Of Product). Let S ⊆ P(Π). The heard-of product generated by S, HOP rod(S) {h | ∀p ∈ Π, ∀r > 0 : h(r, p) ∈ S}.

Lemma 2 (Heard-Of Predicate of an Oblivious Strategy). Let P Del be a delivered predicate containing c tot and let f be a valid oblivious strategy for P Del. Then PHO f (P Del) = HOProd(Nexts f ).

Proof. Proved in [START_REF] Shimi | Characterizing asynchronous message-passing models through rounds[END_REF]Theorem 20,Section 4.1].

Thanks to this characterization, the heard-of predicate generated by the minimal strategies for the operations is computed in terms of the heard-of predicate generated by the original minimal strategies.

Theorem 4 (Heard-Of Predicate of Minimal Oblivious Strategies). Let P Del, P Del 1 , P Del 2 be delivered predicates containing c tot . Let f, f 1 , f 2 be their respective minimal oblivious strategies. Then:

Proof (Proof idea). We apply Lemma 2. The containment of c tot was shown in the proof of Theorem 5. As for the equality of the oblivious states, it follows from the intuition in the proofs of the minimal oblivious strategy in the previous section.

Domination by an Oblivious Strategy

From the previous sections, we can compute the Heard-Of predicate of the dominating oblivious strategies for our examples. We first need to give the minimal oblivious strategy for our building blocks P Del crash 1 and P Del total . Definition 17 (Waiting for n -F messages). The strategy to wait for n -F messages is:

For all F < n, f n,F is the minimal oblivious strategy for P Del crash F (shown by Shimi et al. [12,Thm. 17]). For P Del total , since every process receives all the messages all the time, the strategy waits for all the messages (f n,0 ).

Using these strategies, we deduce the heard-of predicates of dominating oblivious strategies for our examples.

-For P Del recover 1 P Del crash 1 P Del total , the minimal oblivious strategy

-For P Del crash

The computed predicate is the predicate of the dominating oblivious strategy. But the dominating strategy might not be oblivious, and this predicate might be too weak. The following result shows that P Del crash 1 and P Del total satisfy conditions that imply their domination by an oblivious strategy. Since these conditions are invariant by our operations, all PDel constructed with these building blocks are dominated by an oblivious strategy.

Theorem 5 (Domination by Oblivious for Operations). Let P Del, P Del 1 , P Del 2 be delivered predicates that satisfy:

-(Total collection) They contains the total collection c tot , -(Symmetry up to a round) ∀c a collection in the predicate, ∀p ∈ Π, ∀r > 0, ∀r ′ > 0, ∃c ′ a collection in the predicate:

Conservative Strategies

We now broaden our family of considered strategies, by allowing them to consider past and present rounds, as well as the round number itself. This is a generalization of oblivious strategies, that tradeoff simplicity for expressivity, while retaining a nice structure. Even better, we show that both our building blocks and all the predicates built from them are dominated by such a strategy.

For the examples then, no expressivity is lost.

Minimal Conservative Strategy

Definition 18 (Conservative Strategy). Let cons be the function such that ∀q ∈ Q, cons(q) q.round, { r, k ∈ q.mes | r ≤ q.round} . Let ≈ cons the equivalence relation defined by q 1 ≈ cons q 2 cons(q 1 ) = cons(q 2 ). The family of conservative strategies is f amily(≈ cons ). We write Nexts R f {cons(q) | q ∈ f } for the set of conservative states in f . This uniquely defines f .

In analogy with the case of oblivious strategies, we can define a minimal conservative strategy of P Del, and it is a strategy dominating all conservative strategies for this delivered predicate.

Definition 19 (Minimal Conservative Strategy). Let P Del be a delivered predicate. The minimal conservative strategy for P Del is f min the conservative strategy such that f = {q ∈ Q | ∃c ∈ P Del, ∃p ∈ Π, ∀r ≤ q.round : q(r) = c(r, p)}.

Lemma 3 (Domination of Minimal Conservative Strategy). Let P Del be a delivered predicate and f min be its minimal conservative strategy. Then f min dominates the conservative strategies for P Del.

Proof (Proof idea). Analogous to the case of minimal oblivious strategies: it is valid because it allows to change round for each possible conservative state (the round and the messages received for this round and before) of collections in P Del. And since any other valid conservative strategy f must accept these states (or it would block forever in some execution of a collection of P Del), we have that f contains f min and thus that f min dominates f .

Operations Maintain Minimal Conservative Strategies

Like oblivious strategies, minimal conservative strategies give minimal conservative strategies of resulting delivered predicates.

Theorem 6 (Minimal Conservative Strategy for Union).

Let P Del 1 , P Del 2 be two delivered predicates, f 1 and f 2 the minimal conservative strategies for, respectively, P Del 1 and P Del 2 . Then f 1 ∪ f 2 is the minimal conservative strategy for P Del 1 ∪ P Del 2 .

Proof (Proof idea).

A prefix of a collection in P Del 1 ∪ P Del 2 comes from either P Del 1 or P Del 2 , and thus is accepted by f 1 or f 2 . And any state accepted by f 1 ∪ f 2 corresponds to some prefix of P Del 1 or P Del 2 .

For the other three operations, slightly more structure is needed on the predicates. More precisely, they have to be independent of the processes. Any prefix of a process p in a collection of the predicate is also the prefix of any other process q in a possibly different collection of the same PDel. Hence, the behaviors (fault, crashes, loss) are not targeting specific processes. This restriction fits the intuition behind many common fault models.

Definition 20 (Symmetric PDel). Let P Del be a delivered predicate. P Del is symmetric ∀c ∈ P Del, ∀p ∈ Π, ∀r > 0, ∀q ∈ Π, ∃c ′ ∈ P Del, ∀r ′ ≤ r : c ′ (r ′ , q) = c(r ′ , p) Theorem 7 (Minimal Conservative Strategy for Combination). Let P Del 1 , P Del 2 be two symmetric delivered predicates, f 1 and f 2 the minimal conservative strategies for, respectively, P Del 1 and P Del 2 . Then f 1 f 2 is the minimal conservative strategy for P Del 1 P Del 2 .

Proof (Proof idea). Since f 1 and f 2 are the minimal conservative strategies of P Del 1 and P Del 2 , N exts R f 1 is the set of the conservative states of prefixes of P Del 1 and N exts R f 2 is the set of the conservative states of prefixes of P Del 2 . Also, the states accepted by f 1 f 2 are the combination of the states accepted by f 1 and the states accepted by f 2 . And the prefixes of P Del 1 P Del 2 are the prefixes of P Del 1 combined with the prefixes of P Del 2 for the same process. Thanks to symmetry, we can take a prefix of P Del 2 and any process, and find a collection such that the process has that prefix. Therefore the combined prefixes for the same process are the same as the combined prefixes of P Del 1 and P Del 2 . Thus, N exts R f 1 f 2 is the set of conservative states of prefixes of P Del 1 P Del 2 , and f 1 f 2 is its minimal conservative strategy.

Theorem 8 (Minimal Conservative Strategy for Succession). Let P Del 1 , P Del 2 be two symmetric delivered predicates, f 1 and f 2 the minimal conservative strategies for, respectively, P Del 1 and P Del 2 . Then f 1 f 2 is the minimal conservative strategy for P Del 1 P Del 2 .

Proof (Proof idea). Since f 1 and f 2 are the minimal conservative strategies of P Del 1 and P Del 2 , N exts R f 1 is the set of the conservative states of prefixes of P Del 1 and N exts R f 2 is the set of the conservative states of prefixes of P Del 2 . Also, the states accepted by f 1 f 2 are the succession of the states accepted by f 1 and the states accepted by f 2 . And the prefixes of P Del 1 P Del 2 are the successions of prefixes of P Del 1 and prefixes of P Del 2 for the same process. But thanks to symmetry, we can take a prefix of P Del 2 and any process, and find a collection such that the process has that prefix.

Therefore the succession of prefixes for the same process are the same as the succession of prefixes of P Del 1 and P Del 2 . Thus, N exts R f 1 f 2 is the set of conservative states of prefixes of P Del 1 P Del 2 , and is therefore its minimal conservative strategy.

Theorem 9 (Minimal Conservative Strategy for Repetition). Let P Del be a symmetric delivered predicate, and f be its minimal conservative strategy. Then f ω is the minimal conservative strategy for P Del ω . Proof (Proof idea). The idea is the same as in the succession.

Computing Heard-Of Predicates

Here we split from the analogy with oblivious strategies: the heard-of predicate of conservative strategies is hard to compute, as it depends in intricate ways on the delivered predicate itself.

Yet it is still possible to compute interesting information on this HO: upper bounds. These are overapproximations of the actual HO, but they can serve for formal verification of LTL properties. Indeed, the executions of an algorithm for the actual HO are contained in the executions of the algorithm for any overapproximation of the HO, and LTL properties must be true for all executions of the algorithm. So proving the property on an overapproximation also proves it on the actual HO.

Theorem 10 (Upper Bounds on HO of Minimal Conservative Strategies). Let P Del, P Del 1 , P Del 2 be delivered predicates containing c tot . Let f cons , f cons 1 , f cons 2 be their respective minimal conservative strategies, and f obliv , f obliv 1 , f obliv 2 be their respective minimal oblivious strategies. Then:

Proof (Proof idea). These bounds follow from the fact that an oblivious strategy, is a conservative strategy, and thus the minimal conservative strategy dominates the minimal oblivious strategy.

Conclusion

To summarize, we propose operations on delivered predicates that allow the construction of complex predicates from simpler ones. The corresponding operations on strategies behave nicely regarding dominating strategies, for the conservative and oblivious strategies. This entails bounds and characterizations of the dominating heard-of predicate for the constructions.

What needs to be done next comes in two kinds: first, the logical continuation is to look for constraints on delivered predicates for which we can compute the dominating heard-of predicate of conservative strategies. More ambitiously, we will study strategies looking in the future, i.e. strategies that can take into account messages from processes that have already reached a strictly higher round than the recipient. These strategies are useful for inherently asymmetric delivered predicates. For example, message loss is asymmetric, in the sense that we cannot force processes to receive the same set of messages.

Funding. This work was supported by project PARDI ANR-16-CE25-0006.


Helene Martin-Yken

Arnaud Lagorce

Jean François

Yeast cells are surrounded by a thick cell wall which ensures their shape, their integrity and constitutes the first interface with the environment. The yeast cell wall consists of a complex structure of polysaccharides chains, mostly β-glucans and a small amount of chitin, interconnected to mannoproteins. Cell division, developmental programs and response to environmental changes lead to extensive cell wall remodelling. These alterations are controlled by complex signalling pathways involving stress sensors, MAP kinases and several transcription factors. Understanding the molecular mechanisms underlying yeast cell wall assembly represents a great interest for biotechnological processes including research of new antifungal agents and new cell targets.

INTRODUCTION

The yeast cell wall is the main determinant of cellular strength, and plays an important role in cell morphogenesis and cell growth. It is the first cellular structure in direct contact with the surroundings. Under a normal growth situation, the cell wall amounts to about 20 % of the cell dry mass. The yeast cells have a very high turgor pressure, and a minor chink in the cell wall can lead to bursting and death. Moreover, the cell wall is not a rigid structure as it endures all the changes that the cell undergoes during division, morphogenesis and differentiation. To ensure a continuous integrity of the wall in accordance with its plasticity, elaborated mechanisms must be operating, which need to be strictly coordinated with those governing the cell cycle progression. This review will focus on recent data on the cell wall biogenesis and remodelling in response to environmental stress and in relation to cell growth. Emphasis on the reasons to study yeast cell wall will be depicted through the biotechnological values of the cell wall components and as an attractive antifungal target. The reader wishing more detailed information about the molecular organisation of the yeast wall, or on specific metabolic or mechanistic issues related to cell wall synthesis may consult excellent reviews that have appeared very recently [START_REF] Orlean | The Molecular Biology and Cellular Biology of the Yeast Saccharomyces[END_REF][START_REF] Popolo | [END_REF][3][4][5][6].

CELL WALL COMPOSITION AND BIOGENESIS

The cell wall of Saccharomyces cerevisiae is organized into two layers that are made up of four classes of covalent cross-linked macromolecules:

β1,3-glucan, β1,6glucan, chitin and cell wall mannoproteins (CWPs). Electron-microscopic studies have shown that the mannoproteins form a fibrillar outer layer extending radially from the inner skeletal layer, which is formed by the polysaccharide fraction of the cell wall [7]. The architecture of the cell wall from the yeast S. cerevisiae is outlined in Figure 1.

1,3-glucans: structure, enzymology and regulation

The β1,3-glucans, the most prominent carbohydrates of the cell wall, account for about 50% of the cell wall dry mass. They form a fibrillar structure, composed of three helically entwined linear chains of about 1500 β(1→3) linked glucose units [8]. This structure provides the rigidity and integrity of the cell wall, and determines the cell shape. The β1,3-glucans are produced from UDP-glucose by the membrane-bound β1,3-glucan synthase (GS) encoded by two homologs genes, FKS1 and FKS2 [9;10]. The expression of FKS1 is more abundant during vegetative growth and is in part cell cycle regulated, while FKS2 is transcribed under stress conditions or in response to cell wall defects such as in a fks1 mutant [START_REF] Mazur | [END_REF][11][12]. Thus, only the double knock out of FKS1 and FKS2 is lethal. While Fks1 and Fks2 are suspected to correspond to the catalytic subunit of GS [13], it is however clear that the GS activity requires the presence of a 26 kDa GTP binding protein encoded by RHO1 [14]. This small G-protein is loosely attached to the plasma membrane through prenylation at the Cterminus. Rho1 acts as a 'switch' of the GS activity due the conversion between an inactive GDP-bound to an active GTPbound form catalysed by the guanine exchange factor Rom1 and Rom2 [15]. Conversely, GTPase-activating proteins, encoded by BEM2 and SAC7, switch off the GS activity by converting GTP-bound active Rho1 to the inactive GDP-bound form [16;17]. Very recently, it was found that GS was non-competitively inhibited by a physiological concentration of phytosphingosine, an intermediate of the sphingolipid biosynthesis that is located in the endoplasmic reticulum [18]. This inhibition was supposed to have a regulatory role in the interaction between Fks1 and Rho1. To conclude, many questions are not yet solved on the structure-function, and regulation, of the β1,3-glucan synthase isoforms in yeast, which therefore precludes decisive antimicrobial development towards this potential target.

1,6-glucans: structure, enzymology and regulation

The structure of β-glucans also comprises a minor amount (about 5 %) of β1,6glucan, a polymer of ca 100-350 β (1→6) linked glucose units. The biosynthesis of this polymer, which likely arises from UDP-glucose as the glucosyl donor, has been mainly studied by a genetic approach (see [4], for an extensive review), and a 'β1,6-glucan synthase' enzyme has not been discovered yet. Nonetheless, this polymer is an essential fungal-specific component of the cell wall that interconnects all other wall components into a lattice (see Figure 1 and2). The genetic approach which took the advantage that cells devoid of β1,6-glucan were highly resistant to K1 Killer toxin (called kre mutants for Killer REsistant) has elucidated only part of the biosynthetic pathway of this polymer. The biosynthesis is initiated in the endoplasmic reticulum, continues in the Golgi apparatus and ends up at the cell surface. However, Klis group [19] failed to identify intracellular material that reacts with specific β1,6-glucan antibodies, even in mutants of the secretory pathway. Thus, the complete metabolic scheme leading to the synthesis of β1,6glucans, as well as the biochemical activity corresponding to most of the isolated KRE genes remains to be elucidated.

Chitin: structure, enzymology and regulation

Chitin is an essential component of the yeast cell wall even though it amounts to only 1-2% of the cell wall dry mass in a wild type strain [START_REF] Fleet | The Yeast[END_REF]. It is a linear homopolymer composed of ca 120 Nacetylglucosamine residues that are linked by β(1→4) bonds. Chitin structure consists of antiparallel hydrogen-bonded chains called microfibrils that can retain the dye Calcofluor White [START_REF] Minke | [END_REF][22][23]. In S. cerevisiae and in the pathogenic yeast Candida albicans, it has been shown that chitin is attached covalently to β 1,3 and β1,6glucans [24][25][26][27]. Since β 1,6-glucans are in turn attached to the glycosylphosphatidylinositol (GPI)containing cell wall proteins, all components are attached directly or indirectly to chitin. In S. cerevisiae, the formation of chitin is taken over by three distinct chitin synthases, encoded by CHS1, CHS2 and CHS3 [28][29][30][31][32]. They are integral membrane proteins with the catalytic domain located at the cytoplasmic face. Localisation of chitin synthases has been also reported in vesicles named chitosomes [33;34]. Chitin synthases are all stimulated by acetylglucosamine and feedback inhibited by UDP. The activity of the three chitin synthases can be distinguished by their differential sensitivity to Mg 2+ , Co 2+ or Mn 2+ [35] and, in the case of Chs1 and Chs2, by a 'in vitro activation' after mild treatment with trypsin, suggesting that the two latter enzymes occur naturally in a zymogenic state [28]. The existence of three distinct chitin synthases raises questions about their specific roles and regulation mechanism in yeast. These questions have been addressed at the genetic and biochemical levels. As it was shown that chitin synthesis is a cell cycle regulated process, the action of each of the chitin synthases can be assigned to specific steps during this process. Chs1 is a repair enzyme that synthesises chitin in response to an acidification event following separation of mother and daughter cells [36]. Because the in vitro activity of Chs1 cannot be detected without proteolytic treatment, it is thought that Chs1 is tightly controlled 'in vivo' by a proteolytic system that has not been identified yet. Chs2 is localised to the mother -bud septum and is responsible for primary septum formation between mother and daughter cells [37;38]. Chs3 is the most important enzyme catalysing ca 90 % of the chitin content of the cells. This enzyme is spatially and temporarily controlled by a number of regulatory proteins encoded by CHS4, CHS5, CHS6 and CHS7 [39][40][41][42][43][44]. The interaction of Chs3 with Chs4 that in turn interacts with one of the septin protein, Bni4 (Bud-Neck-Involved) may account for the targeting of Chs3 to a ring at the mother-bud neck. This interaction could explain that Chs3 is no longer localised at this site in a bni4∆ or chs4∆ mutant [39;45]. The Chs5 and Chs6 proteins have also a role of targeting the Chs3 to polarized growth sites [41][42][43]. Chs7 is a membrane protein that is required for the export of Chs3 from the ER, which together with Chs4 determines the full Chs3 activity in vivo [39]. The levels and localisation of the three chitin synthases have been monitored through the cell cycle. Chs1 and Chs3 are synthesized constitutively, and localised in plasma membrane and/or in chitosomes, with a probably cell-cycle dependent trafficking of chitin synthases between these two cellular structures [34;46]. This cycling mechanism constitutes a mean to maintain a constant pool of enzymes for chitin synthesis. Chs2 does not follow this pathway and probably processes via the secretory pathway, where it is packaged and transported to the plasma membrane at the site of septum formation. The enzyme is then internalised and degraded when it is no longer needed [START_REF] Chuang | [END_REF].

The genome of S. cerevisiae contains two genes CTS1 and CTS2 encoding endochitinases, which cleave off chitin into N-acetylglucosamine units. Cts1 is present in vegetative cells as a protein noncovalently bound to cell wall [47]. The main function of this hydrolase is to dissolve the chitinous primary septum that is synthesized by Chs2 during cell separation. Since excessive activity can be lethal for the cell, the Cts1 is supposed to be tightly controlled by both transcriptional and post-translational mechanisms [48][49][50]. The CTS2 gene is induced during sporulation, but the role of CTS2 product during this process remains unknown.

Mannoproteins: structure, enzymology and regulation

The outer layer of the yeast wall is made up of proteins that are bound via a serine, threonine or an asparagine residue to a polysaccharide complex of 150 or more Dmannose units (the so-called mannan). Early chemical studies have shown that the mannans are composed of an α (1 6) linked backbone of mannoses to which are attached short side chains of mannoses linked by α (1 2) and α(1 3) bonds. The polysaccharide structure can reach up to 50 % of cell wall dry mass. The biosynthetic pathway of mannans starts in the cytosol by the isomerisation of fructose-6P into mannose-6P catalysed by the phosphomannose isomerase (Pmi1), which is then epimerised into mannose-1P. The GDP-mannose is formed from mannose-1P and GTP by a GDP-mannose pyrophosporylase encoded by the essential gene PSA1 [51]. A dolichol-phosphate synthase, localised at the cytosolic face of the ER and encoded by the essential gene DPM1, transfers the mannose from GDPmannose to Dolichol-phosphate to form Dol-P-mannose. This molecule is a key intermediate in three protein glycosylation processes, namely the N-glycosylation, Oglycosylation and glycosylphosphatidylinositol (GPI) membrane anchoring [52]. These reactions all occur in the rough endoplasmic reticulum.

N-glycosylation involves a set of glycosyltransferases encoded by ALG1 to ALG10 genes which produce the oligosaccharide precursor GlcNac 2 Man 9 Glc 3 on a polyisoprenoid carrier lipid Dol-PP. The last step in the ER is the transfer of the oligosaccharide to the amide group of an asparagine residue of the protein in the tripeptide 'sequon' Asn-X-Ser/Thr, where X is any amino acid except proline. This reaction is catalysed by the oligosaccharide transferase (OTase) complex composed of eight proteins, all of which are encoded by essential genes [53;54]. Maturation of glycolysated protein occurs in the Golgi apparatus by successive addition of mannose units from GDP-mannose catalysed by specific αmannosyltransferases.

The O-mannosylation is initiated in the ER by transferring a mannose from Dol-Pmannose to a Ser or Thr residue of the protein. This reaction is carried out by a Dol-P Man::protein Omannosyltransferase encoded by one of the seven PMT genes [55;56]. Only deletion of three of them (PMT1, 2 and 4 or PMT2, 3 and 4) leads to inviability, leaving the other four with no clear function yet. Elongation of O-linked chains, i.e. addition of 2 to 4 more mannoses relies on GDPmannose as mannosyl donor, and these reactions that also occur in the Golgi apparatus are catalysed by αmannosyltransferase [57;58]. It can be noticed that most glycoproteins of S. cerevisiae are both N and O-glycosylated.

Once the mannoproteins have reached the outer cell surface, they can be retained to β1,6-glucan through a remnant of the GPI anchor which they have received during maturation in the endoplasmic reticulum (the so-called GPI-CWPs). Lack of this GPI-anchor results in secretion of the CWPs in the medium [26;59;60]. A second class of cell wall mannoproteins characterized by Protein Internal Repeat regions (PIR-CWPs) are directly linked to β1,3-glucan and exhibit not obvious function [61;62]. A last category are cellsurface proteins attached to cell wall either by disulphide bridges to other CWPs, or by 'affinity' or non specific binding as it is the case for many glycolytic enzymes [63][64][65].

THE MODULAR STRUCTURE OF THE CELL WALL

The structural components described above are not simply juxtaposed. They are rather assembled to each other by covalent linkages, which generate a modular architecture of the yeast cell wall (see Figure 2). The first fully characterized linkage was a β(1 4) link between the reducing terminal GlcNac residue of a chitin chain and the non reducing terminal glucose of a β1,3-glucan chain [66]. Covalent association between mannoproteins, β1,6-glucan and β1,3glucan have been identified later on [24;26;67;68]. Thus, the cell wall modules, i. Apparently not all modules actually contain chitin, which accounts for the existence of two chemical fractions of βglucan : a chitin-free alkali-soluble fraction and a chitin-enriched alkali-insoluble one.

The increased amount of the latter fraction is indicative of a chitin enrichment of the cell wall [20;26;70]. The different modules are interconnected by noncovalent interactions in the β-glucan-chitin layer and by covalent cross-links in the mannoprotein layer including disulfite bonds between mannoproteins [1;12;71] and perhaps also through other mannoprotein-glucan links not yet characterized [26].

Although the chemical bonds between the different cell wall components have been described in details, the enzymes involved in the generation of these links are largely unknown. These are enzymes involved in the cleavage of the GPI-anchor of the GPIproteins and the subsequent attachment to β1,6-glucans, as well as enzymes involved in the coupling between β-glucan and chitin. Yeast possesses several exoglucanases that catalyze in vitro the hydrolysis of linkages at the non-reducing ends of β1,3-glucans, and endo-glucanases activities which cleave within the chains [20;72]. However, some of the identified β-glucanases may also carry out glycosyl transferase activity. This is the case for Bgl2 which was originally characterized as an endo-β1,3-glucanase [73;74], and latter on found to display also a glycosyl transferase activity [75]. Apparently, a low water environment, which is likewise the situation existing in the cell wall, favours this transferase activity [75]. Another example of β1,3-glucanosyltransferase has been decrypted recently by investigating the kinetic properties of Gas1, a highly glycosylated protein which belongs to a family of related yeast and fungal proteins attached to cell membrane by a GPI-anchor [START_REF] Popolo | [END_REF]. Gas1 plays a major role in cell wall assembly as mutants defective in this protein display aberrant phenotypes, such as very slow-growth, clumpiness, high thermotolerance, hypersensitivity to cellwall perturbing drugs [12;76], reduction of incorporation in cell wall of β1,3-glucan and more abundant release of β1,6glucosylated GPI-mannoproteins in the growth medium [77]. These pleiotropic defects can be a consequence of the inability of the Gas1 enzyme to create anchoring sites for mannoproteins on glucan chains by its transferase activity [78] Many other genes, as for instance the SCW gene family [47;79] or the CRH1 and CRH2 [80] that encode proteins with putative glycosyl transferase activity may also be implicated in cross-linking of the cell wall components. These assembly enzymes are interesting candidates as antifungal targets since their inactivation should weaken cell wall structure and eventually inhibit growth. This challenge is being raised by a European project named "EUROCELLWALL" under the European Commission Framework V (see http://www.insa-tlse.fr/gba/Recherche /Equipes/Eucariote/fr).

COORDINATION OF CELL WALL INTEGRITY AND CELL GROWTH

During cell growth and development, the cell wall undergoes extensive remodelling and modifications in its structure and composition. Regulation of cell wall assembly must be coordinated with cell cycle control during vegetative growth, as well as during the different developmental programs such as mating, sporulation and formation of pseudo-hyphae. Since these questions have been recently reviewed [5;81], we will mainly focus this part on recent data about mechanisms that coordinate cell wall integrity to cell proliferation.

The cell wall integrity is mainly under the control of the Pkc1-MAP kinase pathway

Cells sense and respond to environmental constraints via signalling pathways. As shown in Figure 3, five signalling pathways based on a module of three protein kinases highly conserved among eucaryotes and which culminate in the activation of a mitogen-activated protein kinase (MAPK) have been analysed in great details in the yeast S. cerevisiae [81][82][83]. It is particularly important to notice that some of the signalling pathways can share common elements. This partial overlapping actually does not interfere with the specificity of the response, which depends largely on the upstream (sensors) and downstream (transcription factors) elements that are specific to each pathway. The sharing of partners likely illustrates a cross talk between the various pathways that is necessary to produce a coordinated cellular response.

The MAPK cascade dependent on the protein kinase C encoded by PKC1 is considered as the main pathway controlling cell wall integrity. The PKC1 gene of S. cerevisiae was isolated as homologous of the mammalian PKC gene [84]. Pkc1 protein kinase is essential for the formation of an osmotically stable cell wall since loss of its function results in cell lysis at all temperatures, a phenotype that can be partially remediable by osmotic stabilizators, such as sorbitol 1M [84;85]. The signalling pathway is constituted of two branches that diverge downstream of the Pkc1. One of them is a linear pathway consisting of the sequentially activated protein kinases Bck1, the redundant Mkk1/Mkk2 and the Slt2/Mpk1 MAPK, which ultimately activates by phosphorylation transcription factors including Rlm1 and SBF complex [86;87]. The evidence that there is another branch arose from the finding that phenotypes of a pkc1 null mutant are stronger than those of mutants downstream of the cascade [88]. However, the components of this second branch have not been completely worked out (see below). The Pkc1-MAP kinase pathway is activated by cell wall stress such as heat, hypo-osmotic conditions, mutations of cell wall structural genes, cell-wall perturbing drugs like Calcofluor White, Congo Red, caffeine, SDS, zymolyase [12;89-91]. This activation is transmitted through plasma membrane sensors including Hcs77 /Slg1/Wsc1, Wsc2, Wsc3, Wsc4 and Mid2 [92][START_REF] Verna | Proc.Natl.Acad.Sci.U.S.A[END_REF][START_REF] Jacoby | [END_REF][95]. MID2 and HCS77 genes have the major in vivo role, since deletion of both genes is synthetically lethal, and deletion of each of them results in pkc1∆-like phenotypes, such as sorbitol-remediable cell lysis at high temperature and high sensitivity to cell wall affecting drugs, while deletion of their homologues causes only minor phenotypes. Mid2 is believed to transduce a calcium signal of the pheromone response [96], as well as signal from cellwall-perturbations [95;97], whereas the Hcs77 protein probably sends to the Pkc1 kinase signals resulting from membrane perturbations in response to hypo-osmotic and temperature shock [START_REF] Verna | Proc.Natl.Acad.Sci.U.S.A[END_REF]. These sensors relay the signal to Rho1, an essential and highly conserved small GTP-binding protein, which directly activates Pkc1 [98;99] Members of this family are known to dimerize and to be MAPK targets in yeast and mammalian cells [86].

Recent works suggest the existence of three potential pathways that acts in parallel to Pkc1 in the control of cell wall integrity pathway. The first one was identified from a genetic screen aiming to isolate suppressors of pkc1∆ and mpk1? ∆ cell lysis. This screen led to the cloning of BCK2 (bypass of C kinase 2), encoding a serine-threonine rich protein of unknown function and PPZ1 and PPZ2, a pair of functionally redundant protein phosphatases [106]. These genes are likely members of a SIT4-dependent pathway that also interacts with cell cycle progression ([107], see below). Two other pathways parallel to Pkc1 were recently identified by genetic interactions observed between pkc1, mpt5 and ssd1 mutations [108]. MPT5 encodes a protein involved in cell longevity that is required for growth at high temperature, affects telomeric silencing and is implicated in resistance to starvation [109][110][111]. Mutants of MPT5 also harbour phenotypes associated with a weakened cell wall. On the other hand, Ssd1 has homology to several ribonucleases and seems to bind poly(A) mRNA. SSD1 has been shown to interact genetically with genes downstream of PKC1 [112]. Sensitivity to cell wall perturbing drugs and effects on cell wall weakening are synergistically amplified by the mpt5ssd1 double mutation. In addition, synthetic lethality is obtained by mutation of MPT5, SSD1 with SWI4 or SWI6, two downstream targets of the PKC1-SLT2 pathway [108], and see below). Taken together, these genetic data illustrate the complexity of the cell wall integrity mechanisms and the interconnections of these mechanisms with the cell cycle progression.

Coordination between cell wall biogenesis and cell proliferation

Cell proliferation and cell wall biogenesis must be coordinated to allow budding. The process of bud emergence and bud expansion involves remodelling of the mother cell wall as well as synthesis and assembly of new cell wall components. Coherent with this picture, a periodic transcription has been reported for many cell wall genes with a maximum expression in late G1/early S phase of the cell cycle, coincident with the early stages of budding [113]. Cytokinesis, in turn, requires the expression of genes encoding specific enzymes related to synthesis and degradation of cell wall components [114]. For these two cell cycle steps, the transcription factors involved are Swi4, the DNA binding subunit of SBF, and Rlm1, a MADS box transcription factor, which are both under the control of the Slt2 MAP kinase [87;105;113-115].

The interrelationship between the Pkc1-MAP kinase pathway and the cell cycle progression, dependent upon the cyclin-Cdc28 (the yeast counterpart of mammalian Cdc2), has been illustrated by several experimental data. It was first shown that a slt2 mutation enhances the defect in G1-S transition associated with cdc28 alleles [116], and later on, that Slt2 is specifically activated during periods in which cells undergo polarized growth (i.e. just after the START in G1 phase of the cell cycle), in a manner partially dependent of Cdc28 [117]. The proposed mechanism for this effect was that the activation of Cdc28 at START induces a burst in the production of diacylglycerol, which in turn would activate the yeast Pkc1, although, in contrast to its mammalian counterpart, a direct activating effect of diacylglycerol has not been reported for the yeast enzyme [118]. Pkc1 activation at START promotes three different cellular processes: the transcriptional activation of cell wall synthesis genes [113], actin polarization [103;119], and spindle pole body duplication [120].

Another aspect of the cross talk between Pkc1 and Cln-Cdc28 pathways concerns the control of the transcription factor SBF (for SCB binding factor) by these two kinases. SBF is a heterodimeric complex composed of Swi6, a regulatory subunit, and Swi4 that binds the DNA sequence CACGAAA (SCB, for Swi4 cell cycle box) [121][122][123][124]. Swi6 is also part of another cell cycle transcription factor, MBF (for MluI binding factor), together with the DNA binding protein Mbp1 [125]. Both SBF and MBF activate gene expression at the G1/S transition of the cell cycle, but SBF target genes are predominantly involved in budding, in membrane and cell wall biosynthesis, whereas DNA replication and repair are the dominant functions of MBF activated genes [126]. Control of the SBF factor by the cyclin-Cdc28 complex occurs by a Cdc28-dependent phosphorylation of a serine residue on Swi6, which allows nuclear localization of the protein at the end of the M phase and during G1 phase [127]. Swi4 remains nuclear throughout the cell cycle, but is unable to bind SCBcontaining DNA in the absence of Swi6, due to an intramolecular mechanism of auto-inhibition that involves both its DNA binding domain and its Swi6 binding domain [128]. Control of the SBF factor also occurs by another cyclin/Cdc28 kinase complex, which in G2 phase inhibits and possibly inactivates SBF [129;130]. Meanwhile, Pkc1-MAP kinase pathway can control SBF activity at the G1-phase through Slt2-dependent phosphorylation of Swi4 and Swi6 [87], enabling recruitment of SBF to the promoters of some SBF target genes [115]. In addition, it was recently shown that Swi4, independently of Swi6, could activate a subset of genes in a Slt2-dependent manner [115]. Slt2 might relieve the intra-molecular interactions that prevent Swi4 from binding to its DNA binding motif in the absence of Swi6, and thus allow Swi4 to regulate transcription of genes partly independently of the G1 phase. SBF is a key element in the control of cell wall synthesis genes and, while it is a target of Slt2, SBF also acts independently of Pkc1 as indicated by the synthetic lethality between swi4 and pkc1 mutants [113].

Knr4 as an element for the coordination between cell wall integrity and cell proliferation

Data given above could lead to the idea that Pkc1 and the cyclin-Cdc28 pathways converge at the level of Slt2 protein kinase. This is by far too simplistic because a deletion of SLT2 does not harbour phenotypes that are characteristic of a pkc1 or a cdc28 mutant. More specifically, the cell lysis defect associated with lack of Pkc1 is much severe than those caused by any mutation in the downstream MAP kinase cascade, including SLT2. These findings argue for the existence of another branch of the Pkc1 pathway that bifurcates just downstream of Pkc1 [88]. To identify genes that function in this hypothetical second branch, a screen for dosage dependent suppressors of pkc1∆ and mpk1? ∆ defects has been conducted. The BCK2 (bypass of C kinase 2) gene, encoding a serine-threonine rich protein was isolated, together with PPZ1 and PPZ2, a pair of functionally redundant protein phosphatases [106]. BCK2 was also identified as a suppressor of cln deficiency (lack of the G1 cyclins Cln1, Cln2 and Cln3) [131;132]. Moreover, it was shown that BCK2 deletion is synthetic lethal with cln3 mutation [131]. This effect was attributed to the transcriptional activation of CLN1 and CLN2 genes by Bck2 in the absence of Cln3 [132]. Bck2 is thus part of a parallel PKC1-pathway that activates, together with Cln3/Cdc28, CLN1 and CLN2 during late G1, and this activation was found to be partly but not completely dependent on SBF and MBF [133].

The synthetic lethality between mutations in PKC1-SLT2 linear pathway and SWI4 or SWI6 [92;113], between BCK2 and CLN3 deletions [131][132][133], and the fact that a bck2∆ pkc1∆ double mutant displays an extremely severe growth defect [106], suggests that PKC1 and BCK2 pathways converge to hit common targets or that both pathways are connected at some points to affect common targets. Several arguments in favour of this second hypothesis were obtained and identified Knr4 protein as one of the elements that allows Pkc1 to coordinate cell wall integrity with cell cycle progression. The KNR4 gene was originally isolated from a recessive mutation giving resistance to the killer toxin from Hansenula Mrakii [134], and later on as a multicopy suppressor of many cwh (calcofluor white hypersensitive) mutants [135]. Although there is no proof yet that Bck2 interacts physically with Knr4, all genetic data converge to the idea that these two proteins are part of a complex that is involved in the control of G1-target genes together with Cln3-Ccd28 (see Figure 4). A major evidence for this model is that deletion of KNR4 is, like that of BCK2, synthetically lethal with cln3 mutation [136]. In addition, the phenotypes associated with deletion or overexpression of these two genes are similar, and they both exhibit synthetic lethal interactions with members of the Pkc1 pathway. However, a genome wide analysis of cells overexpresssing BCK2 or KNR4 indicates that Bck2 when it is overproduced, can act independently of Knr4. These independent effects can account for the fact that overexpression of this gene, but not of KNR4, can rescue cell lysis of a pkc1∆ [136]. Knr4 physically interacts with the MAP kinase Slt2, and is required for the strong increase of Slt2 kinase activity induced by heat shock [137]. Remarkably, deletion of KNR4 does not impair signalling through the PKC1 pathway that leads to dual phosphorylation of Slt2 protein, but it prevents this kinase to efficiently phosphorylate some of its substrates. Although all the targets of Slt2 are not known yet, the transcription factors Rlm1 and SBF have been reported to be among them. In cells defective for KNR4, the transcriptional activity of Rlm1 is dramatically reduced whereas the transcriptional activity of SBF is strongly increased, and the phosphorylated (and probably) activated form of Swi6 is more abundant. Thus, during vegetative growth, Knr4 seems to monitor the fine tuning of output signals of the Pkc1-MAP kinase, acting as a switch to favour Rlm1, and hence the cell wall synthesis genes, versus SBF and cell cycle progression (see Figure 4). Knr4 is a small protein conserved among yeasts, which localizes to sites of polarized growth [135]. Its interaction with Slt2 and Bck2 is only one of the regulatory aspects driven by this protein because other protein interactions with Knr4 have been reported. Knr4 strongly interacts with the tyrosyl-tRNA synthetase encoded by TYS1, and this physical interaction seems to be required for dityrosine formation during the sporulation process. This hypothesis was reinforced by the finding that the efficiency of spore formation was drastically reduced in diploid cells homozygous for the disruption of KNR4 or for a temperature-sensitive mutation of TYS1 [138]. Other interactions such as with Cin5, a transcription factor of the Yap family, and Bas1, a transcription factor implicated in basal expression of adenine metabolic genes [138;139] have been reported, but not fully analysed yet.

BIOCHEMISTRY AND MOLECULAR ANALYSIS OF THE CELL WALL REPAIR MECHANISM

Yeast cells are living in environmental conditions that can weaken their wall. It is therefore not surprising that they have developed some mechanisms for cell wall rearrangement to combat cell lysis. Consistent with this idea, cell wall damages induced by wall perturbing drugs such as Calcofluor White, caffeine, SDS, zymolyase, or by mutations in cell wall related genes are accompanied by dramatic changes in the molecular architecture of the wall [3;5;83]. Three major responses characterize the so-called 'cell-wall salvage' pathway. First, the balance among the cell wall polysaccharides components is modified, with chitin content being the most affected since it can reach up to 20 % of the cell wall mass. Secondly, the type of association among components is changed. For instance, lowering the amount of β-1,6-glucan leads to a larger fraction of the cell wall proteins to become linked directly to β1,3-glucan and chitin, consistent with an increased levels of PIR-proteins. A third response that ensures strengthening of the cell wall is a transient redistribution of the cell wall synthesis and repair machinery, that is normally focused to active growth regions, all over the cell periphery [5].

A consequence of cell wall damages is a considerable increase in chitin [77;140;141] which likely contributes to strengthening the cell wall. It was initially considered that the rise of chitin in response to cell wall defects was consecutive to an activation of the chitin synthase 3 encoded by CHS3 [142;143]. However, the conclusion of these works was hampered by inconsistencies of data on Chs3. Indeed, abolition of chitin synthesis activation by deletion of CHS3 in cell wall defective mutants is not a proof that Chs3 is the controlling enzyme in this mechanism. Reconsidering this question, we actually showed that GFA1 encoding glutamine -fructose-6-phosphate amidotransferase (Gfa1), the first committed enzyme of chitin biosynthesis pathway, plays a major role in this process. Using the terminology of the Metabolic Control Analysis [144], we showed that in quantitative terms, the reaction catalysed by Gfa1 has a flux-coefficient control in the range of 0.90, indicating that the major control of the chitin metabolic pathway takes place at the level of this reaction. Moreover, our data established that the control of the chitin metabolic pathway is mainly hierarchical [145], i.e. dominated by a transcriptional control of GFA1 [146].

The DNA microarrays and proteomic are powerful technologies that have been recently used to decipher the molecular mechanisms underlying the cell wall repair mechanism. A first attempt was made by Jung and Levin [105] who created a permanent and strong activation of the linear Pkc1-Slt2 MAP kinase cascade using a gain-of-function allele of MKK1 (MKK S368P ) that was placed under the galactose-inducible promoter. This work led to the identification of a collection of about 25 genes whose up-regulation was totally dependent upon Rlm1. This approach also brings about some intriguing remarks, since, for instance, many genes previously recognized as being activated by Rlm1 were not found, and FKS2 was strongly activated in a possible Rlm1independent manner, although the promoter of this gene harbours a specific Rlm1-DNA binding consensus [147]. Another genome wide study was carried out by comparing expression profiles of a fks1∆ mutant with its isogenic wild type [11]. This work also led to the identification of genes whose transcriptional changes were clearly dependent upon the Pkc1 Map kinase pathway. Interestingly, SLT2 transcript was upregulated, indicating a positive feedback loop of the phosphorylated Slt2 on its own expression. These two genome wide analysis illustrate the role of the Pkc1-MAP kinase cascade in the cell wall repair mechanism, and show that the transcriptional response implicates Rlm1 as well as other transcriptional factors. Therefore, to enlarge this analysis, we conducted a genome-wide survey of genes expression changes caused by five independent cell-wall mutations, namely mutations in genes implicated in cell wall structure (mnn9, fks1 and kre6), in the interconnection of cell wall components (gas1) and in the regulation of cell wall biosynthesis (knr4). Overall, roughly 300 genes were responsive with transcriptional changes ranging from 1.4 to more than 10fold. The repartition of the differentially expressed genes into functional categories revealed an enrichment of genes that belong to energy metabolism and cell defense. A two-dimensional hierarchical clustering method identified a major group of about 100 genes that were up regulated in the five cell wall mutants, from which roughly 30 % have no annotated function, and less than 10 % were known to be controlled by the PKC1-dependent cell integrity pathway. Using available softwares, over-represented DNA sequences were identified in the upstream non-coding regions of these genes. They correspond to binding sites of known transcriptional factors involved in activation of cell wall genes (Rlm1), in stress and heat shock responses (Msn2/4 and Hsf1), in the cell cycle (Sok2), as well as in carbon and phosphate metabolism (Gcr1 and Pho4). Interestingly, a novel putative 6-bp regulatory motif was found in the promoters of 30 % of the coregulated genes. This motif was shown to be functional by site-directed mutagenesis, but its implication in cell wall assembly as well as the transcription factor it may bind remains to be established. To conclude, these global analyses demonstrate that the cell wall compensatory mechanism likely encompasses the coordinated action of multiple transcription factors responsible of the expression patterns in response to cell wall defects [148].

BIOTECHNOLOGICAL VALUES OF THE CELL WALL COMPONENTS

Yeast is a eucaryote, which represents an ideal tool because of its short generation time, its well-known metabolism and the possibility to easily carry out genetic modifications. Moreover, yeast is a GRAS ("Generally Regarded As Safe") organism, so it can be legally used in agro-food and pharmaceutical productions. The cell wall components present several advantages towards these issues that we will revise shortly below.

Biotechnological values in traditional use of yeasts

Yeast flocculation and flotation in beverages

Flocculation refers to an asexual cellular aggregation when yeast cells adhere, reversibly to one another to form microscopic flocs which sediment out of the suspension. Conversely, yeast flotation defines the ability of non-aggregated yeast cells to trap C0 2 bubbles in a fermenting liquid and form a film or vellum at the top of fermentation vessels [149;150]. Both phenomena are highly relevant for the production of several yeast-fermented products. Flocculation and flotation are governed by many external (physicochemical, environmental) and intrinsic (genetic) parameters that are still poorly understood. Biochemical analysis of the flocculation process has identified at least two types of molecules on the yeast cell surface that are responsible of the flocculation. One type is the mannan core of the mannoproteins, and the other is flocculins (surface glycoproteins) that are encoded by FLO genes [149][150][151][152]. The overall structure of flocculins, encoded by FLO1, FLO5, FLO10 and FLO11, comprise an amino-terminal domain containing a hydrophobic signal sequence and a carboxyl-terminal domain with homology to the GPI-anchor proteins, separated by a domain of highly repeated sequences rich in serine and threonine residues. These proteins bind to mannans on the surface of neighbouring cells, leading to the cross binding of cells and ultimately the formation of flocs, each consisting of several cells. Cell surface charge and hydrophobicity have also been implicated with flocculins to facilitate flocculation. Cell flotation is associated with the formation of a vellum. This structure is likely the result of a complex association of highly glycosylated cellsurface proteins as indicated by genetic and biochemical studies [149;150;153;154]. For both phenomena, the relevant genetic and metabolic mechanisms need to be worked out in order to develop strategies for controlling flocs and vellum formation during fermentation.

Yeast polysaccharides in winemaking

Besides many polysaccharides present during winemaking and that arise from grapes or from deceased microorganisms, mannoproteins from the wall of Saccharomyces cerevisiae have some beneficial effects on fining and clarification during wine production by ensuring physicochemical stability of the end product, for at least four reasons [155]. Firstly, mannoproteins have a positive effect on the tartrate stability [156], which likely limits crystal formation [157]. Secondly, mannoproteins have a noticeable influence on the protein stability of white and rosé wines [158] and display the ability to increase the stabilisation of aroma components [159]. Moreover, mannoproteins are supposed to bind to tannins, which reduce the astringency of wines [160]. Another reason comes from the finding that mannoproteins affects positively the onset and development of malolactic fermentation [161;162]. In practice, some winemakers add to the wine broth commercially available β-glucanases that release mannoproteins, to enhance natural effect of endo-β-glucanases obtained after yeast autolysis [163]. Due to the beneficial effect of mannoproteins on wine quality, future efforts should be concentrated on methods that increase the mannoproteins content of the yeast cell wall and favour yeast autolysis at some stage of the wine process [149;150].

Cell wall components as a benefit for human health

Yeasts extracts have been used since a long time for cosmetic and pharmaceutical purposes, and the first pharmaceutical 'Zymosan' was just composed of a raw yeast cell wall preparation that exhibited an immune-stimulating activity [164]. It was then recognized some years later that β-glucans of the yeast Saccharomyces cerevisiae, have immune-suppressive activity [165][166][167][168]

Animal Nutrition and Prevention against Mycotoxins

Yeast cells and yeast cell walls are currently added to animal diets in order to facilitate the digestion and to protect them from pathogens. On the other hand, one of the most important applications resides in the ability of cell wall to protect animal from mycotoxins. These latter are secondary products of fungal metabolism that may be produced in contaminated feeds during production and storage. Aflatoxins and fusarium toxins are responsible of liver damages, decrease of reproductive performances, tumor formation, immuno-suppression. A trivial method for attenuating the effect of mycotoxins is based on the use of materials that can absorb mycotoxins in animal feeds, without any secondary effects. This allows the toxin to pass through the animal's digestive tract without being retained. The carbohydrate complexes of the yeast cell wall was reported to express this capacity when administrated to chicken [186;187]. Modifications in the manufacturing techniques have allowed the production of more efficient yeast cell wall preparation with the ability to bind a wide range of mycotoxins, such as the Mycosorb™, a yeast cell wall-derived glucomannan product [188]. A better understanding of biochemistry related to the interaction of mycotoxins with the cell wall components should be important for development of advanced mycotoxins adsorbents in the future [189]. Genetic modifications of the yeast cell wall or strain selection could lead to the discovery of cell wall structures able to bind an even wider range of mycotoxins with even higher affinity.

Cell Wall Engineering

The attachment of homologous or heterologous proteins to the cell surface to create new metabolic abilities of cells was investigated only a few years ago, thanks to the identification of GPI-structure as a mean to anchor proteins to cell wall βglucans [190]. As an example, a chimeric protein bearing the Rhizopus oryzae glucoamylase has been fused to the Cterminal half of the yeast α-agglutinin, a protein involved in mating and which is covalently anchored to the cell wall. The transformed strain expresses the chimeric enzyme at the cell surface, allowing growth on starch as the sole carbon source [191]. A similar strategy was followed with many other proteins like α-amylase from Bacillus stearothermophilus [192], cellulase and lipase [193;194]. This strategy was also applied to generate polypeptide libraries and then to screen by cell sorting techniques those proteins showing the best affinity for specific ligands [190;195-197]. The expression of antigens at the cell-surface of yeast is an attractive approach for the development of recombinant live vaccines whose efficiency was already proven in the treatment of diarrhoea [198]. Although first trials of this approach was disappointing regarding the low antigenicity of the immobilized protein, more extensive engineering of the outer surface should lead to the production of a cheap and safe oral vaccine [199;200]. We can also foresee many more applications, such as immobilization of proteins with specific binding properties for purification, bioseparation and detection of a wide range of chemical and biological compounds.

Strategies to weaken the yeast cell wall

Yeast cells surrounded by a 'thin cell wall' would be of great value for those agrofactories that want to extract flavours and macromolecules from the intracellular compartments, since rupture of cell wall by mechanical devices is time and money consuming in comparison to downstream steps of the process. The biotechnological challenge has been to generate by metabolic engineering strains that possesses a wall easy to break, without modifying the physiological performance of the industrial yeast strains [201]. Until now, no compromise solution between reducing cell wall and keeping intact the physiological parameters has been achieved [202]. For instance, mutations in PKC1 dependent cell wall integrity pathway cause pleiotropic consequences for industrial applications, whereas strains that produce reduced amount of a βglucans or mannoproteins grow very slowly and induce a cell wall rescue mechanism that actually leads to an increase of cell wall strength [140]. An alternative strategy would be to impair some of the covalent linkages that link together the cell wall components.

Ideal target for antifungal agents ?

Fungal infections in humans range from superficial and cutaneous, like dermatophytose, to deeply invasive, such as candidiasis and cryptococcosis [203]. In the last 25 years, the frequency of systemic, often life-threatening, fungal infections has dramatically increased due to the proliferation of patients who are severely immuno-compromised by cancer chemotherapy, organ transplantation, HIV infection. Current available antifungal drugs for serious infections are either fungistatic (azoles) or fungicidal (polyenes) but also toxic for the host. Cell wall-acting antimicrobial agents are inherently selective and fungicidal, features that make them particularly attractive for clinical development. Three classes of such compounds, targeted respectively to chitin synthase (nikkomycins), β1,3-glucan (echinocandins) and mannoproteins (pradimicins) have entered in clinical development.

Nikkomycins act competitively as substrate analogous of the UDP-N-acetyl-glucosamine in preventing chitin synthesis [204], echinocandins are fatty acid derivatives of cyclic hexapeptides that inhibit non competitively β1,3-glucan synthesis, and the pradimicin family of antifungals exerts its selectivity by calcium-dependent binding of cell surface mannoproteins, which leads to cell wall leakage and loss of viability [205]. While nikkomycins and pradimicins are no longer in development due to their low 'in vivo' efficiency, the echinocandins have emerged as clinically useful and three compounds, caspofungin, micafungin and anidulafungin are in late development (clinical phase II and III) [206]. Although these products are quite promising, continued efforts are necessary to find even better targets at the cell surface. The enzymes involved in cross-linking of the cell wall modules are likely good candidates, but this requires much more attention at the biochemical and enzymological levels, in order to develop high throughput assays to screen natural or chemical libraries that are already available in many pharmaceutical companies.

CONCLUSIONS AND PERSPECTIVES

A clear picture of the cell wall architecture is now emerging thanks to recent biochemical and genetic studies carried out by many public and private research groups worldwide. This knowledge is very important as it will orient our future research programs aimed at optimising cell wall components production for nutrition and to find better antifungal targets. It is clear that the urgent step today is to identify the cross-linking enzymes, the precise sequence by which these crosslinking reactions occur, and their genetic and metabolic regulation. The molecular deciphering of the cell wall repair mechanism is only emerging, and a key issue will be to clarify the cross talks that certainly exist between the different signalling pathways, namely PKC1-MAP kinase, HOG-MAPK, RAS-cAMP, and probably others like TOR [82;207]. Although S. cerevisiae is not known to be pathogen, most of the information collected on this organism will surely facilitate our understanding of the physiology of pathogenic fungi, like Candida albicans.

Figure 1 :

 1 Figure 1: Molecular model of the Saccharomyces cerevisiae cell wall. Yeast cell wall consists of a 100 nm thick extra-cellular matrix. The internal skeletal layer is made of β1,3glucans that form a three dimensional network surrounding the entire cell and strengthened by chitin fibers. β 1,3-glucans are branched with β1,6-glucans side chains which also interact with chitin and function as a flexible tether for GPI-anchored mannoproteins (GPI-CWPs). A second class of mannoproteins (PIR-CWP) are directly linked to β1,3glucans. Other cell-surface proteins are attached to cell wall either by disulphide bridges to other CWPs, or by non specific binding.

  Figure2). The first fully characterized linkage was a β(1 4) link between the reducing terminal GlcNac residue of a chitin chain and the non reducing terminal glucose of a β1,3-glucan chain[66]. Covalent association between mannoproteins, β1,6-glucan and β1,3glucan have been identified later on[24;26;67;68]. Thus, the cell wall modules, i.e. CWP β1,6-glucan chitin and CWP β1,6-glucan β1,3-glucan chitin involve glycosidic attachments between β-glucans and chitin. GPI-CWPs mannoproteins are linked to β1,6polysaccharide via a processed form of GPI anchors. The remnant structure of the GPI anchor of CWPs to which β1,6-glucan is attached harbours the ethanolamine-PO 4 -Man 5 structure [69]. The PIR-CWPs are on the other hand directly linked to the β1,3 glucan through an alkali-labile linkage of yet unidentified nature [3;61]. A model of the yeast cell wall building block is shown in Figure 2.

Figure 2 :

 2 Figure 2: Typical building blocks of the yeast cell wall. Relationships among components of a cell wall module (or building block) are schematically depicted on this figure. See in the text for further details.

Figure 3 :

 3 Figure 3: MAP kinase cascades in Saccharomyces cerevisiae. Five different signalling pathways of S. cerevisiae involve MAPK modules, highly conserved among eucaryotes, which consist of a MAPKKK (or MEKK), a MAPKK (or MEK), and a MAPK (ERK). The receptors which activate the MAPK modules in response to extracellular signals (Inputs) are specific for each of these pathways. The substrates of the activated MAPK (Outputs), among which many are transcription factors, are also specific for each pathway and induce specific cellular responses such as altered patterns of gene expression and protein activity. Question marks indicate that no protein has been identified yet for that step in the cascade.

  . Meanwhile, Rho1 also controls cell wall synthesis by activating the β 1,3glucan synthase [100;101], and by taking part in the actin cytoskeleton organization during polarized growth [102;103]. The activation of the Pkc1-MAP kinase pathway by environmental stress, α-factor treatment, heat shock or cell wall perturbing molecules leads to the dual phosphorylation of the downstream Slt2 MAP kinase on Thr 202 and Tyr 204 residues. It is supposed that this dual phosphorylation results in an active Slt2 kinase [91]. The kinase in turn activates transcription factors, among which Rlm1, a member of the MADS box (MCM1, Agamous, Deficiens, and serum response factor) family of transcription factors [104], which plays a key role in the activation of cell wall related genes [105].

Figure 4 :

 4 Figure 4: A model proposed for the function of Knr4 protein in the Slt2-MAP kinase pathway of Saccharomyces cerevisiae. The dual interaction of Knr4 with Bck2 and Slt2 is one of the elements by which Pkc1-pathway coordinates cell wall integrity with cell growth. Solid arrows indicate activation, double arrowhead indicates protein interaction, and dashed arrow is still suggestive interaction.

ACKNOWLEDGMENTS

We thank colleagues of our laboratory for fruitful discussions related to many aspects of the cell wall work. The work in the authors' laboratory has been supported in part by a grant (QKL3-2000-01537) from the European Commission Framework Program and from 'Fonds de Recherche Hoechst Marion Roussel' (grant FRHMR 2/9972) and from the Region Midi-Pyrenées (grant Rech n°9407652, 9507440 et Rech/9609656).

The yeast Saccharomyces cerevisiae cell wall: Molecular architecture, regulatory pathways and remodelling mechanisms in response to environmental conditions, and biotechnological values

This document was created with Win2PDF available at http://www.daneprairie.com. The unregistered version of Win2PDF is for evaluation or non-commercial use only.