James Aspnes
email: james.aspnes@gmail.com

Joffroy Beauquier
email: joffroy.beauquier@lri.fr

Janna Burman
email: janna.burman@lri.fr

Devan Sohier
email: devan.sohier@uvsq.fr

Time and Space Optimal Counting in Population Protocols

Keywords: 1998 ACM Subject Classification C.2.4 Distributed Systems, I.1.2 Algorithms networks of passively mobile agents/sensors, population protocols, counting, anonymous non-initialized agents, time and space complexity, lower bounds, probabilstic/weak fairness Digital Object Identifier 10.4230/LIPIcs

This work concerns the general issue of combined optimality in terms of time and space complexity. In this context, we study the problem of (exact) counting resource-limited and passively mobile nodes in the model of population protocols, in which the space complexity is crucial. The counted nodes are memory-limited anonymous devices (called agents) communicating asynchronously in pairs (according to a fairness condition). Moreover, we assume that these agents are prone to failures so that they cannot be correctly initialized.

This study considers two classical fairness conditions, and for each we investigate the issue of time optimality of counting given the optimal space per agent. In the case of randomly interacting agents (probabilistic fairness), as usual, the convergence time is measured in terms of parallel time (or parallel interactions), which is defined as the number of pairwise interactions until convergence, divided by n (the number of agents). In case of weak fairness, where it is only required that every pair of agents interacts infinitely often, the convergence time is defined in terms of non-null transitions, i.e, the transitions that affect the states of the interacting agents.

First, assuming probabilistic fairness, we present a "non-guessing" time optimal protocol of O(n log n) expected time given an optimal space of only one bit, and we prove the time optimality of this protocol. Then, for weak fairness, we show that a space optimal (semi-uniform) solution cannot converge faster than in Ω(2 n ) time (non-null transitions). This result, together with the time complexity analysis of an already known space optimal protocol, shows that it is also optimal in time (given the optimal space constrains).

Introduction

In this paper we are interested in the determination of the exact number of nodes in a mobile sensor network. In the considered networks, sensors are typically attached to mobile supports XX:2

Time and Space Optimal Counting in Population Protocols

(vehicles, animals, people, etc.) moving in an unpredictable way. Moreover, nodes may be deployed at large scale. Therefore they should be cheap and consequently can be prone to failures. One can think of sensors attached to zebras (ZebraNet [START_REF] Juang | Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet[END_REF]), pigeons (Pigeon Air Patrol [START_REF]Pigeon Air Patrol project[END_REF]), or public transport vehicles (EMMA project [START_REF] Lahde | A practical analysis of communication characteristics for mobile and distributed pollution measurements on the road[END_REF]). In this context, counting can be part of the task being realized (How many animals have a temperature exceeding some bound?), or part of the managing of the network (Should some nodes be added or replaced?).

In relation with the domain of application we are looking at, we consider that the nodes are anonymous, undistinguishable, have a bounded memory and poor communication capabilities (no broadcast; only a pairwise communication when two nodes come close enough to each other). A distributed computing model that fits this description is the model of population protocols (PP) [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF].

In PP, mobile nodes, which are called agents, can be represented as finite state transition systems. One can imagine that, when two agents are close enough, they interact and the effect of the interaction is a transition with a possible change of states. In this work we study the case of symmetric protocols, where two agents in a transition are indistinguishable if their states are identical (thus, their states have to be identical also after the transition). This assumption makes the protocol design more difficult than in the asymmetric case (as it restrains the set of possible transition rules), but provides a more general solution (correct in both cases).

The mobility and the resulting interactions of agents are completely asynchronous and modeled in a very general way -by a fairness assumption. Here, we study the problem of counting considering two classical fairness assumptions. One ensures that each pair of agents is drawn uniformly at random for each interaction, and the other, weaker assumption (called here weak), ensures only that every pair of agents interact infinitely often. While the probabilistic fairness captures the randomization inherent to many real systems, weak fairness only ensures progress of system entities (see Sec. 2 for an illustrating example).

As the agents are likely to be cheap and prone to failures (memory corruption, crash failures, etc.), re-counting may be required frequently. Since the population of agents may be very large, re-initialization may be infeasible. Hence, it is natural to assume that the agents are not initialized (i.e., an agent can be initially in any possible state). However, it is easy to prove that, in this case, counting in PP is impossible [START_REF] Beauquier | Self-stabilizing counting in mobile sensor networks with a base station[END_REF]. The solution is to use only one initialized and distinguishable agent, called the base station (BST). In this work, for the first time, we also prove, the necessity of such an agent being distinguishable (in case of symmetric protocols; see Sec. 4). BST is also the agent that eventually obtains the correct count of the population. Thus the considered protocols are semi-uniform, in the sense that all the agents, except BST, are a priori undistinguishable and execute the same protocol, for any population size n and upper bound P on n (see Sec. 2 for a formal definition).

In this context, previous works [START_REF] Beauquier | Self-stabilizing counting in mobile sensor networks with a base station[END_REF][START_REF] Izumi | Space-efficient self-stabilizing counting population protocols on mobile sensor networks[END_REF][START_REF] Beauquier | Comptage et nommage simples et efficaces dans les protocoles de populations symétriques[END_REF] and a companion paper [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] study the issue of space complexity (of the counted nodes), a factor that is particulary important in the considered large-scale and unreliable networks. For instance, [START_REF] Beauquier | Self-stabilizing counting in mobile sensor networks with a base station[END_REF] shows that under weak fairness, P (or more) agents cannot be counted with strictly less than P states per counted agent, by deterministic protocols (considered here as well). Here, as a by-product, we present an alternative proof of this result, for the case of symmetric protocols (see Proposition 10). However, as shown in [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF], under probabilistic or global fairness 1 , counting can be performed with only two states (one bit) per counted agent. [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] presents two space optimal solutions to counting in PP, one under weak fairness and the other under global fairness (the latter is also correct under probabilistic fairness). The solution for global fairness uses a memory of only one bit per agent, while the solution for weak fairness needs log P bits (P states) per counted agent. In the latter case, as the number P of states for a given counting protocol is fixed, it represents an upper bound on the size of populations to which the protocol applies, and is considered as an explicit parameter.

In addition to the state space optimality, this paper raises the issue of the convergence time. Our objective is to determine the best guarantees on the convergence times given the established necessary minimum on the memory. To obtain this goal, we show, in particular, that the convergence times of the two previous space optimal solutions (in [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF]) are exponential. In Sec. 3, for reasons explained there, we restrict our attention to so called "non-guessing" counting protocols. We prove that any such state optimal counting protocol, correct under probabilistic fairness, converges in Ω(n log n) expected parallel interactions (Sec. 3.1). In Sec. 3.2, we propose a new state optimal protocol fitting this complexity.

In the case of weak fairness, in Sec. 4, we show that a space optimal solution requires an exponential convergence time (in terms of non-null transitions). In particular, this result shows that the space optimal protocol under weak fairness in [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] is time optimal among the space optimal semi-uniform protocols.

Related Work.

We provide here the most relevant and recent works. Please, refer to [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] for additional related literature on the subject.

Considering PP, [START_REF] Beauquier | Self-stabilizing counting in mobile sensor networks with a base station[END_REF][START_REF] Izumi | Space-efficient self-stabilizing counting population protocols on mobile sensor networks[END_REF][START_REF] Beauquier | Comptage et nommage simples et efficaces dans les protocoles de populations symétriques[END_REF] proposed efficient counting protocols in terms of exact state space that were improved in [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] by space optimal solutions. For weak fairness, the protocol proposed in [START_REF] Izumi | Space-efficient self-stabilizing counting population protocols on mobile sensor networks[END_REF] uses 2P states per agent (only 1 bit more than the optimal) and converges in only O(log n) asynchronous rounds (a round being a shortest fragment of execution where each agent interacts with each other). This presents an interesting trade-off for counting in PP. A recent work [START_REF] Mocquard | Counting with population protocols[END_REF] studies a problem related to counting in random PP, where agents should determine the difference between the number of agents started in state A and the number of those started in state B. In contrast with the current work, [START_REF] Mocquard | Counting with population protocols[END_REF] assumes initialized agents, but similarly to the current work, it investigates the efficiency in terms of both time and space. It presents an O(n 3/2 )-state population protocol that allows each agent to converge to the exact solution by interacting no more than O(log n) times. Additional very recent works (as [START_REF] Alistarh | Time-space trade-offs in population protocols[END_REF][START_REF] Doty | Stable leader election in population protocols requires linear time[END_REF][START_REF] Alistarh | Polylogarithmic-time leader election in population protocols[END_REF][START_REF] Alistarh | Fast and exact majority in population protocols[END_REF]) jointly contribute to the time and space trade-offs study of fundamental tasks, as majority and leader election, in random PP. For example, [START_REF] Doty | Stable leader election in population protocols requires linear time[END_REF] shows that it is impossible to achieve sub-linear leader election with only constant state space per agent, but due to [START_REF] Alistarh | Polylogarithmic-time leader election in population protocols[END_REF] this problem can be solved in O(log 3 n) time with O(log 3 n) states. For majority, sub-linear time is impossible for protocols with at most four states per node, while there exists a poly-logarithmic time protocol which requires a linear in n state space [START_REF] Alistarh | Fast and exact majority in population protocols[END_REF]. [START_REF] Alistarh | Time-space trade-offs in population protocols[END_REF] presents additional upper and lower bounds for these tasks that highlight a time complexity separation between O(log log n) and Θ(log 2 n) state space for both majority and leader election. The present work contributes to the general study of time-space trade-offs in the case of counting.

In the context of dynamic networks with anonymous nodes, recent works [START_REF] Michail | Naming and counting in anonymous unknown dynamic networks[END_REF][START_REF] Luna | Counting in anonymous dynamic networks under worst-case adversary[END_REF][START_REF] Luna | Conscious and unconscious counting on anonymous dynamic networks[END_REF][START_REF] Milani | A faster counting protocol for anonymous dynamic networks[END_REF][START_REF] Di Luna | Brief announcement: Investigating the cost of anonymity on dynamic networks[END_REF], study the counting problem in the synchronous model of dynamic graphs. PP can be also represented by dynamic graphs, but is a completely asynchronous model. Moreover, in contrast with the current study, protocols in these works require that all nodes are initialized. These essential differences make the techniques (e.g., termination detection), extensively used there, inappropriate in our case. Note however that their protocols determining the exact count have exponential convergence time, except the results of [START_REF] Di Luna | Brief announcement: Investigating the cost of anonymity on dynamic networks[END_REF] considering more restricted networks. In some sense this supports the results presented here for weak fairness. [START_REF] Di Luna | Brief announcement: Investigating the cost of anonymity on dynamic networks[END_REF] presents interesting time complexity lower bounds for counting, but considers networks where anonymous nodes can communicate (by broadcast) any amount of data and diffuse it to all other nodes in a constant time w.r.t. n, what is of course impossible in our context.

Due to the difficulty of the problem, a lot of work has been devoted to design protocols counting approximately the number of network nodes (see, e.g., [START_REF] Gkantsidis | Random walks in peer-to-peer networks: Algorithms and evaluation[END_REF][START_REF] Kostoulas | Active and passive techniques for group size estimation in large-scale and dynamic distributed systems[END_REF][START_REF] Ganesh | Peer counting and sampling in overlay networks based on random walks[END_REF][START_REF] Ribeiro | Estimating and sampling graphs with multidimensional random walks[END_REF][START_REF] Baquero | Extrema propagation: Fast distributed estimation of sums and network sizes[END_REF][START_REF] Varagnolo | Distributed statistical estimation of the number of nodes in sensor networks[END_REF][START_REF] Anta | An early-stopping protocol for computing aggregate functions in sensor networks[END_REF]). These protocols use gossiping and probabilistic methods, like probabilistic polling, random walks, epidemic-based approaches, and also exploit classical results on order statistics to infer an estimated number of the nodes. Here, we consider only deterministic protocols for exact counting.

Model and Notations

