Distributed event-triggered coordination for average
consensus on weight-balanced digraphs

arXiv:1407.7921v3 [math.OC] 8 Jul 2015

Cameron Nowzari a
a

Jorge Cortés b

Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA, 19104, USA

b

Department of Mechanical and Aerospace Engineering, University of California, San Diego, CA, 92093, USA

Abstract
This paper proposes a novel distributed event-triggered algorithmic solution to the multi-agent average consensus problem
for networks whose communication topology is described by weight-balanced, strongly connected digraphs. The proposed
event-triggered communication and control strategy does not rely on individual agents having continuous or periodic access
to information about the state of their neighbors. In addition, it does not require the agents to have a priori knowledge of
any global parameter to execute the algorithm. We show that, under the proposed law, events cannot be triggered an infinite
number of times in any finite period (i.e., no Zeno behavior), and that the resulting network executions provably converge
to the average of the initial agents’ states exponentially fast. We also provide weaker conditions on connectivity under which
convergence is guaranteed when the communication topology is switching. Finally, we also propose and analyze a periodic
implementation of our algorithm where the relevant triggering functions do not need to be evaluated continuously. Simulations
illustrate our results and provide comparisons with other existing algorithms.
Key words: discrete event systems, event-triggered control, average consensus, multi-agent systems, weight-balanced digraphs

1

Introduction

This paper studies the multi-agent average consensus
problem, where a group of agents seek to agree on the average of their initial states. Due to its numerous applications in networked systems, many algorithmic solutions
exist to this problem; however, a majority of them rely on
agents having continuous or periodic availability of information from other agents. Unfortunately, this assumption leads to inefficient implementations in terms of energy consumption, communication bandwidth, congestion, and processor usage. Motivated by these observations, our main goal here is the design of a provably correct distributed event-triggered strategy that prescribes
when communication and control updates should occur
so that the resulting asynchronous network executions
still achieve average consensus.
Literature review: Triggered control seeks to understand the trade-offs between computation, communication, sensing, and actuator effort in achieving a
⋆ A preliminary version was presented as (Nowzari and
Cortés, 2014) at the 2014 American Control Conference.
Email addresses: cnowzari@seas.upenn.edu (Cameron
Nowzari), cortes@ucsd.edu (Jorge Cortés).

Preprint submitted to Automatica

desired task with a guaranteed level of performance.
Early works (Åström and Bernhardsson., 2002) consider tuning controller executions to the state evolution
of a given system, but the ideas have since then been
extended to consider other tasks, see (Heemels et al.,
2012) and references therein for a recent overview.
Among the many references in the context of multiagent systems, (Mazo Jr. and Tabuada, 2011) specifies the responsibility of each agent in updating the
control signals, (Wang and Lemmon, 2011) considers
network scenarios with disturbances, communication
delays, and packet drops, and (Stöker et al., 2013)
studies decentralized event-based control that incorporates estimators of the interconnection signals among
agents. Several works have explored the application
of event-triggered ideas to the acquisition of information by the agents. To this end, Xie et al. (2009);
Heemels and Donkers (2013); Meng and Chen (2013)
combine event-triggered controller updates with sampled data that allows for the periodic evaluation of the
triggers. Zhong and Cassandras (2010) drop the need
for periodic access to information by considering eventbased broadcasts, where agents decide with local information only when to obtain further information about
neighbors. Self-triggered control (Anta and Tabuada,
2010; Wang and Lemmon, 2009) relaxes the need for

22 August 2021

the algorithm. Our Lyapunov-based design builds on
the evolution of the network disagreement to synthesize
triggers that agents can evaluate using locally available
information to make decisions about when to broadcast their current state to neighbors. In our design, we
carefully take into account the discontinuities in the information available to the agents caused by broadcasts
received from neighbors and their effect on the feasibility of the resulting implementation. Our analysis shows
that the resulting asynchronous network executions are
free from Zeno behavior, i.e., only a finite number of
events are triggered in any finite time period, and exponentially converge to agreement on the average of
all agents’ initial states over weight-balanced, strongly
connected digraphs. We also provide a lower bound on
the exponential convergence rate and characterize the
asymptotic convergence of the network under switching
topologies that remain weight-balanced and are jointly
strongly connected. Lastly, we propose a periodic implementation of our event-triggered design that has agents
check the triggers periodically and characterize the
sampling period that guarantees correctness. Various
simulations illustrate our results.

