# Coordination in networks of linear impulsive agents

Irinel-Constantin Morarescu, Samuel Martin, Antoine Girard, Aurélie Muller-Gueudin

► To cite this version:

Irinel-Constantin Morarescu, Samuel Martin, Antoine Girard, Aurélie Muller-Gueudin. Coordination in networks of linear impulsive agents. IEEE Transactions on Automatic Control, 2016, 61 (9), pp.2402-2415. 10.1109/TAC.2015.2492058. [hal-01096071v2](https://hal.science/hal-01096071v2)

HAL Id: hal-01096071

https://hal.science/hal-01096071v2

Submitted on 20 Nov 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Coordination in networks of linear impulsive agents

Irinel-Constantin Morărescu, Samuel Martin, Antoine Girard, Aurélie Muller-Gueudin

## Abstract

Consensus in heterogeneous networks containing both linear and linear impulsive dynamics is considered in this paper. The model applies for networks of interconnected dynamical systems, called agents, that are partitioned into several clusters. Most of the agents can only update their state in a continuous way using only inner-cluster agent states. On top of this, few agents also have the peculiarity to update their states in a discrete way by resetting it using states from agents outside their clusters. Our main result gives sufficient conditions for consensus in these networks. We firstly analyze the case when the reset sequence verifies some explicit time conditions. Secondly we consider the case when the reset instants are event-triggered, i.e. defined by the occurrence of specific events. Finally, we treat the case when the reset instants arrive stochastically following a Poisson renewal process.

## Index Terms

Multiagent systems; consensus; reset systems.

## I. INTRODUCTION

The problem of consensus or synchronization is motivated by different applications as communication networks, power and transport grids, decentralized computing networks, and social

This work has been supported by the ANR project COMPACS - "Computation Aware Control Systems", ANR-13-BS03-004
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, 54506 Vandœuvre-lès-Nancy, France. A Girard is with Laboratoire Jean Kuntzmann, Université de Grenoble, B.P. 53, 38041 Grenoble, France. Aurélie Muller-Gueudin is with Université de Lorraine, IECL, UMR 7502, CNRS, IECL, UMR 7502, 54506 Vandœuvre-lès-Nancy, France and INRIA BIGS team, 54600 Villers-lès-Nancy, France. e-mails: {constantin.morarescu, samuel.martin, aurelie.gueudin}@univ-lorraine.fr, antoine.girard@imag.fr
networks. Throughout the paper, the network is modeled as a graph with nodes and edges representing the agents and their interconnections, respectively. The connectivity of the network, persistence of links and interactions reciprocity influence the convergence speed [1], [2] and the achievement of consensus wether the dynamics is linear [3], [4], [5], [6], [7], or nonlinear [8], [9], [10]. For this reason, most of the studies assume connectivity over bounded or unbounded time intervals. However, there also exist analysis and control designs for network connectivity preservation [11], [12], [13] as well as studies of networks that loose connectivity property [14], [15].

Our point of view is that real networks are partitioned in several clusters inside which the inter-
actions take place often and can be seen as continuous while, due to communication constraints
(harsh environment, energy optimization or opinion preferences for instance), the inter-cluster
interactions are rare, thus discrete. In social networks, the opinion of each individual evolves
by taking into account the opinions of the members belonging to its community. Nevertheless,
one or several individuals can change its opinion by interacting with individuals outside its
community. These inter-cluster interactions can be seen as resets of the opinions. This leads us
to a network dynamics that is expressed in term of reset systems (see [16], [17], [18] for details).
In [19] the authors assumed that each cluster has a leader and all the leaders nearly-periodically
reset their state by taking into account the state of their neighboring leaders. However, generally
we can have several agents in the same cluster that interact in a discrete manner with agents in
other clusters and, more importantly, we cannot synchronize the inter-cluster interactions in a
decentralized way. Therefore, in this paper we address the more general and realistic problem
of decentralized synchronization in heterogeneous networks containing both linear and linear
impulsive dynamics. Unlike the preliminary work [20], we consider here also the possibility
that reset instants are triggered by some events or, they arrive stochastically following a Poisson
renewal process.

The main contribution of this work is to provide sufficient conditions for consensus in networks of linear systems subject to impulses associated with point-wise activation of some interconnections. The results assumes the presence of a spanning tree in the communication structure although communication strength may vary in time. Our proof is based on the fact that the global diameter of the network decreases by a uniform rate over some fixed period of time in the worst case. Therefore, the global diameter of the network undergoes an exponential decrease.
The rest of the paper is organized as follows. In Section II we introduce the concepts necessary for the problem formulation. Section III contains the working assumptions on the network structure and system dynamics. We also provide there a prerequisite reset property of the fundamental matrix associated with the dynamics defined by a time varying Laplacian matrix. The main results concerning the convergence analysis are presented in Section IV. Section V considers the case where the reset instants are imposed by some events while Section VI deals with reset instants that follow a probability law. Before conclusions we illustrate numerically the behavior of the network under consideration.

**Notation.** The following standard notation will be used throughout the paper. The sets of non-negative integers, real and nonnegative real numbers are denoted by $\mathbb{N}$, $\mathbb{R}$ and $\mathbb{R}_+$, respectively. For a vector $x$ we denote by $\|x\|$ its Euclidian norm. By $I_n$ we denote the $n \times n$ identity matrix. $\mathbb{1}_n$ and $\mathbf{0}_n$ are the column vectors of size $n$ having all the components equal 1 and 0, respectively. We also use $\mathbf{0}_{n \times n}$ to denote the square matrix of dimension $n$ having all the components equal 0. Finally, for a left continuous function $x(\cdot)$ we use $x(t_k^-) = \lim_{t \to t_k, t < t_k} x(t)$.

## II. PROBLEM FORMULATION

### A. Graph theory prerequisites

We consider a network of $n$ agents described by the digraph (i.e. directed graph) $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ where the vertex set $\mathcal{V}$ represents the set of agents and the edge set $\mathcal{E} \subset \mathcal{V} \times \mathcal{V}$ represents the interactions.

**Definition 1:** A **directed path of length $p$** in a given digraph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ is a union of directed edges $\cup_{k=1}^p (i_k, j_k)$ such that $i_{k+1} = j_k, \forall k \in \{1, \dots, p-1\}$. The node $j$ is **connected** with node $i$ in a digraph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ if there exists at least a directed path in $\mathcal{G}$ from $i$ to $j$ (i.e. $i_1 = i$ and $j_p = j$). A **strongly connected digraph** is such that any two distinct elements are connected. A **strongly connected component** of a digraph is a maximal subset of $\mathcal{V}$ such that any of its two distinct nodes are connected. We say node $i$ is a **parent** of node $j$ in the digraph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ if $(i, j) \in \mathcal{E}$. A **directed tree** is a directed subgraph in which there exists a single node without parents called **root** while all the others have exactly one parent. The length of a directed tree is the length of its longest path. A **directed spanning tree** of a digraph is a directed tree that connects all the nodes of the graph. For a given graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, the subgraph **induced** by a subset of nodes $\mathcal{U} \subseteq \mathcal{V}$ is the graph $(\mathcal{U}, \mathcal{E} \cap (\mathcal{U} \times \mathcal{U}))$.
In the sequel, we consider that the vertex set $\mathcal{V}$ is partitioned in $m$ clusters $C_1, \dots, C_m$. We denote by $n_i$ the cardinality of each cluster $C_i$. For the sake of simplicity we reorder the nodes to obtain, for $i \in \{1, \dots, n\}$,

$$C_i = \{m_{i-1} + 1, \dots, m_i\}, \quad (1)$$

where $m_0 = 0$, $m_i \ge m_{i-1} + 1$, $m_m = n$, and thus,

$$n_i = m_i - m_{i-1}.$$

Let us also introduce the intra-cluster graph $\mathcal{G}_L = (\mathcal{V}, \mathcal{E}_L)$ containing only the edges of $\mathcal{G}$ that connect agents belonging to the same cluster. That is

$$\mathcal{E}_L = \{(i, j) \in \mathcal{E} \mid \exists k \in \{1, \dots, m\} \text{ such that } i, j \in C_k\}.$$

## B. System dynamics

The state of each agent evolves continuously by taking into account the states of other agents belonging to their cluster. Doing so, the agents approach local agreements which can be different from one cluster to another. In order to reach the consensus in the entire network every inter-cluster connection is activated at some discrete instants. When the inter-cluster link $(j, i) \in \mathcal{E} \setminus \mathcal{E}_L$ is activated, the state of agent $i$ is reset to a weighted average of the states of $i$ and $j$. If several links arriving at $i$ are activated simultaneously, all the source states of these edges are considered in the weighted average. In order to keep the presentation simple each agent will have a scalar state denoted by $x_i$. We also introduce the vectors $x = (x_1, \dots, x_n)^\top \in \mathbb{R}^n$ collecting the states of all the agents and $x_{C_i} = (x_{m_{i-1}+1}, \dots, x_{m_i})^\top \in \mathbb{R}^{n_i}$, $i \in \{1, \dots, m\}$ collecting the states of the agents belonging to cluster $i$, respectively.

The previous discussion is formally described by the linear reset system defining the overall network dynamics:

$$\left\{
\begin{array}{l}
\dot{x}(t) = -L(t)x(t), \quad \forall t \in \mathbb{R}_+ \setminus \mathcal{T} \\
x(t_k) = P(t_k)x(t_k^-) \quad \forall k \in \mathbb{N} \\
x(0) = x_0
\end{array}
\right.
\quad (2)$$

where $x_0 \in \mathbb{R}^n$, $\mathcal{T}$ is the countable set of reset instants which are described by the diverging and increasing sequence $(t_k)_k$, $L(t) \in \mathbb{R}^{n \times n}$ is a weighted time-varying Laplacian matrix associated to the intra-cluster graph $\mathcal{G}_L$ and $P(t_k) \in \mathbb{R}^{n \times n}$ is a stochastic matrix associated to the inter-cluster graph $\mathcal{G}_P(t_k) = (\mathcal{V}, \mathcal{E}_P(t_k))$ where $\mathcal{E}_P(t_k) \neq \emptyset$ is the set of inter-cluster links activated at
time $t_k$, so that $\mathcal{E}_P(t_k) \subseteq \mathcal{E} \setminus \mathcal{E}_L$. Precisely, the entries of $L(t)$ and $P(t_k)$ satisfy the following relations:

$$ \left\{ \begin{array}{l} L_{i,j}(t) = 0, \text{ if } (j,i) \notin \mathcal{E}_L \\ L_{i,j}(t) < 0, \text{ if } (j,i) \in \mathcal{E}_L, i \neq j \\ L_{i,i}(t) = - \sum_{j \neq i, j=1}^{n} L_{i,j}(t), \forall i \in \{1, \dots, n\}, \end{array} \right. \qquad (3) $$

$$ \left\{ \begin{array}{l} P_{i,j}(t_k) = 0, \text{ if } (j,i) \notin \mathcal{E}_P(t_k), i \neq j \\ P_{i,i}(t_k) > 0, \forall i = \{1, \dots, n\} \\ P_{i,j}(t_k) > 0, \text{ if } (j,i) \in \mathcal{E}_P(t_k), i \neq j \\ \sum_{j=1}^{n} P_{i,j}(t_k) = 1, \forall i \in \{1, \dots, n\}. \end{array} \right. \qquad (4) $$

In order to guarantee that system (2) admits a unique solution we further impose that for all $i, j \in \{1, \dots, n\}$ the functions $L_{i,j}$ are measurable functions of time (see Theorem 54 in [21]). According to (4), given some $i$, if $P_{i,j}(t_k) = 0$ for all $j \neq i$ then $P_{i,i}(t_k) = 1$, meaning that no jump occurs on the state of the agent $i$ at time $t_k$. The values $L_{i,j}(t)$ and $P_{i,j}(t_k)$ represent the weight of the state of the agent $j$ in the updating process of the state of agent $i$ when using the continuous and discrete dynamics, respectively. The matrices $L(t)$ and $P(t_k)$ describe the level of influence of each agent inside its cluster and outside it, respectively. So, $L$ and $P$ vary in time depending on which agents update their state. The weight of influence $P_{i,j}$ or $L_{i,j}$ may also vary in time for a given pair $(j, i)$.

It is worth noting that $L(t)$ has the following block diagonal structure

$$ L(t) = \begin{pmatrix} L_1(t) & & & \\ & \ddots & & \\ & & L_m(t) & \\ & & & L_n(t) \end{pmatrix}, \quad L_i(t) \in \mathbb{R}^{n_i} \qquad (5) $$

with $L_i(t)1_{n_i} = 0_{n_i}$ and $P(t_k)1_n = 1_n$.

### III. PRELIMINARIES

#### A. Framework assumptions

In order to prove that the reset algorithm (2) guarantees asymptotic consensus for every initial condition $x_0$ we have to impose some standard assumptions. The first one concerns a minimal
connectivity property of the whole network and of each cluster.

Assumption 1 (Network structure): The graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ is such that

1a) For each cluster $C_i$, the induced graph $(C_i, \mathcal{E}_L \cap (C_i \times C_i))$ contains a spanning tree,

1b) If needed one can reorder the clusters such that: for all $i \ge 2$ there exist $j < i$, $l_i \in C_j$ and $r_i$ a root of a spanning tree of $C_i$ such that $(l_i, r_i) \in \mathcal{E}$. We denote by

$$ \mathcal{E}_T = \{(l_i, r_i)|i \in \{2, \dots, m\}\} $$

the set of these $m-1$ such edges.

The previous assumption implies that $\mathcal{G}$ contains a spanning tree having the root in $C_1$ (formed by the union of the spanning trees in each cluster together with the edges in $\mathcal{E}_T$). The assumption is satisfied if the induced graph of each cluster is strongly connected and so is $\mathcal{G}$. It also holds if we replace (1b) by the requirement that the graph induced by the set of roots of all clusters contains a spanning tree. We note that Assumption 1 implies that 0 is a simple eigenvalue of each $L_i, \forall i \in \{1, \dots, m\}$ (see [22]). The first part of Assumption 1 has a direct consequence on the continuous dynamics since equation (3) imposes $L_{i,j} < 0$ when $(j, i) \in \mathcal{E}_L$. The second part of Assumption 1 guarantees the existence of the inter-cluster interaction structure formed by $\mathcal{E}_T$.

The next hypothesis of this work is standard in the literature (see [23]) and it ensures a minimal influence of the states implicated in the reset process of the agents.

Assumption 2 (Minimal influence): There exists a constant $\alpha' \in (0, 1)$ such that, for all reset times $t_k$, $P_{i,i}(t_k) \ge \alpha'$ and, if $P_{i,j}(t_k) \ne 0$ and $(i, j) \in \mathcal{E}_T$ then $P_{i,j}(t_k) \ge \alpha'$.

Remark 1: Assumption 2 guarantees a minimal influence of one cluster on the root of some other at the reset time.

We also need to bound the non-zero influence occuring during the continuous dynamics.

Assumption 3 (Bounded continuous influence): The components of the Laplacian matrix $L(t)$ satisfy the following two constraints :

* influence weights are uniformly upper bounded i.e., there exists $\bar{\alpha} > 0$ a finite real number such that $|L_{i,j}(t)| \le \bar{\alpha}, \forall i, j \in \{1, \dots, n\}$ and $t \ge 0$,

* non-zero influence weights are uniformly lower bounded i.e., there exists $\underline{\alpha} > 0$ a finite real number such that $|L_{i,j}(t)| > 0 \Rightarrow |L_{i,j}(t)| \ge \underline{\alpha}, \forall i, j \in \{1, \dots, n\}$.

The first item is necessary to ensure that during the continuous dynamics, the agents do not approach one to another indefinitely fast, oscillations may otherwise prevent consensus to take
place. We can notice that, in practice, this assumption is very natural and is almost always satisfied. The second item makes sure that enough interaction takes place within clusters, as Assumption 2 does for interactions between clusters.

We use an extraction function $\phi_i$ to emphasize that an agent belonging to the cluster $C_i$ resets its state at time $t_k$. This function selects the instants $t_k \in \mathcal{T}$ corresponding to a reset of an agent in cluster $C_i$. Precisely, for any $h \in \mathbb{N}$ we denote by $t_{\phi_i(h)}$ the h-th time an agent in cluster $C_i$ resets its state meaning that

$$ \phi_i(h) = \min\{k > \phi_i(h-1) | \exists j \in C_i, \ell \in \mathcal{V} \setminus C_i, P_{j,\ell}(t_k) > 0\}, $$

where for consistency, we imposed $\phi_i(-1) = -1$ and $t_{\phi_i(-1)} = 0$, for all $i \in \{1, \dots, m\}$. We do not disregard the situation in which agents from different clusters reset their state simultaneously. Therefore, we may have $\phi_i(k) = \phi_j(h)$ for $i \neq j$ and $k, h \in \mathbb{N}$.

While in discrete time, a minimal influence is guaranteed by Assumption 2, in continuous time, a minimal influence can be ensured using a dwell time. This will be shown in Proposition 3 below.

**Assumption 4 (Dwell time):** There exists a positive constant $\delta > 0$ such that

$$ t_{\phi_i(k+1)} - t_{\phi_i(k)} \geq \delta, \forall i \in \{1, \dots, m\}. $$

In other words, there exists a lower bound for the period between the consecutive reset instants on the state of agents belonging to the same cluster. Notice that according to Assumptions 1 and 5 below, all clusters in $\{2, \dots, m\}$ reset an infinite number of times, so that for these clusters, $\phi_i$ is well defined. Cluster $C_1$ may not reset an infinite number of times. In this case, $t_{\phi_1(k)}$ is only defined for $k$ smaller than some finite bound, and should still satisfy Assumption 4 for these $k$. This has no impact on the results of the paper.

**Remark 2:** A simple manner to ensure Assumption 4 in a decentralized way is for each cluster $C_i$, to allow only one agent to interact outside $C_i$. Then, this one agent has full control of $t_{\phi_i(k)}$ and can reset respecting the dwell time condition without the need for further communication. Otherwise, since Assumption 4 concerns the resets of all agents in a cluster (unlike Assumption 5), these agents should have a way to communicate the last reset time which occured in the cluster.

The next assumption establishes the relationship between $\mathcal{E}_T$ and the reset dynamics.
**Assumption 5 (Recurrent activation of inter-cluster links):** There exists a positive constant $\delta_{max} > \delta$ satisfying the following: for all $(l, r) \in \mathcal{E}_T$,

* there exists $k \in \mathbb{N}$ such that $t_k \le \delta_{max}$ and $(l, r) \in \mathcal{E}_P(t_k)$,

* if $(l, r) \in \mathcal{E}_P(t_k)$ there exists $\tau \in [t_k, t_k + \delta_{max}]$ such that $(l, r) \in \mathcal{E}_P(\tau)$.

**Remark 3:** Assumption 5 can be easily imposed in a decentralized way since it concerns inter-cluster links one by one in a decoupled manner. This assumption bears only on the few links in $\mathcal{E}_T$ which connect a node in a parent cluster to a root in a child cluster of the structure defined in Assumption 1. Other links may appear in $\mathcal{E}_P(t_k)$ but these are not constrained by Assumption 5. Notice that Assumption 5 ensures that edges in $\mathcal{E}_T$ reset an infinite number of times. We emphasize that a time-invariant $\delta_{max}$ is only required to ensure convergence with a geometric rate (see Theorem 10). This can be relaxed to time-varying but sufficiently slowly growing $\delta_{max}$ (see Remark 8).

To justify Assumption 5 we provide an example where consensus is not reached when only Assumptions 1-4 hold.

**Example 1:** Consider a 3-agent system where each agent is considered as a cluster, so the continuous dynamics is constant. Initially, $x_1(0) = 1$ and $x_2(0) = x_3(0) = 0$. Recursively define sequence $(\tau_k)_{k \in \mathbb{N}}$ such that $\tau_0 = 0$, and for $k \ge 0$,

$$ \tau_{2k+1} = \tau_{2k} + 2^k + 2, \quad \tau_{2k+2} = \tau_{2k+1} + 2^k + 2. $$

The system undergoes resets for all integer times as follows: first, agent 1 attracts agent 2 at the discrete time instants $h \in \{\tau_{2k}, \dots, \tau_{2k+1} - 2\}$,

$$ P_{2,1}(h) = P_{2,2}(h) = \frac{1}{2}, \qquad (6) $$

and then agent 2 attracts agent 1 during one reset only :

$$ P_{1,2}(\tau_{2k+1} - 1) = P_{1,1}(\tau_{2k+1} - 1) = \frac{1}{2}. $$

Then, agent 3 attracts agent 2 at $h \in \{\tau_{2k+1}, \dots, \tau_{2k+2} - 2\}$,

$$ P_{2,3}(h) = P_{2,2}(h) = \frac{1}{2}, \qquad (7) $$

and then agent 2 attracts agent 3 during one reset only :

$$ P_{3,2}(\tau_{2k+2} - 1) = P_{3,3}(\tau_{2k+2} - 1) = \frac{1}{2}. $$
The interaction weights of matrices $P(h)$, $h \ge 0$ which have not been explicitly defined are equal to 0. Notice that in this example the reset sequence is precisely defined and no uncertainty exist on the activation instant of one specific link. Let us denote by $\delta_{max}(\tau_{2k+1})$ the maximum period between the activations of the same link before the instant $\tau_{2k+2}$. This system corresponds to a maximum inactivation time which grows exponentially fast with $\delta_{max}(\tau_{2k+1}) \ge 2^{k+1}$, due to the inactivation times of links (2, 3) or (2, 1).

Under this configuration, we show that agent 2 oscillates between agents 1 and 3 without agents 1 and 3 ever converging towards each other.

**Proposition 2:** The distance between agents 1 and 3 is lower bounded as follows : for all $k \in \mathbb{N}$,

$$x_1(\tau_{2k+2}) - x_3(\tau_{2k+2}) \ge \left(1 - \frac{1}{2^k}\right) (x_1(\tau_{2k}) - x_3(\tau_{2k})),$$

and

$$\lim_{t \to \infty} (x_1(t) - x_3(t)) > 0.$$

*Proof:* Notice that we clearly have, the following invariant property :

$$\forall t \ge 0, x_1(t) \ge x_2(t) \ge x_3(t).$$

Let $k \in \mathbb{N}$. The dynamics of agents 1 and 2 satisfies

$$x_1(\tau_{2k+2}) = x_1(\tau_{2k+1}) \ge x_2(\tau_{2k+1}) \ge x_2(\tau_{2k+1} - 1),$$

and using equation (6),

$$\begin{aligned} x_2(\tau_{2k+1} - 1) &= \frac{1}{2^{k+1}} x_2(\tau_{2k}) + \left(1 - \frac{1}{2^{k+1}}\right) x_1(\tau_{2k}) \\ &\ge \frac{1}{2^{k+1}} x_3(\tau_{2k}) + \left(1 - \frac{1}{2^{k+1}}\right) x_1(\tau_{2k}). \end{aligned}$$

Combining the two previous equations leads to

$$x_1(\tau_{2k+2}) \ge \frac{1}{2^{k+1}} x_3(\tau_{2k}) + \left(1 - \frac{1}{2^{k+1}}\right) x_1(\tau_{2k}). \quad (8)$$

We now turn to the second part of the dynamics involving interactions between agents 2 and 3.

We have

$$x_3(\tau_{2k+2}) \le x_2(\tau_{2k+2}) \le x_2(\tau_{2k+2} - 1),$$
and using equation (7),

$$
\begin{align*}
x_2(\tau_{2k+2} - 1) &= \frac{1}{2^{k+1}} x_2(\tau_{2k+1}) + \left(1 - \frac{1}{2^{k+1}}\right) x_3(\tau_{2k+1}) \\
&\le \frac{1}{2^{k+1}} x_1(\tau_{2k+1}) + \left(1 - \frac{1}{2^{k+1}}\right) x_3(\tau_{2k}) \\
&= \frac{1}{2^{k+1}} x_1(\tau_{2k}) + \left(1 - \frac{1}{2^{k+1}}\right) x_3(\tau_{2k}).
\end{align*}
$$

The two previous equations yields

$$
x_3(\tau_{2k+2}) \le \frac{1}{2^{k+1}} x_1(\tau_{2k}) + \left(1 - \frac{1}{2^{k+1}}\right) x_3(\tau_{2k}). \quad (9)
$$

Taking the difference between (8) and (9) provides a proof for the first equation of Proposition 2.
Finally, recalling that for a sequence of numbers $\beta_k \in [0, 1]$, $k \in \mathbb{N}$, $\prod_{k=1}^{\infty} (1 - \beta_k) > 0$ if
$\sum_{k=1}^{\infty} \beta_k < \infty$, we have

$$
\prod_{k=1}^{\infty} \left(1 - \frac{1}{2^k}\right) > 0,
$$

so

$$
\lim_{t \to \infty} (x_1(t) - x_3(t)) > 0,
$$

which ends the proof of the Proposition and Example 1.

<figure><img src="image_2.png" /></figure>

Remark 4: Notice that Assumption 5 implies that for all cluster $i \in \{2, \dots, m\}$ and for all $k \in \mathbb{N}$,

$$
t_{\phi_i(k+1)} - t_{\phi_i(k)} \le \delta_{\max}.
$$

Denote by $\Phi(t, T)$ the fundamental matrix over time interval $[t, T]$ of the global linear dynam-
ics $\dot{x}(t) = -L(t)x(t)$, for any $T \ge t \ge 0$, which is uniquely defined [24] by $x(T) = \Phi(t, T)x(t)$.
Denote $\Phi_{C_i}(t, T)$ the fundamental matrix of the linear dynamics $\dot{x}_{C_i}(t) = -L_i(t)x_{C_i}(t)$ within
cluster $C_i$. It is important to mention that dynamics (2) leads to the collective state trajectory

$$
\left\{
\begin{array}{l}
x(t) = \Phi(t_k, t) P(t_k) x(t_k^-), \quad \forall k \in \mathbb{N} \text{ and } \forall t \in [t_k, t_{k+1}) \\
x(0) = x_0
\end{array}
\right.
\qquad (10)
$$

but a jump occurs in $x_{C_i}$ only at times $t_{\phi_i(k)}$, which involves edges with sink in cluster $i$. This
can be formalized as

$$
\left\{
\begin{array}{l}
x_{C_i}(t) = \Phi_{C_i}(t_{\phi_i(k)}, t) P_{C_i}(t_{\phi_i(k)}) x(t_{\phi_i(k)}^{-}), \\
\quad \forall k \in \mathbb{N} \text{ and } \forall t \in [t_{\phi_i(k)}, t_{\phi_i(k+1)}) \\
\\
x(0) = x_0
\end{array}
\right.
\qquad (11)
$$
where $P_{C_i}(t_{\phi_i(k)})$ contains only the rows of $P(t_{\phi_i(k)})$ corresponding to the cluster $C_i$ (i.e. the rows $m_{i-1} + 1, \dots, m_i$ of $P(t_{\phi_i(k)})$).

## B. Matrix prerequisite properties

In this subsection we provide an instrumental result concerning the matrices defining the state-trajectory associated with the dynamics (2). With the graph $\bar{\mathcal{G}} = (\bar{\mathcal{V}}, \bar{\mathcal{E}})$ we associate a time-varying weighted adjacency matrix $A(t)$ which is a matrix with non-negative entries satisfying $A_{i,j}(t) > 0 \Leftrightarrow (i, j) \in \bar{\mathcal{E}}$ for all $t \ge 0$. The corresponding degree matrix $D(t)$ is diagonal and $D_{i,i}(t) = \sum_{j=1}^n A_{i,j}(t)$ where $n$ is the size of $A(t)$ which is equal to the cardinality of $\bar{\mathcal{V}}$. The weighted Laplacian matrix associated with $A(t)$ is simply defined as $\bar{L}(t) = D(t) - A(t)$. Moreover, we suppose that $\bar{L}(t)$ satisfies Assumption 3 which implies the fact that there exist $\bar{\alpha} > 0$ and $\bar{\alpha} > 0$ such that $\bar{\alpha} \le A_{i,j}(t) \le \bar{\alpha}$ for all $(i, j) \in \bar{\mathcal{E}}$ and for all $t \ge 0$. Finally, denote by $\bar{\Phi}(t, T)$ the fundamental matrix over time interval $[t, T]$ of the linear dynamics $\dot{y}(t) = -\bar{L}(t)y(t)$, for any $T \ge t \ge 0$, which is uniquely defined by

$$y(T) = \bar{\Phi}(t, T)y(t).$$

**Proposition 3:** Let $\bar{\mathcal{G}}$ be a directed graph without self loops with $n$ vertices containing a spanning tree and $A(t)$ a weighted adjacency matrix associated with it. Denote $r$ the root of a spanning tree in $\bar{\mathcal{G}}$. Let $D(t)$ and $\bar{L}(t)$ the corresponding degree and weighted Laplacian matrices. Then the fundamental matrix $\bar{\Phi}(t, T)$ is a stochastic matrix. Furthermore, if $\bar{L}$ satisfies Assumption 3, then there holds

$$ \begin{cases} \forall \delta > 0, \forall t \ge 0, \forall T \ge t + \delta, \forall i \in \{1, \dots, n\}, \\ (\bar{\Phi}(t, T))_{i,r} \ge \gamma^n, \\ (\bar{\Phi}(t, T))_{i,i} \ge \gamma^n \end{cases} \tag{12} $$

with

$$ \gamma = (n\bar{\alpha})^{-1}\bar{\alpha}e^{-2\bar{\alpha}\delta}(1 - e^{-\bar{\alpha}\delta}). \tag{13} $$

To prove Proposition 3, we need the following intermediate lemma.

**Lemma 4:** Let $(j, i) \in \bar{\mathcal{E}}$ and $t, t' \ge 0$ such that $t' \ge t$. Then, there holds

$$ \left\{ \begin{array}{l} (\bar{\Phi}(t, t'))_{i,j} \ge \gamma', \\ (\bar{\Phi}(t, t'))_{i,i} \ge \gamma', \end{array} \right. $$
with $\gamma' = (n\bar{\alpha})^{-1}\alpha e^{-2n\bar{\alpha}(t'-t)}(1 - e^{-n\bar{\alpha}(t'-t)})$.

*Proof:* The proof relies on ideas from [25], and is very similar to the first part of the proof of [25, Proposition 7] (although here we prove the lower bound on one element $(\bar{\Phi}(t, t'))_{i,j}$ rather than on a sum of elements, this is possible thanks to Assumption 3). For the first inequality, we set artificial states $y_j(t) = 1$ and $y_k(t) = 0$ for $k \neq j$. We then have

$$(\bar{\Phi}(t, t'))_{i,j} = y_i(t'),$$

as given in [25, equation (15)]. We now show that $y_i(t')$ is lower-bounded by $\gamma'$. Denote $M = \bar{\alpha}(t' - t)$. Using [25, equation (17)], we have

$$y_j(\tau) \geq e^{-nM}, \forall \tau \in [t, t'.] \qquad (14)$$

As a first case, assume that $\forall \tau \in [t, t']$, $y_i(\tau) \leq e^{-nM}$. Then,

$$\begin{aligned} \dot{y}_i(\tau) &= A_{i,j}(\tau)(y_j(\tau) - y_i(\tau)) \\ &\quad + \sum_{k \neq i, j} A_{i,h}(\tau)(y_h(\tau) - y_i(\tau)) \\ &\geq \alpha(e^{-nM} - y_i(\tau)) - (n-2)\bar{\alpha}y_i(\tau) \\ &\geq \alpha e^{-nM} - n\bar{\alpha}y_i(\tau) \\ &\geq -n\bar{\alpha}(y_i(\tau) - (n\bar{\alpha})^{-1}\alpha e^{-nM}), \end{aligned}$$

where we have used $y_h(\tau) \geq 0$ and Assumption 3. It follows then from Gronwall's inequality that

$$\begin{aligned} y_i(t') &\geq (n\bar{\alpha})^{-1}\alpha e^{-nM} + e^{-nM}(y_i(t) - (n\bar{\alpha})^{-1}\alpha e^{-nM}) \\ &\geq (n\bar{\alpha})^{-1}\alpha e^{-n\bar{\alpha}(t'-t)}(1 - e^{-n\bar{\alpha}(t'-t)}) \\ &\geq (n\bar{\alpha})^{-1}\alpha e^{-2n\bar{\alpha}(t'-t)}(1 - e^{-n\bar{\alpha}(t'-t)}). \end{aligned}$$

In the alternative case, denote $\tau$ the first time $y_i(\tau) = e^{-nM}$. Let $s \in [\tau, t']$. Using a similar reasoning as in the first case, since $y_h \geq 0, h \in \mathbb{N}$,

$$\begin{aligned} \dot{y}_i(s) &= \sum_{k \neq i} A_{i,h}(s)(y_h(s) - y_i(s)) \\ &\geq -n\bar{\alpha}y_i(s), \end{aligned}$$
which by integration over time interval $[\tau, t']$ yields

$$y_i(t') \geq e^{-2n\bar{\alpha}(t'-t)} \geq \gamma'$$

We turn to the second inequality. A direct consequence of equation (14) with $j := i$ is that

$$(\bar{\Phi}(t, t'))_{i,i} \geq e^{-n\bar{\alpha}(t'-t)} \geq \gamma'$$

<figure><img src="image_3.png" /></figure>

**Proof of Proposition 3:** The stochasticity of the fundamental matrix $\bar{\Phi}(t, T)$ was proven in [25, Lemma 6]. We first prove the first item of equation (12) when $T = t + \delta$. Let $i \in \{1, \dots, n\}$. Since $r$ is a root of a spanning tree in the graph, $i$ is connected to $r$ by a directed path $(i_0, \dots, i_d)$ with $i_0 = r$ and $i_d = i$. Denote $\tau_h = t + h \frac{\delta}{n}$ for $h \in \{0, \dots, n-1\}$. We have

$$\bar{\Phi}(t, t + \delta) = \prod_{h=n-1}^{0} \bar{\Phi}(\tau_h, \tau_{h+1}),$$

so that

$$\begin{align*}
(\bar{\Phi}(t, t + \delta))_{i,r} & \\
&\geq \prod_{h=n-1}^{d} (\bar{\Phi}(\tau_h, \tau_{h+1}))_{i,i} \prod_{h=d-1}^{0} (\bar{\Phi}(\tau_h, \tau_{h+1}))_{i_{h+1}, i_h} \\
&\geq \gamma^n,
\end{align*}$$

where we used both the first and second inequalities in Lemma 4.

Then, we have

$$\begin{align*}
(\bar{\Phi}(t, T))_{i,r} &= \sum_{k=1}^{n} (\bar{\Phi}(t + \delta, T))_{i,k} (\bar{\Phi}(t, t + \delta))_{k,r} \\
&\geq \sum_{k=1}^{n} (\bar{\Phi}(t + \delta, T))_{i,k} \gamma^n \geq \gamma^n,
\end{align*}$$

where we have used the stochasticity of $\bar{\Phi}(t + \delta, T)$ for the last inequality.

The fact that the second item of equation (12) holds can be shown similarly using the second inequality of Lemma 4 applied $n$ times. ■

**Remark 5:** Notice that (see (11)) the matrix $\Phi_{C_i}(t_{\phi_i(k)}, t)$ defines the state trajectory of the cluster $C_i$ between two reset instants. Moreover, the graph associated with any cluster satisfies the hypothesis of Proposition 3 and the time interval between consecutive reset instants is bounded.
Thus, Proposition 3 shows that Assumption 4 (Dwell time) is the corresponding of Assumption 2 (Minimal influence) for the continuous dynamics defined by $L_i$.

Remark 6: We can apply Proposition 3 to the continuous dynamics in each cluster defined in section II. For given $\delta$ and $\delta_{max} > \delta$, Proposition 3 states that for all $i \in \{1, \dots, m\}$ $\Phi_{C_i}(t_{\phi_i(k)}, t)$ satisfies (12) for all $t \in [\delta, \delta_{max}]$. As a consequence, we can define a lower bound on both the impulsive attraction strengths and the attraction strengths resulting from the continuous dynamics as

$$ \alpha = \min(\alpha', \gamma^n), $$

where $\alpha'$ is defined in Assumption 2 and $\gamma$ is defined in equation (13).

## IV. CONVERGENCE ANALYSIS

This part contains the main results of the paper concerning fully decentralized reset rules. The resets of clusters are not synchronized and the intervals $(t_{\phi_i(k)}, t_{\phi_i(k+1)})$ and $(t_{\phi_j(h)}, t_{\phi_j(h+1)})$ may overlap for distinct $i$ and $j$. This means, $t_{k+1} - t_k$ can be arbitrarily small and the existing results in the literature are not applicable. Assumption 4 (Dwell time) only ensures a dwell time on the resets of the same cluster. In this section, we assume that Assumptions 1-4, are satisfied. Under such assumptions, we will show that all agents eventually converge toward the same consensus state at exponential speed (Theorem 10). Prior to stating the main result we provide the necessary intermediate ingredients.

For all time $t \in \mathbb{R}_+$, we define the global diameter of the group as

$$ \Delta(t) = \bar{x}(t) - \underline{x}(t) $$

with

$$ \bar{x}(t) = \max_{i \in \{1, \dots, n\}} x_i(t) \text{ and } \underline{x}(t) = \min_{i \in \{1, \dots, n\}} x_i(t). $$

Our goal in the sequel is to show that $\Delta(t)$ approaches 0 when $t$ increases. This requires some intermediate results presented as lemmas in the sequel. All of them are written in terms of minimum $\underline{x}(t)$ but they can be easily transformed in terms of maximum $\bar{x}(t)$.

## Summary

* In Lemma 5 we prove that: if an agent resets its state by taking into account a state bigger than $\underline{x}(t)$, then its state after reset will be bigger than $\underline{x}(t)$.
* In Lemma 6 we complement Lemma 5 by proving that, if all the states in the cluster $C_i$ are bigger than $\underline{x}(t)$ at some time, they will remain bigger than $\underline{x}(t)$ after a finite number of resets.

* In Lemma 7 we prove that during the continuous dynamics the root of a cluster will pull all the states of the corresponding cluster far from the minimum value. Before the next reset concerning this cluster, all its agents are at a strictly positive distance from the minimum $\underline{x}(t)$.

* In Lemma 8 we show that, the distances between the agents of an arbitrarily fixed cluster $C_w$ and $\underline{x}(t)$ are uniformly lower bounded by a strictly positive value. This is done by induction on a sequence of clusters going from $C_1$ to $C_w$ chosen along the spanning tree in $G$ (see Assumption 1). Combining Lemma 5 and Lemma 7 provides the induction step.

* Finally, in Theorem 10 we use the lemmas to prove the geometric decrease of the diameter $\Delta(t)$.

**Lemma 5 (Reset):** Let $i \in \{1, \dots, m\}$ and $t \ge 0$ fixed. Let $k \in \mathbb{N}$ such that $t_{\phi_i(k)} > t$ the first reset instant of cluster $i$ after $t$. Assume that there are some $\ell \in \mathcal{V}$, some bound $X \in \mathbb{R}_+$, some $j \in C_i$ and some bound $\alpha \in (0, 1)$ such that

$$x_{\ell}(t_{\phi_i(k)}^{-}) - \underline{x}(t) \ge X \text{ and } P_{j,\ell}(t_{\phi_i(k)}) \ge \alpha.$$

Then, we have

$$x_j(t_{\phi_i(k)}) - \underline{x}(t) \ge \alpha X.$$

*Proof:* Using the stochasticity of $P(t_k)$, one obtains $1 = \sum_{h \in \mathcal{V}, h \neq \ell} P_{j,h}(t_{\phi_i(k)}) + P_{j,\ell}(t_{\phi_i(k)})$, thus, by equation (2),

$$x_j(t_{\phi_i(k)}) - \underline{x}(t) = \sum_{h \in \mathcal{V}, h \neq \ell} P_{j,h}(t_{\phi_i(k)})(x_h(t_{\phi_i(k)}^{-}) - \underline{x}(t)) + P_{j,\ell}(t_{\phi_i(k)})(x_{\ell}(t_{\phi_i(k)}^{-}) - \underline{x}(t)) \ge \alpha X.$$

The last inequality follows from the fact that $P(t_{\phi_i(k)}) \ge \mathbf{0}_{n \times n}$, $P_{j,\ell}(t_{\phi_i(k)}) \ge \alpha$ and $x_h(t_{\phi_i(k)}^{-}) \ge \underline{x}(t)$ since $\underline{x}$ is non-decreasing (i.e. $\underline{x}(t) \le \underline{x}(t_{\phi_i(k)}^{-})$).

Considering $\bar{x}_{C_i}(t) = \max_{j \in C_i} x_j(t)$, $\underline{x}_{C_i}(t) = \min_{j \in C_i} x_j(t)$, the previous lemma can be complemented as follows.
**Lemma 6 (Reset):** Let $i \in \{1, \dots, m\}$ and $t \ge 0$ fixed. Let $t_{\phi_i(k)} > t$ be some reset instant. Assume that there is some bound $X \in \mathbb{R}_+$, such that

$$ \underline{x}_{C_i}(t_{\phi_i(k)}^{-}) - \underline{x}(t) \geq X. $$

Then, for all $h \in \mathbb{N}$, for all $\tau \in [t_{\phi_i(k)}^{-}, t_{\phi_i(k+h)}^{-}]$,

$$ \underline{x}_{C_i}(\tau) - \underline{x}(t) \geq \alpha^{h+1} X. $$

*Proof:* Using Assumption 2 (Minimal influence) and equation (4), we have $P_{j,j}(t_{\phi_i(k+h)}) \ge \alpha$ for all $h \in \mathbb{N}$ and $j \in C_i$. Thus we can apply Lemma 5 with $l := j$ for all $j \in C_i$. Also, $\underline{x}_{C_i}$ is non-decreasing between two consecutive reset instants, thus the bound from Lemma 5 is preserved until the next reset of the cluster. This allows us to iterate on $h$ to conclude. ■

**Lemma 7 (Continuous dynamics):** Let $i \in \{1, \dots, m\}$ and $t \ge 0$ fixed. Let $k \in \mathbb{N}$ such that $t_{\phi_i(k)} > t$ and denote for conciseness the matrix $R = \Phi_{C_i}(t_{\phi_i(k)}, t_{\phi_i(k+1)})$. Assume that for the root $r_i$ of one spanning tree of the cluster $C_i$, there exist some bounds $Y \in \mathbb{R}_+$ and $\alpha \in [0, 1]$ such that

$$ x_{r_i}(t_{\phi_i(k)}) - \underline{x}(t) \geq Y \text{ and } \forall j \in C_i, R_{j,r_i} \geq \alpha. $$

Then, we have

$$ \underline{x}_{C_i}(t_{\phi_i(k+1)}^{-}) - \underline{x}(t) \geq \alpha Y. $$

*Proof:* Since $x_{C_i}(t_{\phi_i(k+1)}^{-}) = Rx_{C_i}(t_{\phi_i(k)})$ with $R$ stochastic, the proof is the same as the one in Lemma 5. The difference is that $\forall j \in C_i, R_{j,r_i} \ge \alpha$. The proof can be applied for all $j \in C_i$ and a minimum can be taken at the end. ■

Before giving the next result, let us introduce some notation that will simplify the presentation. Let $C_w$ be some cluster. According to Assumption 1, there is a sequence of clusters $(K_1, \dots, K_q)$ with $q \le m$ connecting $C_w$ to $C_1$, meaning that $K_1 = C_1, K_q = C_w$ and for each intermediate cluster $h \in \{1, \dots, q-1\}$, there is a node $l \in K_h$ and a root $r$ of a spanning tree of $K_{h+1}$ with $(l, r) \in \mathcal{E}_T$.

Let $t \ge 0$ be fixed. We define a sequence of integers

$$ t \le f_1 < s_1 < f_2 < s_2 < \dots < f_q < s_q \qquad (15) $$

such that
* $f_1$ is the first reset instant after $t$ of a root of a spanning tree of cluster $K_1$, if a root reseting its state exists in $K_1$. This may not be the case since $K_1$ may not be influenced by the other clusters (according to Assumption 1), then $f_1 = t$ and $s_1 = t + \delta$.

* For all $h \in \{2, \dots, q\}$, we define $s_h$ the first instant after $f_h$ when an agent of $K_h$ resets its state.

* For all $h \in \{1, \dots, q-1\}$ we define $f_{h+1}$ as the first reset instant of a root of a spanning tree of cluster $K_{h+1}$ after time $s_h$.

It is noteworthy that, thanks to Assumption 5,

$$f_{h+1} - s_h \le \delta_{max} \quad \text{and} \quad s_h - f_h \le \delta_{max}. \qquad (16)$$

This also gives

$$s_q - f_1 \le (2q - 1)\delta_{max} \le (2m - 1)\delta_{max}. \qquad (17)$$

Let also introduce

$$\mu = \lfloor \delta_{max} / \delta \rfloor \qquad (18)$$

where $\lfloor y \rfloor$ denotes the biggest integer smaller than $y$.

**Remark 7:** Due to Assumptions 5 (Maximum inactivation time) and 4 (Dwell time), we have at most $\mu$ resets of a root of cluster $K_h$ between $s_h$ and $f_{h+1}$.

In the sequel, iteratively applying Lemmas 5 and 7, we will show in Theorem 10 that $\Delta(s_q)$ geometrically decreases. For the next result we assume that a root $r_1$ of a spanning tree of $K_1 = C_1$ satisfies

$$x_{r_1}(f_1) - \underline{x}(f_1^-) \ge \Delta(f_1^-) / 2.$$

If it is not the case, we instead consider the system where all the states have been reversed: $x_i := -x_i$ and apply the same reasoning. In other words we relate the reasoning to the maximum instead of the minimum. In the sequel, we use $\underline{x}_{K_h}(t) = \min_{i \in K_h} x_i(t)$.

**Lemma 8 (Path of clusters):** For all $h \in \{1, \dots, q\}$, we have

$$\underline{x}_{K_h}(s_h^-) - \underline{x}(f_1^-) \ge \frac{\alpha^{(\mu+3)(h-1)+1} \Delta(f_1^-)}{2}. \qquad (19)$$

where $\mu$ is given in equation (18).
*Proof:* We show the lemma by induction. Due to Assumptions 4 (Dwell time) and 5 (Maximum inactivation time), one has $\delta_{max} \ge s_1 - f_1 \ge \delta$, so that Proposition 3 applies to $R = \Phi_{C_{i_1}}(f_1, s_1)$. The value $\alpha$ is chosen as in Remark 6. As a consequence we can apply previous lemmas with the same $\alpha$. Lemma 7 yields

$$ \underline{x}_{K_1}(s_1^-) - \underline{x}(f_1^-) \ge \frac{\alpha \Delta(f_1^-)}{2}, $$

which shows equation (19) for $h = 1$. Assume the proposition is true for some $h \in \{1, \dots, p\}$ where $p \le q-1$ and we prove the same for $h = p+1$. As mentioned in Remark 7, there will be at most $\mu$ resets of cluster $K_p$ over $(s_p, f_{p+1})$. Thus, denoting $\ell$ such that $t_{\phi_p(\ell)} = s_p$, we have $f_{p+1} \le t_{\phi_p(\ell+\mu)}$. We can apply Lemma 6 so that

$$ \underline{x}_{K_p}(f_{p+1}) - \underline{x}(f_1^-) \ge \alpha^{\mu+1} \cdot \frac{\alpha^{(\mu+3)(p-1)+1} \Delta(f_1^-)}{2}. $$

At time $f_{p+1}$, cluster $K_{p+1}$ resets. A root $r_{p+1}$ of $K_{p+1}$ receives influence from at least one agent $j$ in cluster $K_p$. Because of Assumption 2, $P_{r_{p+1},j}(f_{p+1}) \ge \alpha$. So, we apply Lemma 5 on $K_{p+1}$ to get

$$ x_{r_{p+1}}(f_{p+1}) - \underline{x}(f_1^-) \ge \alpha^{\mu+2} \cdot \frac{\alpha^{(\mu+3)(p-1)+1} \Delta(f_1^-)}{2}. $$

To conclude, we apply Lemma 7 on $C_{p+1}$ with $R = \text{Phi}_{C_{p+1}}(f_{p+1}, s_{p+1})$ and we get

$$ \underline{x}_{K_{p+1}}(s_{p+1}^-) - \underline{x}(f_1^-) \ge \frac{\alpha^{(\mu+3)p+1} \Delta(f_1^-)}{2}. $$

<figure><img src="image_4.png" /></figure>

A corollary of Lemma 8 is the following proposition.

*Proposition 9:* We have

$$ \underline{x}((2m-1)\delta_{max} + f_1) - \underline{x}(f_1^-) \ge \alpha^{\nu+1} \frac{\alpha^{(\mu+3)(m-1)+1} \Delta(f_1^-)}{2} \quad (20) $$

with $\nu = \lfloor (2m-1)\delta_{max}/\delta \rfloor$.

*Proof:* Taking $h = q$ in Lemma 8 gives a lower bound on the minimum of $C_w = K_q$. This is true for any cluster $C_w$. Using $h \le m$ in equation (19), the bound can be replaced by

$$ \frac{\alpha^{(\mu+3)(m-1)+1} \Delta(f_1^-)}{2}. $$
Then, equation (17) guarantees that there is no more than $\nu$ resets of cluster $C_w$ over $[f_1^-, (2m-1)\delta_{max} + f_1^-]$, thus Lemma 6 gives that for all cluster $C_w$,

$$ \underline{x}_{C_w}((2m-1)\delta_{max} + f_1) - \underline{x}(f_1^-) \\ \geq \alpha^{\nu+1} \frac{\alpha^{(\mu+3)(m-1)+1}\Delta(f_1^-)}{2}. $$

In other words, equation (20) holds.

<figure><img src="image_5.png" /></figure>

Once Proposition 9 is given, the exponential decay of the network diameter comes easily.

**Theorem 10:** Denote $\nu = \lfloor(2m-1)\delta_{max}/\delta\rfloor$ and $\mu = \lfloor\delta_{max}/\delta\rfloor$ and let us define $\beta = (1 - \alpha^{\nu+1}\frac{\alpha^{(\mu+3)(m-1)+1}}{2}) \in [0, 1)$ with $\alpha = \min(\gamma^n, \alpha)$ where $\alpha'$ is defined in Assumption 2 and $\gamma$ is defined in equation (13). Then, for all $t \in \mathbb{R}_+$,

$$ \Delta(2(m+1)\delta_{max} + t) \leq \beta\Delta(t). $$

**Remark 8:** From the definition of $\beta$ in Theorem 10 one can see that, considering a time-varying $\delta_{max}$ leads to a time-varying $\beta$. The consensus is still guaranteed as far as $\delta_{max}$ is not growing too fast i.e. for all $t \in \mathbb{R}_+$ one has

$$ \lim_{k \to \infty} \prod_{i=1}^{k} \beta(t + 2(m+1) \sum_{j=1}^{i} \delta_{max}^{i}) = 0, \quad (21) $$

where $(\delta_{max}^i)_{i \geq 1}$ denotes the sequence of upper bounds of the time intervals between consecutive activations of inter-clusters links. When $\delta_{max}$ grows sufficiently fast to make the limit in (21) strictly positive, the consensus is no longer guaranteed as proven in Example 1.

*Proof:* Let $t \geq 0$ be fixed and define $f_1$ as in (15). It follows that

$$ t \leq f_1 < f_1 + (2m - 1)\delta_{max} \leq t + 2(m + 1)\delta_{max}. $$

Since $\bar{x}$ is non-increasing and $\underline{x}$ is non-decreasing, one has

$$ \begin{aligned} \Delta(t + 2(m + 1)\delta_{max}) &\leq \Delta((2m - 1)\delta_{max} + f_1), \\ \Delta(f_1^-) &\leq \Delta(t). \end{aligned} \quad (22) $$

On the other hand, using Proposition 9, we have

$$ \begin{aligned} \Delta((2m - 1)\delta_{max} + f_1) &= \\ &= \bar{x}((2m - 1)\delta_{max} + f_1) - \underline{x}((2m - 1)\delta_{max} + f_1) \\ &\leq \bar{x}(f_1^-) - \underline{x}(f_1^-) - \alpha^{\nu+1} \frac{\alpha^{(\mu+3)(m-1)+1}\Delta(f_1^-)}{2} \\ &\leq (1 - \alpha^{\nu+1} \frac{\alpha^{(\mu+3)(m-1)+1}}{2})\Delta(f_1^-). \end{aligned} $$
The proof ends by combining this with (22).

■

## V. EVENT TRIGGERED RESET RULE

The dynamics (2) can be used for consensus in fleets of robots that are partitioned in clusters. The robots that are relatively close one to another continuously interact and form a cluster. Inter-cluster interactions need supplementary energy associated to long distance communications between clusters and consequently, they have to be activated only if needed. In order to avoid unnecessary inter-cluster communications we can define the reset sequence using an event-based strategy. One example of such strategy is analyzed in this section. Precisely, we consider the asynchronous resets case and suppose Assumptions 1 (Network structure) and 2 (Minimal influence) are satisfied. We will show that under the event triggered reset rule, Assumption 4 and 5 are satisfied so that Theorem 10 applies and the consensus occurs.

*Definition 11:* The diameter of the cluster $C_i$ is defined as $\Delta_i(t) = \bar{x}_{C_i}(t) - \underline{x}_{C_i}(t)$. The reset sequence $(t_k)_{k \in \mathbb{N}}$ associated with the dynamics (2) is defined as follows: for all $i \in \{1, \dots, m\}$ and for all $k \ge 0$,

* if $\Delta_i(t_{\phi_i(k-1)}) = 0$, $t_{\phi_i(k)} = t_{\phi_i(k-1)} + \delta$ with $\delta = \min_{i \in \{1, \dots, m\}} \frac{1}{2n_i\alpha} \ln(a_i)$,

* otherwise $t_{\phi_i(k)} = \min_{t \ge t_{\phi_i(k-1)}} \left\{ \Delta_i(t) \le \frac{\Delta_i(t_{\phi_i(k-1)})}{a_i} \right\}$,

where the $a_i > 1$ are design parameters fixed a priori. (We recall that for consistency, we denote $t_{\phi_i(-1)} = 0$).

Notice that the first point of the definition is required to avoid zeno-type behavior. The objective of this section is to prove that the reset sequence defined above satisfies Assumptions 5 (Recurrent activation of inter-cluster links) and 4 (Dwell time). Once this objective is accomplished, we can apply the results stated in Section IV to ensure the coordination of all agents in the network.

**Remark 9:**

1) It is noteworthy that the reset rule is centralized at the cluster level. In other words, in each cluster exists a central entity that is able to compute the diameter of the cluster and transmit it continuously to the resetting agents. The resets of the agents belonging to the same cluster are synchronized. For the sake of simplicity, in the following, we assume that each cluster possesses only one agent (a root of a spanning tree of the graph representing the cluster) that resets its state and this agent can continuously compute the diameter of the cluster.
2) The parameters $a_i > 1, i \in \{1, \dots, m\}$ in Definition 11 can be chosen all equal but they can be also designed as functions of the decreasing speed of $\Delta_i$. The later requires supplementary knowledge but it can be used, if needed, to homogenize the reset intervals from one cluster to another. We do not focus on this issue and in our numerical illustrations: we consider $a_i = 2, \forall i \in \{1, \dots, m\}$.

**Theorem 12:** Let us consider the dynamics (2) under Assumptions 1 (Network structure), 2 (Minimal influence) and 3 (Maximal influence). Then, the associated reset sequence introduced in Definition 11 satisfies the Assumptions 5 (Recurrent activation of inter-cluster links) and 4 (Dwell time).

*Proof:*

* We start by proving that Assumption 4 holds. If $\Delta_i(t_{\phi_i(k)}) = 0$, the first point in Definition 11 applies and Assumption 4 holds. Otherwise, the second point applies and for a fixed cluster $C_i$, $i \in \{1, \dots, m\}$ we have to show that $\Delta_i$ does not decrease infinitely fast. This means, a dwell time $\delta$ exists between a reset time $t_{\phi_i(k)}$ and the first time $t$ such that when $\Delta_i(t) \le \frac{\Delta_i(t_{\phi_i(k)})}{a_i}$.

Let $t \in (t_{\phi_i(k)}, t_{\phi_i(k+1)})$. First, recall that (see [7]) for almost all $t \ge 0$, there exist $m_i(t) \in \text{argmin}_{j \in C_i}(x_j(t))$ and $M_i(t) \in \text{argmax}_{j \in C_i}(x_j(t))$ such that:

$$ \dot{x}_{C_i}(t) = \dot{x}_{m_i(t)}(t) = - \sum_{j \in C_i} L_{m_i(t),j}(x_j(t) - x_{m_i(t)}), $$

$$ \dot{x}_{C_i}(t) = \dot{x}_{M_i(t)}(t) = - \sum_{j \in C_i} L_{M_i(t),j}(x_j(t) - x_{M_i(t)}). $$

Thus, using Assumption 3, one obtains that between two reset instants the following holds:

$$ \dot{x}_{C_i}(t) \le n_i \bar{\alpha} \Delta_i(t), \quad \dot{x}_{C_i}(t) \ge -n_i \bar{\alpha} \Delta_i(t), $$

yielding

$$ \dot{\Delta}_i(t) \ge -2n_i \bar{\alpha} \Delta_i(t). $$

In other words, one has

$$ \Delta_i(t) \ge e^{-2n_i \bar{\alpha}(t-t_{\phi_i(k)})} \Delta_i(t_{\phi_i(k)}). $$

Thus, since $\Delta_i(t_{\phi_i(k)}) > 0$, $\Delta_i(t) \le \frac{\Delta_i(t_{\phi_i(k)})}{a_i}$ implies $2n_i \bar{\alpha}(t - t_{\phi_i(k)}) \ge \ln(a_i)$ that is equivalent to

$$ t - t_{\phi_i(k)} \ge \frac{1}{2n_i \bar{\alpha}} \ln(a_i) $$
and Assumptions 4 holds for

$$ \delta = \min_{i \in \{1, \dots, m\}} \frac{1}{2n_i \bar{\alpha}} \ln(a_i). $$

• Now, let us prove that Assumption 5 holds. Since we consider only one agent per cluster can reset its state, this is equivalent to the existence of $\delta_{max} > 0$ finite, such that for all $\forall k \ge 0$, for all $i \in \{1, \dots, m\}$ one has $t_{\phi_i(k)} - t_{\phi_i(k-1)} \le \delta_{max}$.

Let $t \in (t_{\phi_i(k-1)}, t_{\phi_i(k)})$. Let us recall that $n_i$ represents the cardinality of $C_i$. Let us also introduce $\rho_i > 0$ a bound on the convergence speed in the cluster $C_i$ over an interval where $C_i$ does not reset. Mainly we consider an overestimation of the second Lyapunov exponent of the continuous dynamics describing the behavior of $C_i$ (see [1], [2], [26]), yielding

$$ \|x_{C_i}(t) - x_i^*(t_{\phi_i(k-1)})\|_2 \le e^{-\rho_i(t-t_{\phi_i(k-1)})} \|x_{C_i}(t_{\phi_i(k-1)}) - x_i^*(t_{\phi_i(k-1)})\|_2 \quad (23) $$

where we denote

$$ x_i^*(t_{\phi_i(k-1)}) = \lim_{t \to \infty} \Phi_{C_i}(t_{\phi_i(k-1)}, t) x_{C_i}(t_{\phi_i(k-1)}) $$

the agreement of the cluster $C_i$ if no reset occurs in its state after the instant $t_{\phi_i(k-1)}$.

One can prove that

$$ \begin{aligned} \Delta_i(t) &\le \|x_{C_i}(t) - x_i^*(t_{\phi_i(k-1)})\|_1 \\ &\le \sqrt{n_i} \|x_{C_i}(t) - x_i^*(t_{\phi_i(k-1)})\|_2 \end{aligned} $$

and

$$ \begin{aligned} \sqrt{n_i} \Delta_i(t_{\phi_i(k-1)}) &\ge \|x_{C_i}(t_{\phi_i(k-1)}) - x_i^*(t_{\phi_i(k-1)})\|_1 \\ &\ge \|x_{C_i}(t_{\phi_i(k-1)}) - x_i^*(t_{\phi_i(k-1)})\|_2, \end{aligned} $$

where we successively used the triangle inequality, the 1-2 norm inequality, the fact that, since $\Phi_{C_i}(t_{\phi_i(k-1)}, t)$ is stochastic, $x_i^*(t_{\phi_i(k-1)})$ remains in the convex hull of $\{x_j(t_{\phi_i(k-1)})|j \in C_i\}$, and once again, the 1-2 norm inequality. Combining the two previous inequalities with equation (23), gives

$$ \Delta_i(t) \le e^{-\rho_i(t-t_{\phi_i(k-1)})} n_i \Delta_i(t_{\phi_i(k-1)}), $$

so that taking $t \ge t_{\phi_i(k-1)} + \ln(a_i n_i)/\rho_i$ leads to $\Delta_i(t) \le \Delta_i(t_{\phi_i(k-1)})/a_i$. As a conclusion,

$$ \delta_{max} = \max_{i \in \{1, \dots, m\}} \frac{\ln(a_i n_i)}{\rho_i} $$
is a suitable upper bound on the duration between two resets.

The following result is a straightforward consequence of Theorem 10. We only need to observe that Theorem 12 provides the assumptions required for the application of Theorem 10.

*Corollary 1:* Let us consider the dynamics (2) with the reset rule introduced in Definition 11. If Assumptions 1 (Network structure), 2 (Maximal influence) and 3 (Minimal influence) hold, there exists some positive decay rate $\beta \in [0, 1)$ such that for all $t \in \mathbb{R}_+$,

$$ \Delta(2m\delta_{max} + t) \leq \beta\Delta(t). $$

## VI. STOCHASTIC RESET RULE

In some settings, the resets of agent states are the result of uncertain events. In this case, we model the sequences of resets as a stochastic process. In the present section, we show that even under uncertainty, suitable conditions on the probability law governing the sequence of resets lead to consensus with probability one. To prove this fact, we need to show that, at any time, the diameter decay provided in Theorem 10 occurs with positive probability. Throughout this section we denote $\mathbb{P}(X)$ the probability of the event $X$ and $\mathbb{P}(X | Y)$ the probability of $X$ conditioned by $Y$.

*Theorem 13:* Consider dynamics (2). Suppose that Assumptions 1 (Network structure) and 2 (Minimal influence) are satisfied. Also, suppose that no more than one agent in each cluster $C_i$ resets its state and this agent is the one described as $r_i$ in Assumption 1. Finally, assume that these sequences of resets follow independent Poisson renewal processes. Then, there exists some positive decay rate $\beta \in [0, 1)$ and some positive constant bound $p > 0$ such that for all $t \in \mathbb{R}_+$,

$$ \mathbb{P}(\Delta(2m\delta_{max} + t) \leq \beta\Delta(t)) \geq p. $$

Moreover, consensus occurs with probability one.

In what follows, we suppose that the assumptions required in Theorem 13 are satisfied. The Poisson renewal processes implies that the increments between two consecutive reset instants are independent and stationary. Theorem 13 is a consequence of the following lemma and Theorem 10:

*Lemma 14:* Let $\delta_{max} > \delta > 0$. Then, for all $t$ arbitrarily fixed in $\mathbb{R}_+$, Assumptions 5 (Recurrent activation of inter-cluster links) and 4 (Dwell time) hold for all the reset instants belonging to $[t, t + 2m\delta_{max}]$ with a certain strictly positive probability (independent of $t$).
Proof of Theorem 13: Using Lemma 14, we know that Assumptions 5 and 4 hold for all the reset instants belonging to $[t, t + 2m\delta_{max}]$ with some probability $p$, for all $t \in \mathbb{R}_+$. Thus we can apply Theorem 10 restricted to the interval $[t, t + 2m\delta_{max}]$ to obtain that there exists some positive decay rate $\beta \in [0, 1)$, independent of $t$, such that for all $t \in \mathbb{R}_+$,

$$ \mathbb{P}(\Delta(2m\delta_{max} + t) \le \beta\Delta(t)) \ge p. $$

So, using the fact that $\Delta$ is non-increasing, we can bound the expectation of $\Delta$:

$$ \mathbb{E}(\Delta(2m\delta_{max} + t)|\Delta(t)) \le p\beta\Delta(t) + (1-p)\Delta(t), $$

and then,

$$ \mathbb{E}(\Delta(2m\delta_{max} + t)) \le (1 - (1 - \beta)p)\mathbb{E}(\Delta(t)), $$

which shows that $\mathbb{E}(\Delta)$ exponentially converges to 0. Moreover, since $\Delta$ is almost surely non-increasing and non-negative, it converges almost surely. Denote $l$ its limit which is also non-negative. By continuity of $\mathbb{E}$ one has $\lim_{t \to \infty} \mathbb{E}(\Delta) = \mathbb{E}(l)$. Thus, $\mathbb{E}(l) = 0$ and since $l$ is non-negative, we get $l = 0$. Concluding, consensus occurs with probability one. ■

There remains to prove Lemma 14. Notice that, since only one agent per cluster resets its state, Assumption 5 reduces to

$$ t_{\phi_i(k)} - t_{\phi_i(k-1)} \le \delta_{max}, \forall i \in \{2, \dots, m\}, \forall k \in \mathbb{N}, $$

so the conjunction of Assumption 5 and Assumption 4 is equivalent to

$$ t_{\phi_i(k)} - t_{\phi_i(k-1)} \in [\delta, \delta_{max}], \forall i \in \{2, \dots, m\}, \forall k \in \mathbb{N}. \quad (24) $$

We highlight that the reset instants of one cluster are independent of the ones related to other clusters. So, the probability of statement (24) is the product of the probabilities for each cluster. Thus, we can decouple the analysis of reset sequences concerning different clusters. Before proving Lemma 14, we describe some necessary probabilistic notation and an intermediate result. The occurrence of the reset $t_{\phi_i(k)}$ for $k \ge 0$ is described by the random variable $T_{\phi_i(k)}$ and the duration between $T_{\phi_i(k-1)}$ and $T_{\phi_i(k)}$ is given by the random variable $S_{\phi_i(k)}$. Using these notations, the Poisson renewal process corresponds to the case where the reset instants occurs randomly in time and $N_t$ is the number of reset occurrences in $[0, t]$ ($N_t$ depends on the cluster index $i$ but for simplicity of notation we do not display it explicitly):

$$ N_t = \sum_{k=0}^{\infty} \chi_{(T_{\phi_i(k)} \le t)}, $$
where $\chi_{\Omega}$ denote the indicator function of the set $\Omega$. In other words,

$$ \left\{ \begin{array}{l} T_{\phi_i(k-1)} \le t \quad \Leftrightarrow \quad N_t \ge k, \\ T_{\phi_i(k-1)} > t \quad \Leftrightarrow \quad N_t < k. \end{array} \right. \qquad (25) $$

We recall here some important properties of the Poisson renewal process (see for instance [27]).

**Remark 10:** The process $N_t$ has independent and stationary increments:

* for all $0 \le t_0 < t_1 < \dots < t_n$ the random variables $N_{t_1} - N_{t_0}, \dots, N_{t_n} - N_{t_{n-1}}$ are independent,

* for all $t, s \in \mathbb{R}_+$, $N_{t+s} - N_t$ and $N_t$ follow the same distribution: a Poisson distribution with parameter $\lambda_i s$.

Moreover, the $S_{\phi_i(k)}$, $k \ge 0$ are independent and identically distributed (i.i.d.) following an exponential distribution with parameter $\lambda_i > 0$. In particular, for any $b_1 < b_2 \in \mathbb{R}_+$ one has $\mathbb{P}(S_{\phi_i(k)} \in [b_1, b_2]) > 0$.

The next lemma is instrumental since it allows us to reduce the analysis to the interval $[0, 2m\delta_{max}]$. Precisely, we show that the sequence of reset instants higher than $t$ is described by the same probability distribution as the sequence of resets that starts at 0. Let $i$ be some cluster index and $\Lambda$ denote the event $\{N_t = k, N_{t+\xi} = k + \ell\}$

**Lemma 15:** Let $t, \xi$ be arbitrarily fixed in $\mathbb{R}_+$. Then for all $k, \ell \in \mathbb{N}$, the distributions of $(T_{\phi_i(0)}, \dots, T_{\phi_i(\ell-1)}) | \{N_{\xi} = \ell\}$ and $(T_{\phi_i(k)} - t, \dots, T_{\phi_i(k+\ell-1)} - t) | \Lambda$ are equal.

**Proof:** First, it is a well known fact that given $N_{\xi} = \ell$, the $\ell$ arrival times $(T_{\phi_i(0)}, \dots, T_{\phi_i(\ell-1)})$ are distributed as the order statistics corresponding to $\ell$ independent random variables uniformly distributed on the interval $[0, \xi]$ (see for instance [27]). The density is then given by: $f(x_0, \dots, x_{\ell-1}|\ell) = \frac{\ell!}{\xi^\ell} \chi(0<x_0<\dots<x_{\ell-1}<\xi)$.

Secondly, let the following real terms $t < x_k \le x_k + h_k < x_{k+1} \le x_{k+1} + h_{k+1} < \dots < x_{k+\ell-1} \le x_{k+\ell-1} + h_{k+\ell-1} \le t + \xi$. The two followings events:

$$ \Gamma = \{ N_t = k, N_{t+\xi} = k + \ell - 1, T_{\phi_i(k)} \in [x_k, x_k + h_k], \dots, T_{\phi_i(k+\ell-1)} \in [x_{k+\ell-1}, x_{k+\ell-1} + h_{k+\ell-1}] \} \text{ and} $$

$$ \{ N_t = k, N_{x_k} - N_t = 0, N_{x_k + h_k} - N_{x_k} = 1, \dots, N_{x_{k+\ell-1} + h_{k+\ell-1}} - N_{x_{k+\ell-1}} = 1, N_{t+\xi} - N_{x_{k+\ell-1} + h_{k+\ell-1}} = 0 \} \text{ are equal.} $$
Then, by using the Remark 10, we have:

$$ 
\begin{aligned}
\mathbb{P}(\Gamma) &= e^{-\lambda_i t} \frac{(\lambda_i t)^k}{k!} \cdot e^{-\lambda_i (x_k - t)} \cdot e^{-\lambda_i h_k} \lambda_i h_k \dots \\
&\qquad e^{-\lambda_i h_{k+\ell-1}} \lambda_i h_{k+\ell-1} \cdot e^{-\lambda_i (t+\xi - x_{k+\ell-1} - h_{k+\ell-1})} \\
&= \frac{(\lambda_i t)^k}{k!} e^{-\lambda_i t} e^{-\lambda_i \xi} \lambda_i^\ell h_k \dots h_{k+\ell-1}.
\end{aligned}
$$

By Remark 10, we also have:

$$ \mathbb{P}(\Lambda) = \mathbb{P}(N_{t+\xi} - N_t = \ell, N_t = k) = \mathbb{P}(N_{\xi} = \ell)\mathbb{P}(N_t = k) \quad (26) $$

then

$$ 
\begin{aligned}
\mathbb{P}(\forall j \in \{k, \dots, k + \ell - 1\}, T_{\phi_i(j)} \in [x_j, x_j + h_j] | \Lambda) \\
&= \frac{\ell!}{\xi^\ell} h_k \dots h_{k+\ell-1}.
\end{aligned}
$$

Dividing by $h_k \dots h_{k+\ell-1}$ and making successively $h_k, \dots, h_{k+\ell-1}$ tending to 0, we obtain (see [28]) the density of $(T_{\phi_i(k)}, \dots, T_{\phi_i(k+\ell-1)}) | \Lambda$ is defined by

$$ f(x_k, \dots, x_{k+\ell-1} | \ell) = \frac{\ell!}{\xi^\ell} \chi(t < x_k < \dots < x_{k+\ell-1} < t + \xi). $$

It is the distribution of the order statistics corresponding to $\ell$ independent random variables uniformly distributed on the interval $[t, t + \xi]$. By a translation of $-t$, we have proven the lemma. ■

*Proof of Lemma 14:* Using the notation described above and using statement (24), we have to uniformly bound below the following probability:

$$ \mathbb{P}\left(\bigcap_{i=2}^{m} \left(\forall j \in \{N_t + 1, \dots, N_{t+2m\delta_{max}} - 1\}, S_{\phi_i(j)} \in [\delta, \delta_{max}]\right)\right), $$

for all $t \ge 0$. Since the reset sequences associated with different clusters are independent, it is clear that this probability is equal to

$$ \prod_{i=2}^{m} \mathbb{P} \left( \forall j \in \{N_t + 1, \dots, N_{t+2m\delta_{max}} - 1\}, S_{\phi_i(j)} \in [\delta, \delta_{max}] \right). $$

As discussed above, Lemma 15 allows us to prove the result only on the interval $[0, 2m\delta_{max}]$. Indeed, we can map $(T_{\phi_i(k)} - t, \dots, T_{\phi_i(k+\ell-1)} - t)$ to $(S_{\phi_i(k+1)}, \dots, S_{\phi_i(k+\ell-1)})$ and $(T_{\phi_i(0)}, \dots, T_{\phi_i(\ell-1)})$
to $(S_{\phi_i(1)}, \dots, S_{\phi_i(\ell-1)})$ by the same operation. Denoting $\xi = 2m\delta_{max}$ and using (26), we have:

$$
\begin{align*}
\mathbb{P}(\forall j \in \{N_t + 1, \dots, N_{t+\xi} - 1\}, S_{\phi_i(j)} \in [\delta, \delta_{max}]) &= \\
&\quad \sum_{k, \ell \in \mathbb{N}} \mathbb{P}(\forall j \in \{k+1, \dots, k+\ell-1\}, S_{\phi_i(j)} \in [\delta, \delta_{max}] | \Lambda) \mathbb{P}(\Lambda) \\
&= \sum_{k, \ell \in \mathbb{N}} \mathbb{P}(\forall j \in \{1, \dots, \ell-1\}, S_{\phi_i(j)} \in [\delta, \delta_{max}] | N_{\xi} = \ell). \\
&\quad \mathbb{P}(N_t = k) \mathbb{P}(N_{\xi} = \ell) \\
&= \mathbb{P}(\forall j \in \{1, \dots, N_{\xi} - 1\}, S_{\phi_i(j)} \in [\delta, \delta_{max}])
\end{align*}
$$

Thus, it is sufficient to prove that

$$
\mathbb{P} (\forall j \in \{0, \dots, N_{2m\delta_{max}}\}, S_{\phi_i}(j) \in [\delta, \delta_{max}]) > 0.
$$

We denote by $p_i$ this probability. Let us note that

$$
p_i = \sum_{l=1}^{\infty} \mathbb{P} \left( (\forall j \in \{0, \dots, l\}, S_{\phi_i}(j) \in [\delta, \delta_{max}]) \cap (N_{2m\delta_{max}} = l) \right) \\
\geq \mathbb{P} \left( (\forall j \in \{0, \dots, 2m\}, S_{\phi_i}(j) \in [\delta, \delta_{max}]) \cap (N_{2m\delta_{max}} = 2m) \right).
$$

By denoting with $g_S$ the probability density describing the random variable $S$ one obtains

$$
p_i \geq \int_{\delta}^{\delta_{max}} \dots \int_{\delta}^{\delta_{max}} \chi_{(t_{\phi_i(2m-1)} \leq 2m\delta_{max} < t_{\phi_i(2m)})} g(\mathbf{b}) \mathrm{d}\mathbf{b},
$$

where $g(\mathbf{b})\mathrm{d}\mathbf{b} \triangleq g_{S_{\phi_i(0)}}(b_0) \dots g_{S_{\phi_i(2m)}}(b_{2m}) db_0 \dots db_{2m}$ and $t_{\phi_i(2m)} \triangleq \sum_{k=0}^{2m} b_k$. Next, we remark that $\chi_{(t_{\phi_i(2m-1)} \le 2m\delta_{max} < t_{\phi_i(2m)})} = 1$ if $b_k \in [\delta_{min}, \delta_{max}]$, $\forall k \in \{0, \dots, 2m\}$ where $\delta_{min} = \max\{\delta, \frac{2m\delta_{max}}{2m+1}\}$. This yields

$$
\begin{align*}
p_i &\ge \int_{\delta_{min}}^{\delta_{max}} \dots \int_{\delta_{min}}^{\delta_{max}} g_{S_{\phi_i(0)}}(b_0) \dots g_{S_{\phi_i(2m)}}(b_{2m}) db_0 \dots db_{2m} \\
&= \prod_{k=0}^{2m} \mathbb{P} (S_{\phi_i}(k) \in [\delta_{min}, \delta_{max}]) > 0
\end{align*}
$$

The last inequality follows from the last part of Remark 10.

<figure><img src="image_6.png" /></figure>

VII. NUMERICAL EXAMPLES

In this section, we illustrate our main result (Theorem 10) using two examples. The first example is based on a 5-agent system with two clusters and help to clarify the dynamics of the reset system presented in section II. In the second example, we take a more elaborate 30-agent system to illustrate the various network topologies that our framework enables.
## A. 5-agent system

In the following we consider a network of five agents grouped in two clusters. The network structure satisfies Assumption 1 and is described by the following Laplacian matrix:

$$L = \begin{pmatrix} 3 & 0 & -3 & 0 & 0 \\ -1 & 1 & 0 & 0 & 0 \\ -2 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 & 1 \end{pmatrix}$$

which has a block diagonal structure corresponding to the two clusters. Each cluster contains only one node able to interact with agents outside its own cluster (node 1 in the first cluster and node 4 in the second cluster). The weights of the inter-cluster interactions are chosen as follows

$$P = \begin{pmatrix} 0.7 & 0 & 0 & 0.3 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0.25 & 0 & 0 & 0.75 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix},$$

such that Assumption 2 holds. We point out that at reset times $t_k$ either only one or both nodes 1 and 4 reset their state. Therefore, the matrices $P(t_k)$ are either equal to $P$ or obtained by replacing the first or fourth line of $P$ by $(1, 0, 0, 0, 0)$ or $(0, 0, 0, 1, 0)$, respectively. Assumptions 4 and 5 are guaranteed by the choice of $\delta = 4$ and $\delta_{max} = 8$.

In Figure 1 we firstly emphasize the agreement of all five agents. A zoom-in allows to point out that each impulsive agent resets its state in its own rythme and it may happen that one of them resets twice between the reset times of the other.

## B. 30-agent system

We now consider networks of 30 agents grouped in 3 clusters of similar size. We initialize the agents' state so as to enable visual distinction of the 3 clusters. The intra-cluster network is randomly constructed to ensure that each cluster contains a spanning tree (not necessarily unique). Potentially, several agents of the cluster are roots of spanning trees. In a similar way, a network of inter-cluster links between the roots of the clusters is constructed to ensure that a spanning tree
<figure><img src="image_7.png" /><figcaption>Fig. 1. Top: Consensus of the five agents grouped in 2 clusters. Bottom: Zoom in pointing out that the resets are not synchronized.</figcaption></figure>

connects at least one of these roots to all others. This guarantees that Assumption 1 is satisfied. For simplicity, the intra-cluster weights in $L$ and inter-cluster weights in $P$ are chosen constant. Also, we assume that all resets in a given cluster occur synchronously but resets in different clusters may happen asynchronously. We set the minimum and maximum inter-activation reset threshold to $\delta = 10$ and $\delta_{max} = 20$, respectively. In Figure 2 and 3 are displayed the trajectories of the 30-agent system for two distinct topologies. In Figure 2, none of the agents in the top initial cluster (in blue) is influenced by outer agents so that local consensus is quickly reached in this cluster. The top cluster influences the bottom cluster (in red) which in turn influences
the middle cluster (in green). Thus, the overall interaction network is not strongly connected. The zoom-in view presented in the bottom figure shows that several agents reset their states in each cluster. The exponential decrease of the global diameter takes place, as expected thanks to Theorem 10. By contrast, Figure 3 presents a case where the interaction network between the 3 clusters is strongly connected : the top (blue) cluster is influenced by the bottom (red) cluster, the bottom (red) cluster is influenced by the middle (green) cluster and the middle (green) is itself influenced by the top (blue) cluster. So, the overall interaction network between clusters is a cycle. Once again, the diameter exponentially converges to 0.

<figure><img src="image_8.png" /><figcaption>Fig. 2. Trajectory of the reset system (2) with 30 agents grouped in 3 clusters. The overall interaction network topology among cluster is a tree. The top (blue) cluster influences the bottom (red) clusters which influences the middle (green) cluster.</figcaption></figure>

VIII. CONCLUSIONS

In this paper we have studied the consensus in heterogeneous network containing both linear
and linear impulsive dynamics. Under appropriate assumptions, we have proven that all subsys-
tems agree and we have bounded above the convergence speed. One requirement is related to a
minimal dwell-time separating two consecutive reset instants of the same cluster. It is noteworthy
that the reset instants of different clusters are not synchronized, meaning that no global dwell-time
is imposed between two consecutive reset instants in the network. The consensus problem has
been solved under different strategies defining the reset sequence. Firstly we considered a time-
triggering strategy which imposes sufficient assumptions for consensus. Secondly, we designed an
<figure><img src="image_9.png" /><figcaption>Fig. 3. Top : Trajectory of the reset system (2) with 30 agents grouped in 3 clusters. The overall interaction network topology among cluster is a cycle. The top (blue) cluster influences the middle (green) clusters which influences the bottom (red) cluster which influences the top (blue) cluster. Bottom : zoom-in of the trajectory.</figcaption></figure>

event-triggering reset rule and we proved that the proposed sufficient assumptions for consensus are satisfied. Finally, we proved that the reset sequence defined by a Poisson renewal process also satisfies the proposed sufficient assumptions for consensus. Some numerical examples illustrates the validity of the main result ensuring consensus in the heterogeneous network under study.
ACKNOWLEDGEMENT

We would like to thank Anne Gégout-Petit professor in Probability and Statistics at the Université de Lorraine for the helpful discussions on the stochastic part of the paper.

REFERENCES

[1] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” *System and Control Letters*, vol. 53, pp. 65–78, 2004.

[2] A. Olshevsky and J. Tsitsiklis, “Convergence speed in distributed consensus and averaging,” *SIAM Journal of Control and Optimization*, vol. 48, no. 1, pp. 33–55, 2009.

[3] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” *IEEE Trans. on Automatic Control*, vol. 48, no. 6, pp. 988–1001, 2003.

[4] R. Olfati-Saber and R. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” *IEEE Transactions on Automatic Control*, vol. 49, pp. 1520–1533, 2004.

[5] W. Ren and R. W. Beard, “Consensus seeking in multiagent systems under dynamically changing interaction topologies,” *IEEE Trans. on Automatic Control*, vol. 50, no. 5, pp. 655–661, 2005.

[6] S. Martin and A. Girard, “Continuous-time consensus under persistent connectivity and slow divergence of reciprocal interaction weights,” *SIAM Journal on Control and Optimization*, vol. 51, no. 3, pp. 2568–2584, 2013.

[7] J. M. Hendrickx and J. N. Tsitsiklis, “Convergence of type-symmetric and cut-balanced consensus seeking systems,” *IEEE Transactions on Automatic Control*, vol. 58, no. 1, pp. 214–218, 2013.

[8] J. Mei, W. Ren, and G. Ma, “Distributed coordinated tracking with a dynamic leader for multiple Euler-Lagrange systems,” *IEEE Transactions on Automatic Control*, vol. 56, no. 6, pp. 1415–1421, 2011.

[9] H. Su, G. Chen, X. Wang, and Z. Lin, “Adaptive second-order consensus of networked mobile agents with nonlinear dynamics,” *Automatica*, vol. 47, no. 2, pp. 368–375, 2011.

[10] L. Buşoniu and I.-C. Morărescu, “Consensus for black-box nonlinear agents using optimistic optimization,” *Automatica*, vol. 50, no. 4, pp. 1201–1208, 2014.

[11] S. Martin and A. Girard, “Sufficient conditions for flocking via graph robustness analysis,” in *Proc. of the 49th IEEE Conference on Decision and Control*, 2010, pp. 6293–6298.

[12] M. Zavlanos and G. Pappas, “Distributed connectivity control of mobile networks,” *IEEE Transactions on Robotics*, vol. 24, no. 6, pp. 1416–1428, 2008.

[13] M. Fiacchini and I.-C. Morărescu, “Convex conditions on decentralized control for graph topology preservation,” *IEEE Transactions on Automatic Control*, vol. 59, no. 6, pp. 1640–1645, DOI.10.1109/TAC.2013.2292719 2014.

[14] I.-C. Morărescu and A. Girard, “Opinion dynamics with decaying confidence: Application to community detection in graphs,” *IEEE Trans. on Automatic Control*, vol. 56, no. 8, pp. 1862–1873, 2011.

[15] B. Touri and A. Nedić, “On approximations and ergodicity classes in random chains,” *IEEE Transactions on Automatic Control*, vol. 57, no. 11, pp. 2718–2730, 2012.

[16] O. Beker, C. Hollot, and Y. Chait, “Plant with an integrator: an example of reset control overcoming limitations of linear feedback,” *IEEE Transactions on Automatic Control*, vol. 46, no. 11, pp. 1797–1799, 2001.

[17] D.Nešić, L. Zaccarian, and A. R. Teel, “Stability properties of reset systems,” *Automatica*, vol. 44, pp. 2019–2026, 2008.
[18] A. Banos, J. Carrasco, and A. Barreiro, "Reset times-dependent stability of reset control systems," *IEEE Transactions on Automatic Control*, vol. 56, no. 1, pp. 217-223, 2011.

[19] M. C. Bragagnolo, I.-C. Morărescu, J. Daafouz, and P. Riedinger, "Reset strategy for consensus in networks of clusters," *Automatica*, to appear.

[20] I.-C. Morărescu, S. Martin, and A. Girard, "Coordination in networks of linear impulsive agents," in *Proceedings of the 53rd Conference on Decision and Control*, 2014.

[21] E. D. Sontag, *Mathematical Control Theory: Deterministic Finite Dimensional Systems*. Springer, New York, 1998.

[22] W. Ren, R. W. Beard, and T. W. McLain, "Coordination variables and consensus building in multiple vehicle systems," in *Cooperative Control*, ser. Lecture Notes in Control and Information Sciences, V. Kumar, N. Leonard, and A. Morse, Eds. Springer-Verlag Berlin Heidelberg, 2004, vol. 309, pp. 171-188.

[23] V. D. Blondel, J. M. Hendrickx, A. Olshevsky, and J. Tsitsiklis, "Convergence in multiagent coordination, consensus, and flocking," in *Proc. IEEE Conf. on Decision and Control*, 2005, pp. 2996-3000.

[24] A. F. Filippov, *Differential equations with discontinuous righthand sides*. Dordrecht: Kluwer Academic Publishers Group, 1988, translated from the Russian.

[25] S. Martin and J. M. Hendrickx, "Continuous-time consensus under non-instantaneous reciprocity," *arXiv:1409.8332*, 2015.

[26] P. A. Bliman and D. Angeli, "Convergence speed of unsteady distributed consensus: decay estimate along settling spanning-trees," *SIAM Journal on Control and Optimization*, vol. 48, no. 1, pp. 1-32, 2009.

[27] S. Ross, *Introduction to probability models*. Academic Press, Inc., 1985.

[28] D. Foata and A. Fuchs, *Processus stochastiques, Processus de Poisson, chaînes de Markov et Martingales*. Dunod, 2004.