A system consists of a collection A of pairwise interacting agents, also called a population. Each agent represents a finite state sensing and communicating mobile device. Among the agents, there is a distinguishable agent called the base station (BST), which can be as powerful as needed, in contrast with the resource-limited non-BST agents. The non-BST agents are also called mobile, interchangeably. The size of the population is the number of mobile agents, denoted by n, and is unknown (a priori) to the agents. A (population) protocol can be modeled as a finite transition system whose states are called configurations. A configuration is a vector of states of all the agents. Each agent has a state taken from a finite set of states, the same for all mobile agents (denoted Q), but generally different for BST.

In this transition system, every transition C→C between two configurations C and C is modeled by a single transition between two agents happening during an interaction. That is, when two agents x, in state p, and y, in state q, in C, interact (meet), they execute a transition rule (p, q) → (p , q ). As a result, in C , x changes its state from p to p and y from q to q . If p = p and q = q , the corresponding transition is called null (such transitions are specified by default), and non-null otherwise. 2If there is a sequence of configurations

C = C 0 , C 1 , . . . , C k = C , such that C i → C i+1 for all i, 0 ≤ i < k, we say that C is reachable from C, denoted C * → C .
The transition rules of a protocol are deterministic, if for every pair of states (p, q), there is exactly one (p , q ) such that (p, q) → (p , q ). We consider only deterministic transitions and thus, only deterministic protocols. Transitions and protocols can be symmetric or asymmetric. Symmetric means that, if (p, q) → (p , q ) is a transition rule, then (q, p) → (q , p ) is also a transition rule. In particular, if (p, p) → (p , q ) is symmetric, p = q . Asymmetric is the contrary of symmetric.

Let (p 1 , q 1 ) → (p 2 , q 2 ), (p 2 , q 2 ) → (p 3 , q 3 ), . . ., (p k-2 , q k-2 ) → (p k-1 , q k-1 ), (p k-1 , q k-1 ) → (p k , q k ) be the transition rules of a protocol. Then, we shortly write (p 1 , q 1 ) to p k and q k , respectively. We sometimes call an agent in state p a p-state agent, or just p agent.

An execution of a protocol is an infinite sequence of configurations C 0 , C 1 , C 2 , . . . such that C 0 is the starting configuration and for each i ≥ 0, C i → C i+1 . In a real distributed execution, interactions of distinct agents are independent and could take place simultaneously (in parallel), but when writing down an execution we can order those simultaneous interactions arbitrarily.

An execution is said weakly fair, if every pair of agents in A interacts infinitely often. An execution is said probabilistically fair, if, for each interaction in the execution, a pair of agents in A is chosen uniformly at random. An execution is said globally fair, if for every two configurations C and C such that C → C , if C occurs infinitely often in the execution, then C also occurs infinitely often in the execution. This also implies that, if in an execution there is an infinitely often reachable configuration, then it is infinitely often reached [START_REF] Angluin | The computational power of population protocols[END_REF]. Global fairness can be viewed as simulating randomized systems without introducing randomization explicitly (any probabilistically fair execution is globally fair with probability 1 [START_REF] Jiang | Distributed Systems of Simple Interacting Agents[END_REF]).

A simple example allows to understand better the difference between weak and global (or probabilistic) fairness. Consider a population of 3 agents. Each agent can be white or black, and initially one agent is black and the two others are white. Consider also the protocol in which, when two white agents interact, they become both black and when two agents of different colors interact, they exchange their colors. It is easy to see that there is an infinite weakly fair execution in which there is always one black and two white agents (the black color "jump" indefinitely from agent to agent). At the contrary, every globally fair execution terminates in a configuration in which the 3 agents are black, because otherwise there would be infinitely many configurations during an execution from which the "all black" configuration could be reached, without ever being reached (contradicting global fairness).

A problem is defined by a predicate D on executions. A population protocol P is said to solve a problem D, if and only if every execution of P satisfies the conditions defining D. The problem of counting is defined by the following condition: eventually, in any execution, there is at least one agent (BST, in our case) obtaining a value of n in some (estimate) variable (called c in the following) and this value does not change. Note that the counting predicate has to be satisfied only eventually (and forever after). When it happens, we say that the protocol has converged. A protocol is called silent, if in any execution, eventually, no state of an agent changes [START_REF] Dolev | Memory requirements for silent stabilization[END_REF].

In the case of probabilistic fairness, the convergence time of a protocol is measured in terms of parallel time or parallel interactions, i.e., the independent interactions (of distinct agents) occurring in parallel. It is customary to define one unit of parallel time as n consecutive interactions in a probabilistically fair execution. Then, in this case, the convergence time of a protocol is defined by the expected number of parallel time units in a fair execution till convergence. Moreover, under probabilistic fairness, it appears that technically (in the context of this specific work), we can perform the convergence time analysis in terms of transitions involving BST. It is easy to see that this corresponds to the (asymptotic) expected convergence time in terms of parallel time units.

In the case of weak fairness, the convergence time of a protocol is defined as the maximum number of non-null transitions in a fair execution till convergence.

We consider only semi-uniform protocols (cf. [START_REF] Dolev | Self-stabilization of dynamic systems assuming only read/write atomicity[END_REF][START_REF] Tel | Introduction to Distributed Algorithms[END_REF]) in the sense that all agents, except BST (whence semi-), are a priori indistinguishable and interact according to the same transition rules. Moreover, the protocol functions similarly for any n and any upper bound P on n. More formally, we can define a semi-uniform protocol so: Definition 1. A protocol PP is called semi-uniform if for any upper bound P and any execution prefix e in which only agents from a subset S ⊂ A (including BST) interact, the (standard) projection3 e| S of e on the agents of S is an execution prefix of PP for any bound P such that |S| ≤ P < P .

Remark. Similarly, if e is an execution prefix of a semi-uniform protocol PP for n ≤ P , it is also an execution prefix of PP for n s.t. n ≤ n ≤ P and P ≤ P , if we consider e as an execution prefix for p, and then extend the configurations of e with n -n agents (missing in e and performing no interactions in the extended prefix).

3

Time and Space Optimal Counting under Probabilistic Fairness

Time Lower Bound for a Space Optimal Protocol