local information by deciding when a future sample of
the state should be taken based on the available information from the last sampled state. Team-triggered
coordination (Nowzari and Cortés, 2016) combines the
strengths of event- and self-triggered control into a
unified approach for networked systems.
The literature on multi-agent average consensus is vast,
see e.g., (Olfati-Saber et al., 2007; Ren and Beard, 2008;
Mesbahi and Egerstedt, 2010) and references therein.
Olfati-Saber and Murray (2004) introduce a continuoustime algorithm that achieves asymptotic convergence
to average consensus for both undirected and weightbalanced directed graphs. Dimarogonas et al. (2012)
build on this algorithm to propose a Lyapunov-based
event-triggered strategy that dictates when agents
should update their control signals but its implementation relies on each agent having perfect information about their neighbors at all times. The
work (Seybotha et al., 2013) uses event-triggered broadcasting with time-dependent triggering functions to
provide an algorithm where each agent only requires
exact information about itself, rather than its neighbors. However, its implementation requires knowledge
of the algebraic connectivity of the network. In addition,
the strictly time-dependent nature of the thresholds
makes the network executions decoupled from the actual state of the agents. Closer to our treatment here,
Garcia et al. (2013) propose an event-triggered broadcasting law with state-dependent triggering functions
where agents do not rely on the availability of continuous information about their neighbors (under the
assumption that all agents have initial access to a common parameter). This algorithm works for networks
with undirected communication topologies and guarantees that all inter-event times are strictly positive, but
does not discard the possibility of an infinite number of
events happening in a finite time period. We consider
here a more general class of communication topologies described by weight-balanced, directed graphs.
The works (Gharesifard and Cortés, 2012; Rikos et al.,
2014) present provably correct distributed strategies
that, given a directed communication topology, allow a
network of agents to find such weight edge assignments.

2

Preliminaries

This section introduces some notational conventions and
notions on graph theory. Let R, R>0 , R≥0 , and Z>0
denote the set of real, positive real, nonnegative real,
and positive integer numbers, respectively. We denote
by 1N and 0N ∈ RN the column vectors with entries
all equal to one and zero, respectively. We let k · kdenote the Euclidean norm on RN . We let diag RN =
{x ∈ RN | x1 = · · · = xN }. For a finite set S, we let |S|
denote its cardinality. Given x, y ∈ R, Young’s inequality (Hardy et al., 1952) states that, for any ε ∈ R>0 ,
xy ≤

x2
εy 2
+
.
2ε
2

(1)

A weighted directed graph (or weighted digraph)
G = (V, E, W ) is comprised of a set of vertices
V = {1, . . . , N }, directed edges E ⊂ V × V and
×N
weighted adjacency matrix W ∈ RN
. Given an edge
≥0
(i, j) ∈ E, we refer to j as an out-neighbor of i and i as
an in-neighbor of j. The sets of out- and in-neighbors
of a given node i are Niout and Niin , respectively. The
weighted adjacency matrix W ∈ RN ×N satisfies wij > 0
if (i, j) ∈ E and wij = 0 otherwise. A path from vertex
i to j is an ordered sequence of vertices such that each
intermediate pair of vertices is an edge. A digraph G is
strongly connected if there exists a path from all i ∈ V
to all j ∈ V . The out- and in-degree matrices Dout and
Din are diagonal matrices where

Statement of contributions: Our main contribution is the
design and analysis of novel event-triggered broadcasting and controller update strategies to solve the multiagent average consensus problem over weight-balanced
digraphs. With respect to the conference version of
this work (Nowzari and Cortés, 2014), the present
manuscript introduces new trigger designs, extends the
treatment from undirected graphs to weight-balanced
digraphs, and provides a comprehensive technical treatment. Our proposed law does not require individual
agents to have continuous access to information about
the state of their neighbors and is fully distributed in
the sense that it does not require any a priori knowledge by agents of global network parameters to execute

dout
=
i

X

j∈Niout

2

wij ,

din
i =

X

j∈Niin

wji ,

respectively. A digraph is weight-balanced if Dout = Din .
The (weighted) Laplacian matrix is L = Dout − W .
Based on the structure of L, at least one of its eigenvalues is zero and the rest of them have nonnegative real
parts. If the digraph G is strongly connected, 0 is simple with associated eigenvector 1N . The digraph G is
weight-balanced if and only if 1TN L = 0N if and only if
Ls = 12 (L + LT ) is positive semidefinite. For a strongly
connected and weight-balanced digraph, zero is a simple
eigenvalue of Ls . In this case, we order its eigenvalues as
λ1 = 0 < λ2 ≤ · · · ≤ λN , and note the inequality
xT Lx ≥ λ2 (Ls )kx −

1 T
(1 x)1N k2 ,
N N

Under this framework, neighbors of a given agent only
receive state information from it when this agent decides to broadcast its state to them. Equipped with this
information, the neighbors update their respective control laws. We denote by x
bi (t) the last broadcast state of
agent i ∈ {1, . . . , N } at any given time t ∈ R≥0 . We assume that each agent has continuous access to its own
state. We then utilize an event-triggered implementation
of the controller (5) given by
ui (t) = −

j∈Niout

(2)

for all x ∈ R . The following property will also be of
use later,

Note that although agent i has access to its own state
xi (t), the controller (6) uses the last broadcast state
x
bi (t). This is to ensure that the average of the agents’
initial states is preserved throughout the evolution of the
system. More specifically, using this controller, one has

Problem statement

d T
(1 x(t)) = 1TN ẋ(t) = −1TN Lb
x(t) = 0,
dt N

