N R Chowdhury

I.-C Morȃrescu

S Martin

S Srikant

Continuous opinions and discrete actions in social networks: a multi-agent system approach

This paper proposes and analyzes a novel multiagent opinion dynamics model in which agents have access to actions which are quantized version of the opinions of their neighbors. The model produces different behaviors observed in social networks such as disensus, clustering, oscillations, opinion propagation, even when the communication network is connected. The main results of the paper provides the characterization of preservation and diffusion of actions under general communication topologies. A complete analysis allowing the opinion forecasting is given in the particular cases of complete and ring communication graphs. Numerical examples illustrate the main features of this model.

I. INTRODUCTION

The analysis of social networks received an increasing interest during the last decade. This is certainly related with the increasing use of Facebook, Twitter, LinkedIn and other on-line platforms allowing to get information about social networks. Multi-agent systems have been shown to efficiently model how opinion dynamics occur as a result of social interactions [START_REF] Vande Kerckhove | Modelling influence and opinion evolution in online collective behaviour[END_REF]. The existing models can be split in two main classes: those considering that opinions can evolve in a discrete set and those considering a continuous set of values that can be taken by each agent. The models in first class come from statistical physics and the most employed are the Ising [START_REF] Ising | Contribution to the theory of ferromagnetism[END_REF], voter [START_REF] Clifford | A model for spatial conflict[END_REF] and Sznajd [START_REF] Sznajd-Weron | Opinion evolution in closed community[END_REF] models. When the opinions are not constrained to a discrete set, we can find in the literature two popular models: the Deffuant [START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF] and the Hegselmann-Krause [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF] models. They are usually known as bounded confidence models since they depend on one parameter characterizing the fact that one agent takes into account the opinion of another only if their opinions are close enough. The bounded confidence models above do not guarantee consensus and instead several local agreements can be reached. The Hegselmann-Krause model has been adapted in [START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF] to a model of opinion dynamics with decaying confidence.

In order to more accurately describe the opinion dynamics and to recover more realistic behaviors, a mix of continuous opinion with discrete actions (CODA) was proposed in [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF]. This model reflects the fact that even if we often face binary choices or actions, the opinion behind evolves in a continuous space of values. For instance we may think that car A is 70% more appropriate for our use than car B. However, our action will be 100%

The work of I.-C. Morȃrescu, S. Martin was partially funded by the ANR project COMPACS -"Computation Aware Control Systems", ANR-13-BS03-004 and by CNRS projects PEPS MADRES and PEPS CONAS.

N. Roy Chowdhury and S. Srikant are with the Department of Systems and Control Engineering, Indian Institute of Technology, Bombay, Mumbai-400076, India. e-mails: {nilanjan, srikant}@sc.iitb.ac.in. I.-C. Morȃrescu and S. Martin are with Université de Lorraine, CRAN, UMR 7039 and CNRS, CRAN, UMR 7039, 2 Avenue de la Forêt de Haye, Vandoeuvre-lès-Nancy, France. {constantin.morarescu samuel.martin}@univ-lorraine.fr buy car A. Moreover, our neighbors often only see our action without any access to our opinion. Similar idea was employed in [START_REF] Ceragioli | Continuous-time consensus dynamics with quantized all-to-all communication[END_REF] where it is studied the emergence of consensus under quantized all-to-all communication. In this paper the authors assume constant interaction weights and quantized information on the opinion of all the other individuals belonging to a given social network. In [START_REF] Frasca | Continuous-time quantized consensus: Convergence of krasovskii solutions[END_REF], a system with quantized communication and general communication topologies is studied. There, the author focuses on consensus (up to the quantizer precision) while in the present paper, we precisely focus on dynamics such as dissensus which occur within the quantizer precision. As explained above, this is of particular relevance for the social sciences.

Whatever is the model employed to describe the opinion dynamics, many studies focus on the emergence of consensus in social networks [START_REF] Galam | Towards a theory of collective phenomena: Consensus and attitude changes in groups[END_REF], [START_REF] Axelrod | The dissemination of culture: A model with local convergence and global polarization[END_REF], [START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF], [START_REF] Fortunato | Vector opinion dynamics in a bounded confidence consensus model[END_REF]. Nevertheless, this behavior is rarely observed in real large social networks. The present study provides a possible explanation for dissensus even though the communication graph is connected.

Conceptually the model proposed in this paper is close to the one in [START_REF] Ceragioli | Continuous-time consensus dynamics with quantized all-to-all communication[END_REF] with the difference that we are considering state-dependent interaction weights instead of constant ones. Beside the heterogeneity introduced in the model by the state-dependent interaction weights we are also dealing with more general interaction topologies and we are not trying to characterize consensus. Instead we highlight that extremist individuals are less influenceable, that several equilibria can be reached and one can also have oscillatory behaviors in the network. From behavioral view-point our model is close to the one in [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF] (this similarity is highlighted in Section II). The difference here is that we are able to analytically study this model and go beyond simulations and theirs interpretation.

The main contributions of this work are threefold. (i) We propose a consensus-like dynamics that approaches the dynamics described in [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF]. This CODA model is given by a quantized consensus system with state-dependent interaction weights. (ii) We describe the possible equilibria of the proposed model and depict the main properties characterizing the opinions dynamics. Precisely, we provide a criterion to detect stabilization of the actions of a group of agents and to predict the propagation of this action throughout the network. Our criterion depends on the initial conditions and interaction topology only. (iii)

We completely analyze some particular interaction topologies such as: the complete graph and the ring graph.

The rest of the paper is organized as follows. Section II formulates the problem and illustrates that our model is close to the one proposed in [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF]. In Section III we show when the quantization effect is removed i.e. in the context of continuous opinions with continuous actions (COCA), that consensus is always achieved provided that the interaction graph is connected. The main features of our CODA model under general interaction topologies are derived in Section IV. Precisely we characterize the preservation and the propagation of actions inside a group and outside it, respectively. Some particular interaction topologies such as: the complete graph and the ring graph are analyzed in V.

II. PROBLEM FORMULATION AND PRELIMINARIES

We consider a network of n agents denoted by V = {1, . . . , n}. The interaction topology between agents is described by a fixed graph G = (V, E) that can be directed or not. Let N i be the set of agents that influence i according to the graph G (i.e. j ∈ N i ⇔ (j, i) ∈ E) and n i be the cardinality of N i . Initially, agent i ∈ V has a given opinion p i (0) = p 0 i ∈ (0, 1) and this opinion evolves according to a discrete-time protocol. Let p i (k) be the opinion of agent i ∈ V at time k. Assume that ∀i ∈ V, p i (0) = 1 2 and introduce the action value q i (k) ∈ {0, 1} as a quantized version of p i (k) defined by:

q i (k) =    0 if p i (k) < 1 2 , 0 if p i (k) = 1 2 and p i (k -1) < 1 2 , 1 otherwise.
Two distinct situations are considered in the following. COCA model: each agent has access to the opinion of its neighbors. In this case, our model simply writes as a consensus protocol with state-dependent interaction weights. Precisely, the opinion of an agent i ∈ V updates according to the following rule

p i (k + 1) = p i (k) + p i (k)(1 -p i (k)) n i j∈Ni (p j (k) -p i (k)). (1)
Denoting by p(•) = (p 1 (•), . . . , p n (•)) the vector that collects the opinions of all agents, the collective opinion dynamics is given by:

p(k + 1) = (I n + A(p(k))) p(k), (2)
where A(p(k)) is the opposite of the Laplacian matrix associated to adjacency matrix

(a ij (k)) ij with off-diagonal weights a ij (k) = p i (k)(1 -p i (k))/n i if j ∈ N i and a ij (k) = 0 otherwise.
Remark 1: We assume that p 0 i belongs to (0, 1) which is a normalized version of R. Doing so, the matrix I n + A(p(k)) is row stochastic and for all k ∈ N one has p(k) ∈ (0, 1).

CODA model: provides the main model under study in this paper. This model assumes that each individual has access only to the action of its neighbors. The opinion of agent i ∈ V in this case updates according to the following rule:

p i (k + 1) = p i (k) + p i (k)(1 -p i (k)) n i j∈Ni (q j (k) -p i (k)). (3)
Remark 2: For an agent i ∈ V, both COCA and CODA models propose interaction weights depending only on the opinion p i .

We can emphasize a natural partition of V in two subsets

N -(k) = {i ∈ V | q i (k) = 0} and N + (k) = {i ∈ V | q i (k) = 1}.
The main objective of this paper is to study how these sets evolve in time and what is the behavior of the opinions p i (k) inside these sets.

Throughout the paper we denote by n -(k) and n + (k) the cardinality of N -(k) and N + (k), respectively. Similarly, for an agent i we denote by

N - i (k) = N i ∩ N -(k) and N + i (k) = N i ∩ N + (k)
and by n - i (k) and n + i (k) the cardinalities of these sets.

The CODA model (3) was inspired by Martins' model [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF] which was formulated in terms of the following bayesian update. Let us denote by pi (k) the opinion of agent i ∈ V at time k ∈ N when using Martins' model [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF]. The updates of this opinion follows the rule described below. When agent i is influenced by agent j,

pi (k + 1) 1 -pi (k + 1) = pi (k) 1 -pi (k) • α 1 -α if q j (k) = 1, (4)
and where α is replaced by 1 -α if q j (k) = 0. The constant α ≥ 0.5 is a model parameter linked to the amplitude of opinion change as a result of interactions. This parameter does not appear in our model. The study [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF] is based on numerical experiments and do not present a theoretical analysis. The simulations found in [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF] where obtained with α = 0.7. The simulations appear to be qualitatively close to the ones resulting from our update (3) (see Section VI). To understand this fact, one can show that for α = 2/3 ≈ 0.7, and q j (k) = 1, update (3) and ( 4) are equivalent for small p i (k) values. Similarly, if q j (k) = 0 the two updates are equivalent for p i (k) values close to 1. For other p i (k) values, p i (k + 1) still remains close to pi (k + 1). These facts are illustrated in Figure 1. As a consequence, our CODA model (3) can be seen as a consensus-type version of Martins' model. One advantage of our model is to explicitly explains why extremist agents with opinion close to 0 or 1 hardly change their actions. This is due to the weight p i (1 -p i ) in update (3). 4) when the influencing agent has action q j = 1. The two bottom curves display the update (3) and (4) when the influencing agent has action q j = 0. Discontinuous red lines correspond to update (3) while strait blue lines correspond to update (4).

(k) = 1 q j (k) = 0 p i (k) p i (k+1)

III. ANALYSIS OF THE COCA MODEL