Defining time optimality for a counting protocol asks to be cautious. Indeed, a protocol could be efficient for counting some set of agents and slow for counting others. Think of a protocol that "guesses" initially a count and checks afterwards whether this count is correct or not. On the right set of agents, this counting protocol would converge in zero time. For other sets it is certainly less efficient than the protocols which estimate the count gradually, starting from 0. We would like to avoid such behavior and thus restrict our attention to protocols having always a "proof" that the estimate they have corresponds to a lower bound on the actual population size (i.e., they have observed a sequence of interactions that justifies this count). For such protocols, called here "non-guessing", the estimate of the size (in the variable c) is a non-decreasing function along an execution (and so c is always a lower bound on the number of agents in the population). In the sequel of the section, we consider an arbitrary state-optimal protocol Count and we prove that it converges in expected Ω(n log(n)) interactions with BST, or equivalently Ω(n 2 log(n)) interactions between agents, or Ω(n log(n) parallel time. Count uses (optimally) only two states per mobile agent (with one state, counting is impossible [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF]). Note also that the result in this section does not assume that Count is symmetric. We call trace of an execution prefix the sequence of transitions of BST in this prefix. Thus, a trace T is a sequence of transitions of the form (s BST , i) → (s BST , j), where s BST and s BST are states of BST, and i and j are states of a mobile agent in the corresponding interaction. Note that this sequence captures all the information that BST has, and completely determines its state. Let us denote by x(T ) the minimal population size for which there exists at least one execution prefix with trace T . Thus, since the estimate counter c is non-decreasing, we have c ≤ x(T ): if it was not the case, by definition of x(T ), the protocol could run with x(T ) agents and estimate, at some point of the execution, that c > x(T ); then, to converge, the protocol would be required to decrease c, which is impossible by the assumption above. We denote by x i (T ) the minimal number of mobile agents in state i (w.l.o.g., i ∈ {0, 1}) in a configuration at the end of any possible execution prefix corresponding to trace T (and with x(T ) agents). Obviously, for all execution prefixes with n agents and a trace T , we have

x 0 (T ) + x 1 (T ) ≤ x(T ) ≤ n.
The idea behind Lemma 2 is that, if there is such a transition rule of mobile agents that can decrease the number of agents in state i, then when several such agents are present in the population, making them interact and execute this transition will decrease their number to the minimum. The proof appears in the appendix.

Lemma 2. If the considered protocol Count has a transition rule that allows to decrease the number of agents in state i through interactions between mobile agents (rules

(i, i) → (i, 1 -i), (i, i) → (1 -i, 1 -i) or (i, 1 -i) → (1 -i, 1 -i))
, then for any trace T , we have x i (T ) ≤ 1. Lemma 3. Let T be a trace obtained from a trace T by adding a transition (s BST , i) → (s BST , j) between BST and a mobile agent. If x(T ) > x(T ), then x 1-i (T ) = x(T ) and x(T ) = x(T ) + 1.

Proof. We show the contrapositive: if

x 1-i (T ) < x(T ), then x(T ) = x(T ); if x 1-i (T ) = x(T ), then x(T ) = x(T ) + 1.
Let the added interaction in T be (s BST , i) → (s BST , i):

If x 1-i (T ) < x(T )
, some executions with trace T and x(T ) agents lead to a configuration with x(T ) -x 1-i (T ) > 0 agents in state i. These agents may interact with BST, so that there still exist executions with trace T and with x(T ) agents, and with the same number of agents in both states. Thus x(T ) = x(T ), x 0 (T ) = x 0 (T ), and

x 1 (T ) = x 1 (T ); If x 1-i (T ) = x(T ) (which implies that x i (T ) = 0
), all executions with trace T and x(T ) agents contain no agent in state i. Thus, x(T ) = x(T ) + 1 (it cannot be higher, since one can build an execution with x(T ) agents interacting in pattern resulting in trace T , and an extra agent in state i that does not interact, then released for this last interaction). Since, as a result of this interaction, an agent in state i remains, if no rule (i,

1 -i) → (1 -i, 1 -i) can remove it, x i (T ) = 1, else x i (T ) = 0. In addition, x 1-i (T ) = x 1-i (T )
, because the execution described above with x(T ) = x(T ) + 1 agents results in a configuration with x 1-i (T ) agents in state i. Finally, we have:

x(T ) = x(T ) + 1, x i (T ) ≤ 1, and x 1-i (T ) = x 1-i (T ).
Now, let the added interaction in T be (s BST , i) → (s BST , 1 -i):

If x 1-i (T ) < x(T ), some executions with trace T and x(T ) agents contain agents in state i. These agents may interact with BST, so that there still exist executions with trace T and with x(T ) agents, and with an agent in state i that has changed its state. Thus

x(T ) = x(T ), x i (T ) = max{x i (T ) -1, 0}, and x 1-i (T ) ≤ x 1-i (T ) + 1. If x 1-i (T ) = x(T ) (which implies that x i (T ) = 0
), all executions with trace T and x(T ) agents contain no agent in state i. Thus, trace T cannot be achieved with x(T ) agents, and x(T ) ≥ x(T ) + 1. T can be achieved by adding an extra agent in state i during trace T and releasing it to realize the last interaction, so that x(T ) = x(T ) + 1. An agent in state i has its state changed to 1 -i, so that x i (T ) = max{x i (T ) -1, 0}, and

x 1-i (T ) ≤ x 1-i (T ) + 1.
Thus, x can increase only as the result of an interaction of BST with an agent in state i such that x 1-i = x. After this interaction, to increment x again, BST must increment x 1-i , which it can do only by switching an agent state to 1 -i.

In particular, this implies that, if interactions between mobile agents can decrease the number of agents in both states 0 and 1, x i ≤ 1 for i ∈ {0, 1}, and x ≤ 2, i.e., any trace can be obtained with two agents only, and Count is incorrect.

Theorem 4. A two-state non-guessing counting protocol Count (correct under probabilistic fairness) converges in Ω(n log n) expected interactions with BST (equivalently, in Ω(n log n) expected parallel time).

Proof. Consider a converging execution of this protocol with n ≥ 3 mobile agents. Denote by T the trace of this execution until x(T ) = n (which occurs, since the protocol converges), and by T the trace obtained from T by removing its last interaction. Denote by i the mobile agents state such that x i (T ) = x(T ) = n -1 > 1 (this state exists by Lemma 3).

Thus, x i must increase from 0 to n. Now, x i increases only when BST meets an agent in state 1 -i and changes its state to i, and the number of mobile agents in state 1 -i can only increase in an interaction with BST (from Lemma 2, as x i (T ) > 1, no interaction between mobile agents can increase the number of agents in state 1 -i). Thus, in the last configuration before convergence with x i = 0, all agents are in state 1 -i (because x i eventually reaches n, and can increase only when a mobile agent state is switched from 1 -i to i).

Thus, in any converging execution, there is a configuration in which all agents are in state 1 -i, and then all agents are switched to state i in interactions with BST (except possibly one, that has been counted by BST, and will be switched to state i by it only in a further interaction). Now, if k agents are in state i, the probability for BST to meet an agent in state 1 -i in its next interaction is n-k n , and the expected number of interactions (involving BST) before meeting an agent in state i and incrementing x is n n-k . So, the expected length of an execution before convergence is

≥ n-1 k=0 n n-k = n l=1 n l = n n l=1 1 l = nH n , with H n the nth harmonic number. It is known that H n = Θ(log n), hence the result.
Given that there are n agents in the system, one interaction out of n involves BST in average. Hence, the expected Ω(n log n) interactions with BST are equivalent to expected Ω(n 2 log n) interactions between agents, and to the expected Ω(n log n) parallel time.

Time and Space Optimal Protocol (Prot. 1)

The one bit space optimal protocol of [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] is recalled in the appendix (Prot. 2) together with its time complexity analysis that gives the average convergence time of Θ(2 n ) interactions. In this section, we modify Prot. 2 to obtain an (asymptotically) time optimal protocol, Prot. 1, converging in O(n log n) time, and still optimally using only one bit of memory per mobile agent. We present and prove this protocol and its convergence time below.

In Prot. 1, each mobile agent can be in one of two states 0 or 1, and respectively called 0 or 1 agent. We write c 0 and c 1 for the protocol's count of 0 and 1 agents resp., and n 0 and n 1 for the actual number of 0 and 1 agents in the population. The total number of agents is then n = n 0 + n 1 and the base station's estimate of n is c = c 0 + c 1 . The values c 0 and c 1 are both initialized to 0. They may be seen as the implementations of the x 0 and x 1 used in the lower bound proof in the previous subsection.

The modified protocol proceeds in alternating phases. In a zero phase, BST only converts zeros to ones. Whenever it does so, it decrements c 0 if it is positive and increments c 1 . In a one phase, it does the reverse. We start the protocol in a zero phase.

The same argument as for the original protocol shows that c b ≤ n b holds as an invariant and that c = c 0 + c 1 is non-decreasing over time (Lemma 1 in [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF]). If, in addition, we can stay in two phases long enough that every agent is converted from b to 1 -b in the first phase, and then every agent is converted from 1 -b to b in the second phase, at the end of the second phase we will have c = n, giving convergence.

Let us now specify when BST switches between phases. Suppose that BST is going to start in a b phase. We adopt the following procedure (in two stages): The first rule (the pre-phase) guarantees that whenever we start a b phase, c 1-b is always zero. This in turn guarantees that c b is never lower at the start of a b phase than it is at the start of any previous b phase. Proof. Suppose we are in a b phase. Using standard bounds on the Coupon Collector Problem it holds with high probability that BST has interacted with every agent after O(n log n) interactions. So either the phase has already ended, or every agent now carries 1 -b. In the latter case, the phase can run for at most 6(n ln n + 1) = O(n log n) interactions before ending.

We now show that, on average, the protocol executes O(1) phases. This requires the following technical lemma showing that BST finds all b agents in a b phase if there are enough to begin with. Proof. For simplicity we will assume b = 0; the b = 1 case is symmetric. So we are looking at a zero phase that starts with n 0 ≥ n/2. From the structure of the protocol, we know that at the start of this phase, c 1 = 0, but c 0 might be larger. It happens that the worst case is when c 0 = 0, but we will analyze the process for any initial value of c 0 .

In the analysis below we will fix n 0 , n 1 , to their values at the start of the phase. To keep track of what happens, let i be the number of zero values converted to ones so far during this phase; given the value of i, this gives n 0 -i zeros and n 1 + i ones in the population, and the value of the c 1 register will be i. We fail to convert all zeros to ones if we exit the phase while i is less than n 0 .

For each particular value of i, this occurs only if (a) c 0 is already 0, and (b) BST observes 6(n ln n + 1) ones in a row. Whether or not c 0 = 0, the latter event occurs with probability exactly

n 1 + i n 6(i ln i+1) (1)
which by the union bound gives an upper bound on the probability that we leave the phase for any i < n 0 of

n0-1 i=0 n 1 + i n 6(i ln i+1) (2)
We will bound this sum by considering the terms with i < n 0 /2 and i ≥ n 0 /2 separately. The detailed computations for each case appear in the appendix and give a bound of 2/5 for the case i < n 0 /2, and 1/200 for i ≥ n 0 /2. The original sum is thus bounded by 2/5 + 1/200 < 1/2 for all n > 0, giving the claimed bound.

Theorem 7. The modified protocol (Prot. 1) converges to c = n in an expected O(n log n) interactions with BST (equivalently, in an expected O(n log n) parallel interactions).

Proof. There are two cases, depending on the initial value of n 0 . 1. If n 0 ≥ n/2 in the starting configuration, then n 0 ≥ n/2 at the start of each zero phase.

From Lemma 6, BST converts all zeros to ones in any of these phases with probability at least 1/2. If this event occurs, the following one phase converts all ones to zeros with probability at least 1/2 as well, giving a probability of at least 1/4 for each pair of phases that we converge to the correct count. Thus the protocol converges in an expected 4 • 2 = 8 phases. 2. If n 0 < n/2, then the initial zero phase ends with at least n/2 ones (because any conversion during this phase can only increase the number of ones). So the first one phase starts with n 1 = n/2. Repeating the above analysis shows that the protocol converges after at most 8 phases on average on top of the initial zero phase, giving an expected 9 phases total. Because each of these O(1) phases takes O(n log n) expected interactions (Lemma 5), this gives a total expected number of interactions of O(n log n).

Time Lower Bound for Space Optimal Counting under Weak Fairness

To obtain this lower bound we first prove properties that have to be satisfied by any space optimal symmetric counting protocol functioning under weak fairness. These properties are important by themselves, as they can be useful in future studies of counting under weak fairness in PP. For instance, Proposition 8, states that a counting protocol has to distinctly name all the agents in any population of size n < P . Recall that P is the upper bound on the size n of the population.

XX:11

Next, from Proposition 8 and Lemma 9, it easily follows that any symmetric counting protocol under weak fairness has to use at least P states per mobile agent (to be able to count any population of at most P agents). This gives a somewhat simpler proof than the original one in [START_REF] Beauquier | Self-stabilizing counting in mobile sensor networks with a base station[END_REF].

The next important property, given in Proposition 11, is that any space optimal symmetric counting protocol under weak fairness has a unique "sink" state m s.t., for every possible state s ∈ Q of a mobile agent, there is a transition sequence (s, s) * → (m, m), with (m, m)→(m, m) and m cannot be one of the distinct names given by the protocol in case n < P .

The results above show in particular that, for any considered space-optimal counting protocol, if mobile agents are not named yet, agents in state m will continue to appear (for any P and n ≤ P ).

Moreover, recall that we consider counting with non-initialized mobile agents. In this case, to overcome the known impossibility [START_REF] Beauquier | Self-stabilizing counting in mobile sensor networks with a base station[END_REF], we assume one initialized and distinguishable agent BST that eventually counts the other n (mobile) agents. Note that having a distinguishable agent is necessary. To see this, consider a starting configuration where all agents start at the same state (which has to be equal to the state of the only initialized agent). If the size of the population is even, by Proposition 11, there is a weakly fair execution reaching and staying in the configuration where all agents are in the "sink" state m, and by Proposition 8, no counting can be realized.

Using the above-mentioned properties and those of semi-uniform protocols (see Definition 1 in Sec. 2), we prove the lower bound given in Theorem 14. This is one of the main results of the paper. It shows that, under weak fairness, counting undistinguishable, state-optimal and non-initialized agents in symmetric PP is a costly task in terms of a convergence time. It takes Ω(2 n ) non-null transitions.

Finally, we show (Proposition 15 in the appendix) that the space optimal protocol for weak fairness presented in [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] converges in Θ(2 n ) non-null transitions. This proves that this is a time optimal protocol among all the space optimal semi-uniform protocols, under weak fairness.

Proposition 8. Let Count be a (silent or not) counting protocol correct under weak fairness (for any n ≤ P ). For any weakly fair execution e = C 1 , C 2 , C 3 , . . . , C j , . . . of Count on a population A of size n < P , there is an integer k such that, for any j ≥ k, no two mobile agents are in the same state in C j .

Proof. Let us assume, by contradiction, that in e, there are infinitely many configurations with two agents in the same state. Since the state space is finite and the number of agents too, two specific agents x 2 and x 3 from A are necessarily simultaneously in some state s ∈ Q in infinitely many configurations. Let C j1 , C j2 , C j3 , . . . be these configurations such that e = e 1 , C j1 , e 2 , C j2 , e 3 , C j3 , . . . W.l.o.g., we choose these configurations such that, in every execution segment e i , every agent in A interacts with every other (this is possible with weak fairness). Now consider a population A = A ∪ {x 1 } of size n + 1. To prove the proposition, we will construct a weakly fair execution e of Count in population A where no agent can distinguish e from e, and where consequently Count wrongly counts only n agents instead of the existing n + 1.

We construct e based on e. First, we assume that in e , x 1 is in state s in the starting configuration, and e = e 1 , C j1 , e 2 , C j2 , e 3 , C j3 , . . . such that each segment e i follows the same transition sequence as in e i , but where the agents x 2 or x 3 participating in the corresponding interactions can be replaced by x 1 in the appropriate state, as we explain below. We ensure also that in every C ji , each of the three agents x 1 , x 2 , x 3 is in state s.

More precisely, in segment e 3r+1 , C j3r+1 (r ≥ 0), agent x 1 does not interact with the rest of the agents, and all the others interact exactly as in e 3r+1 , C j3r+1 (each agent x i is in state s in C j3r+1 ). In e 3r+2 , C j3r+2 , agent x 2 does not interact with the rest of the agents, and x 1 replaces x 2 in all the interactions where x 2 interacts in e 3r+2 , C j3r+2 , and all the others interact as in e 3r+2 (but with x 1 instead of x 2 in the corresponding interactions). Each agent x i is in state s in C j3r+2 . In e 3r+3 , C j3r+3 , agent x 3 does not interact with the rest of the agents, and x 1 replaces x 3 in all the interactions where x 3 interacts in e 3r+3 , C j3r+3 , and all the others interact as in e 3r+3 (but with x 1 instead of x 3 in the corresponding interactions). Each agent x i is in state s in C j3r+3 .

We emphasize again that e is possible, because in every C ji , each of the three agents x 1 , x 2 , x 3 is in state s, so any of them can replace any other in the transition sequence of the next segment e i+1 . Moreover, e is weakly fair, because each agent x i interacts with all the other agents in the appropriate e i segments (and by the assumption on e i ), and other agents too, due to the weak fairness of e. Finally, in e , every agent from A (including BST), executes exactly the same sequence of transition rules as it does in e, so no agent can distinguish the fact that the population is actually A with n + 1 agents, and Count counts only n agents as it does in e. This is a contradiction to the assumption that Count is a correct counting protocol.

The proof of Lemma 9 uses similar techniques as the proof of Proposition 8 and appears in the appendix.

Lemma 9. Let Count be a symmetric (silent or not) counting protocol correct under weak fairness (for any n ≤ P ). Consider any weakly fair execution

e = C 1 , C 2 , C 3 , . . . , C j , . . . of
Count on a population A of size n < P . There is an integer k such that, for any j ≥ k, no mobile agent is in a state m ∈ Q such that there is a possible sequence of transitions of Count (m, m) * → (m, m).

The following two propositions follow from Proposition 8 and Lemma 9. A proof of Proposition 10 uses similar techniques as the proof of Proposition 11 and appears in the appendix.

Proposition 10. Any symmetric counting protocol Count correct for any n ≤ P (undistinguishable and non-initialized) mobile agents, under weak fairness, has to use at least P states per mobile agent.

Proposition 11. Consider any symmetric (silent or not) counting protocol Count correct under weak fairness (for any n ≤ P ), and using at most P states per mobile agent. For every state s ∈ Q, there is a transition sequence (s, s) * → (m, m), s.t. m is unique and does not appear infinitely often in executions with n < P . Moreover, (m, m)→(m, m).

Proof. As Count is symmetric, any two agents, both in some state s ∈ Q, in an interaction, have to execute a symmetric transition of the form (s, s) → (s 1 , s 1 ). Thus there is a possible sequence of transitions (s, s) → (s 1 , s 1 ) → (s 2 , s 2 ) → (s 3 , s 3 ) . . . As mobile agents are finite state, for some j > i ≥ 1, s i = s j , i.e. (s i , s i ) * → (s i , s i ). By Lem. 9, s i = m s.t. m does not appear infinitely often in executions with n < P . As there are at least P -1 states appearing infinitely often in an execution with n = P -1 (by Proposition 8), there is at most one such possible state m in a P state protocol. Thus, the first part of the lemma holds.

Finally, by contradiction, if (m, m)→(s, s) s.t. s = m, then the previous part of the proof implies (s, s) * → (s, s). When n = P -1, and as Count uses only P states, and m never appears infinitely often in an execution, s does appear infinitely often in configurations of an execution (by Proposition 8). This is a contradiction to Lem. 9. Thus, (m, m)→(m, m).

To prove the lower bound (Theorem 14), in addition to the results above, we use the following definitions related to the considered counting protocols.

Definition 12.

We call homonyms, or homonymous agents, mobile agents in the population having the same state, but different from m. We say that two (or more) homonyms (in state s) are reduced (to m) whenever a sequence of transitions (s, s) * → (m, m) is applied to them. We say that a mobile agent is named if it has a state different from m (a name). A group of agents is named if each of them is named with a distinct name. Similarly, a configuration of agents is named, if all the agents in this configuration are named. A reduced (from homonyms) configuration is a configuration without any homonym. Given a configuration C, let R(C) be the set of names of mobile agents appearing an odd number of times in C, i.e., the set of names appearing in the corresponding reduced configuration. For any two sets E, E ⊆ {1, . . . , n}, we denote by

E E ≡ E ∪ E -E ∩ E their symmetric difference. In particular, E {e} (e ∈ {1, . . . , n}) is E ∪ {e} if e / ∈ E, and E -{e} if e ∈ E.
A stationary point (or state) of BST is a state s BST of BST such that (s BST , m) → (s BST , m) and s BST is also stationary. (Note that this transition sequence can be broken, i.e., BST can change its state to a non-stationary one, after an interaction with an agent in a state s = m.) The naming sequence is a sequence U = (s i BST , s i ) i≥1 of pairs (s i BST , s i ), where s i BST is a BST state and s i is a mobile agent state. U is defined inductively as follows: s 1 BST is the initial state of BST, and for any i ≥ 1, (s i BST , m) → (s i+1 BST , s i ) is a transition rule of the protocol. Let U j be a prefix of U s.t. U j = (s i BST , s i ) 1≤i≤j .

To obtain the result of Theorem 14, we focus on the set of the longest execution prefixes where BST meets and names agents in state m (according to the fixed naming sequence, defined in Def. 12). In such prefixes, we study the possibility of the occurrence of a stationary point (Def. 12). We show that, for a semi-uniform counting protocol (Definition 1, Sec. 2), for any n < P , such a point does not exist (Lemma 13), before BST has named all the n agents. That is, in the case of the considered executions, BST will continue giving names to m-state agents that it meets (it won't be "blocked" waiting for some named agent, for possibly deciding to change its strategy accordingly).

So, using Lemma 13, we prove that there exists an execution prefix in which BST continuously meets and names agents in state m without entering a stationary state. Then, we show that the longest such prefix corresponds to the naming sequence of length Ω(2 n ). This is by observing that the number of starting unnamed (reduced) configurations is 2 n -1, for n = P -1, and that after each step (transition) of the naming sequence, BST can accomplish naming of only one such starting configuration. To prove the result for any n and P , we use Definition 1 of semi-uniform protocols. Intuitively, for such a protocol, when only a subset of a population of x < n agents interacts with BST, BST should behave like P = x is possible, even if it is larger.

In the following lemma, we show that the naming sequence does not contain any stationary state.

Lemma 13. Let Count be a symmetric (silent or not) semi-uniform counting protocol correct under weak fairness (for any n ≤ P ) and using P states per mobile agent. The naming sequence U (Def. 12) of Count does not contain any stationary state.

Proof. Assume by contradiction that the first stationary state in U = (s i BST , s i ) i≥1 is in the k th step (element), i.e., the state s k BST is stationary, for some k > 0. In the following, we assume that P > 2k (we justify this assumption later) and for any j ≥ 0, we construct an execution e j of Count for a population of 2k + j (< P ) agents. In e j , k + j agents are initially in state m, while the k other agents are in states s 1 , s 2 , . . . , s k (these are the states s i appearing in U ). Each e j is composed of two phases.

In the first phase, let k m-state agents interact one by one with BST, and at the end of this phase (by the definition of U ) the states of these agents are s 1 , s 2 , . . . , s k . Notice that now among these k agents (call it the first sub-population), those that have names have homonyms in the second sub-population (of other k + j agents). Notice also that, by Definition 1 of semi-uniform protocols, this is also a prefix of an execution projected on a population of only k agents. By the same property, this can be also a prefix of execution for a larger population and for an upper bound P as large as we want. Thus, P > 2k is a valid assumption.

In the second phase, let every named (let us say, by s) agent of the first sub-population interact with its homonym in the second sub-population, s.t. the sequence of transitions (s, s) * → (m, m) takes place for each such pair of homonyms (possible by Proposition 11). At the end of this second phase, all agents are thus in state m (at most 2k were homonyms at the end of the first phase, and j were initially in state m and never interacted). Now, no matter how the agents continue to interact, as all mobile agents are in state m, and BST is in a stationary state s k BS , all mobile agents remain forever in state m (Proposition 11) and BST remains in a stationary state (by definition of such a state). Thus, after the second phase, we make all pairs of agents interact infinitely often to obtain a weakly fair execution for any j. In all these constructed executions, no agent can distinguish between the executions and the corresponding population sizes (2k + j < P agents for any j ≥ 0), and thus a correct counting cannot be obtained.

By Definition 1 of a semi-uniform protocol, the projection of the first phase (of any e j ) on the first sub-population (a group of k agents interacting with BST in this phase), is also a prefix of an execution of Count for a bound P ≥ k (k ≤ P ≤ P ). Thus, for any such k and P , there is no stationary point in U k . In other words, the lemma holds for any value of k and P , and thus also for any prefix of U . Theorem 14. Let Count be a symmetric (silent or not) semi-uniform counting protocol correct under weak fairness (for any n ≤ P ) and using P states per mobile agent. The convergence time of Count is at least 2 n -1 non-null transitions.

Proof. We will build an execution of Count where the length of the corresponding naming sequence U before convergence (and thus the convergence time of Count) is at least 2 n -1.

Consider a population of n = P -1 agents. Consider a possible execution prefix e where BST interacts only with m-state agents as long as they are not distinctly named. If the agents are not distinctly named, by Proposition 11, there is always either at least one agent in state m, or some homonyms that can be reduced to m. So, assume that in e, whenever the mobile agents are not distinctly named and there is no agent in state m, a reduction of some homonyms is done. Then, an agent in state m interacts with BST. By Lemma 13, in every such corresponding transition, the state of BST is not stationary, and thus eventually an m-state mobile agent is "given" a name by BST. Let us repeat this scenario, until all the n agents are named. This is an execution prefix e (with n = P -1) that we consider below.

By Lemma 13, Count has to name n = P -1 mobile agents, starting from any unnamed configuration C j . For this specific case of n = P -1, there is exactly one possible configuration XX:15 C * (ignoring the state of BST and the permuted configurations 4 ) where all n mobile agents are named. Notice that R(C * ) = Q \ m (R() is defined in Def. 12). Consider a prefix U j = (s i BS , s i ) 0≤i≤j of the unique naming sequence U . Notice also that, by Def. 12, A B = A B iff A = A . This implies that, given U j , there is a unique R(C j ) such that R(C j ) {s 1 } {s 2 } {s 3 } . . . {s j } = {a 1 , a 2 , . . . , a P -1 } = R(C * ) = Q \ m. As |{R(C j ) : C j is any possible unnamed starting configuration}| = 2 P -1 -1, the length of U is at least 2 P -1 -1 = 2 n -1. Hence, the length of the longest execution e is at least 2 n-1 -1 s.t. n = P -1. By the Remark following Definition 1, e is also an execution prefix for any bound ≥ P , given the same population size. Thus, the theorem actually holds for any n and any upper bound P on n.

Conclusion and Perspectives

This work is a sequel to [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] and it answers the questions concerning time complexity of the symmetric space optimal protocols proposed there. What can be learned from the current work is that there exists a big difference, not only in terms of the required space, but also in terms of time complexity, between the case where the interactions between agents are random and the case where they are only weakly fair. From a more practical point of view, it would be interesting to investigate if this difference still exists when more memory space is given to the agents. We already know that, concerning weak fairness, a supplementary bit (2P states) allows to design protocols like in [START_REF] Izumi | Space-efficient self-stabilizing counting population protocols on mobile sensor networks[END_REF] with a logarithmic round complexity (a round being a shortest fragment of execution where each agent interacts with each other), while another additional bit allows to solve this problem in only constant number of rounds [START_REF] Beauquier | Self-stabilizing counting in mobile sensor networks with a base station[END_REF]. Concerning global or probabilistic fairness, there exist less studies about counting protocols and especially about their complexity analysis. For example, it would be certainly interesting to determine which size of memory is needed, for having an expected constant convergence time. More generally, studying formally the tradeoffs between space and time complexities for counting algorithms in population protocols could be a valuable sequel to the present work. possible non-null transitions are between homonyms. Each agent in such a transition changes its state to 0, and its next non-null transition necessarily involves BST. Thus, there cannot be more than 2 n non-null transition between homonyms. Hence, the proposition follows.

Convergence Time Analysis of Protocol 2 [9]

Protocol 2 -Space Optimal Counting under Global or Probabilistic Fairness [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] Variables at BST: c 0 : non-negative integer, initialized to 0; c 1 : non-negative integer, initialized to 0; c: non-negative integer initialized to 0; eventually holds n Variable at a mobile agent x: b: in {0, 1}, initialized arbitrarily We evaluate the convergence time of Protocol 2 in terms of the average number of transitions, assuming probabilistic fairness (uniformly random interactions). Note that, in case of this protocol, any transition involves BST. Below, we sketch the analysis and after we give the details.

To compute the convergence time, we use the observation (stated by Lemma 16 appeared and proven below) that Protocol 2 must first reach a configuration with all mobile agents in the same state, and then a configuration with all the agents in the other state (recall that there are only two mobile agent states). Thus, consider a population of n agents, and let t k be the average number of transitions that happen before all agents are in state 0, starting from a configuration with k agents in state 1. Then, t 0 = 0 trivially. For 1 ≤ k ≤ n -1, t k = 1 + k n t k-1 + n-k n t k+1 . This is because, at the current step, there are k chances out of n that an agent in state 1 meets BST, leading to a configuration with k -1 agents in state 1; and n -k chances out of n that an agent in state 0 interacts with BST resulting in a configuration with k + 1 agents in state 1. Finally, t n = 1 + t n-1 .

From that we have t n = 2 n-1 n-1 Proof. Thus, the counting is achieved in C 1 . This happens following an interaction of BST with an agent, let us say w.l.o.g., in state 0. By definition, c = c 0 + c 1 = n, and since c increases in this interaction, we had and we still have c 0 = 0 (otherwise, c cannot increase). Then, after this transition, c 1 becomes n.

XX:21

We show now that at the last transition with c 1 = 0, before C 1 has been reached (at least the first step is such), all agents were in state 0 (this will prove the existence of C 0 ). Denote by r the number of 1-0 transitions (transitions changing a state of a mobile agent from 1 to 0). Then, the number of 0-1 transitions is n + r, since 1-0 transitions increment c, and 0-1 ones decrement it (c 1 never goes to 0, by assumption). Thus, BST meets n + r agents in state 0 that turn to 1, and r in state 1 that turn to 0. This creates n new agents in state 1 thus, at the step when c 1 = 0, all agents were in state 0. Thus, consider a population of n agents, and let u k be the average number of transitions that happen before all agents are in state 0, starting from a configuration with k agents in state 1.

We have the following relations: u 0 = 0 by definition; for 1 ≤ k ≤ n -1, u k = 1 + k n u k-1 + n-k n u k+1 : at the current step, there is k chances in n that an agent with mark 1 meets BST, leading to a configuration with k -1 agents with mark 1, and n -k chances in n that an agent marked 0 interacts with BST resulting in a configuration with k + 1 agents marked 1;

u n = 1 + u n-1 .
For 0 ≤ k ≤ n -1, set v k = u k+1 -u k . We have:

v n-1 = 1 ∀1 ≤ k ≤ n-1, v k-1 = u k -u k-1 = u k -n k u k -1 -n-k n u k+1 = k-n k u k + n k + n-k k u k+1 = n-k k v k + n k Thus, for 0 ≤ k ≤ n -1 v n-k = n-1 i=n-k+1 n -i i + k-1 i=1 k j=i j n -j n i = (n -k)!(k -1)! (n -1)! + n k-1 i=1 (k -1)!(n -k)! i!(n -i)! = = n k-1 i=0 (k -1)!(n -k)! i!(n -i)! v n-k = 1 n-1 k-1 + n k-1 i=1 (k -1)!(n -k)! n! n! i!(n -i)! = 1 n-1 k-1 + k-1 i=1 n i n-1 k-1 = k-1 i=0 n i n-1 k-1
From that, we get:

u n = n-1 k=0 v k = n-1 k=0 k i=0 n i n-1 k
First, consider the case when n is even:

u n = n/2-1 k=0 k i=0 n i n-1 k + n-1 k=n/2 k i=0 n i n-1 k u n = n/2-1 k=0 k i=0 n i n-1 k + n-1 k=n/2 2 n - n i=k+1 n i n-1 k

1 .

 1 (pre-phase) Flip any b agents we encounter to 1 -b as long as c b > 0. 2. (the phase itself) Continuing flipping any b agents BST encounters to 1 -b until it sees 6(c b ln c b + 1) agents marked 1 -b in a row without seeing an agent marked b. If this event occurs, flip the phase (switch to the 1 -b phase).

Protocol 1 -c b ← c b + 1 8 :c ← c 0 + c 1 ForLemma 5 .

 1815 Time and Space Optimal Counting under Probabilistic Fairness Variables at BST: c 0 : non-negative integer, initialized to 0; eventually holds n 0 c 1 : non-negative integer, initialized to 0; eventually holds n 1 c: non-negative integer initialized to 0; eventually holds n cnt: non-negative integer initialized to 0 phase ∈ {0, 1}, initialized to 0 Variable at a mobile agent x: b ∈ {0, 1}, initialized arbitrarily 1: when a mobile agent x with mark b interacts with BST do else if cnt ≥ 6(c b ln c b + 1) the convergence bound, begin by bounding the likely length of a phase: Each phase requires O(n log n) parallel interactions with high probability.

Lemma 6 .

 6 If phase b starts with n b ≥ n/2, then it ends with n b = 0 with probability at least 1/2.

1 : 4 :b ← 1 -b 5 : c b ← c b + 1 6 :

 14156 when a mobile agent x interacts with BST do2: if c b > 0 then 3: c b ← c b -1 c ← c 0 + c 1

k=0 1 (= 2 nLemma 16 .

 1216 + o(2 n ), and the average convergence time of Protocol 2 is Θ(2 n ) transitions. The formal proof is below. In the first configuration C 1 after the convergence of Protocol 2, i.e., the first time when c = n (and does not change after), all agents have the same mark m ∈ {0, 1}. Moreover, there is a configuration C 0 s.t. C 0 * → C 1 , and all agents in C 0 are in state 1 -m.

Global fairness can be viewed as simulating probabilistic one without introducing randomization explicitly. One can see probabilistic fairness as a quantitative version of the global one. Moreover, it allows to analyze protocols' time complexity, what is impossible in general with global fairness (see Sec.

2).

For simplicity, in some cases, we do not present protocols under the form of transition rules, but under the equivalent form of a pseudo-code.

The projection of a configuration on a set of agents S is a restriction of the vector representing the configuration to the elements corresponding to the agents of S. Naturally, the projection of an execution e on a set of agents S (e| S ) is obtained from e by projecting every configuration of e on S, representing an execution where the agents of S (the complement of S) do not interact.

The work of this author is supported in part by NSF grants CCF-1650596 and CCF-1637385. , Janna Burman and Devan Sohier; licensed under

Appendix

Lemma 2. If the considered protocol Count has a transition rule that allows to decrease the number of agents in state i through interactions between mobile agents (rules (i, i) → (i, 1 -i), (i, i) → (1 -i, 1 -i) or (i, 1 -i) → (1 -i, 1 -i)), then for any trace T , we have x i (T ) ≤ 1.

Proof. Consider such a protocol, with a rule (i, i) → (i, 1 -i) or (1 -i, 1 -i). Consider a trace T . This trace can be obtained by an execution prefix e = C 1 , C 2 , . . . , C k , such that in configuration C k , there are agents in state i, and x(T ) -agents in state 1 -i. Now, we can expand this execution prefix by making agents in state i interact, until they all are in state 1 -i, except one in the case of the interaction (i, i) → (i, 1 -i). This new execution prefix contains the same interactions with BST, and thus, has the same trace. The last configuration of this execution prefix contains at most one agent in state i. So,

is the only rule allowing the number of agents in state i to decrease, to use the same kind of reasoning, one must first show that there can always be an agent in state 1 -i in the configuration, to allow this rule to be executed. So let us show that a situation with x i (T ) = x(T ) > 1 cannot be reached. Indeed, consider a trace T such that x(T ) = x i (T ) = 1. At least one execution with this trace can lead to a configuration with a single agent in state i. In this configuration, transition (s BST , i) → (s BST , i) is always possible, so that either transition (s BST , 1 -i) → (s BST , * ) or (s BST , i) → (s BST , 1 -i) must eventually occur for x(T ) to increase. When the transition (s BST , 1 -i) → (s BST , * ) takes place, all executions with this trace contain at least one agent in state 1-i in the configuration before, and this agent can interact with any agent in state i, so that x i (T ) = x i (T ) = 0. If an interaction (s BST , i) → (s BST , 1 -i) occurs, then x i (T ) = 0. In any case, the trace is such that x i (T ) = 0 < x(T ), so that any traces built upon T corresponds to some execution ending with some agent in state 1 -i and one or zero agent in state i. Thus, any trace T can be expanded with (i, 1 -i) → (1 -i, 1 -i) interactions until at most one agent in state i remains, and x i (T ) ≤ 1. Proof. For simplicity we will assume b = 0; the b = 1 case is symmetric. So we are looking at a zero phase that starts with n 0 ≥ n/2. From the structure of the protocol, we know that at the start of this phase, c 1 = 0, but c 0 might be larger. It happens that the worst case is when c 0 = 0, but we will analyze the process for any initial value of c 0 .

In the analysis below we will fix n 0 , n 1 , to their values at the start of the phase. To keep track of what happens, let i be the number of zero values converted to ones so far during this phase; given the value of i, this gives n 0 -i zeros and n 1 + i ones in the population, and the value of the c 1 register will be i. We fail to convert all zeros to ones if we exit the phase while i is less than n 0 .

For each particular value of i, this occurs only if (a) c 0 is already 0, and (b) BST observes 6(n ln n + 1) ones in a row. Whether or not c 0 = 0, the latter event occurs with probability exactly

which by the union bound gives an upper bound on the probability that we leave the phase

XX:18 Time and Space Optimal Counting in Population Protocols

We will bound this sum by considering the terms with i < n 0 /2 and i ≥ n 0 /2 separately. For i < n 0 /2, we have

The original sum is thus bounded by 2/5 + 1/200 < 1/2 for all n > 0, giving the claimed bound. Proof. Let us assume, by contradiction, that there are infinitely many configurations in e with a mobile agent in state m. Since there is a finite number of agents, there is a particular mobile agent x in A which is in state m in infinitely many configurations. Let C j1 , C j2 , C j3 , . . . be these configurations such that e = e 1 , C j1 , e 2 , C j2 , e 3 , C j3 , . . . W.l.o.g., we choose these configurations such that, in every execution segment e i , every agent in A interacts with every other (this is possible with weak fairness). Now consider a population A = A ∪ {x } of size n + 1. To prove the lemma, we will construct a weakly fair execution e of Count in population A where no agent can distinguish e from e, and where consequently Count wrongly counts only n agents instead of the existing n + 1.

We construct e based on e. First, we assume that in e , x is in state m in the starting configuration, and e = e 1 , C j1 , e m , e 2 , C j2 , e m , e 3 , C j3 , e m , . . . Every segment e i follows exactly the same transition sequence as in e i . In every segment e 2r+1 , C j2r+1 (for r ≥ 0) the interactions are exactly the same as in e 2r+1 , C j2r+1 , and x does not interact. However, in e 2r , C j2r , all the interactions are as in e 2r+2 , C j2r , but the interactions with x. In this case, x is replaced by x in the appropriate state, and x does not interact. Finally, e m is an execution segment where only x and x interact. They both start in state m, performing the sequence (m, m) * → (m, m). The configurations at the beginning and at the end of e m are identical. The construction of e ensures that in every C ji , both x and x are in the state m.

It is easy to verify that e is possible. In particular, this is because, at the end of every segment e i , C ji , e m , both x and x are in the state m, so they can be exchanged in the following transitions of e i+1 . Moreover, e is weakly fair, because x interacts with x in every e m ; in every e 2r+1 and e 2r+2 , x and x , respectively, interact with every other agent (by the assumption on e i ); and all the other agents interact with all the others infinitely often, by the later arguments and by weak fairness of e.

Finally, in e , every agent from A (including BST), executes exactly the same sequence of transition rules as it does in e, so no agent can distinguish the fact that the population is actually A with n + 1 agents, and Count counts only n agents as it does in e. This is a contradiction to the assumption that Count is a correct counting protocol.

Proposition 10. Any symmetric counting protocol correct for any n ≤ P (undistinguishable and non-initialized) mobile agents, under weak fairness, have to use at least P states per mobile agent.

Proof. As Count is symmetric, any two agents, both in some state s ∈ Q, in an interaction, have to execute a symmetric transition of the form (s, s) → (s 1 , s 1 ). Thus there is a possible sequence of transitions (s, s) → (s 1 , s 1 ) → (s 2 , s 2 ) → (s 3 , s 3 ) . . . As mobile agents are finite state, for some j > i ≥ 1, s i = s j , i.e. (s i , s i ) * → (s i , s i ). By Lem. 9, s i does not appear infinitely often in executions with n < P . As there are at least P -1 states appearing infinitely often in an execution with n = P -1 (by Proposition 8), and there is at least one such state s i , there are at least P distinct states to be maintained by mobile agents. Proposition 15. The convergence time of the space optimal protocol under weak fairness presented in [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF] is Θ(2 n ) non-null transitions.

Proof. Following the study of the Gros sequence U n , in [START_REF] Beauquier | Space-optimal counting in population protocols[END_REF], used by the protocol to name n agents (U n ≡ U n-1 , n, U n-1 , where U 1 ≡ 1), the number of terms in U n is 2 n -1. In consequence, the number of non-null transitions, before convergence, between BST and an agent in state 0 (the m-state) or > n (whom BST "gives" a new name), is at most 2 n . Other since

The case when n is odd is similar:

And, similarly

Thus, u n ≥ 2 n , and u n ∼ n→∞ 2 n . The average complexity of the protocol is Θ(2 n ). The best starting configurations, for the complexity, is when all agents have the same mark. The average complexity is then 2 n + o(2 n ). Starting from any other configuration, the protocol first has to reach a configuration where all agents have identical marks. This takes less than 2 n + o(2 n ) transitions, since starting with all agents having the same mark, and switching it, makes the protocol traverse all configurations. Hence, in this case, the overall complexity is less than 2 × (2 n + o(2 n )).


Caterina Calgaro
email: caterina.calgaro@math.univ-lille1.fr

Meriem Ezzoug
email: meriemezzoug@yahoo.fr

Ezzeddine Zahrouni
email: zahrouniez@gmail.com

Global weak solution to a 3-D Kazhikhov-Smagulov model with Korteweg stress

Keywords: Kazhikhov-Smagulov model, Korteweg model, weak solution, global existence result. MOTS-CLÉS : Modèle de Kazhikhov-Smagulov, modèle de Korteweg, solution faible, existence globale

In this article, we consider a multiphasic incompressible fluid model, called the Kazhikhov-Smagulov model, with a specific stress tensor which depends on density derivatives, introduced by Korteweg. We establish the existence of global weak solution to this model in a 3D bounded domain.

RÉSUMÉ. Dans cet article, nous considérons un modèle de fluide incompressible multiphasique, appelé modèle de Kazhikhov-Smagulov, avec un tenseur de contraintes spécifique qui dépend des dérivées d'ordre élevé de la densité, introduit par Korteweg. Nous établissons l'existence d'une solution faible globale pour ce modèle dans un domaine borné en 3D.

Introduction

We are concerned with systems of PDEs describing the evolution of mixture flows.

Let Ω be a bounded open set in R 3 with boundary Γ that is regular enough and let n be the outwards unit normal on the boundary Γ. We denote by [0, T ] the time interval, for T > 0. The mixture of two fluids is described by the density ρ(t, x) ≥ 0, the velocity field v(t, x) ∈ R 3 and the pressure p(t, x), depending on the time and space variables (t, x) ∈ [0, T ] × Ω. According to [START_REF] Dunn | On the thermomechanics of interstitial working[END_REF][START_REF] Galdi | Mathematical problems for miscible, incompressible fluids with Korteweg stresses[END_REF][START_REF] Joseph | Fluid dynamics of two miscible liquids with diffusion and gradient stresses[END_REF], we consider the Korteweg equations for generalized incompressible fluids whose density and volume change with the concentration φ(t, x) ≥ 0 and eventually the temperature, but not with pressure. In general, the velocity field v of such incompressible fluids is not solenoidal, div v = 0. Assuming that each fluid is incompressible, the mass density is conserved in the absence of diffusion. The theory of Korteweg, introduced in [START_REF] Korteweg | Sur la forme que prennent les équations du mouvement des fluides si l'on tient compte des forces capillaires causées par des variations de densité considérables mais continues et sur la théorie de la capillarité dans l'hypothèse d'une variation continue de la densité[END_REF], considers the possibility that stresses are induced by gradients of concentration and density in a slow process of diffusion of incompressible miscible liquids. Such stresses could be important in regions of high gradients and they mimic the surface tension.

In order to model the fluid capillarity effects, Korteweg introduced in the usual compressible fluid model a specific stress tensor which depends on density derivatives. Following the rigorous formulation presented in [START_REF] Dunn | On the thermomechanics of interstitial working[END_REF] (see also [START_REF] Bresch | On some compressible fluid models: Korteweg, lubrication and shallow water systems[END_REF]) and neglecting thermal fluctuations, the model reads

∂ t ρ + div (ρv) = 0, ∂ t (ρv) + div (ρv ⊗ v) = ρg + div (S + K), (1)
where g stands for the gravity acceleration (but it can include further external forces). The viscous stress tensor S and the Korteweg stress tensor K are given by :

S = (ν div v -p)I + 2µD(v), K = (α∆ρ + β|∇ρ| 2 )I + δ(∇ρ ⊗ ∇ρ) + γD 2 x ρ, (2)
where D(v) = (∇v + ∇v T )/2 is the strain tensor and D 2 x ρ is the hessian matrix of the density ρ. Here, the pressure p and the coefficients α, β, γ, δ, µ and ν are functions of ρ. The special case

α = κρ, β = κ 2 , δ = -κ, γ = 0,
for some constant κ > 0, corresponds precisely to Korteweg's original assumptions connected with the variational theory of Van Der Waals. In this case, the Korteweg stress tensor yields

K = κ 2 (∆ρ 2 -|∇ρ| 2 )I -κ(∇ρ ⊗ ∇ρ). (3)
Writing div K = κρ∇(∆ρ) = κ∇(ρ∆ρ) -κ∇ρ∆ρ, (4)
and incorporating ∇(ρ∆ρ) in the pressure term, we obtain -κ∇ρ∆ρ as a right hand side term in the momentum equation. The Korteweg's theory can be applied to processes of slow diffusion on miscible incompressible fluids, for example, water and glycerin. The two fluids are characterized by their reference mass density : ρ1 the density of the dilute phase and ρ2 the density of the dense phase. We need the velocity field of each constituent : v 1 (t, x) and v 2 (t, x), respectively. We define the volume fraction of the dilute phase 0 ≤ φ(t, x) ≤ 1 :

φ(t, x) = lim r→0
Volume occupied at time t by the dilute phase in B(x, r)

|B(x, r)| .

Then, admitting that each fluid is incompressible and keeping a constant mass density, the density of the mixture is defined by

ρ(t, x) = ρ2 1 -φ(t, x) :=ρ2(t,x) + ρ1 φ(t, x) :=ρ1(t,x) = ρ2 + (ρ 1 -ρ2 )φ(t, x).
Writing the mass conservation for the two phases, we obtain

∂ t ρ + div (ρv) = 0, with ρv(t, x) = (ρ 2 v 2 + ρ 1 v 1 )(t,
x) presents the mean mass velocity v(t, x), which is not divergence free, div v = 0. Moreover, we define the mean volume velocity

u(t, x) = 1 -φ(t, x) v 2 (t, x) + φ(t, x)v 1 (t, x).
Applying the definitions, we verify that the velocity field u is solenoidal (div u = 0). According to Kazhikhov and Smagulov [START_REF] Kazhikhov | The correctness of boundary value problems in a diffusion model of an inhomogeneous fluid[END_REF], we consider the following non-standard constraint associated to the pressure p :

div v = -div (λ∇ ln(ρ)), (5)
where λ > 0 is a diffusion coefficient. This Fick's law (5) describes the diffusive fluxes of one fluid into the other, see also [START_REF] Calgaro | Modeling and simulation of mixture flows: Application to powder-snow avalanches[END_REF]. Obviously, when we set

v = u -λ∇ ln(ρ), (6)
the relation yields [START_REF] Calgaro | Modeling and simulation of mixture flows: Application to powder-snow avalanches[END_REF]. The mixture density ρ verifies the mass conservation and we obtain

∂ t ρ + div (ρu) = div (λ∇ρ). (7)
For the momentum equation (1) 2 , we start by developing each term using the relation [START_REF] Calgaro | On the global existence of weak solution for a multiphasic incompressible fluid model with Korteweg stress[END_REF], in order to eliminate v. After some calculations and using (4), we get

∂ t ρu + div ρu ⊗ u -λ div ∇ρ ⊗ u -λ div u ⊗ ∇ρ + λ∇ u • ∇ρ + λ div 2µD 2 x ln(ρ) -div 2µD(u) + ∇p -λ 2 ∇∆ρ -div ∇ρ ⊗ ∇ρ ρ = ρg + κ∇(ρ∆ρ) -κ∇ρ∆ρ. (8)
Choosing the dynamic viscosity µ constant, as in [START_REF] Franchi | A comparison of Graffi and Kazhikov-Smagulov models for top heavy pollution instability[END_REF], we have div 2µD(u) = µ∆u and div 2µD 2

x ln(ρ) = 2µ∇∆ ln(ρ). Including all the gradient terms in the modified pressure

P = p + λ(ν + 2µ)∆ ln(ρ) + λu • ∇ρ -λ 2 ∆ρ -κρ∆ρ.
Then, we obtain the Kazhikhov-Smagulov-Korteweg model in conservative form :

           ∂ t ρu + div ρu ⊗ u -λ div ∇ρ ⊗ u -λ div u ⊗ ∇ρ -µ∆u +∇P + λ 2 div ∇ρ ⊗ ∇ρ ρ = ρg -κ∇ρ∆ρ, ∂ t ρ + div ρu = λ∆ρ, div u = 0. (9)
The tensorial product matrix of two vectors a = (a

i ) d i=1 , b = (b i ) d i=1 is denoted by a ⊗ b with coefficients (a ⊗ b) i,j = a i b j . Taking into account the equalities ∂ t ρu + div ρu ⊗ u -λ div ∇ρ ⊗ u = ρ∂ t u + ρ(u • ∇)u -λ(∇ρ • ∇)u, -λ div u ⊗ ∇ρ = -λ(u • ∇)∇ρ = -λ∇(u • ∇ρ) + λ div ρ∇u T . Then, denoting Q T = (0, T ) × Ω, Σ = (0, T ) × Γ, the Kazhikhov-Smagulov-Korteweg (KSK) model can be written in Q T as :              ρ ∂ t u + (u • ∇)u -λ(∇ρ • ∇)u + λ div ρ∇u T -µ∆u + ∇P +λ 2 div ∇ρ ⊗ ∇ρ ρ = ρg -κ∆ρ∇ρ, ∂ t ρ + div ρu = λ∆ρ, div u = 0. (10)
The KSK model ( 10) is completed by the following boundary and initial conditions

u(t, x) = 0, ∂ρ ∂n (t, x) = 0, (t, x) ∈ Σ, (11)
u(0, x) = u 0 (x), ρ(0, x) = ρ 0 (x), x ∈ Ω, (12)
with the compatibility condition div u 0 = 0, where ρ 0 : Ω → R and u 0 : Ω → R 3 are given functions. Throughout this work, we assume the hypothesis

0 < m ≤ ρ 0 (x) ≤ M < +∞, x ∈ Ω. (13)
Let us mention some known results about the Kazhikhov-Smagulov-Korteweg model, for κ = 0 and κ > 0. Without the Korteweg stress tensor (i.e. taking κ = 0), many authors treat the so-called Kazhikhov-Smagulov model. We can refer for instance to [START_REF] Antontsev | Boundary value problems in mechanics of nonhomogeneous fluids[END_REF][START_REF] Bresch | Effects of density dependent viscosities on multiphasic incompressible fluid models[END_REF][START_REF] Franchi | A comparison of Graffi and Kazhikov-Smagulov models for top heavy pollution instability[END_REF][START_REF] Kazhikhov | The correctness of boundary value problems in a diffusion model of an inhomogeneous fluid[END_REF] for the study of the simplified model without O(λ 2 ) terms, and to [START_REF] Beirão | Diffusion on viscous fluids. Existence and asymptotic properties of solutions[END_REF][START_REF] Secchi | On the motion of viscous fluids in the presence of diffusion[END_REF] for the study of the same problem with all the terms. In [START_REF] Cai | Global regularity for the initial value problem of a 2-D Kazhikhov-Smagulov type model[END_REF][START_REF] Cai | Global strong solution to the initial-boundary value problem of a 2-D Kazhikhov-Smagulov type model[END_REF], the authors study a two-dimensional generalized Kazhikhov-Smagulov model. Taking κ > 0, the mathematical analysis in a three-dimensional domain of different types of Kazhikhov-Smagulov-Korteweg models, was carried in the recent works [START_REF] Ezzoug | Existence and asymptotic behavior of global regular solutions to a 3-D Kazhikhov-Smagulov model with Korteweg stress[END_REF][START_REF] Calgaro | On the global existence of weak solution for a multiphasic incompressible fluid model with Korteweg stress[END_REF]. In [START_REF] Ezzoug | Existence and asymptotic behavior of global regular solutions to a 3-D Kazhikhov-Smagulov model with Korteweg stress[END_REF], the authors consider the same KSK model [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF], and they prove the existence of a unique global in time regular solution for small initial data and external forces. Also, if g = 0, they study the longtime behavior of the solution and show that it converges to the equilibrium solution with zero velocity field. In [START_REF] Calgaro | On the global existence of weak solution for a multiphasic incompressible fluid model with Korteweg stress[END_REF], the equation (10) 1 is replaced by:

ρ ∂u ∂t +(u•∇)u -λ(∇ρ•∇)u - λ 2 div ρ∇u-ρ∇u T +∇P = ρ g -κ ∆ρ∇ρ. ( 14
)
Following [START_REF] Bresch | Effects of density dependent viscosities on multiphasic incompressible fluid models[END_REF], we have chosen a particular relation between the linear dynamic viscosity µ = µ 0 ρ and the mass diffusion coefficient λ = 2µ 0 , in order to remove the O(λ 2 ) terms in [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF] 1 . Then, we prove the global existence of weak solution of the problem ( 14)-(10) 2 -(10) 3 for arbitrary initial data and external forces, and without any assumption on the diffusivity λ.

The paper is organized as follows. In Section 2 we present the main results about [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF]. After some preliminary results recalled in Section 3, the proof of existence of global weak solution for [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF] is given in Section 4. The conclusions are summarized in Section 5.

Functional setup and main results

Let us introduce the following functional spaces (see [START_REF] Lions | Quelques méthodes de résolution des problèmes aux limites non linéaires[END_REF][START_REF] Temam | Navier-Stokes equations, theory and numerical analysis[END_REF] for their properties):

V = u ∈ D(Ω) 3 : div u = 0 in Ω , V = u ∈ H 1 0 (Ω) : div u = 0 in Ω , H = u ∈ L 2 (Ω) : div u = 0 in Ω, u • n = 0 on Γ , H s N = ρ ∈ H s (Ω) : ∂ρ ∂n = 0 on Γ, Ω ρ(x) dx = Ω ρ 0 (x) dx , s ≥ 2.
The spaces V and H are the closures of V in H 1 0 (Ω) and L 2 (Ω), respectively. Let us recall the definition of weak solution for the KSK model [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF]. Such class of solutions can be found in [START_REF] Bresch | Effects of density dependent viscosities on multiphasic incompressible fluid models[END_REF] for Kazhikhov-Smagulov type models and in [START_REF] Temam | Navier-Stokes equations, theory and numerical analysis[END_REF] for the incompressible Navier-Stokes equations. Definition 2.1 A pair of functions (u, ρ) is called a weak solution of problem [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF], [START_REF] Ezzoug | Existence and asymptotic behavior of global regular solutions to a 3-D Kazhikhov-Smagulov model with Korteweg stress[END_REF], [START_REF] Feireisl | On the existence of globally defined weak solutions to the Navier-Stokes equations[END_REF] on Ω if and only if the following assumptions are satisfied :

1) u ∈ L ∞ 0, T ; H ∩ L 2 0, T ; V , ρ ∈ L ∞ 0, T ; H 1 (Ω) ∩ L 2 0, T ; H 2 N and 0 < m ≤ ρ(t, x) ≤ M < +∞, a.e. (t, x) ∈ Q T .
2) For all φ ∈ C 1 [0, T ]; V such that φ(T, .) = 0, one has :