We consider the multi-agent average consensus problem for a network of N agents. We let G denote the
weight-balanced, strongly connected digraph describing
the communication topology of the network. Without
loss of generality, we use the convention that an agent
i is able to receive information from neighbors in Niout
and send information to neighbors in Niin . We denote by
xi ∈ R the state of agent i ∈ {1, . . . , N }. We consider
single-integrator dynamics
ẋi (t) = ui (t),

(6)

u(t) = −Lb
x.

(3)

This can be seen by noting that Ls is diagonalizable and
rewriting Ls = S −1 DS, where D is a diagonal matrix
containing the eigenvalues of Ls .
3

wij (b
xi (t) − x
bj (t)).

Letting u(t) = (u1 (t), . . . , uN (t)) ∈ RN and x
b =
(b
x1 , . . . , x
bN ) ∈ RN , we write (6) as

N

λ2 (Ls )xT Lx ≤ xT L2s x ≤ λN (Ls )xT Lx.

X

(7)

where we have used the fact that G is weight-balanced.
Our aim is to identify triggers that prescribe in an opportunistic fashion when agents should broadcast their
state to their neighbors so that the network converges
to the average of the initial agents’ states. Given that
the average is conserved by (6), all the triggers should
enforce is that the agents’ states ultimately agree.

(4)

4 Distributed trigger design
for all i ∈ {1, . . . , N }. It is well known (Olfati-Saber and Murray,
2004) that the distributed continuous control law
In this section we synthesize a distributed triggering
X
strategy that prescribes when agents should broadcast
ui (t) = −
wij (xi (t) − xj (t)),
(5)
state information and update their control signals. Our
j∈Niout
design builds on the analysis of the evolution of the network disagreement characterized by the following candrives each agent of the system to asymptotically condidate Lyapunov function,
verge to the average of the agents’ initial conditions. In
compact form, this can be expressed by
1
V (x) = (x − x̄)T (x − x̄),
(8)
2
ẋ(t) = −Lx(t),
where x̄ = N1 (1TN x)1N corresponds to agreement at the
average of the states of all agents. The next result characterizes a local condition for all agents in the network
such that this candidate Lyapunov function is monotonically nonincreasing.

where x(t) = (x1 (t), . . . , xN (t)) is the column vector of
all agent states and L is the Laplacian of G. However, in
order to be implemented, this control law requires each
agent to continuously access state information about its
neighbors and continuously update its control law. Here,
we are interested in controller implementations that relax both of these requirements by having agents decide in
an opportunistic fashion when to perform these actions.

Proposition 4.1 (Evolution of network disagreement) For i ∈ {1, . . . , N }, let ai ∈ R>0 and denote by

3

for all i ∈ {1, . . . , N }. The maximum of the function
ai (1 − ai ) in the domain (0, ∞) is attained at ai = 12 ,
so we have each agent select this value to optimize the
trigger design. As a consequence of the above discussion,
we have the following result.

ei (t) = x
bi (t)−xi (t) the error between agent i’s last broadcast state and its current state at time t ∈ R≥0 . Then,
V̇ (t) ≤ −