When agents have a direct access to opinions without quantification, opinions tend to a consensus at exponential speed as is shown in the present section. This is no longer the case when agents only have access the quantized actions instead of opinions of their neighbors, as will be shown in Section IV. It is noteworthy that an opinion stays constant according to dynamics (1) if it is initialized at the value 0 or 1. Therefore, by the following assumption we exclude these extreme cases from the analysis.

Assumption 1: There exists a strictly positive constant ∈ 0, 1 2 such that for all i ∈ V, one has The following result can be easily proven by induction.

p 0 i ∈ [ , 1 -].
Lemma 1: Let V ⊆ V such that V is isolated i.e. for all i ∈ V , for all j ∈ V \ V , (j, i) / ∈ E. Then, 1) M V (k + 1) ≤ M V (k) 2) m V (k + 1) ≥ m V (k)
Let us assume for the rest of this section that the graph is strongly connected.

Applying Lemma 1 with V = V one obtains that sequences m V (k) and M V (k) are both monotonic and bounded, thus convergent. The interaction weight from the agent j ∈ N i to the agent i at time k is defined by

a ij (k) := pi(k) 1-pi(k) ni . Taking into account that p 0 i ∈ [ , 1 -], the behavior of the function x → x(1 -x) on (0, 1) and Lemma 1, one deduces that a ij (k) ∈ [ (1-) ni , 1 4ni ] for all k ∈ N and j ∈ N i . Moreover, for all i ∈ V one has 1 ≤ n i ≤ n -1 yielding a ij (k) ∈ (1 -) n -1 , 1 4 , ∀i ∈ V, ∀j ∈ N i . (5)
Since a ii = 1 -j∈Ni a ij , straightforward computation shows that

a ii (k) ∈ 3 4 , 1 -(1 -) , ∀i ∈ V. (6)
Equation ( 5) and [START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF] shows that Assumption 1 in [START_REF] Blondel | Convergence in multiagent coordination, consensus, and flocking[END_REF] holds true. Moreover, in this paper we are dealing with a fixed (strongly) connected graph meaning that Assumption 2 and 3 in [14] also hold. Therefore the following result is a consequence of Theorems 1 and Lemma 1 in [START_REF] Blondel | Convergence in multiagent coordination, consensus, and flocking[END_REF].

Proposition 2: As far as the graph G is (strongly) connected and Assumption 1 is satisfied, the update rule (1) guarantees asymptotic consensus of all opinions. Furthermore, there exist two constants β ∈ (0, 1) and T ∈ N such that ∀k ∈ N

M V (k + T ) -m V (k + T ) ≤ β M V (k) -m V (k) .

IV. ANALYSIS OF THE CODA MODEL

For the remaining part of this work we consider the update rule [START_REF] Clifford | A model for spatial conflict[END_REF]. In this section we derive the set of possible equilibrium points and we give the conditions guaranteeing that the action q i of the agent i ∈ V is preserved/changed over time. Throughout the rest of the paper we assume that ∀i ∈ V, p i (0) ∈ (0, 1).

A. Characterization of equilibria

Let us define the following finite set of rational numbers:

S = k m k, m ∈ N, k ≤ m ≤ n -1 ⊂ Q. (7)
The main result of this section states that the possible equilibrium points of the opinions belong to S. Let us first introduce an instrumental result. For the rest of the paper we use the notation r i (k

) := n + i (k) n i .
Lemma 3: Let i ∈ V, p i (0) ∈ (0, 1). Then, for all k ∈ N, one of the following relations holds

p i (k) < p i (k + 1) < r i (k), (8)
p i (k) > p i (k + 1) > r i (k), (9)
or p i (k) = p i (k + 1) = r i (k). (10)
Moreover, ∀k ∈ N, p i (k) ∈ (0, 1).

Proposition 4: Let i ∈ V and suppose Assumption 1 holds.

If n + i (k) k≥0 (and thus n - i (k) k≥0 ) is stationary, then the sequence of opinions p i (k) k≥0 converges and has the following limit :

p * i = lim k→∞ p i (k) = lim k→∞ n + i (k) n i ∈ S.
Conversely, if the sequence of opinions p i (k) k≥0 converges towards a non-extreme value p * i ∈ (0, 1), then the sequence n + i (k) k≥0 is stationary and the equality between the limits still holds.

Proof: If the sequence n + i (k) k≥0 is stationary, one gets that n + i (k) is constant for k bigger than or equal to a fixed integer k * . Let us denote by ρ * i the value of r i (k) for k ≥ k * . According to Assumption 1, p i (0) ∈ (0, 1), so that Lemma 3 applies. By induction one has either

∀k ≥ k * , p i (k) ≤ p i (k + 1) ≤ ρ * i (11) or ∀k ≥ k * , p i (k) ≥ p i (k + 1) ≥ ρ * i . (12)
In the first case p i (k) k≥0 is increasing and upper-bounded, in the second p i (k) k≥0 is decreasing and lower-bounded. Thus p i (k) k≥0 converges. Denote p * i its limit. If p * i = 1, equation ( 11) must be satisfied and ρ * i = 1. If p * i = 0, equation (12) must be satisfied and ρ * i = 0. Finally, if p * i ∈ (0, 1), one can take the limit of equation (3) to show that p * i = ρ * i . Reversely, assume that the sequence of opinions p i (k) k≥0 converges to a limit p * i ∈ (0, 1). So that for some k * ∈ N, ∀k ≥ k * , p i (k) ∈ (0, 1). As a consequence, equation (3) rewrites as

p i (k + 1) -p i (k) p i (k)(1 -p i (k)) + p i (k) = r i (k).
Taking the limit of the previous equation shows that (n + i (k)/n i ) k≥0 converges and is thus stationary and its limit satisfies

ρ * i = p * i . Since n + i (k), n i ∈ N and n + i (k) ≤ n i , it is clear that p * i ∈ S.

B. Preservation of actions

In this subsection we investigate the conditions ensuring that the action q i does not change over time. More precisely, we provide a criterion to detect when a group of agents sharing the same action will preserve it for all time. For the sake of simplicity we focus on q i (0) = 0 but using similar arguments the same results can be obtained for q i (0) = 1.

Lemma 5: Let i ∈ V, if n - i (k) ≥ n + i (k) and q i (k) = 0 then q i (k + 1) = 0.
In the sequel we denote by |A| the cardinality of a set A.

Definition 6:

We say a subset of agents A ⊆ V is a robust polarized cluster if the following hold:

• ∀i, j ∈ A, q i (0) = q j (0);

• ∀i ∈ A, |N i ∩ A| ≥ |N i \ A|.
Remark 3: Notice that, in this section we do not make any assumption on the connectivity of the interaction graph. This means in particular that it may happen to have n i = 0 for some agents belonging to A above.

The next result explains why the word robust appears in the previous definition.

Proposition 7:

If A is a robust polarized cluster with q i (0) = 0 for a certain i ∈ A then

• ∀i ∈ A, ∀k ∈ N, q i (k) = 0; • ∀i ∈ A, lim k→∞ p i (k) ≤ 1 2 .
Proof: The proof will be done by induction. Let us remark first that following the first item of Definition 6 we have q i (0) = 0, ∀i ∈ A. Let us assume that for a fixed k * and ∀i ∈ A one has q i (k * ) = 0. Let us also recall that the interaction graph under consideration is fixed. Therefore we still have that

|N i ∩ A| ≥ |N i \ A|. Moreover, |N i ∩ A| ⊆ N - i (k * ) implying that n - i (k * ) ≥ n + i (k * ), ∀i ∈ A.
Thus, Lemma 5 yields that ∀i ∈ A one has q i (k * +1) = 0 and the proof ends.

C. Change and diffusion of actions

The goal of this subsection is twofold. First to provide conditions at a given time k ∈ N guaranteeing that the action of a fixed agent i ∈ V will change at time k + 1. Secondly, we analyze the propagation/diffusion of the action of a robust polarized cluster inside the overall network. Due to the symmetry of reasonings we continue to focus only on one case q i (0) = 0 or q i (0) = 1.

Proposition 8: Let i ∈ V and k ∈ N such that p i (k) > 1 2 and n - i (k) > n + i (k). Let (n + i (k), n i ) ∈ 0, 1 2
be the unique positive real solution of the equation:

x 3 - 1 2 -r i (k) x 2 - 3 4 x + 1 2 -r i (k) 1 4 = 0. (13)
Then

p i (k + 1) ≤ 1 2 if and only if p i (k) < 1 2 + (n + i (k), n i ).
The previous result states that an agent will change its action when it is influenced by more opposite actions, only if its opinion is sufficiently close to the boundary between the actions. The notion of sufficiently closed depends on the proportion of opposite actions that influence the agent and is exactly quantified by

(n + i (k), n i ). Lemma 9: Let i ∈ V and T i ∈ N such that n - i (k) > n + i (k), ∀k ≥ T i . Then it exists k * ≥ T i such that q i (k) = 0, ∀k ≥ k * .
The next result characterizes the diffusion of the action of a robust polarized cluster over the network.

Proposition 10: Let us consider the sets A 1 , A 2 , . . . , A d such that

• A 1 is a robust polarized set with q i (0) = 0 for a certain i ∈ A 1 (and thus ∀i ∈ A 1 , q i (0) = 0); • ∀h ∈ {1, . . . , d -1} and ∀i ∈ A h+1 one has

|N i ∩ A h | > |N i \ A h |.
Then, for all h ∈ {1, . . . , d}, ∃T h ∈ N, such that,

∀k ≥ T h , ∀i ∈ A h , q i (k) = 0,
where one can choose T 1 = 0. Consequently, ∀i ∈

d h=1 A h one has lim k→∞ p i (k) ≤ 1 2 .
Proof: The proposition with h = 1 and T 1 = 0 follows from the Proposition 7. For h > 1, we proceed recursively. Assume that the proposition holds for h ∈ {1, . . . , f } with f < d and show that it holds for h = f + 1. We know that ∀i ∈ A f +1 one has

|N i ∩ A f | > |N i \ A f |. Moreover N i ∩ A f ⊆ N - i (k), ∀k ≥ T f and ∀i ∈ A f +1 .

Therefore we can apply Lemma 9 for any

i ∈ A f +1 . Choosing T f +1 = max i∈A f +1
T i one obtains that the proposition holds for

h = f + 1.
The last part of the statement is a simple consequence of the fact that ∀i ∈

d h=1 A h one has q i (k) = 0, ∀k ≥ T where T = max h∈{2,...,d} T h .

V. SOME PARTICULAR NETWORK TOPOLOGIES

A. Complete graph