T 0 -u, ρ∂ t φ + (ρu -λ∇ρ) • ∇ φ + µ ∇u, ∇φ -λ ρ∇u T , ∇φ dt -λ 2 T 0 1 ρ ∇ρ ⊗ ∇ρ, ∇φ dt = T 0 ρg -κ∆ρ∇ρ, φ dt + ρ 0 u 0 , φ(0) . (15)
3) For all ϕ ∈ C 1 [0, T ]; H 1 (Ω) such that ϕ(T, .) = 0, one has :

T 0 u • ∇ρ, ϕ + λ ∇ρ, ∇ϕ -ρ, ∂ t ϕ dt = ρ 0 , ϕ(0) . (16)
REMARK. -The pressure P associated with the weak solution (u, ρ) can be obtained using [START_REF] Joseph | Fluid dynamics of two miscible liquids with diffusion and gradient stresses[END_REF] and the Rham's lemma [START_REF] Temam | Navier-Stokes equations, theory and numerical analysis[END_REF].

We present the aim of this work about the Kazhikhov-Smagulov-Korteweg model [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF]. Under some assumption on the coefficients λ, µ, κ, we prove via a Faedo-Galerkin method, the global existence of weak solution of [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF] for arbitrary initial data and external force field. Our main result reads :

Theorem 2.2 Let u 0 ∈ H, ρ 0 ∈ H 1 (Ω) satisfy (13), T > 0 and g ∈ L 2 0, T ; L 2 (Ω) . If λ µ max(1, λ 2 κ
) is sufficiently small, then there exists a weak solution (u, ρ) of [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF] global