N
1X X
e2
xi − x
bj )2 − i .
wij (1 − ai )(b
2 i=1
ai
out
j∈Ni

Corollary 4.2 For each i ∈ {1, . . . , N }, let σi ∈ (0, 1)
and define

PROOF. Note that, since the average is preserved,
cf. (7), under the control law (6), x̄ = N1 (1TN x(0))1N .
The function t 7→ V (x(t)) is continuous and piecewise
continuously differentiable, with points of discontinuity
of V̇ corresponding to instants of time where an agent
broadcasts its state. Whenever defined, this derivative
takes the form

fi (ei ) = e2i − σi

If each agent i enforces the condition fi (ei (t)) ≤ 0 at all
times, then
V̇ (t) ≤ −

where we have used that the graph is weight-balanced
in the last equality. Let e = (e1 , . . . , eN ) ∈ RN be the
vector of errors of all agents. We can then rewrite V̇ as

j∈Ni

V̇ ≤ −

wij

i=1 j∈Niout

=−

An important observation is that, since the triggering
function fi depends on the last broadcast states x
b, a
broadcast from a neighbor of i might cause a discontinuity in the evaluation of f (ei ), where just before the
update was received, fi (ei ) < 0, and immediately after,
fi (ei ) > 0. Such event would make agent i miss the trigger. Thus, rather than prescribing agent i ∈ {1, . . . , N }
to broadcast its state when fi (ei ) = 0, we instead define
an event by either





N
1X X
e2
xi − x
bj )2 − i ,
wij (1 − ai )(b
2 i=1
ai
out
j∈Ni

fi (ei ) > 0,

(10)

fi (ei ) = 0 and φi 6= 0,

(11)

which concludes the proof. ✷
or

From Proposition 4.1, a sufficient condition to ensure
that the proposed candidate Lyapunov function V is
monotonically decreasing is to maintain
X

wij

j∈Niout



where for convenience, we use the shorthand notation


e2i
(1 − ai )(b
xi − x
bj ) −
≥ 0,
ai
2

φi =

X

j∈Niout

for all i ∈ {1, . . . , N } at all times. This is accomplished
by ensuring
e2i ≤

j∈Niout

wij (b
xi − x
bj )2 .

For each i ∈ {1, . . . , N }, we refer to the function fi defined in Corollary 4.2 as the triggering function and to
the condition fi (ei ) = 0 as the trigger. Note that the design parameter σi affects how flexible the trigger is: as
the value of σi is selected closer to 1, the trigger is enabled less frequently at the cost of agent i contributing
less to the decrease of the Lyapunov function.


N
X
X 1
2
V̇ = −
wij (b
xi − x
bj ) − ei wij (b
xi − x
bj ) .
2
out
i=1

ai (b
xi − x
bj )2
e2
1
(b
xi − x
bj )2 − i −
2
2ai
2

4

(Note that the latter quantity is strictly negative for all
x
b∈
/ diag RN because the graph is strongly connected).

Expanding this out yields



N
X
1 − σi X
i=1

V̇ = −b
xT Lb
x + eT Lb
x.

N
X
X

(9)

j∈Ni

V̇ = xT ẋ − x̄T ẋ = −xT Lb
x − x̄T Lb
x = −xT Lb
x,

Using Young’s inequality (1) for each product ei (b
xi − x
bj )
with ε = ai > 0 yields,

X
1
wij (b
xi − x
bj )2 .
4dout
i
out

wij (b
xi − x
bj )2 ∈ R≥0 .

PN
bT Lb
x. The reaWe note the useful equality i=1 φi = 2 x
soning behind these triggers is the following. The inequality (10) makes sure that the discontinuities of φi
do not make the agent miss an event. The trigger (11)
makes sure that the agent is not required to continuously

ai (1 − ai ) X
wij (b
xi − x
bj )2 ,
dout
i
out
j∈Ni

4

broadcast its state to neighbors when its last broadcast
state is in agreement with the states received from them.

shows that the network executions are guaranteed not
to exhibit Zeno behavior. Its proof illustrates the role
played by the additional trigger (12) in facilitating the
analysis to establish this property.

The triggers (10) and (11) are a generalization of the ones
proposed in (Garcia et al., 2013). However, it is unknown
whether they are sufficient to exclude the possibility of
Zeno behavior in the resulting executions. To address
this issue, we prescribe the following additional trigger.
Let tilast be the last time at which agent i broadcast its
information to its neighbors Niin . If at some time t ≥
tilast , agent i receives new information from a neighbor
j ∈ Niout , then i immediately broadcasts its state if
t ∈ (tilast , tilast + εi ).

Proposition 5.1 (No Zeno behavior) Given the
system (4) with control law (6) executing the eventtriggered communication and control law over
a weight-balanced, strongly connected digraph, the agents
will not be required to communicate an infinite number
of times in any finite time period.

(12)

PROOF. We are interested in showing here that no
agent will broadcast its state an infinite number of times
in any finite time period. Our first step consists of showing that, if an agent does not receive new information
from neighbors, its inter-event times are lower bounded
by a positive constant. Assume agent i ∈ {1, . . . , N } has
just broadcast its state at time t0 , and thus ei (t0 ) = 0.
For t ≥ t0 , while no new information is received, x
bi (t)
and x
bj (t) remain constant. Given that ėi = −ẋi , the
evolution of the error is simply

Here, εi ∈ R>0 is a design parameter selected so that
r
σi
εi <
,
(13)
max
out
4di wi |Niout |
where wimax = maxj∈Niout wij . Our analysis in Section 5
will expand on the role of this bound and the additional
trigger in preventing the occurrence of Zeno behavior.
In conclusion, the triggers (10)-(12) form the basis of the
event-triggered communication and control
law, which is formally presented in Table 1.

ei (t) = −(t − t0 )b
zi ,

where,P
for convenience, we use the shorthand notation
xj − x
bi ). Since we are considering
zbi =
j∈Niout wij (b
the case when no neighbors of i broadcast information,
the trigger (12) is irrelevant. We are then interested in
finding the time t∗ when fi (ei ) = 0 occurs, triggering a
broadcast of agent i’s state. If zbi = 0, no broadcasts will
ever happen (t∗ = ∞) because ei (t) = 0 for all t ≥ t0 .
Hence, consider the case when zbi 6= 0, which in turn
implies φi 6= 0. Using (14), the trigger (11) prescribes a
broadcast at the time t∗ ≥ t0 satisfying

At all times t agent i ∈ {1, . . . , N } performs:
1: if fi (ei (t)) > 0 or (fi (ei (t)) = 0 and φi (t) 6= 0)
then
2:
broadcast state information xi (t) and update
control signal
3: end if
4: if new information xj (t) is received from some
neighbor(s) j ∈ Niout then
5:
if agent i has broadcast its state at any time
t′ ∈ (t − εi , t) then
6:
broadcast state information xi (t)
7:
end if
8:
update control signal
9: end if

(t∗ − t0 )2 zbi2 − σi

Table 1
event-triggered communication and control law.

X
1
wij (b
xi − x
bj )2 = 0,
4dout
i
out
j∈Ni

or, equivalently,

Each time an event is triggered by an agent, say
i ∈ {1, . . . , N }, that agent broadcasts its current state
to its out-neighbors and updates its control signal,
while its in-neighbors j ∈ Niin update their control
signal. This is in contrast to other event-triggered
designs, see e.g., (Zhongxin and Zengqiang, 2010;
Dimarogonas et al., 2012), where events only correspond
to updates of control signals because exact information
is available to the agents at all times.
5

(14)

∗

2

(t − t0 ) =

σi
4dout
i

P

xi − x
bj )2
j∈Niout wij (b

P

2 .

xi − x
bj )
j∈Niout wij (b

Pp
Pp
Using the fact that ( k=1 yk )2 ≤ p k=1 yk2 for any
y1 , . . . , yp ∈ R and p ∈ Z>0 (which readily follows from
the Cauchy-Schwarz inequality), we obtain
 X

Analysis of the event-triggered communication and control law

j∈Niout

Here we analyze the properties of the control law (6) in
conjunction with the event-triggered communication and control law of Section 4. Our first result

2
X
2
wij (b
xi − x
bj ) ≤ |Niout |
wij
(b
xi − x
bj )2
≤ |Niout |wimax

X

j∈Niout

5

j∈Niout

wij (b
xi − x
bj )2 . (15)

PROOF. By design, we know that the event-triggers (10)(11) ensure that, cf. Corollary 4.2,

Therefore, we can lower bound the inter-event time by
∗

τi = t − t0 ≥

r

σi
max |N out | > 0,
w
4dout
i
i
i

V̇ ≤

N
X
σi − 1
i=1

(incidentally, this explains our choice in (13)). Our second step builds on this fact to show that messages cannot be sent an infinite number of times between agents
in a finite time period. Let time t0 be the time at which
agent i has broadcast its information to neighbors and
thus ei (t0 ) = 0. If no information is received by time
t0 + εi < t0 + τi , there is no problem since εi > 0, so
we now consider the case that at least one neighbor of i
broadcasts its information at some time t1 ∈ (t0 , t0 +εi ).
In this case it means that at least one neighbor j ∈ Niout
has broadcast new information, thus agent i would also
rebroadcast its information at time t1 due to trigger (12).
Let I denote the set of all agents who have broadcast
information at time t1 (we refer to these agents as synchronized). This means that, as long as no agent k ∈
/I
sends new information to any agent in I, the agents in I
will not broadcast new information for at least minj∈I τj
seconds, which includes the original agent i. As before, if
no new information is received by any agent in I by time
t1 + minj∈I εj there is no problem, so we now consider
the case that at least one agent k sends new information
to some agent j ∈ I at time t2 ∈ (t1 , t1 + minj∈I εj ).
By trigger (12), this would require all agents in I to also
broadcast their state information at time t2 and agent
k will now be added to the set I. Reasoning repeatedly
in this way, the only way for infinite communications to
occur in a finite time period is for an infinite number of
agents to be added to the set I, which is not possible
because there are only a finite number of agents N . ✷

4

φi .

(16)

We show that convergence is exponential by establishing
that the evolution of V towards 0 is exponential. Define
σmax = maxi∈{1,...,N } σi to further bounding (16) by
N

V̇ ≤

σmax − 1 X
σmax − 1 T
φi =
x
b Lb
x.
4
2
i=1

Given this inequality, our next step is to relate the value
of V (x) with x
bT Lb
x. Note that
1
1
xT Lx =
(b
x − e)T L(b
x − e)
2λ2 (Ls )
2λ2 (Ls )

1
=
x
bT Lb
x − 2b
xT Ls e + eT Le ,
2λ2 (Ls )

V (x) ≤

where we have used (2) in the inequality. Now,
eT Le ≤ λN (Ls )kek2 ≤ λN (Ls )

σmax T
x
b Lb
x,
2dout
min

out
where dout
and we have used
min = mini∈{1,...,N } di
fi (ei ) ≤ 0 in the second inequality. On the other hand,
r
q
σmax T
x
b Lb
x
xT Lb
x
|b
xT Ls e| ≤ kLs x
bk kek ≤ λN (Ls )b
2dout
min
r
σmax T
= λN (Ls ) out x
b Lb
x,
2dmin

where we have used (3) in the second inequality. Putting
these bounds together, we obtain

Remark 5.2 (Conditions for Zeno) We note here
that the introduction of the trigger (12) is sufficient to
ensure Zeno behavior does not occur but it is an open
problem to determine whether it is also necessary. The
design in (Garcia et al., 2013, Corollary 2) specifies
triggers of a nature similar to (10)-(11) for undirected
graphs and guarantees that no agent undergoes an infinite number of updates at any given instant of time, but
does not discard the possibility of an infinite number of
updates in a finite time period, as Proposition 5.1 does.•

V (x) ≤ A x
bT Lb
x,

with A = 2λ21(Ls ) 1 +

q

σmax 2
. Using this exλN (Ls ) 2d
out
min

pression in the bound for the Lie derivative, we get
V̇ ≤

σmax − 1 T
σmax − 1
x
b Lb
x≤
V (x(t)).
2
2A

This, together with the fact that t 7→ V (x(t)) is
continuous and piecewise differentiable implies, using the Comparison Lemma, cf. (Khalil, 2002), that
−1
V (x(t)) ≤ V (x(0)) exp( σmax
2A t) and hence the exponential convergence of the network trajectories to the
average state. ✷

Next, we establish global exponential convergence.

Theorem 5.3 (Exponential convergence to average consensus) Given the system (4) with control
law (6) executing the event-triggered communication and control law over a weight-balanced strongly
connected digraph, all agents exponentially converge to
the average of the initial states, i.e., limt→∞ x(t) = x̄.

The Lyapunov function used in the proof of Theorem 5.3
does not depend on the specific network topology. Therefore, when the communication digraph is time-varying,

6

guarantee fi (ei (t)) ≤ 0 at all times t but, instead, have

this function can be used as a common Lyapunov function to establish asymptotic convergence to average consensus. This observation is key to establish the next result, whose proof we omit for reasons of space.

fi (ei (tℓ )) ≤ 0,

for ℓ ∈ Z≥0 . The next result provides a condition on h
that guarantees the correctness of our design.

Proposition 5.4 (Convergence under switching
topologies) Let ΞN be the set of weight-balanced digraphs over N vertices. Denote the communication
digraph at time t by G(t). Consider the system (4)
with control law (6) executing the event-triggered
communication and control law over a switching
digraph, where t 7→ G(t) ∈ ΞN is piecewise constant and
such that there exists an infinite sequence of contiguous, nonempty, uniformly bounded time intervals over
which the union of communication graphs is strongly
connected. Then, assuming all agents are aware of who
its neighbors are at each time and agents broadcast their
state if their neighbors change, all agents asymptotically
converge to the average of the initial states.
6

(17)

Theorem 6.1 (Exponential convergence under
periodic event-triggered communication and
control law) Let h ∈ R>0 be such that
out
σmax + 4hwmax |Nmax
| < 1,

(18)

out
where wmax = maxi∈{1,...,N } wimax and |Nmax
| =
out
maxi∈{1,...,N } |Ni |. Then, given the system (4)
with control law (6) executing the periodic eventtriggered communication and control law over
a weight-balanced strongly connected digraph, all agents
exponentially converge to the average of the initial states.

Periodically checked event-triggered coordination

PROOF. Since (17) is only guaranteed at the sampling
times under the periodic event-triggered communication and control law, we analyze what happens to the Lyapunov function V in between them. For
t ∈ [tℓ , tℓ+1 ), note that

Here we propose an alternative strategy, termed periodic event-triggered communication and control law, where agents only evaluate triggers (10)
and (11) periodically, instead of continuously. Specifically, given a sampling period h ∈ R>0 , we let {tℓ }ℓ∈Z≥0 ,
where tℓ+1 = tℓ + h, denote the sequence of times at
which agents evaluate the decision of whether to broadcast their state to their neighbors. This type of design is
more in line with the constraints imposed by real-time
implementations, where individual components work at
some given frequency, rather than continuously. An inherent and convenient feature of this strategy is the lack
of Zeno behavior (since inter-event times are naturally
lower bounded by h), making the need for the additional trigger (12) superfluous. The strategy is formally
presented in Table 2.

e(t) = e(tℓ ) + (t − tℓ )Lb
x(tℓ ).
Substituting this expression into V̇ (t) = −b
xT (t)Lb
x(t) +
T
e (t)Lb
x(t), we obtain
V̇ (t) = −b
xT (tℓ )Lb
x(tℓ ) + eT (tℓ )Lb
x(tℓ )
+ (t − tℓ )b
xT (tℓ )LT Lb
x(tℓ ),
for all t ∈ [tℓ , tℓ+1 ). For a simpler exposition, we drop all
arguments referring to time tℓ in the sequel. Following
the same line of reasoning as in Proposition 4.1 yields

At times t ∈ {0, h, 2h, . . . }, agent i ∈ {1, . . . , N }
performs:
1: if fi (ei (t)) > 0 or (fi (ei (t)) = 0 and φi (t) 6= 0)
then
2:
broadcast state information xi (t) and update
control signal
3: end if
4: if new information xj (t) is received from some
neighbor(s) j ∈ Niout then
5:
update control signal
6: end if

V̇ (t) ≤

N
X
σi − 1

4

i=1

φi + (t − tℓ )b
xT LT Lb
x.

Using (15), we bound
x
bT LT Lb
x=

Table 2
periodic event-triggered communication and control law.

≤

N
X
i=1

N
X

X

j∈Niout

2
wij (b
xi − x
bj )

|Niout |wimax

j∈Niout

i=1

Each time an agent i ∈ {1, . . . , N } broadcasts, this resets the error to zero, ei = 0. However, because triggers
are not evaluated continuously, we no longer have the

out
= |Nmax
|wmax

N
X
i=1

7

X

φi .

wij (b
xi − x
bj )2
(19)

14

14

16

16

5

Hence, for t ∈ [tℓ , tℓ+1 ),

20

N 
X
σi − 1

15
V
35

V̇ (t) ≤

i=1

≤



4


out
+ hwmax |Nmax
| φi


1 σmax
out
+ 2hwmax |Nmax
| x
bT Lb
x.
− +
2
2

150

200

0

250

14
16 150

2
Time

3

200
4
250

0

1

2
Time

(a)

3

4

(b)

Proposed
described
by the weight-balanced digraph
({1, . . . , 5}, {(1, 2), (2, 3), (2, 4), (3, 4), (4, 5), (5, 1), (5, 2)})
with weights (1, 1, 0.5, 1, 1.5, 1, 0.5). The initial condition is
x(0) = [−1, 0, 2, 2, 1]T .

We have also compared the periodic
event-triggered
4
communication
and
control
law
with a periodic
5
5
implementation
of
Laplacian
consensus,
cf.
(Olfati-Saber et al.,
6
6
2007). For the latter, trajectories
are guaranteed to con7
7
verge if the timestep satisfies
h < 1/dmax , where dmax
8
8
is the maximum degree of10the graph G. Figure 3 shows
10
this comparison using h =
0.1 and also demonstrates
12
12
N
the
effect
of
{σ
}
on
the
executions
of the periodic
i i=1
14
14
event-triggered
communication
and control
16
16
law. For simplicity, we have used σi = σ to be the same
for all agents in each execution. One can observe the
trade-off between communication and convergence rate
for varying σ: higher σ results in less communication
but slower convergence compared
to smaller values of σ.
5
5
4

20

3.5NE

2.5

0.5

1

40 150
3

15

1.5

1.5

20

40

2.5 100

2

35
50

25
1
Time

(a)

1.5

2

0

2

4
6
Time

8

10

15
NE

V

30

0.5
0.5

1

10
5

Proposedcation topology

16 3.5
V 3

150

1

(Garcia et al., 2013)for all i. The(Garcia
et al.,
2013)
network
consists
of 5 agents with communi-

14

0

15

25
150

7 Simulations
placements
PSfrag replacements
illustrates
performance of the proposed
a et al., 2013)This section (Garcia
et al., the
2013)
Figure 1 shows a comparison
Proposedalgorithms in simulation.
Proposed
of the event-triggered communication and control law with the algorithm
proposed in (Garcia et al.,
1
2013) for undirected graphs over a network of 5 agents.
Both algorithms operate under
the dynamics (4) with
3
control
law
(6),
and
differ
in
the
way events are trig4
gered.
The
algorithm
in
(Garcia
et
al.,
2013) requires all
5
5
network agents to have knowledge of an a priori cho6
sen common parameter a ∈
R>0 , which we set here to
7
7
a
=
0.2.
Figure
1(a)
shows
the evolution of the Lya8
punov
function
V
and
Figure
1(b) shows the number of
10
events triggered over time 12by each strategy.
12