In this subsection we use previous results to completely characterize the opinion dynamics when the interactions are described by the complete graph.

Proposition 11: If n -(0) > n + (0) then ∀i ∈ V the limit behavior of the opinion is given by lim

k→∞ p i (k) = 0. Reversely, n + (0) > n -(0) implies lim k→∞ p i (k) = 1.
Let us consider now the case n -(0) = n + (0). It is noteworthy that in this case n = |V| is even and

• ∀i ∈ N + (0) one has |N i ∩ N -(0)| = n 2 > n 2 -1 = |N i \ N -(0)|. • ∀i ∈ N -(0) one has |N i ∩ N + (0)| = n 2 > n 2 -1 = |N i \ N + (0)|.
If the initial conditions are not symmetric w.r.t.

1 2 an agent will cross from N + to N -(or reversely) and we recover the situation treated in Proposition 11. Therefore, to finish the analysis we give the following result that deals with initial conditions symmetrically displayed w.r.t.

1 2 . This case emphasizes an interesting oscillatory behavior of the opinions.

Proposition 12: Assume that n + (0) = n -(0) and moreover ∀i ∈ {1, . . . , n 2 } there exist η i (0) ∈ 0,

1 2 such that p i (0) = 1 2 -η i (0) and p n 2 +i (0) = 1 2 + η i (0). (14)
Then

n + (k) = n -(k), ∀k ∈ N and ∃k * ∈ N such that ∀k ≥ k * , ∀j ∈ V, |p j (k) - 1 2 | ≤ * and p j (k) - 1 2 p j (k + 1) - 1 2 < 0,
where * < 1 6(n-1) is the unique positive solution of the equation

x 3 + 1 2(n -1) x 2 + 3 4 x - 1 8(n -1) = 0.
Remark 4: The result above states that all the agents in the network will finish by oscillating around 1 2 in a 2 * strip.

B. Ring graph

Throughout this section we consider the particular configuration in which the interactions are described by an undirected graph in which each vertex has exactly two neighbors. In the following we identify agent n + 1 as agent 1 and agent 0 as agent n. For a precise representation of the graph we assume that ∀i ∈ {1, . . . , n} one has N i = {i -1, i + 1}.

Proposition 13: Under the ring graph topology the opinions dynamics (3) leads to the following properties:

• the set S defined in [START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF] reduces to 0, 1 2 , 1 ;

• if ∃i ∈ V such that q i (0) = q i+1 (0) = 0 then {i, i+1} is a robust polarized cluster (i.e. q i (k) = q i+1 (k), ∀k ∈ N); • if ∀i ∈ V one has q i (0) = 1 -q i+1 (0) then either the initial opinions are not symmetric w.r.t. 1 2 and agents will change actions asynchronously leading to robust polarized sets {i -1, i, i + 1}.

or p i (0) ∈ 1 2 -σ, 1 2 + σ , ∀i ∈ V and agents will change actions synchronously preserving n -(k) = n + (k), ∀k ∈ N. Moreover, for σ solving

8σ 3 + 8σ 2 + 14σ -1 = 0 one has p i (k) ∈ 1 2 -σ, 1 2 + σ , ∀i ∈ V, ∀k ∈ N VI. NUMERICAL ILLUSTRATIONS

A. Influential minority

We illustrate that a well connected minority can convince a majority of agents located in the periphery of the interaction network. Proposition 10 can be used to predict the phenomenon given the topology of the social network and the initial actions only. Figure 2 illustrates this fact. From Proposition 10, taking A 1 = {1, 2, 3, 4}, A 2 = {5, 6, 7, 8}, A 3 = {9} and A 4 = {10}, we predict that all agents will converge to a state with action lim q i = 0. We see in Figure 2-B that initially agents 9 and 3 tend to approach 1/2 since they have neighbors equally distributed over 1/2. This behavior changes when agent 8 passes the 1/2 threshold. Moreover, the action diffusion propagates to agent 10 even though it originally had no neighbor with q i (0) = 0. The decrease of agent 10 towards 0 only starts when agent 9 passes the 1/2 threshold.

(A) (B) Fig. 2. Illustration of the action diffusion process described in Proposition 10. Agents 1, 2, 3 and 4 start with q i (0) = 0 and form a robust polarized cluster (Definition 6), while agents 5, 6, 7, 8, 9 and 10 start with q i (0) = 1. All agents converge to a state with action lim q i = 0.

B. CODA on a square lattice

We illustrate our results when the topology of interactions is a square lattice. First, we use a 6 × 6 lattice (see Figure 3). As illustrated in Figure 3-B, for this type of structure, the smallest robust clusters are formed by 2 × 2 squares. As expected from Proposition 7, the robust clusters keep their initial actions and patches of same actions form around the robust clusters. Notice also that the values of convergence lie in set {0, 1/4, 1/3, 1/2, 2/3, 3/4, 1} as predicted by Proposition 4.

Patches of agents with same actions are also observed for bigger lattice (see Figure 4 for an instance final actions in a 50 × 50 lattice where initial conditions were drawn following independent uniform distributions.). This is in accordance with the patterns found in [START_REF] Martins | Continuous opinions and discrete actions in opinion dynamics problems[END_REF].

C. Oscillatory dynamics on a ring graph

The following simulation displays the oscillation of agents'opinion around 1/2 when the interaction graph is complete and when the initial opinions are symmetrically distributed around 1/2 (see Proposition 12). Figure 5 shows an instance of this phenomenon for a system of 100 agents. Red lines correspond to agents belonging to a robust cluster with q i (0) = 1. Blue lines correspond to agents belonging to a robust cluster with q i (0) = 0.

VII. CONCLUSIONS

In this paper we have introduced a novel opinion dynamics model in which agents have access to actions which are quantized version of the opinions of their neighbors. The model reproduces different behaviors observed in social networks such as dissensus, clustering, oscillations, opinion propagation. The main results of the paper provides the characterization of preservation and diffusion of action under general communication topologies. A complete analysis of the opinions behavior is given in the particular cases of complete and ring communication graphs. Numerical examples illustrate the main features of this model.

Fig. 1 .

 1 Fig. 1. Comparison of the CODA model (3) and the model by Martins [8]. The two top curves display the update (3) and (4) when the influencing agent has action q j = 1. The two bottom curves display the update (3) and (4) when the influencing agent has action q j = 0. Discontinuous red lines correspond to update (3) while strait blue lines correspond to update (4).

  For a subset of agents, V ⊆ V and for all k ∈ N, let us define m V (k) := min j∈V p j (k) and M V (k) := max j∈V p j (k).

Fig. 3 .

 3 Fig. 3. Illustration of the CODA dynamics on a 6 × 6 square lattice. (A) Each colored squared cell represents the initial opinion of an agent. Agents communicate with adjacent cells (above, below, left and right). (B) Robust clusters initially detected. (C) Final opinions of the agents. (D) Trajectories of the agents'opinions.Red lines correspond to agents belonging to a robust cluster with q i (0) = 1. Blue lines correspond to agents belonging to a robust cluster with q i (0) = 0.

Fig. 4 .

 4 Fig.[START_REF] Sznajd-Weron | Opinion evolution in closed community[END_REF]. Illustration of the CODA dynamics on a 50 × 50 square lattice. Each colored squared cell represents the opinion of an agent after 100 iterations where initial conditions were drawn following independent uniform distributions. Agents communicate with adjacent cells (above, below, left and right).

Fig. 5 .

 5 Fig. 5. Trajectories of 100 agents with the complete interaction graph and initial opinions distributed symmetrically around 1/2.


Samuel Martin

Irinel-Constantin Morarescu

Dragan Nesic

Time scale modeling for consensus in sparse

come   L'archive ouverte pluridisciplinaire

Time scale modeling for consensus in sparse directed networks with time-varying topologies

Samuel Martin * , Irinel-Constantin Morȃrescu * , Dragan Nešić # Abstract-The paper considers the consensus problem in large networks represented by time-varying directed graphs. A practical way of dealing with large-scale networks is to reduce their dimension by collapsing the states of nodes belonging to densely and intensively connected clusters into aggregate variables. It will be shown that under suitable conditions, the states of the agents in each cluster converge fast toward a local agreement. Local agreements correspond to aggregate variables which slowly converge to consensus. Existing results concerning the time-scale separation in large networks focus on fixed and undirected graphs. The aim of this work is to extend these results to the more general case of time-varying directed topologies. It is noteworthy that in the fixed and undirected graph case the average of the states in each cluster is time-invariant when neglecting the interactions between clusters. Therefore, they are good candidates for the aggregate variables. This is no longer possible here. Instead, we find suitable time-varying weights to compute the aggregate variables as time-invariant weighted averages of the states in each cluster. This allows to deal with the more challenging time-varying directed graph case. We end up with a singularly perturbed system which is analyzed by using the tools of two time-scales averaging which seem appropriate to this system.

I. INTRODUCTION

Large dynamical systems of interacting units such as power grids, transportation networks or the brain can be modeled as multi-agent systems. Unfortunately, these models consist of very large number of coupled differential equations whose analysis becomes intractable. Therefore, it is crucial to reduce the complexity of the system by proposing appropriate reduced-order models that still capture the asymptotic behavior of the network. A natural approach is to merge a number of agents into a single node whose state approximates the states of the agents that generated it. This idea has been successfully applied for networks represented as fixed undirected graphs [START_REF] Hanski | Metapopulation dynamics[END_REF], [START_REF] Gfeller | Spectral coarse graining and synchronization in oscillator networks[END_REF], [START_REF] Bıyık | Area aggregation and time-scale modeling for sparse nonlinear networks[END_REF], [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF], [START_REF] Romeres | Novel results on slow coherency in consensus and power networks[END_REF]. An extension of this idea to networks represented as fixed directed graphs was proposed in [START_REF] Morȃrescu | Dimension reduction for large-scale networked systems[END_REF].

The goal of this paper is to provide a methodology to generate appropriate reduced systems for multi-agent systems with a large number of agents interacting through directed time-varying networks. A fundamental assumption is that the interaction network consist of sparsely connected clusters of densely connected agents [START_REF] Bıyık | Area aggregation and time-scale modeling for sparse nonlinear networks[END_REF], [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF], [START_REF] Morȃrescu | Coordination in networks of linear impulsive agents[END_REF]. An interesting feature of these networks is that the agents first converge fast toward * Université de Lorraine, CRAN, UMR 7039, and CNRS, CRAN, UMR 7039, 2, Avenue de la Forêt de Haye, 54500, Vandoeuvre, France. (samuel.martin,constantin.morarescu)@univ-lorraine.fr.