in time such that u ∈ L ∞ 0, T ; H ∩ L 2 0, T ; V , ρ ∈ L ∞ 0, T ; H 1 (Ω) ∩ L 2 0, T ; H 2
N , with finite and uniformly bounded energy such that ∀t ≤ T,

ρ(t)u(t) 2 L 2 (Ω) +κ ∇ρ(t) 2 L 2 (Ω) + t 0 µ 2 ∇u(s) 2 L 2 (Ω) +κλ ∆ρ(s) 2 L 2 (Ω) ds ≤ √ ρ 0 u 0 2 L 2 (Ω) +κ ∇ρ 0 2 L 2 (Ω) + CM 2 µ T 0 g(s) 2 L 2 (Ω) ds.

Preliminary results

To prove the main result of this article, Theorem 2.2, we need some useful results concerning the density ρ which verifies the convection-diffusion equation. For detailed proofs of these results, we refer the readers to [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF]. Given the initial density ρ 0 and the velocity field u, we find the density ρ as solution of the following Neumann problem :

       ∂ t ρ + u • ∇ρ = λ ∆ρ in Q T , ρ(0, x) = ρ 0 (x) in Ω, ∂ρ ∂n = 0 on Σ. (17)
The density ρ satisfies the maximum principle. This result is classical (see [START_REF] Bresch | Effects of density dependent viscosities on multiphasic incompressible fluid models[END_REF]).