100

25
20

2

Fig. 2. Plots of (a) the evolution of the Lyapunov function V

1 
out
the total number NE of events of the event-trigσmax + 4hwmax |Nmax
| − 1PSfrag
V (x(t)),
replacementsand (b) PSfrag
replacements
2B
gered communication and control law with σi = 0.999

which implies the result. ✷

50

35
NE 30

3

30

Under (18), a reasoning similar to the proof of Theorem 5.3 using (19) leads to finding B > 0 such that
V̇ (t) ≤

40

40

35 100
2

30
σ = 0.2

25 50

1

σ = 0.5
σ = 0.8

150
50

(b)

100

0

1

Time

2

(a)

Fig. 1. Plots of (a) the evolution of the Lyapunov function V and (b) the total number NE of events of the
event-triggered communication and control law
with σi = 0.999 for all i (solid blue) and the algorithm proposed in (Garcia et al., 2013) with a = 0.2
(dashed black). The network consists of 5 agents with communication topology described by the undirected graph
({1, . . . , 5}, {(1, 2), (1, 3), (2, 4), (4, 5)}). The initial condition
is x(0) = [−1, 0, 2, 2, 1]T .

3

0

1

Time

2

3

(b)

Fig. 3. Plots of (a) the evolution of the Lyapunov function V and (b) the total number NE of events of the periodic event-triggered communication and control
law (with varying σ, solid blue) and a standard periodic
Laplacian consensus algorithm (dashed red) with timestep
h = 0.1. Network and initial condition are as in Figure 2.