# Department of Electrical and Electronic Engineering, The University of Melbourne, Parkville, 3010 VIC, Australia. dnesic@unimelb.edu.au a local agreement inside the clusters and then they slowly converge to a global consensus. This time scale separation has been emphasized and used for the analysis of power grids with fixed and undirected interconnections [START_REF] Bıyık | Area aggregation and time-scale modeling for sparse nonlinear networks[END_REF], [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF], [START_REF] Romeres | Novel results on slow coherency in consensus and power networks[END_REF]. The same feature has been used in [START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF] for clusters detection in large scale networks. However, up to now, only symmetric and time-invariant communication networks have been dealt with.

In the case of fixed and undirected graph the average of the states in each cluster is time invariant when neglecting the interactions between clusters. Therefore, it is natural to use it as an aggregate state. When the interactions are directed and time varying we have to define appropriate aggregate variables. To do so, we introduce time-varying weights defining a time-invariant weighted average (using reasoning similar to [START_REF] Martin | Continuous-time consensus under non-instantaneous reciprocity[END_REF]) as aggregate state of a cluster isolated from the other clusters. As a result we exhibit a time-scale separation in the network justifying the approximation of the overall network dynamics with the dynamics of the slow aggregate variables. It is important to note that unlike the fixed undirected interconnections graph [START_REF] Bıyık | Area aggregation and time-scale modeling for sparse nonlinear networks[END_REF], [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF], [START_REF] Romeres | Novel results on slow coherency in consensus and power networks[END_REF], the resulting singularly perturbed system in this paper is not in standard form and we cannot use the standard tools [START_REF] Khalil | Nonlinear Systems[END_REF], [START_REF] Kokotović | Singular perturbation methods in control: analysis and design[END_REF]. Instead it is more natural to employ averaging theory for two time-scales systems [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF], [START_REF] Nesic | Input-to-state stability for nonlinear time-varying systems via averaging[END_REF], [START_REF] Teel | A unified framework for input-to-state stability in systems with two time scales[END_REF]. Note that these results are not restricted to periodic systems. The contribution of the paper can be summarized as follows:

• we provide the assumptions guaranteeing that the convergence is faster inside clusters than between clusters; • under these assumptions, we show that time-scale separation occurs and can be used for analysis of directed and time varying interconnections; • we use averaging theory for two time-scales systems which seems to be appropriate, under the stated conditions, for the analysis of networks structured in sparsely connected clusters of densely connected agents.

The rest of the paper is organized as follows. Section II introduces the model under study, the assumptions allowing to rewrite the model in singular perturbation form and presents the main contributions related to the singular perturbation modeling and analysis. In Section III we give some technical results concerning the two time-scales modeling. The singular perturbation analysis is provided in Section IV and an illustrative numerical examples is presented in Section V.

Notation. The following standard notation will be used throughout the paper. The set of non-negative integers, real and non-negative real numbers are denoted by N, R and R + , respectively. For a matrix A we denote by A ∞ its infinity norm. The transpose of a matrix A is denoted by A . By I k we denote the k × k identity matrix. 1 k and 0 k are the column vectors of size k having all the components equal 1 and 0, respectively. A non trivial subset S of a set C, denoted as S C, is a non-empty set with S C. A directed path of length p in a given directed graph G = (N , E) is a union of directed edges p k=1 (i k , j k ) such that i k+1 = j k , ∀k ∈ {1, . . . , p -1}. The node j is connected to node i in a directed graph G = (N , E) if there exists at least a directed path in G from i to j (i.e. i 1 = i and j p = j).

II. PRELIMINARIES A. Model statement

Let N {1, . . . , n} be a set of n agents. By abuse of notation we denote both the agent and its index by the same symbol i ∈ N . Each agent is characterized by a scalar state x i ∈ R, ∀i ∈ N that evolves according to the following consensus system

ẋi (t) = n j=1 a ij (t)(x j (t) -x i (t)), ∀i ∈ N , (1)
where a ij (t) ≥ 0 are twice continuously differentiable and uniformly upper-bounded functions of time representing the interaction weights. Let x(t) = (x 1 (t), . . . , x n (t)) ∈ R n be the overall state of the network collecting the states of all the agents. Under these conditions, there exists a unique differentiable function of time x : R + → R n whose components satisfy equation ( 1) for all t ∈ R + [START_REF] Filippov | Differential equations with discontinuous righthand sides[END_REF], and it is bounded [START_REF] Hendrickx | Convergence of type-symmetric and cut-balanced consensus seeking systems[END_REF]. We call it the trajectory of the overall system. We say the trajectory asymptotically reaches a consensus when there exists a common agreement value α ∈ R such that

lim t→+∞ x i (t) = α, ∀i ∈ N .
In the sequel, agents are assumed to be partitioned in m nonempty clusters: C 1 , C 2 , . . . , C m ⊂ N , that are assumed to be given or can be easily identified. For instance clusters may correspond to groups of agents which are spatially close to each other while different clusters are distant to each other. Let us introduce the following supplementary notation: M {1, . . . , m} and n i denotes the cardinality of cluster C i and n = min i∈M n i . Without loss of generality, we permute the agents' labels according to the partition so that when j ∈ C i and j ∈ C i+1 , j < j . Denote A(t) = (a ij (t)) the adjacency matrix of communication weights at time t, D(t

) = diag(d ii (t)) with d ii (t) =
j∈N a ij (t), and L(t) = D(t) -A(t) its associated Laplacian matrix. We denote as

A I (t) = diag(A 1 (t), . . . , A m (t)) the block-diagonal intra-cluster adjacency matrix where for k ∈ M, A k (t) = (a ij (t)) (i,j)∈C 2
k . We also denote by L k (t) the Laplacian matrix associated to A k (t) and L I (t) = diag(L 1 (t), . . . , L m (t)) the blockdiagonal Laplacian matrix associated to A I (t). The inter-cluster communications are then described by A E (t) = A(t) -A I (t) and its associated Laplacian matrix L E (t) = L(t) -L I (t). The inter-cluster adjacency matrix has zero elements A E ij (t) if i and j belong to the same cluster.

B. Framework assumptions

In the following let us introduce some notation and the main hypotheses of this work. For two subsets of nodes A, B ⊂ N , the sum of communication weights from B to A is denoted as

w A ← B (t) = i∈A,j∈B a ij (t).
Let us also recall some notation in [START_REF] Bıyık | Area aggregation and time-scale modeling for sparse nonlinear networks[END_REF], [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF], [START_REF] Romeres | Novel results on slow coherency in consensus and power networks[END_REF] by adapting them to cope with non constant internal communications:

c I (t) = min k∈M,S C k w S ← (C k \S) (t), γ E (t) = max k∈M w C k ← (N \C k ) (t), δ(t) = γ E (t) c I (t) . (2)
Assumption 1 (Intra-cluster communication): There exist constants c ≥ 0, K I ≥ 1 such that c I (t) ≥ c, ∀t ≥ 0 and for any cluster k ∈ M and for all non trivial subsets S C k ,

w S ← (C k \S) (t) ≤ K I • w (C k \S) ← S (t), ∀t ≥ 0.
As proven in the sequel, Assumption 1 ensures exponential consensus inside each cluster seen as an independent network (see Lemma 1). This will justify the merging of all the nodes belonging to a cluster into one aggregate node. Assumption 2 (Inter-cluster communication): There exist constants K E ≥ 1 and ā ∈ (0, 1) such that for all non trivial subset S M, for all t ≥ 0, the two following equations hold :

k∈S w C k ← (N \C k ) (t) ≤ K E • k∈S w (N \C k ) ← C k (t), (3)
k∈S h∈M\S w C k ← C h (t) ≥ c I (t)ε ā. (4)
Assumption 2 ensures consensus of the aggregate state associated with the clusters, where equation ( 3) ensures reciprocity of the external interactions while equation ( 4) guarantees their persistence when Assumption 1 is satisfied (see e.g. [START_REF] Martin | Continuous-time consensus under persistent connectivity and slow divergence of reciprocal interaction weights[END_REF] for definitions). Constant ā can be chosen arbitrarily small. It is necessary that K I ≥ 1 and K E ≥ 1 and the equality corresponds to symmetric communication. The next assumption ensures that the total communication weight which a cluster C k receives cannot exceed a proportion of the weight received by any non-trivial subset of C k from the rest of C k . Assumption 3: The ratio between internal and external interaction weights (defined in [START_REF] Gfeller | Spectral coarse graining and synchronization in oscillator networks[END_REF]) is bounded by a constant bound ε > 0 : for all t ≥ 0, δ(t) ≤ ε. The purpose of Assumption 3 is to ensure that the partition in clusters corresponds to the distribution of communication weights. It prevents cases where two subsets of a cluster are more connected to the outside than with each other. As it will be detailed in section III, Assumption 3 is necessary in order to exhibit a two time-scale separation of the system.

Remark 1: Assumption 3 guarantees that for each cluster k ∈ M and for all non trivial subsets S C k ,

w C k ← (N \C k ) (t) ≤ ε • w S ← (C k \S) (t), ∀t ≥ 0.
Remark 2: Note that Assumption 3 does not follow from Assumptions 1 and 2 hold. For a counter-example see [START_REF] Martin | Cut-balance conditions for consensus in networks of clusters[END_REF].

Remark 3: For instances of classes of communication weights satisfying Assumptions 1 and 2, see [START_REF] Hendrickx | Convergence of type-symmetric and cut-balanced consensus seeking systems[END_REF]. Section V also provides an instance where Assumptions 1, 2 and 3 are all satisfied.

Using the formalism of communication in clusters, one has the following result.

Proposition 1: Supposing that Assumptions 1, 2 and 3 hold, the trajectory of system (1) reaches consensus exponentially fast.

Proof: As shown in [18, Theorem 1], Assumptions 1, 2 and 3 ensure the cut-balance condition in [START_REF] Hendrickx | Convergence of type-symmetric and cut-balanced consensus seeking systems[END_REF]. Moreover, (4) and the lower-bound imposed on c I (t) guarantee that there exists a strongly connected graph G = (N , E) such that

t 0 a ij (s)ds ≥ εt āc , ∀(j, i) ∈ E
and following [START_REF] Martin | Continuous-time consensus under persistent connectivity and slow divergence of reciprocal interaction weights[END_REF]Proposition 4] one obtains the exponential convergence toward consensus. Remark 4: Proposition 1 applies in the more general setting of integral equations with non smooth a ij (see [START_REF] Hendrickx | Convergence of type-symmetric and cut-balanced consensus seeking systems[END_REF]) but in the present study, we use only smooth a ij due to the singular perturbation analysis that is presented in the next section.