Proposition 3.1 If (u, ρ) is a weak solution of (10), then

0 < m ≤ ρ(t, x) ≤ M < +∞ a.e. (t, x) ∈ Q T . ( 18
)
Proposition 3.2 Let ρ 0 ∈ H 1 (Ω) verify ( 13) and u ∈ C [0, T ]; V ∩ H 2 (Ω) . Then there exists a unique solution ρ of ( 17) such that

ρ ∈ L ∞ 0, T ; H 1 (Ω) ∩ L 2 0, T ; H 2 N .
Moreover, we have

sup 0≤t≤T ρ(t) 2 L 2 (Ω) ≤ ρ 0 2 H 1 (Ω) , (19)
T 0 ∇ρ(t) 2 L 2 (Ω) dt ≤ 1 2λ ρ 0 2 H 1 (Ω) , (20)
sup 0≤t≤T ∇ρ(t) 2 L 2 (Ω) ≤ C λ ρ 0 2 H 1 (Ω) 1 + sup 0≤t≤T u(t) 2 L ∞ (Ω) , (21)
T 0 ∆ρ(t) 2 L 2 (Ω) dt ≤ C λ λ ρ 0 2 H 1 (Ω) 1 + sup 0≤t≤T u(t) 2 L ∞ (Ω) , (22)
where C λ is a positive constant depending only on λ.