8

Figure 2 shows an execution of event-triggered communication and control law over a network of 5
agents whose communication topology is described by a
weight-balanced digraph. In this case, we do not compare it against the algorithm in Garcia et al. (2013) because the latter is only designed to work for undirected
graphs.

Conclusions

We have proposed novel event-triggered communication
and control strategies for the multi-agent average consensus problem. Among the novelties of our first design, we highlight that it works over weight-balanced directed communication topologies, does not require individual agents to continuously access information about

8

control. In IEEE Conf. on Decision and Control, pages
3270–3285, Maui, HI, 2012.
H. K. Khalil. Nonlinear Systems. Prentice Hall, 3 edition, 2002. ISBN 0130673897.
M. Mazo Jr. and P. Tabuada. Decentralized eventtriggered control over wireless sensor/actuator networks. IEEE Transactions on Automatic Control, 56
(10):2456–2461, 2011.
X. Meng and T. Chen. Event based agreement protocols for multi-agent networks. Automatica, 49(7):
2125–2132, 2013.
M. Mesbahi and M. Egerstedt. Graph Theoretic Methods
in Multiagent Networks. Applied Mathematics Series.
Princeton University Press, 2010.
C. Nowzari and J. Cortés. Zeno-free, distributed eventtriggered communication and control for multi-agent
average consensus. In American Control Conference,
pages 2148–2153, Portland, OR, 2014.
C. Nowzari and J. Cortés. Team-triggered coordination
for real-time control of networked cyberphysical systems. IEEE Transactions on Automatic Control, 61
(1), 2016. To appear.
R. Olfati-Saber and R. M. Murray. Consensus problems
in networks of agents with switching topology and
time-delays. IEEE Transactions on Automatic Control, 49(9):1520–1533, 2004.
R. Olfati-Saber, J. A. Fax, and R. M. Murray. Consensus
and cooperation in networked multi-agent systems.
Proceedings of the IEEE, 95(1):215–233, 2007.
W. Ren and R. W. Beard. Distributed Consensus in
Multi-Vehicle Cooperative Control. Communications
and Control Engineering. Springer, 2008. ISBN 9781-84800-014-8.
A. Rikos, T. Charalambous, and C. N. Hadjicostis. Distributed weight balancing over digraphs. IEEE Transactions on Control of Network Systems, 2014. To appear.
G. S. Seybotha, D. V. Dimarogonas, and K. H. Johansson. Event-based broadcasting for multi-agent average consensus. Automatica, 49(1):245–252, 2013.
C. Stöker, D. Vey, and J. Lunze. Decentralized eventbased control: Stability analysis and experimental
evaluation. Nonlinear Analysis: Hybrid Systems, 10:
141–155, 2013.
X. Wang and M. D. Lemmon. Self-triggered feedback
control systems with finite-gain L2 stability. IEEE
Transactions on Automatic Control, 54(3):452–467,
2009.
X. Wang and M. D. Lemmon. Event-triggering in distributed networked control systems. IEEE Transactions on Automatic Control, 56(3):586–601, 2011.
G. Xie, H. Liu, L. Wang, and Y. Jia. Consensus in networked multi-agent systems via sampled control: fixed
topology case. In American Control Conference, pages
3902–3907, St. Louis, MO, 2009.
M. Zhong and C. G. Cassandras. Asynchronous distributed optimization with event-driven communication. IEEE Transactions on Automatic Control, 55
(12):2735–2750, 2010.