From Proposition 1, it is known that the trajectory of system (1) will converge to consensus. It remains to characterize this convergence. In particular, we want to show that convergence occurs faster within clusters than between clusters. Therefore aggregating the nodes inside clusters yields a smaller dimension model that approximates the overall dynamics. The analysis is carried out for general time-varying, non-symmetric communication weights.

C. Contributions

Firstly, we show that under Assumptions 1, 2 and 3 the system (1) rewrites in a singular perturbation form:

       dŷ dt f (t f ) = εA 11 (t f , ε)ŷ(t f ) + εA 12 (t f , ε)ẑ(t f ), dẑ dt f (t f ) = εA 21 (t f , ε)ŷ(t f ) + A 22 (t f , ε)ẑ(t f ), (5)
where ε is a small parameter, t f represents the fast time-scale that will be defined as well as all the matrices involved in the dynamics. The matrices A ij (t f , ε) will be shown to be continuously differentiable in their arguments and the norms of matrices A 11 (t f , ε), A 12 (t f , ε) and A 21 (t f , ε) will be proven to be bounded above by a constant while the norm of A 22 (t f , ε) is bounded below away from 0 (see equation [START_REF] Martin | Cut-balance conditions for consensus in networks of clusters[END_REF]). The bounds are uniform in time t f and in ε. Roughly speaking, ŷ ∈ R m and ẑ ∈ R n-m describe the aggregate state of the clusters and the disagreement variables inside clusters, respectively. It is worth mentioning that we will emphasize the presence of a slow time-scale t s = εt f and show that ŷ evolves slowly while ẑ evolves fast.

Assumption 4: Suppose that the following limit exists and is independent of

t f A av = lim T →∞ 1 T t f +T t f A 11 (s, 0)ds.
We define the reduced (slow) system and boundary layer (fast) system:

       dy s dt s (t s ) = A av y s (t s ); dz f dt f (t f ) = A 22 (t f , 0) z f (t f ); (6)
to approximate the solutions of system [START_REF] Romeres | Novel results on slow coherency in consensus and power networks[END_REF]. The following approximation result is based on Theorem 1 in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF].

Theorem 1: Let y s (0) = y s,0 ∈ R m and z f (0) = z f,0 ∈ R n-m
some fixed initial conditions to system [START_REF] Morȃrescu | Dimension reduction for large-scale networked systems[END_REF]. Set the same initial conditions to system (5), independently of ε. Then, under Assumptions 1, 2, 3 and 4, for any fixed ε > 0, system (5) possesses unique bounded solutions ŷ(t f , ε) and ẑ(t f , ε) defined on R + (here, the dependence in ε is made explicit), and system (6) possesses unique bounded solutions y s and z f defined on R + . These solutions satisfy

lim ε→0 sup t f ∈R+ ŷ(t f , ε) -y s (εt f ) = 0, lim ε→0 sup t f ∈R+ ẑ(t f , ε) -z f (t f ) = 0.
Furthermore, for any fixed ε > 0, the trajectories ŷ(t f , ε) and y s (εt f ) converge exponentially fast to consensus and the trajectories ẑ(t f , ε) and z f (t f ) converge exponentially fast to 0, when t f → ∞.

III. TWO TIME-SCALE MODELING

Using the matrix notation, system (1) can be represented as

ẋ = -L(t)x = -(L I (t) + L E (t))x. (7)

A. Aggregate state

When trying to reduce the model and carry out time-scale separation between internal and external dynamics, difficulties arrise when the internal communication are neither constant nor symmetric as it was assumed in [START_REF] Bıyık | Area aggregation and time-scale modeling for sparse nonlinear networks[END_REF], [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF], [START_REF] Romeres | Novel results on slow coherency in consensus and power networks[END_REF]. In the present section, we introduce some time-varying weights defining a time-invariant weighted average for stand alone clusters, which defines the aggregate state of the cluster. Let us consider the isolated internal dynamics :

ẋC k (t) = -L k (t)x C k (t), (8)
which corresponds to the internal dynamics x C k (t) when L E (t) = 0, where x C k (t) denotes the vector collecting states x i (t) for i ∈ C k . We define, for all t, τ ≥ 0 with t ≤ τ , the fundamental matrix Φ k (t, τ ) of system (8) such that

xC k (τ ) = Φ k (t, τ )x C k (t). (9)
As a direct consequence of Lemma 6 in [START_REF] Martin | Continuous-time consensus under non-instantaneous reciprocity[END_REF], for all t, τ ≥ 0 with τ ≥ t, for any i, j ∈ C k , weight Φ k ij (t, τ ) is non-negative and

j∈C k Φ k ij (t, τ ) = 1. ( 10
)
Lemma 1: Under Assumption 1 (intra-cluster communication) system [START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF] converges to consensus at exponential rate.

Lemma 1 is a direct consequence of Proposition 4 [START_REF] Martin | Continuous-time consensus under persistent connectivity and slow divergence of reciprocal interaction weights[END_REF]. In the sequel, we assume that Assumption 2 is satisfied so that xC k converges to a consensus at exponential speed. We denote the limit matrix Φ k (t, ∞) = lim τ →∞ Φ k (t, τ ), which exists thanks to Lemma 1. Moreover, since xC k converges to a consensus independently of the inital conditions, there exists

q k (t) ∈ R n k such that Φ k (t, ∞) = 1 • (q k (t)) T . (11)
Vector q k (t) plays an important role in the rest of the study, in particular it serves to define an invariant for the isolated internal dynamics (8) as given in the next lemma.

Lemma 2: The vector q k (t) satisfies q k (t) T • 1 = 1 and its components q k i (t) are positive uniformly bounded i.e., for all t ≥ 0 and i ∈ C k , q k i (t) ∈ [q min , q max ] ∈ (0, 1),

with q min = (exp(-K I )/n) n-1 , q max = 1 -( n -1)q min ,
where n = min k∈{1,...,m} n k and n = max k∈M n k . Furthermore, quantity q k (t

) T • xC k (t) is invariant in time, i.e., ∀t ≥ 0, q k (t) T • xC k (t) = q k (0) T • xC k (0).
Proof: See the Appendix in [START_REF] Martin | Time scale modeling for consensus in sparse directed networks with time-varying topologies[END_REF]. Remark 5: Computing vector q k (t) is straightforward when the internal communication weights are constant up to a multiplicative factor, i.e., L k (t) = l k (t)L k (0), with l k (t) ∈ R (but not necessarilly symmetric). In this case, q k is constant, obtained as the left eigenvector of L k (0) associated to the eigenvalue 0 such that (q k ) T 1 n k = 1 (see for instance [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF]). More generally, q k (t) can be computed whenever the internal dynamics is simple enough to be computed analytically. In other cases, the time-scale separation still occurs naturally as the present study shows and Lemma 2 provides bounds for the invariant q k (t) T • xC k (t).

In the following we introduce variables y(t) ∈ R m which corresponds to the cluster-aggregate state collecting weighted averages of the agents' states in each cluster:

y k (t) = (q k (t)) x C k (t) or y(t) = J(t)x(t) ∈ R m ,
with x C k the vector collecting the states x i of the nodes i ∈ C k and where J(t) is the following block-diagonal matrix: J(t) = diag (q 1 (t)) , (q 2 (t)) , . . . , (q m (t)) ∈ R m×n .

(12) The next lemma states that in each cluster k, the weight vector q k (t) is taken so that y is invariant through system [START_REF] Morȃrescu | Coordination in networks of linear impulsive agents[END_REF] when no inter-cluster communication takes place. This justifies why y(t) is a good candidate to represent the cluster-aggregate states.

Lemma 3: Suppose Assumption 3 holds. When ε (defined in Assumption 3) equals 0, no inter-cluster communication takes place, and in this case, y is invariant in time i.e.,

ε = 0 ⇒ L E (t) = 0 ⇒ ẏ(t) = 0. ( 13
)
In this case, if Assumptions 1 (intra-cluster communication) is also satisfied, the trajectory x C k in each cluster k is identical to xC k and converges at exponential speed to a local consensus with consensus value y k (0). Proof: The first part of statement ( 13) is a consequence of the second inequality in Assumption 2. The second part of statement ( 13) is a direct consequence of Lemma 2. The convergence to consensus comes from Lemma 1. Denote

x * C k ∈ R the consensus value. Then, lim t→∞ x C k (t) = x * C k 1 and y k (0) = lim t→∞ y k (t) = x * C k lim q k (t) T 1 n k = x * C k ,
where we successively used equation ( 13), the definition of y k and Lemma 2.

B. Disagreement variables

In the following, we provide a change of variable adapted to the clustered communication with non-symmetric and time-varying weights. First, In order to characterize the disagreement inside each cluster, let us introduce the variable z(t) ∈ R n-m which represents for all k ∈ M the distances to the first agent in C k :

z(t) = Qx(t), with Q = diag(Q 1 , Q 2 , . . . , Q m ) where Q k =     -1 1 0 . . . 0 -1 0 1 . . . 0 . . . . . . . . . . . . . . . -1 0 0 . . . 1     ∈ R (n k -1)×n k .
The initial state variable x(t) can be written in function of y(t) and z(t) as follows :

x(t) = Hy(t) + Q(t)z(t), (14)
where

H = diag 1 n1 , 1 n2 , . . . , 1 nm ∈ R n×m , Q(t) = diag( Q1 (t), Q2 (t), . . . , Qm (t)) and Qk (t) ∈ R n k ×(n k -1)
such that

Qk (t) =        -q k 2 (t) -q k 3 (t) . . . -q k n k (t) 1 -q k 2 (t) -q k 3 (t) . . . -q k n k (t) -q k 2 (t) 1 -q k 3 (t) . . . -q k n k (t) . . . . . . . . . . . . -q k 2 (t) -q k 3 (t) . . . 1 -q k n k (t)        . Matrices Q, Q(t)
were chosen to verify the following lemma. Lemma 4: The following properties hold true

• Q k 1 n k = 0, (q k (t)) Qk (t) = 0, • Q k Qk (t) = I n k -1 • Qk (t)Q k = I n k -1 n k (q k (t)) Proof:
The first property is obvious. The second comes from property (q k (t)) Lemma 2). For the third one, we compute each element of the first column of the product Qk (t)Q k . The first element is