Given ρ 0 ∈ H 1 (Ω) satisfying ( 13) and u ∈ C [0, T ]; V ∩ H 2 (Ω) , let ρ the solution obtained by Proposition 3.2. Therefore, it is clear that the following map is well defined

S : C [0, T ]; V ∩ H 2 (Ω) -→ L ∞ 0, T ; H 1 (Ω) ∩ L 2 0, T ; H 2 N , such that ρ = Su is well defined. Proposition 3.3 Let ρ 0 ∈ H 1 (Ω) verify (13) and u 1 , u 2 ∈ C [0, T ]; V ∩ H 2 (Ω) . Set ρ = ρ 1 -ρ 2 = Su 1 -Su 2 and u = u 1 -u 2 ,
we have the following estimates :

sup 0≤t≤T ρ(t) 2 L 2 (Ω) +λ T 0 ∇ρ(t) 2 L 2 (Ω) dt ≤ M 2 λ T sup 0≤t≤T u(t) 2 L 2 (Ω) , ( 23
)
sup 0≤t≤T ∇ρ(t) 2 L 2 (Ω) + λ T 0 ∆ρ(t) 2 L 2 (Ω) dt ≤ 2T λ sup 0≤t≤T ∇ρ 1 2 L 2 (Ω) sup 0≤t≤T u 2 L ∞ (Ω) + 2M 2 T λ 3 sup 0≤t≤T u 2 2 L ∞ (Ω) sup 0≤t≤T u 2 L 2 (Ω) . (24)
We recall that there exists an orthonormal basis of L 2 (Ω) defined by

ω k ∈ V ∩ H 2 (Ω) -P∆ω k = λ k ω k on Ω,
where P is the orthogonal projection operator of L 2 (Ω) onto H. For any n ∈ N * , we define by X n the finite dimensional subspace of H such that

X n = Vect{ω k , k = 1, . . . , n},
and we consider the orthogonal projection

P n : L 2 (Ω) → X n defined by ∀w ∈ H, P n w, v = w, v , ∀v ∈ X n . (25)
As in [START_REF] Feireisl | On the existence of globally defined weak solutions to the Navier-Stokes equations[END_REF], we introduce a family of operators M[ρ] : X n -→ X n defined by

M[ρ]v, ω = Ω ρ v • ω dx for all v, ω ∈ X n . ( 26
) If ρ ∈ L ∞ (Ω), then M[ρ] is well defined. Moreover, let m > 0, we set D = ρ ∈ L ∞ (Ω); ρ(x) ≥ m > 0 . Proposition 3.4 M[ρ]
is one-to-one and its inverse verifies

M[ρ] -1 L(Xn,Xn) ≤ inf x∈Ω ρ(x) -1 ∀ρ ∈ D, (27)
M[ρ 1 ] -1 -M[ρ 2 ] -1 L(Xn,Xn) ≤ C n m 2 ρ 1 -ρ 2 L 2 (Ω) ∀ρ 1 , ρ 2 ∈ D, ( 28
)
where C n is a constant depending on the dimension of the space X n . Thanks to Proposition 4.1, we verify that Ψ is a contraction mapping on B Tn R and we conclude the existence of a unique fixed point of Ψ. It is clear that u n the fixed point of Ψ, obtained in Proposition 4.2, implies that (u n , ρ n = Su n ) is a local solution of the Galerkin approximate problem (29). Now, we will prove that this local solution is in fact a global one. For this, we establish some uniform estimates for (u n , ρ n ) with respect to time.

Proposition 4.3 If λ µ max(1, λ 2 κ
) small enough, there exists a constant C > 0 depending on ρ 0 , u 0 , g, M, µ, κ, such that for all t ∈ [0, T n )

m u n (t) 2 L 2 (Ω) + µ 2 t 0 ∇u n (s) 2 L 2 (Ω) ds ≤ C, (35)
κ ∇ρ n (t) 2 L 2 (Ω) + κλ t 0 ∆ρ n (s) 2 L 2 (Ω) ds ≤ C. (36)
Proof. First, we take v = u n (t) in (29) 1 :

1 2 d dt Ω ρ n |u n | 2 dx + µ ∇u n 2 L 2 (Ω) = λ 2 Ω ∇ρ n ⊗ ∇ρ n ρ n : ∇u n dx + λ Ω ρ n ∇u T n : ∇u n dx + Ω ρ n g • u n dx -κ Ω ∆ρ n ∇ρ n • u n dx. (37)
Second, by (29) 2 , we have