the states of their neighbors, and does not necessitate
a priori agent knowledge of global network parameters
to execute the algorithm. We have shown that our algorithms exclude the possibility of Zeno behavior and identified conditions such that the network state exponentially converges to agreement on the initial average of the
agents’ state. We have also provided a lower bound on
the convergence rate and characterized the network convergence when the topology is switching under a weaker
form of connectivity. Finally, we have developed a periodic implementation of our event-triggered law that relaxes the need for agents to evaluate the relevant triggering functions continuously and provided a sufficient
condition on the sampling period that guarantee its the
asymptotic correctness. Future work will explore scenarios with more general dynamics and physical sources of
error such as communication delays or packet drops, the
extension of our design and results to distributed convex
optimization and other coordination tasks, and further
analysis of trigger designs that rule out the possibility
of Zeno behavior.
Acknowledgments
This research was supported in part by NSF award CNS1329619.
References
A. Anta and P. Tabuada. To sample or not to sample: self-triggered control for nonlinear systems. IEEE
Transactions on Automatic Control, 55(9):2030–2042,
2010.
K. J. Åström and B. M. Bernhardsson. Comparison
of Riemann and Lebesgue sampling for first order
stochastic systems. In IEEE Conf. on Decision and
Control, pages 2011–2016, Las Vegas, NV, December
2002.
D. V. Dimarogonas, E. Frazzoli, and K. H. Johansson. Distributed event-triggered control for multiagent systems. IEEE Transactions on Automatic Control, 57(5):1291–1297, 2012.
E. Garcia, Y. Cao, H. Yu, P. Antsaklis, and D. Casbeer. Decentralised event-triggered cooperative control with limited communication. International Journal of Control, 86(9):1479–1488, 2013.
B. Gharesifard and J. Cortés. Distributed strategies for
generating weight-balanced and doubly stochastic digraphs. European Journal of Control, 18(6):539–557,
2012.
G. H. Hardy, J. E. Littlewood, and G. Polya. Inequalities. Cambridge University Press, Cambridge, UK,
1952.
W. P. M. H. Heemels and M. C. F. Donkers. Modelbased periodic event-triggered control for linear systems. Automatica, 49(3):698–711, 2013.
W. P. M. H. Heemels, K. H. Johansson, and P. Tabuada.
An introduction to event-triggered and self-triggered

9

L. Zhongxin and C. Zengqiang. Event-triggered averageconsensus for multi-agent systems. In Chinese Control
Conference, pages 4506–4511, July 2010.

10