1 n k = 1 meaning that n k i=1 q k i (t) = 1 (see
n k i=2 q k i (t)
and is replaced by 1 -q k 1 (t) while the rest of them are

n k i=2 q k i (t) -1 which is replaced by -q k 1 (t). Remark 6:
We note that definitions of y(t) and z(t) coincide with those used in [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF] if we consider that the interactions are symmetric and constant i.e. a ij (t) = a ji (t). We also note that, for constant symmetric interactions, the variables y(t) and z(t) can be introduced using another metric [START_REF] Bıyık | Area aggregation and time-scale modeling for sparse nonlinear networks[END_REF] such that Q = Q .

Using equation [START_REF] Teel | A unified framework for input-to-state stability in systems with two time scales[END_REF], system (7) can be rewritten to make explicit the dynamics in terms of variables y(t) = J(t)x(t) and z(t) = Qx(t) :

ẏ(t) = Ā11 (t)y(t) + Ā12 (t)z(t), ż(t) = Ā21 (t)y(t) + Ā22 (t)z(t), (15)
where

Ā11 (t) = -J(t)L(t)H, Ā12 (t) = -J(t)L(t) Q(t), Ā21 (t) = -QL(t)H, Ā22 (t) = -QL(t) Q(t).

C. Time-scale separation

The next lemma shows that the aggregate variable y and the intra-cluster disagreement variable z evolve according to different time-scale, parametrized by factor ε.

Lemma 5: The ∞-norms of the matrices in [START_REF] Filippov | Differential equations with discontinuous righthand sides[END_REF] satisfy

Ā11 (t) ∞ = J(t)L(t)H ∞ ≤ 2c I (t)ε, Ā12 (t) ∞ = J(t)L(t) Q(t) ∞ ≤ 2c I (t)ε, Ā21 (t) ∞ = QL(t)H ∞ ≤ 2c I (t)ε, Ā22 (t) ∞ = QL(t) Q(t) ∞ ≥ (1 -8ε)c I (t). ( 16
)
The proof of the lemma is given in the Appendix in [START_REF] Martin | Time scale modeling for consensus in sparse directed networks with time-varying topologies[END_REF].

The only matrix in system [START_REF] Filippov | Differential equations with discontinuous righthand sides[END_REF] which is not O(c I (t)ε) is Ā22 which corresponds to the influence of z on its dynamics. As a consequence, Lemma 5 shows that variables y behave as slow variables compared to the z variables. To reveal this fact, we rescale the time with a fast time scale t f = t 0 c I (s)ds and a slow time scale t s = εt f . This rescaling is well defined since according to Assumption 1, t f diverges when t → ∞. The transformation t → t f is invertible and so is t → t s . We denote t = ψ(t f ) the reverse transformation. Then y(t) = y(ψ(t f )) ŷ(t f ), z(t) = z(ψ(t f )) ẑ(t f ). Matrices Āij are also rescaled as

A 11 (t f , ε) = Ā11(ψ(tf )) c I (ψ(t f ))•ε , A 12 (t f , ε) = Ā12(ψ(tf )) c I (ψ(t f ))•ε , A 21 (t f , ε) = Ā21(ψ(tf )) c I (ψ(t f ))•ε , A 22 (t f , ε) = Ā22(ψ(tf )) c I (ψ(t f ))
. Thanks to Assumption 3, the rescaling is well defined. At this point, the dependance in ε has been made explicit to stress that the singular perturbation approximation corresponds to set ε = 0 (see below equation ( 19)).

Without entering in details, writing the system [START_REF] Filippov | Differential equations with discontinuous righthand sides[END_REF] in the slow time-scale leads to non-standard singularly perturbed system because of the appearance of the term 1/ε inside the matrix arguments. Thus singular perturbation analysis in [START_REF] Khalil | Nonlinear Systems[END_REF] cannot be applied. Nevertheless, using averaging theory [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF], [START_REF] Teel | A unified framework for input-to-state stability in systems with two time scales[END_REF] for singularly perturbed systems we can approximate the behavior of system (15) using the fast-time scale dynamics.

Lemma 6: In the fast time-scale system (15) is described by

       dŷ dt f (t f ) = εA 11 (t f , ε)ŷ(t f ) + εA 12 (t f , ε)ẑ(t f ), dẑ dt f (t f ) = εA 21 (t f , ε)ŷ(t f ) + A 22 (t f , ε)ẑ(t f ), (17)
where the ∞-norms of the matrices in (5) satisfy

A 11 (t f , ε) ∞ ≤ 2, A 12 (t f , ε) ∞ ≤ 2, A 21 (t f , ε) ∞ ≤ 2, A 22 (t f , ε) ∞ ≥ (1 -8ε). (18)
Proof: Using equation ( 15),

dŷ dt f (t f ) = d(y • ψ) dt f (t f ) = dψ dt f (t f ) dy dt (ψ(t f )) = ( Ā11 (ψ(t f ))y(ψ(t f )) + Ā12 (ψ(t f ))z(ψ(t f ))) c I (ψ(t f )) . Moreover, Ā11 (ψ(t f ))/c I (ψ(t f )) = εA 11 (t f , ε),
and analogous equalities hold for Ā12 and Ā22 while Ā22 (ψ(t f ))/c I (ψ(t f )) = A 22 (t f , ε).

The bounds on the ∞-norms directly come from Lemma 5.

IV. SINGULAR PERTURBATION ANALYSIS The dynamics given in Lemma 6 fits in the generic form of systems treated in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF], [START_REF] Teel | A unified framework for input-to-state stability in systems with two time scales[END_REF]. Let z f be the solution of

dz f dt f (t f ) = A 22 (t f , 0) z f (t f ). (19)
Note that for ε = 0 the matrix A 22 and corresponds to intra clusters communication only and z f (t f ) = Qx(ψ(t f )). So, as given in Lemma 3, system (19) converges to 0 exponentially fast. Denote A 11 (s, 0) = lim ε→0 A 11 (s, ε), which exists thanks to equation 18.

Let A av be defined in Assumption 4 and y s be the solution of

dy s dt s (t s ) = A av y s (t s ). (20)
Proposition 2: Denote y s,k for k ∈ M the k-th component of y s . Under Assumption 4, system (20) is a consensus system described element-wise by

dy s,k dt s (t s ) = j∈M a s kl (y s,l (t s ) -y s,k (t s )), k ∈ M, (21)
where a s kl = lim T →∞

1 T t f +T t f j∈C l i∈C k q k i (ψ(s))a ij (ψ(s)) c I (ψ(s)
)ε is independent of t f . Moreover, under Assumption 2 (Intercluster communication) y s reaches consensus exponentially fast.

Proof: See [START_REF] Martin | Time scale modeling for consensus in sparse directed networks with time-varying topologies[END_REF].

We are now ready to prove the main result of the study. Proof of Theorem 1: We want to apply Theorem 1 in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF]. Notice that system (5) rewrites as

       dŷ dt f (t f ) = εf (t f , t s , ŷ, ẑ, ε), dẑ dt f (t f ) = g(t f , t s , ŷ, ẑ, ε), (22)
where, following the notation in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF],

f (t f , t s , ŷ, ẑ, ε) = A 11 (t f , ε)ŷ(t f ) + A 12 (t f , ε)ẑ(t f ), g(t f , t s , ŷ, ẑ, ε) = εA 21 (t f , ε)ŷ(t f ) + A 22 (t f , ε)ẑ(t f ) (23
) It is worth noting that in our case f and g do not depend explicitly on the slow time t s . Equation żf = g(t f , τ, y, z f , 0) where τ and y are regarded as parameters corresponds to equation [START_REF] Martin | Time scale modeling for consensus in sparse directed networks with time-varying topologies[END_REF]. According to Lemma 3, z f converges at exponential speed to 0 so that Hypothesis H1 in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF] is satisfied. Moreover, f 0 in H2 in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF] is

f 0 (τ, y) = lim T →∞ 1 T t+T t f (s, τ, y, z f (s), 0)ds = lim T →∞ 1 T t+T t A 11 (s, 0)y + A 12 (s, 0)z f (s)ds = lim T →∞ 1 T t+T t A 11 (s, 0)ds • y = A av • y
where we used the exponential decrease of z f and the bound on A 12 (s, 0) ∞ in equation [START_REF] Martin | Cut-balance conditions for consensus in networks of clusters[END_REF] to remove the second term under the integral. Assumption 4 shows that H2 and equation (2.4) in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF] are satisfied. The averaged equation (2.5) in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF] corresponds to equation ( 20), whose trajectory are bounded and converge to consensus at exponential speed thanks to Proposition 2. As a consequence, Hypothesis H3 and H4 in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF] are satisfied. Finally, H5 is also satisfied because g(t f , τ, y, z f , 0) is independent of y. Under Hypotheses H1 through H5, Theorem 1 in [START_REF] Balachandra | A generalization of the method of averaging for systems with two time scales[END_REF] provides the expected result.

V. NUMERICAL ILLUSTRATIONS Consider the multi-agents system (1) with 8 agents and two clusters whose communication pattern is defined in Figure 1. When not null, internal communication weights are set to a ij (t) = 2+cos(2t) in cluster 1, to a ij (t) = 1 in cluster 2 and external communication weights are set to a ij (t) = ε(sin(t) + 2)/3 where ε is a constant parameter. As a consequence, Assumption 1, 2, 3 and 4 are all satisfied. In the present case, internal weights vary in time all with the same multiplicative factor so that q k (t) is time-invariant and correspond to the left eigenvector of L k (0) associated to eigenvalue 0 such that q k 1 n k = 1 (see Remark 5 for the computation of q k in the general case). We simulate the system with initial conditions x(0) = (6, 6.3, 4.4, 5.2, 3, 3.5, 0.4, 2.2) T (see Figure 2). As expected from Proposition 2 and Lemma 3, all aggregate variables converge to consensus and disagreement variables converge to 0, even when ε is not small. When ε = 1 the approximations are not precise, but they approch the real variables uniformly as ε diminishes, as expected from Theorem 1.

VI. CONCLUSION

In the present study, we have extended the singular perturbation analysis for linear consensus systems found in [START_REF] Chow | Time scale modeling of sparse dynamic networks[END_REF] to time-varying and directed networks. We have emphasized that the right tool to study the network at hand is averaging theory for two time-scales systems. Trajectories in the slow time scale ts of the aggregate (left) and disagreement variables (right) along with their approximations, for ∈ {1, 0.2, 0.04} from top to bottom. Strait lines correspond to the original variables while dashed lines are the approximations. Red lines are for cluster 1 and blue lines for cluster 2. Only the first disagreement variable of each cluster is displayed (the two others present a similar behavior).

  The work of S.Martin and I.-C. Morȃrescu was supported by project PEPS MoMIS MADRES and PEPS INS2I CONAS funded by the CNRS and project Computation Aware Control Systems (COMPACS), ANR-13-BS03-004 funded by ANR. The work of D. Nešić was supported by the Australian Research Council under the Discovery Project DP1094326.