∂ t ρ n -λ∆ρ n = -u n • ∇ρ n , in the distribution sens on Q T . (38)
Since

(u n , ρ n ) ∈ C [0, T n ]; X n × L ∞ 0, T n ; H 1 (Ω) ∩ L 2 0, T n ; H 2 N , we deduce that ∂ t ρ n ∈ L 2 0, T n ; L 2 (Ω) .
Multiplying (38) by -κ∆ρ n (t) and after integration by parts, we obtain

κ 2 d dt ∇ρ n 2 L 2 (Ω) + κ λ ∆ρ n 2 L 2 (Ω) = κ Ω ∆ρ n u n • ∇ρ n dx. (39)
By adding (37) and (39), we get

d dt √ ρ n u n 2 L 2 (Ω) +κ ∇ρ n 2 L 2 (Ω) + 2µ ∇u n 2 L 2 (Ω) +2κλ ∆ρ n 2 L 2 (Ω) = 2λ Ω ρ n ∇u T n : ∇u n dx + 2λ 2 Ω ∇ρ n ⊗ ∇ρ n ρ n : ∇u n dx + 2 Ω ρ n g • u n dx.
Then, thanks to Proposition 3.1, and the Hölder, Poincaré and Young inequalities, we find

λ Ω ρ n ∇u T n : ∇u n dx ≤ λM ∇u n 2 L 2 (Ω) , 2λ 2 Ω ∇ρ n ⊗ ∇ρ n ρ n : ∇u n dx ≤ κλ ∆ρ n 2 L 2 (Ω) + C 2 λ 3 κ ∇u n 2 L 2 (Ω) , 2 Ω ρ n g • u n dx ≤ µ ∇u n 2 L 2 (Ω) + CM 2 µ g 2 L 2 (Ω) .
Finally, we obtain for each t ∈ [0, T n )

d dt √ ρ n u n 2 L 2 (Ω) +κ ∇ρ n 2 L 2 (Ω) + 1 -C 1 λ µ -C 2 λ 3 κµ µ ∇u n 2 L 2 (Ω) + κλ ∆ρ n 2 L 2 (Ω) ≤ CM 2 µ g 2 L 2 (Ω) . For λ µ max(1, λ 2 κ ) small enough such that C 1 λ µ + C 2 λ 3 κµ ≤ 1 2
, we get

d dt √ ρ n u n 2 L 2 (Ω) + κ ∇ρ n 2 L 2 (Ω) + µ 2 ∇u n 2 L 2 (Ω) + κλ ∆ρ n 2 L 2 (Ω) ≤ CM 2 µ g 2 L 2 (Ω) .
Evidently, thanks to the previous Proposition 4.3, we have the following :

Corollary 4.4 (u n , ρ n ) is a global solution of (29) and for all T > 0,

(u n ) n is bounded in L ∞ 0, T ; H ∩ L 2 0, T ; V , ( 40
) (ρ n ) n is bounded in L ∞ 0, T ; H 1 (Ω) ∩ L 2 0, T ; H 2 N .
(41)

Uniform estimates for time derivatives

In this section, we establish uniform estimates for time derivatives ∂ t ρ n and ∂ t u n .

Proposition 4.5 Let T > 0. The sequence

(∂ t ρ n ) n is bounded in L 4/3 0, T ; L 2 (Ω) .
Proof. Taking the L 2 -norm of ∂ t ρ n . Applying the Hölder and Gagliardo-Nirenberg inequalities and the inequality :

∇ρ L 4 (Ω) ≤ C 0 ρ 1/2 L ∞ (Ω) ∆ρ 1/2 L 2 (Ω) , we get ∂ t ρ n L 2 (Ω) ≤ λ ∆ρ n L 2 (Ω) + C u n 1/4 L 2 (Ω) ∇u n 3/4 L 2 (Ω) ρ n 1/2 L ∞ (Ω) ∆ρ n 1/2 L 2 (Ω)
. By the uniform estimate (35) and ( 18), we get

∂ t ρ n L 2 (Ω) ≤ λ ∆ρ n L 2 (Ω) + C ∇u n 3/4 L 2 (Ω) ∆ρ n 1/2 L 2 (Ω) . (42)
Next, applying the Young inequality ab ≤ 1 2 (a 2 + b 2 ) in (42), we get

∂ t ρ n L 2 (Ω) ≤ λ ∆ρ n L 2 (Ω) + C ∇u n 3/2
L 2 (Ω) . Thanks to the uniform time estimates (35) and (36), we deduce that ∂ t ρ n L 2 (Ω) is bounded in L 4/3 0, T . Now, by following [START_REF] Bresch | Effects of density dependent viscosities on multiphasic incompressible fluid models[END_REF], we establish an estimation of the fractional time derivative of u n .

Proposition 4.6 Let 0 < δ < T such that T -δ 0 u n (t + δ) -u n (t) 2 L 2 (Ω) dt ≤ C δ 1 4 , (43)
where C a constant independent of n and δ.

Proof. For all functions φ ∈ X T , the approximate solution (u n , ρ n ) verifies :

d dτ Ω ρ n u n • φ dx - Ω ρ n u n • ∂φ ∂τ dx - Ω ρ n (u n • ∇)φ • u n dx + µ Ω ∇u n : ∇φ dx + λ Ω (∇ρ n • ∇)φ • u n dx -λ Ω ρ n ∇u T n : ∇φ dx -λ 2 Ω ∇ρ n ⊗ ∇ρ n ρ n : ∇φ dx = Ω ρ n g • φ dx -κ Ω ∆ρ n ∇ρ n • φ dx. (44)
Integrating (44) with respect to τ between t and t + δ, and taking φ = u n (t + δ)u n (t)

Ω ρ n (t + δ) u n (t + δ) -ρ n (t) u n (t) u n (t + δ) -u n (t) dx = t+δ t Ω ρ n (τ ) g(τ ) -κ ∆ρ n (τ ) ∇ρ n (τ ) • u n (t + δ) -u n (t) dx dτ + t+δ t Ω ρ n (τ )u n (τ ) -λ∇ρ n (τ ) • ∇ u n (t + δ) -u n (t) • u n (τ ) dx dτ - t+δ t Ω µ ∇u n (τ ) -λ ρ n (τ )∇u T n (τ ) : ∇ u n (t + δ) -u n (t) dx dτ + λ 2 t+δ t Ω ∇ρ n (τ ) ⊗ ∇ρ n (τ ) ρ n (τ ) : ∇ u n (t + δ) -u n (t) dx dτ. (45)
Using the following identity

ρ n (t+δ) u n (t+δ)-ρ n (t) u n (t) = ρ n (t+δ) u n (t+δ)-u n (t) + ρ n (t+δ)-ρ n (t) u n (t),
then, (45) becomes .

ρ n (t + δ) u n (t + δ) -u n (t) 2 L 2 (Ω) = - Ω ρ n (t + δ) -ρ n (t) u n (t + δ) -u n (t)
Similarly, one can obtain the desired estimates of I j (t) terms, for j = 4, . . . , 8.

At last, if we choose 0 < δ < 1 and taking into account Propositions 4.3 and 4.5, then by gathering together all the above estimates, we rewrite (46) as follows : ∇u n (t + δ) .

ρ n (t + δ) u n (t + δ) -u n (t) 2 L 2 (Ω) ≤ Cδ
Thanks to the lower bound of ρ n and Proposition 4.3, we finish the proof.

  • u n (t) dx Let us estimate I 1 (t). Applying the Hölder inequality, we get|I 1 (t)| ≤ ρ n (t + δ)ρ n (t)Using the Hölder and Young inequalities and the embedding H 1 (Ω) ⊂ L 4 (Ω), we obtain|I 1 (t)| ≤ Cδ

		t+δ
	+	t	Ω	ρ (46)
							L 2 (Ω)	u n (t + δ) -u n (t)	L 4 (Ω)	u n (t)	L 4 (Ω) .
	In particular, we write
						ρ n (t + δ) -ρ n (t) =	t	t+δ	∂ρ n ∂τ	dτ.
			1 4	t	t+δ	∂ρ n ∂τ	4 3 L 2 (Ω) dτ	3 4	∇u n (t + δ) 2 L 2 (Ω) + ∇u n (t) 2 L 2 (Ω)	.
	In the same way, we verify the following estimations :
	|I 2 (t)| ≤ Cδ	1 2	t	t+δ	g(τ ) 2 L 2 (Ω) dτ	1 2	∇u n (t + δ) 2 L 2 (Ω) + ∇u n (t) 2 L 2 (Ω)	,
	|I 3 (t)| ≤ Cδ	1 4	t	t+δ	∆ρ n (τ ) 2 L 2 (Ω) dτ	3 4	∇u n (t + δ) 2 L 2 (Ω) + ∇u n (t) 2 L 2 (Ω)

n (τ ) g(τ )κ ∆ρ n (τ ) ∇ρ n (τ ) • u n (t + δ)u n (t) dx dτ + t+δ t Ω ρ n (τ )u n (τ ) -λ∇ρ n (τ ) • ∇ u n (t + δ)u n (t) • u n (τ ) dx dτ -t+δ t Ω µ ∇u n (τ )λ ρ n (τ )∇u T n (τ ) : ∇ u n (t + δ)u n (t) dx dτ + λ 2 t+δ t Ω ∇ρ n (τ ) ⊗ ∇ρ n (τ ) ρ n (τ ) : ∇ u n (t + δ)u n (t) dx dτ = I 1 (t

) + I 2 (t) + I 3 (t) + I 4 (t) + I 5 (t) + I 6 (t) + I 7 (t) + I 8 (t).

4 n 1+ u 0 L

(Ω) +2R 2 ≤

Proof of Theorem 2.2 4.1. Faedo-Galerkin method

We are looking for the approximate solutions

We set

Taking (29) 1 with v = ω k , for k = 1, . . . , n, and integrating in time between 0 and t ≤ T , the solution u n verifies the following integral equations for k = 1, . . . , n :

where ρ n = Su n and q 0 = ρ 0 u 0n . Thanks to (25) and ( 26), we rewrite (31) as follows :

the resulting equation reads

Hence, u n appears as a fixed point of a suitable functional

Let X T be the Banach space C [0, T ]; X n endowed with the norm

In order to apply the Banach fixed point theorem, we establish some uniform estimates for Ψ. With Propositions 3.2, 3.3 and 3.4 in mind, we have the following :

and for all u

At this stage, we set

Proposition 4.2 There T n ∈]0, 1[ small enough and u n ∈ B Tn R such that

The existence of solution (u, ρ)

The final step to complete this study is to employ the previous uniform estimates in order to pass to the limit in the approximate problem (29). When n → +∞, we have

Thanks to (40) and (41), choosing the subsequences (u n ) n and (ρ n ) n such that

weakly-star, and

We are able to pass to the limit in the linear terms of (29), thanks to these above convergence results. Now, to ensure the passage to the limit in the nonlinear terms of (29), it is necessary to use the following strong convergence : Proposition 4.7 There exists a subsequence (u n , ρ n ) n which converges strongly to (u, ρ) in L 2 0, T ; L 2 (Ω) × L 2 0, T ; H 1 (Ω) . Moreover, (u, ρ) is a weak solution of [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF].

Proof. Applying some compactness theorems [21, Chap.3, Theorem 2.1] for ρ n and [20, Theorem 5] for u n and using Propositions 4.5 and 4.6, we get to the desired result.

Conclusions

In this paper, we study the system of PDEs derived from the compressible Navier-Stokes equations with presence of a specific Korteweg stress tensor, called the Kazhikhov-Smagulov-Korteweg (KSK) model. We arrive at verify the existence of a weak solution (u, ρ) of the KSK model [START_REF] Ezzoug | Analyse mathématique et simulation numérique d'écoulements de fluides miscibles[END_REF] global in time with finite and uniformly bounded energy. Then, we conclude the proof of Theorem 2.2, the main result of this paper.