Fig. 1 .

 1 Fig. 1. Communication graph. Red and blue circles are agents in cluster 1 and 2 respectively. Bold and dashed thin arrows correspond to communication inside and between clusters, respectively. Arrows are replaced by lines when the communication is bidirectional. Only communications with non-zero weight are displayed.

  Fig. 2.Trajectories in the slow time scale ts of the aggregate (left) and disagreement variables (right) along with their approximations, for ∈ {1, 0.2, 0.04} from top to bottom. Strait lines correspond to the original variables while dashed lines are the approximations. Red lines are for cluster 1 and blue lines for cluster 2. Only the first disagreement variable of each cluster is displayed (the two others present a similar behavior).


Guillaume Rosinosky
email: guillaume.rosinosky@bonitasoft.com

Samir Youcef
email: samir.youcef@loria.fr

Francois Charoy
email: francois.charoy@loria.fr

A Framework for BPMS Performance and Cost Evaluation on the Cloud

In this paper, we describe a framework that allows to automate and repeat business process execution on different cloud configurations. We present how and why the different components of the experimentation pipeline -like Ansible, Docker and Jenkins-have been set up, and the kind of results we obtained on a large set of configurations from the AWS public cloud. It allows us to calculate actual prices regarding the cost of process execution, in order to compare not only pure performance but also the economic dimension of process execution.

Introduction

A Business Process Management System (BPMS) is usually deployed on traditional software stacks composed of an application engine and databases. Sizing the resources it requires to support a given load or number of transactions per second is not easy, since it may imply to test it on different computer size with different configurations for the engine and its components. Thus, most of the time, BPMS deployment is done on oversized systems. Thanks to the public cloud, it is possible today to conduct these tests in a semi-controlled environment that provides a wide variety of possible deployment configurations and to repeat benchmarking activities as much as one wants. Even better, it is possible to associate a cost to these configurations. Still, setting up a framework that would allow repeatable and controllable execution is not easy. In this paper, we describe and demonstrate that the framework we have designed allows us to evaluate the performances and the cost of the execution of processes on the BonitaBPM execution engine on a whole set of configurations in the cloud, such as the used cloud instance types and the parallel number of executed business processes, combining different well known open source software including Docker and Ansible. Our framework allows to generate data that relate the operating performances to a cost per BPM transactions. It could be adapted to other kinds of BPM systems or frameworks

In the section 2, we describe the context and the hypothesis that we made regarding the deployment and the execution of BPM engines. Then we describe the different initiative that are proposing solutions to similar problems. In section 4 we describe the technical principles of our framework and how its components are combined. Section 5 describes the experimentation and, in the last part, we discuss them in regard of our objectives. Our original goal is to propose elastic resource allocation and scheduling methods for a BPMaaS provider. In order to size our infrastructure in a realistic way, we have to estimate different cloud configurations. Thus, we set up a framework to test multiple combinations of cloud resources by deploying in the Amazon Web Services (AWS) public cloud all the components needed for a BPMS (see figure 1 for an example of BPMS architecture) including the testing tools. Here, we test only configurations with one node for the database and one node for the application server and the BPMS engine. More precisely, we want to be able to :

Motivation and hypothesis

• allocate three separated IaaS virtual machines, one for the database, one for the BPMS engine, and one the BPMN process injector • deallocate the cloud instances At the best of our knowledge, there is no existing tool today that can manage all these steps. It has to be automated since we want to repeat the tests, and later reuse this framework on different cloud providers, databases vendors, BPMS, with different cloud configurations. Furthermore, the tool needs to be customizable on several parameters such as the number of parallel BPMN processes instances launched against the BPM engine, the type and number of cloud resources used for the database or the BPMS engine, the size of the number of working threads of the BPM engine, etc. Some parameters of the application server and the database need to be tuned in regard of multiple cloud configurations with varying number of CPU cores, memory, etc. For instance, the number of available working threads for the BPMS to execute work, the number of connections, or the memory assigned to the application server are important parameters that can completely change the behaviour and the processing speed. These criteria must be passed as parameters or directly as files that have to be be incorporated.

This high variability and the large amount of tests that we have to conduct and to repeat oblige us to set up a highly automated environment. From the execution to the data collection, we must be able to execute the whole test pipeline automatically. In this part, we describe these components, how they are deployed and used for our experimentations. Figure 2 presents examples of configurations we want to obtain.

Figure 2. Example of test launches on three different configurations for the database tier and the BPMS tier. m1.small, t2.micro, m3.medium and m3.large are AWS instances classes with different memory, computing power, etc.

Related work

Since its inception, the Cloud has been recognized as an excellent platform to evaluate different kind of software stacks and to provide a good potential to conduct reproducible experimentation. As a programmable infrastructure, it allows to automate the experimentation pipeline in a very seamless and cost effective way, competitive with large international infrastructures like grid5k 1 or Planetlab 2 . Public Cloud have also the advantage of being actually used by companies for production deployment. The result that we can obtain can be exploited almost directly.

On the case of BPM engine evaluation, Benchflow [START_REF] Ferme | A framework for benchmarking BPMN 2.0 workflow management systems[END_REF] is a very interesting approach. It is a benchmarking framework based on Faban 3 -a generic measurement framework, and Docker. The authors use a process composed of an empty automated task and a timer event. Their main metric is the process throughput. They have tested two anonymized BPMS for a defined duration with various user loads, and observed differences between the performances and the general behaviour of these two systems. However, their tests are not deployed on the cloud, and the framework seems to lack an orchestrator for intensive testing. Betsy [START_REF] Geiger | Process Engine Benchmarking with BetsyCurrent Status and Future Directions[END_REF] is another interesting approach, but it focuses mainly on the BPMN or BPEL compliance of BPMS, even if a performance benchmarking is planned.

There exist several cloud-related generic attempts such as Smart CloudBench [START_REF] Chhetri | Smart CloudBenchA framework for evaluating cloud infrastructure performance[END_REF], where it is possible to test generic application on cloud resources. However these solutions are commercial and, even if they could theoretically be used in our case they are not directly BPMS related.

The framework components

Our framework for performance testing is primarily dedicated to benchmark Cloud configurations performance in order to compare different combinations and parameters. It is composed or uses the following components.

BonitaBPM BPMS

We used Bonita BPM 4 7.3.1 in its community version as the BPMS engine. Bonita BPM is an opensource BPM solution originally developed in Inria [START_REF] Charoy | A dynamic workflow management system for coordination of cooperative activities[END_REF] and now supported by the Bonitasoft company. It is compliant with BPMN and can be deployed on many SQL databases like H2, MySQL, PostgreSQL, Oracle, or SQL Server. In our case, we conducted our tests on Postgresql database. It is the reference database for BonitaBPM.

The Process injector

We need a component able to inject BPMN schemas, execute processes and measure the performances of the engine. For this, we used a testing tool developed by Bonitasoft. It allows to deploy business process model in a BonitaBPM installation, to execute them by mocking process variables, generate metrics about performance, and then undeploy the processes. The results this tool gives are process centric i.e. basic statistics on the processes runtime.

Containerization of software units

There exists several of libraries and parameters in the three main components : it can be difficult to master them, and we need a way to create isolated and repeatable tests. We decided to use Docker. Docker 5 is an open source project combining LXC containers, virtualization, and a configuration management platform. As [START_REF] Boettiger | An introduction to Docker for reproducible research, with examples from the R environment[END_REF] explains, Docker can be very useful for scientific experimentation. It is now used in many production cases, and allows to make repeatable and isolated executions faster than with a virtual machine. A Dockerfile contains the list of commands needed to initialize an environment such as installing libraries, setting environment variables, and execute the required programs. It is possible to version the Docker images, and to save them in a tar file and load afterwards in order to reproduce seamlessly the whole execution environment each time it is needed.

We have adapted a BonitaBPM Docker image in order to be able to select the database vendor, and to use the performance tool. We have developed a Docker image for the performance tool and we have specified environment variables as parameters, such as the type of injected process, the number of parallel processes run by the injector in the BPM engine, the total number of processes runned, etc.

IaaS provider

For our tests, we have used Amazon Web Services 6 . AWS provides a very well defined API to automate our tests and a wide selection of virtual machine configurations. It can also be considered as the reference public Cloud provider. Since our first goal is not to compare Clouds we did not reproduce the experiments on another IaaS but as we will see in the next part the framework could be easily adapted to another environment. We have mainly used here Elastic Compute Cloud (EC2) instances on which we have deployed the different needed components.

Orchestration tool

Thanks to Docker, we are able to manipulate only containers instead of deploying a lots of files. This is an important step, but not sufficient for our needs. Indeed we need to be able to allocate and de-allocate cloud resources, and keep the different IP addresses for each instance for various references. For instance the BPMS instance needs the address of the database, including some credentials. The performance tool instance needs the BPMS instance address. We needed a tool able to execute scripts, deploy, instantiate cloud, keep the inventory of the various instances and is 5. https://www.docker.com/ 6. https://aws.amazon.com/ able to inject in an instance configuration other instance data. Many tools exists for these kind of automation and could be considered, such as Puppet, Ansible, Chef, Salt [START_REF] Venezia | Review: Puppet vs. Chef vs. Ansible vs[END_REF]. We selected Ansible for our framework. As written in Ansible's documentation, Ansible 7 is an IT automation tool programmed in Python. It is able to configure systems, deploy software and orchestrate IT tasks with files usually in YAML. It does not need a component on the client side, as it uses internally SSH for the communications with the target instances.

Several concepts exists in Ansible :

• hosts and groups : target instances and their typeswho can be used to obtain a subset of hosts It is possible to use variables inside a playbook or a role. These can be defined at several places (for instance, in parameter of the playbook, in the host, the group, the role, the playbook, etc.) and can also be overloaded when calling the command line. The template engine Jinja is used by Ansible for variable operations.

We have set up several roles and playbooks for our needs, such as a database role, a benchmark role, etc. We have used the EC2 modules for the allocation and deallocation of EC2 resources, and the Docker module for image instantiation.

For the customization part, we have mainly used default variable definition, variables files for the mandatory customization parameters such as the size of the memory of the Java Virtual Machine used in the application server for the BPMS engine. Indeed this value should be adapted to the memory the instance type is able to provide. For instance, an EC2 m3.medium instance has 3.75 Go of RAM, and a c4.xlarge instance has 7.5 Go de RAM. For these we have assigned respectively 3 Go for the memory allocation pool of the m3.medium and 6.75 Go for the c4.xlarge. A list of the main internal parameters is in table 1.

We have set default values for our various parameters, but needed to be able to overload several with the needed variation in the tests. For this, we have used the possibility to pass variables directly in the command line (the highest priority), in order to make variation in the studied internal variables such as the number of launches, or the types of EC2 instances.

For the resource part, as it is possible to launch roles against a subset of hosts with the group concept, we have prepared one group for each tier (database, BPMS, bench tool). For instance, the database role will be launched against the hosts of the database group only. The dynamic inventory gets each hosts and its corresponding groups by querying AWS inventory servers. Furthermore, in order to identify and be able to launch several tests simultaneously, we have assigned a unique identifier to each current test. For this we have added a variable named test userid that we use in the instantiation part as a supplementary group. For this, we have also modified the generic AWS dynamic inventory so it filters the hosts with this identifier. EC2 instances are declared with this additional EC2 tag in the creation playbook. Furthermore, we have added this value as a filter in the AWS dynamic inventory.

Test result collection

For this part, we used the s3cmd tool to send to a Amazon S3 bucket all our current results. For obvious speed and cost reasons, the scripts synchronizes only the files not already present in the bucket. We use the same command to download results for analysis.

Jenkins

Even with the orchestration offered by Ansible, launching all these scripts manually is not very efficient and can be complicated, mostly since we want to execute a lot of tests. In this case we have launched tests on more than 70 different configurations, each one launched 6 times. Indeed, we need to test a lot of instance types combinations for the BPMS and the database, including several different numbers of injected parallel processes. It was necessary to find a tool able to launch tests for us in an easy way, with a defined list of parameters and able to show logs feedback.

Jenkins 8 is an open source tool designed for continuous integration. It is possible to use it to make tests runs within a web-based user interface. We used it for the sake of simplicity, its scripting ability, and the capability to show different runs, and their log files. We used several plugins to simplify even more the processing, namely : Ansible 8. https://jenkins.io/ plugin, Rebuilder plugin, Environment injector plugin, Conditional Buildstep plugin. We have two parts : parameterized jobs who call their Ansible counterparts, a job calling the command for result archiving and a parametrized Jenkins pipeline who launches the jobs and is able to launch multiple times the test. A Jenkins pipeline is a customizable job orchestration command where it is possible to put a Groovy script for calling jobs. The scripting language is very powerful, for instance it is possible to put exception catching, and we have used to trigger in all the cases the destroy job. Indeed in case of blocking errors, the reserved instances continue to be rented and it can become very expensive : it is important to destroy as soon as they are not needed anymore. We have also added a parameter for the number of test launches, adding simply a loop who will call the specified number of times the test job.

Overview

Figure 3. Test architecture used for the cloud configuration capability determination for EC2. We show here the orchestration units and a target generated configuration. A similar manner, without the Ansible database playbook, and with RDS instance creation and destruction is used for the RDS scenario described in chapter 5.

Figure 3 presents the global architecture. Setting up this entire test pipeline to conduct performance evaluation of different deployments remains a tedious task but we have seen that thanks to the cloud and of current administration automation tools it is possible to deploy and test a software stack under different configuration in a fully automated way and to conduct repeatable execution. In the next section, we describe the kind of result that we were able to produce based on this environment. At this point it is interesting to note that changing the software to test is mainly a matter of Docker Image production and to define the needed parameters in the Ansible playbook and the Jenkins jobs and pipeline.

Experimentation

Overview

A first version of this framework was used for the resource size estimation in [START_REF] Rosinosky | An Efficient Approach for Multi-tenant Elastic Business Processes Management in Cloud Computing environment[END_REF]. In this paper, various AWS m3 family EC2 instances were used for the database and the application server. For this experimentation, we have launched tests against RDS Postgres, with db.r3 family instances (memory optimized) for the persistence tier, and with c4 (computing power optimized) family instances for the BPMS part.

For our tests, we have used the standard process, the reference process used for performance comparison between versions of BonitaBPM. This process is composed of 20 sequential automated tasks each one updating 15 string process variables from a constant and executing afterwards a connector repeatingly computing the Fibonacci number of 25 with a recursive method, until 150 milliseconds or more have passed.

The goal of our experimentation is to find the capacity of cloud resources in tasks per seconds. As a task could be very fast to execute, and the main metric used for size estimation in BonitaBPM benchmark tool is process based, we have used a reference time for the mean process duration. More precisely, we wanted our process to have a mean duration of 10 seconds : an arbitrary but realistic value for the standard process. Indeed, if we look only at the duration of the Fibonacci connectors, we obtain 3 seconds where we must add the process time of each process instantiation, variables allocation, workflow evaluation, and process termination. When launched with only one parallel inject business process, the duration of a process is about 5 seconds, as we will see in the figure 4.

We tested with different numbers of parallel process execution, and instance types for the database and application server. We have tuned BonitaBPM on the number of threads reserved for connectors and execution of tasks and on the database connection count, each one based on the parallel process number. The memory assigned to the Java(tm) VM of the BPMS' application server has also been tuned for each cloud configuration. We have also kept a unique specific parameter group for each RDS database, this one having most important parameters calculated from the size of the memory of the instance type. A parameter group is an AWS RDS reusable list of parameters used to tune the database. The list of parameters we used is listed in table 2 As the tests can be long, and expensive -we pay the cloud configurations during the tests -we have experimented a limited number of parallel processes, and then simply done a linear regression between the nearest upper and lower tests results around 10 seconds. For instance, if we obtain for 10 parallel processes a meantime of 5 seconds and for 20 parallel processes a meantime of 15 seconds, we will deduce we can use 15 process for a meantime of 10 seconds. We have then looked at the mean number of tasks per seconds for this number of processes. In figure 4, we can find the mean process execution time compared to the number of injected parallel processes. The throughput per second is simply obtained by dividing the total duration by the total number of executed tasks, 60000 in this case.

Results

The task throughput and task throughput for one dollar is in table 3. This last metric is important to see which type of cloud instances are the cheapest to use for a given quality of service. We can see here that less powerful instances are more interesting, except for the generic instance type m3.medium used for the database tier or both the database tier and BPMS tier. However this configuration remains less expensive for a low throughput of tasks. More powerful resources are more expensive to use, but are still useful when higher task throughput is required. The configuration db.r3.large / c4.large is the cheapest configuration to use (with the higher throughput for one dollar).

Another interesting thing to notice here is that the db.r3.large / c4.2xlarge is a lot more expensive to use than the other db.r3.large based configurations, and is not able provide a throughput as high as the db.r3.xlarge / db.r3.large while being more expensive. This can be correlated with the fact that a cloud configuration uses both the database tier and the BPMS tier, and paying more only for one of the tier could become counterproductive. This is visible in the figure 5. However, this needs to be tested more, as noisy neighbor effects could be partially at the origin of these results, as we can see in the error bars of figure 4.

Conclusion

In this paper, we have presented our framework that allows to conduct extensive tests of the execution of a BPMS engine under different cloud and engine configuration and to collect data in order to compare the result. Thanks to the entire automation of the test pipeline, based only a collection of open source tools it is possible to execute the test with as many configuration as we need the number of time we need. It remains also very flexible and cost effective. We spent around 250 $ in AWS credit to conduct all the tests needed for this paper, including runs that were required to validate the framework. This price could be reduced on AWS by using spot instances, that would allow to use VM at a fraction of the price. This framework also works with Vagrant for testing purposes, and with on premises computers, with a static inventory including hard coded IP adresses for each tier, and without the cloud instance creation and destruction.

In the near future, we plan to enhance the framework with the capability of testing clustered configurations and other database vendors. These operations are easy to add, since we just have to rely on the creation and orchestration of new docker images. We also want to add the possibility to test other BPMS, and to couple this framework with a load balancer and an resource allocation and scheduling algorithm as in [START_REF] Rosinosky | An Efficient Approach for Multi-tenant Elastic Business Processes Management in Cloud Computing environment[END_REF]. Finally, we plan to make more intensive benchmarks in order to better estimate the price and efficiency of BPMS on cloud configurations.

Figure 1 .

 1 Figure 1. Simple BPMS architecture. This figure shows a clustered version of a BPMS using a clustered database, behind a load balancer.

•

  deploy the relational database on its cloud instance • deploy the application server and the BPMS on their cloud instance • deploy the testing tool (process injector) on its cloud instance • launch the tests • get the results and the meta informations of the test • get other useful data (database dump, logs, etc.) • archive them

Figure 4 .

 4 Figure 4. Process mean time for number of parallel process. Errors bars represent minimum and maximum values obtained. The red line represent the 10 seconds reference.

Figure 5 .

 5 Figure 5. Price vs mean task throughput for each tested configuration. Shapes represent the database tier resource type, colors the BPMS tier resource type.

TABLE 1 .

 1 ANSIBLE INTERNAL PARAMETERS.

	7. https://www.ansible.com/

TABLE 2 .

 2 . USED PARAMETERS.

	Name	Tier	Usage
	name	global	test name
	nb launch	global	number of launches of the test
	database instance type	database	instance type file for database
	bonita instance type	BPMS	instance type file for Bonita
	parallel launch	benchmark	number of parallel instances
	configuration	BPMS	Bonita configuration file
	worker size	BPMS	number of assigned threads
	bonita version	BPMS	version
	test userid	global	unique test identifier

TABLE 3 .

 3 PRICE, MEAN TASK THROUGHPUT, AND MEAN TASK THROUGHPUT BY DOLLAR FOR A MEAN STANDARD PROCESS DURATION OF 10 SECONDS.

	DB inst. type	AS inst. type	price	task TP	task TP per $
	db.m3.medium	m3.medium	0.177	16.400	92.656
	db.m3.medium	c4.large	0.223	23.157	103.845
	db.r3.large	c4.large	0.399	55.164	138.255
	db.r3.large	c4.xlarge	0.518	58.067	112.100
	db.r3.xlarge	c4.large	0.674	65.113	96.607
	db.r3.large	c4.2xlarge	0.757	61.474	81.208
	db.r3.xlarge	c4.xlarge	0.793	83.236	104.963
	db.r3.xlarge	c4.2xlarge	1.032	89.149	86.384
	db.r3.2xlarge	c4.2xlarge	1.587 105.794	66.663
	db.r3.2xlarge	c4.4xlarge	2.063 107.585	52.150
	db.r3.4xlarge	c4.4xlarge	3.173 115.283	36.332
	db.r3.4xlarge	c4.8xlarge	4.126 129.279	31.332

Acknowledgments

The authors would like to thank Amazon Web Services for the free credits (this paper is supported by an AWS in Education Research Grant Award).