Automatica 93 (2018) 454–461

Contents lists available at ScienceDirect

Automatica
journal homepage: www.elsevier.com/locate/automatica

Brief paper

Request-based gossiping without deadlocks✩

Ji Liu a, *, Shaoshuai Mou b , A. Stephen Morse c , Brian D.O. Anderson d,e ,
Changbin (Brad) Yu d,e,f
a
Coordinated Science Laboratory, University of Illinois at Urbana–Champaign, USA
b
Purdue University, USA
c
Yale University, USA
d
Australian National University, Australia
e
National ICT Australia Ltd., Australia
f
Shandong Computer Science Center, Jinan, China

article info a b s t r a c t
Article history: By the distributed averaging problem is meant the problem of computing the average value of a set
Received 20 March 2013 of numbers possessed by the agents in a distributed network using only communication between
Received in revised form 22 August 2017 neighboring agents. Gossiping is a well-known approach to the problem which seeks to iteratively arrive
Accepted 1 January 2018
at a solution by allowing each agent to interchange information with at most one neighbor at each
Available online 7 April 2018
iterative step. Crafting a gossiping protocol which accomplishes this is challenging because gossiping is
an inherently collaborative process which can lead to deadlocks unless careful precautions are taken to
ensure that it does not. Many gossiping protocols are request-based which means simply that a gossip
between two agents will occur whenever one of the two agents accepts a request to gossip placed by the
other. In this paper, we present three deterministic request-based protocols. We show by example that
the first can deadlock. The second is guaranteed to avoid deadlocks by exploiting the idea of local ordering
together with the notion of an agent’s neighbor queue; the protocol requires the simplest queue updates,
which provides an in-depth understanding of how local ordering and queue updates avoid deadlocks.
It is shown that a third protocol which uses a slightly more complicated queue update rule can lead to
significantly faster convergence; a worst case bound on convergence rate is provided.
© 2018 Elsevier Ltd. All rights reserved.

1. Introduction (Xiao & Boyd, 2004). A typical distributed averaging process deals
with a network of n > 1 agents and the constraint that each agent i
Over the past decade, there has been considerable interest in is able to communicate only with certain other agents called agent
developing algorithms for distributed computation and decision i’s neighbors. Neighbor relationships are conveniently character-
making among the members of a group of sensors or mobile au- ized by a simple, undirected, connected graph A in which vertices
tonomous agents via local interactions. Probably the most notable correspond to agents and edges indicate neighbor relationships.
among these are those algorithms intended to cause such a group Thus the neighbors of an agent i have the same labels as the vertices
to reach a consensus in a distributed manner (Jadbabaie, Lin, & in A which are adjacent to vertex i. Initially, each agent i has or
Morse, 2003; Liu, Morse, Nedić, & Başar, 2014; Olfati-Saber &
acquires a real number yi which might be a measured temperature
Murray, 2004).
or something similar. The distributed averaging problem is to devise
We are interested in distributed averaging, a particular type
an algorithm
∑n which will enable each agent to compute the average
of consensus process which has received much attention recently
yavg = 1n i=1 yi using information received only from its neigh-
✩ Proofs of some results in this paper are not included due to space limitations
bors.
There are three important approaches to the distributed av-
and can be found in Liu et al. (2016). The material in this paper was presented at the
50th IEEE Conference on Decision and Control and European Control Conference eraging problem: linear iterations (Xiao & Boyd, 2004), gossip-
(CDC-ECC), December 12–15, 2011, Orlando, Florida, USA. This paper was recom- ing (Boyd, Ghosh, Prabhakar, & Shah, 2006), and double linear
mended for publication in revised form by Associate Editor Claudio De Persis under iterations (Liu & Morse, 2012a) (which are also known as push-
the direction of Editor Christos G. Cassandras. sum algorithms (Kempe, Dobra, & Gehrke, 2003), weighted gos-
*
Corresponding author.
E-mail addresses: jiliu@illinois.edu (J. Liu), mous@purdue.edu (S. Mou),
sip (Bénézit, Blondel, Thiran, Tsitsiklis, & Vetterli, 2010), and ratio
as.morse@yale.edu (A.S. Morse), brian.anderson@anu.edu.au (B.D.O. Anderson), consensus (Domínguez-García, Cady, & Hadjicostis, 2012)). Dou-
brad.yu@anu.edu.au (C. Yu). ble linear iterations are specifically tailored to the case in which

https://doi.org/10.1016/j.automatica.2018.03.001
0005-1098/© 2018 Elsevier Ltd. All rights reserved.
 J. Liu et al. / Automatica 93 (2018) 454–461 455

unidirectional communications exist; they can solve the problem protocol which uses a slightly more complicated queue update rule
when A is directed, strongly connected, but under the assumption can lead to significantly faster convergence.
that each agent is aware of the number of its out-going neighbors. The material in this paper was partially presented in Liu and
Both linear iterations and gossiping work for the case in which all Morse (2012b) and Liu, Mou, Morse, Anderson, and Yu (2011b),
communications between neighbors are bidirectional; in this case, but this paper presents a more comprehensive treatment of the
double linear iterations have the disadvantage that they require work. Specifically, the paper provides proofs for Theorems 2, 4,
updating and transmission of an additional variable for each agent. Proposition 3, Lemmas 1, 2, and establishes an additional result
Linear iterations are a well studied approach to the problem in Proposition 1, which were not included in Liu and Morse (2012b)
which each agent communicates with all of its neighbors on each and Liu et al. (2011b). Note that Protocol III in the paper was briefly
iteration, and thus are sometimes called broadcast algorithms. It is outlined in Liu et al. (2011a), but without a proof of correctness.
clear that broadcast algorithms typically require a lot of transmis-
sions between neighbors per unit time, which may not be possible 2. Gossiping
to secure in some applications, particularly when communication
cost is an important issue on each iteration. For example, fewer Consider a group of n > 1 agents labeled 1 to n.1 Each agent
transmissions per iteration can increase the time interval between i has control over a real-valued scalar quantity xi called agent
any two successive recharges of a sensor, and improve the security i’s gossip variable whose value xi (t) at time t represents agent i’s
of the network by reducing the opportunities of being hacked or estimate of yavg at that time. A gossip between agents i and j, written
eavesdropped. (i, j), occurs at time t if the values of both agents’ variables at time
Gossiping is an alternative approach to the distributed averag- t + 1 equal the average of their values at time t. In other words,
ing problem which does not involve broadcasting. An important xi (t + 1) = xj (t + 1) = 12 (xi (t) + xj (t)). If agent i does not gossip
rule of gossiping is that each agent is allowed to gossip with at at time t, its gossip variable does not change; thus in this case
most one neighbor at one time. This is the reason why gossiping xi (t + 1) = xi (t). Generally not every pair of agents is allowed
algorithms do not involve broadcasting. Thus gossiping algorithms to gossip. The edges of a simple, undirected, connected graph A
have the potential to require less transmissions per iteration than specify which pairs of agents are allowed to gossip. In other words,
broadcast algorithms. Moreover, the peer-to-peer nature of gos- a gossip between agents i and j is allowable if (i, j) is an edge in A.
siping simplifies the implementation of algorithms and reduces We sometimes call A an allowable gossip graph.
computation complexity on each agent. As a trade-off, one would An important rule of gossiping is that in a gossiping process,
not expect gossiping algorithms to converge as fast as broadcast each agent is allowed to gossip with at most one of its neighbors at
algorithms. one time. This rule does not preclude the possibility of two or more
Most existing gossiping algorithms are probabilistic in the sense pairs of agents gossiping at the same time, provided that the pairs
that the actual sequence of gossip pairs which occurs during a have no agent in common. To be more precise, two gossip pairs
specific gossip process is determined probabilistically (Boyd et (i, j) and (k, m) are noninteracting if neither i nor j equals either k or
al., 2006). Recently, deterministic gossiping has received some m. When multiple noninteracting pairs of allowable gossips occur
attention (Liu, Mou, Morse, Anderson, & Yu, 2011a). Probabilistic simultaneously, the simultaneous occurrence of all such gossips is
gossiping algorithms aim at achieving consensus asymptotically called a multi-gossip.
with probability one, whereas deterministic gossiping algorithms Gossiping processes can be modeled by a discrete-time linear
are intended to guarantee that under all conditions, a consensus system of the form
will be achieved asymptotically. Both approaches have merit. The
probabilistic approach is easier both in terms of algorithm de- x(t + 1) = M(t)x(t), t = 0, 1, 2, . . . (1)
velopment and convergence analysis. The deterministic approach n
where x ∈ R is a state vector of gossiping variables and M(t) is
forces one to consider worst case scenarios and has the poten- a matrix characterizing how x changes as the result of the gossips
tial of yielding algorithms which may outperform those obtained which take place at time t. If a single pair of agents i and j gossip
using the probabilistic approach. For example, the deterministic at time t ≥ 0, then M(t) = Pij where Pij is the n × n matrix for
approach rules out the possibility of deadlocks which may occur
which pii = pij = pji = pjj = 21 , pkk = 1, k ̸ ∈ {i, j}, and all
in probabilistic gossiping algorithms.
remaining entries equal 0. We call such Pij a single-gossip primitive
Crafting a deterministic protocol is challenging because gos-
gossip matrix. For convenience, we include in the set of primitive
siping is an inherently collaborative process which can lead to
gossip matrices, the n × n identity matrix I; the identity matrix
deadlocks unless careful precautions are taken to ensure that it
can be thought of as the update matrix to model the case in which
does not. The global ordering (Mehyar, Spanos, Pongsajapan, Low,
no gossips occur at time t. If a multi-gossip occurs at time t, then
& Murray, 2007), centralized scheduling (Liu et al., 2011a), and
as a consequence of non-interaction, M(t) is simply the product
broadcasting (Olshevsky, 2010) are the existing ways to avoid
of the single-gossip primitive gossip matrices corresponding to
deadlocks. Both global ordering and centralized scheduling require
the individual gossips comprising the multi-gossip; moreover, the
a degree of network-wide coordination and broadcasting requires
primitive gossip matrices in the product commute with each other
each agent to obtain the values of all of its neighbors’ ‘‘gossip
and thus any given permutation of the single-gossip primitive
variables’’ at each clock time, which may not be possible to secure
matrices in the product determines the same matrix P. We call P
in some applications.
the primitive gossip matrix determined by the multi-gossip under
The contribution of this paper is to present deterministic gos-
consideration.
siping protocols which do not utilize global ordering, central-
We will see that for any gossiping process determined by the
ized scheduling, or broadcasting and are guaranteed to solve the
protocols presented in this paper, the update matrix M(t) in (1)
distributed averaging problem. Three gossiping protocols are con-
also depends on the state x(t) and thus
sidered in the paper. We show by example that the first can dead-
lock. After minor modifications, a second protocol is obtained. The x(t + 1) = M(x(t), t)x(t), t = 0, 1, 2, . . .
second protocol is guaranteed to avoid deadlocks, which requires
the simplest queue updates and thus provides an in-depth under- 1 The purpose of labeling of the agents is only for convenience. We do not require
standing of how local ordering and queue updates avoid deadlocks. a global labeling of the agents in the network. We only assume that each agent can
It is shown both by analysis and computer studies that a third identify and differentiate between its neighbors.
456 J. Liu et al. / Automatica 93 (2018) 454–461

while each M(x(t), t) is still a primitive gossip matrix. Therefore, protocols which are not linear iterations. To understand why this
the system to be studied is essentially nonlinear, which is a signif- is so, let us agree to say that the transition x(τ ) ↦ −→ x(τ + 1)
icant difference from those in Boyd et al. (2006) and Mehyar et al. contains a virtual gossip if there is a neighborhood L for which
(2007). This difference also makes the protocol design and analysis xi (τ ) = xj (τ ), i, j ∈ L. We say that agent i has gossiped virtually
more challenging than probabilistic protocols. with agent j at time t, if i and j are both labels in L. Thus while
we are only interested in algorithms in which an agent may gossip
2.1. Generalized gossiping with at most one neighbor at any one time, for such algorithms
there may be times at which virtual gossips occur between an
Although in this paper we shall be interested in gossiping pro- agent and one or more of its neighbors. Suppose that for some time
tocols which stipulate that each agent is allowed to gossip with at τ < t, the transition x(τ ) ↦−→ x(τ + 1) contains such a virtual
most one of its neighbors at one time, as we shall see later, there is gossip and let PL denote the primitive gossip matrix determined
value in taking the time here to generalize the idea. by L. Then clearly PL x(τ ) = x(τ ) which means that the matrix Qτ +1
We call a subset L of m > 1 agent a neighborhood if the in the product Qt Qt −1 · · · Q1 can be replaced by the matrix Qτ +1 PL
corresponding vertices in A form a clique.2 We say that the agents without changing the validity of (2). Moreover Qτ +1 PL will be a
with labels in L perform a gossip of order m at time t if each updates primitive gossip matrix if the neighborhoods which define Qτ +1 are
its∑gossip variable to the average of all; that is, if xi (t + 1) = disjoint with L. The importance of this elementary observation is
j∈L xj (t), i ∈ L. A generalized gossip is a gossip of any order. A
1
m simply this. Without taking into account virtual gossips in equa-
gossip without the modifier ‘‘generalized’’, will continue to mean tions such as (2), it may in some cases to be impossible to conclude
a gossip of order 2. A generalized multi-gossip at time t is a finite that the matrix product Qt Qt −1 · · · Q1 converges as t → ∞ even
set of generalized gossips with disjoint neighborhoods which occur though the gossip sequence x(1), x(2), . . . does. Later in this paper
simultaneously at time t. we will describe a gossip protocol for which this is true.
It is worth emphasizing that the concepts of generalized gossips Prompted by the preceding, let us agree to say that a gossiping
and multi-gossips are introduced only for the purpose of analysis. sequence satisfying (2) is consistent with a sequence of primitive
Generalized gossips and multi-gossips do not occur in any gossip- gossip matrices P1 , P2 , . . . if
ing sequence generated by the protocols presented in this paper.
But the effect of ‘‘virtual gossips’’ generated by the protocols in this x(t) = Pt Pt −1 · · · P1 x(0), t > 0. (3)
paper is the same as the occurrence of generalized (multi-)gossips;
see Section 2.2 for detailed explanation. It is obvious that if the sequence x(t), t ≥ 0 is consistent with
The idea of a primitive gossip matrix extends naturally to gen- the sequence P1 , P2 , . . . and the latter converges, then so does the
eralized gossips. In particular, we associate with a neighborhood L former. Given a gossip vector sequence, our task then is to find, if
the n × n doubly stochastic matrix PL where pjk = m+ 1
, j, k ∈ L, possible, a consistent, primitive gossip matrix sequence which is
1
also convergent.
pjj = 1, j ̸ ∈ L, and 0s elsewhere. We call PL the primitive gossip
As we have already noted, A has associated with it a finite
matrix determined by L. By the graph induced by PL , written GL ,
family of primitive gossip matrices and each primitive gossip ma-
we mean the spanning subgraph of A whose edge set is all edges in
trix induces a spanning subgraph of A. It follows that any finite
A which are incident on vertices with labels which are both in L.
sequence of primitive gossip matrix P1 , P2 , . . . , Pk induces a span-
More generally, if L1 , L2 , . . . , Lk are k disjoint neighborhoods, the
ning subgraph of A whose edge set is the union of the edge sets
matrix PL1 PL2 · · · PLk is the primitive gossip matrix determined
of the graphs induced by all of the Pi . We say that the primitive
by L1 , L2 , . . . , Lk and the graph induced by PL1 PL2 · · · PLk is the
union of the induced graphs GLi , i ∈ {1, 2, . . . , k}. Note that gossip matrix sequence P1 , P2 , . . . , Pk is complete if the graph the
the matrices in the product PL1 PL2 · · · PLk commute because the sequence induces is a connected spanning subgraph of A. An infi-
Li are disjoint so the order of the matrices in the product is not nite sequence of primitive gossip matrices P1 , P2 , . . . is repetitively
important for the definition to make sense. Note also that there complete with period T , if each successive subsequence of length T
are only finitely many primitive gossip matrices associated with A. in the sequence is complete. A gossiping sequence x(t), t > 0 is
repetitively complete with period T , if there is a consistent sequence
2.2. Gossiping sequences of primitive gossip matrices which is repetitively complete with
period T . The importance of repetitive completeness is as follows.
Let γ1 , γ2 , . . . be an infinite sequence of multi-gossips corre-
sponding to some or all of the edges in A. Corresponding to such Theorem 1 (Theorem 1 in Liu et al., 2011a). Suppose that P1 , P2 , . . . is
a sequence is a sequence of primitive gossip matrices Q1 , Q2 , . . . an infinite sequence of primitive gossip matrices which is repetitively
where Qi is the primitive gossip matrices of the ith multi-gossip complete with period T . There exists a real nonnegative number λ <
in the sequence. For given x(0), such a gossiping matrix sequence 1, depending only on T and the Pt , for which limt →∞ Pt Pt −1 · · · P1 x(0)
generates the sequence of vectors = yavg 1 as fast as λt converges to zero.

x(t) = Qt Qt −1 · · · Q1 x(0), t>0 (2)

3. Request-based gossiping
which we call a gossiping sequence. We have purposely restricted
this definition of a gossiping sequence to multi-gossip sequences, Request-based gossiping is a gossiping process in which a gos-
as opposed to generalized multi-gossip sequences, since we will sip occurs between two agents whenever one of the two accepts
only be dealing with algorithms involving multi-gossips. Our rea- a request to gossip placed by the other. The aim of this section is
son for considering generalized multi-gossips will become clear in to design deterministic request-based gossiping protocols which
a moment. can solve the distributed averaging problem. The design of such
As will soon be obvious, the matrices Qi in (2) are not necessarily deterministic protocols is more complicated than probabilistic
the only primitive gossip matrices for which (2) holds. This non- ones since a deterministic protocol must rule out the possibility
uniqueness can play a crucial rule in understanding certain gossip of deadlocks whereas in a probabilistic protocol, deadlocks are
allowed to occur as long as their probability goes to zero as time
2 A clique in an undirected graph is a subset of the vertices such that every two goes to infinity. In the cases when an agent who has placed a
distinct vertices are adjacent. request to gossip, at the same time receives a request to gossip
 J. Liu et al. / Automatica 93 (2018) 454–461 457

from another agent, conflicts leading to deadlocks can arise. It is 3.1. A raw model
challenging to devise deterministic protocols which resolve such
conflicts while at the same time ensuring exponential convergence
Protocol I: Between clock times t and t + 1 each agent i performs
of the gossiping process generated by the protocols.
the steps enumerated below in the order indicated. Although the
From time to time, an agent may have more than one neigh-
agents’ actions need not be precisely synchronized, it is understood
bor to which it is able to make a request to gossip with. Also
that for each k ∈ {1, 2, 3} all agents complete step k before any
from time to time, an agent may receive more than one request
to gossip from its neighbors. While in such situations decisions embark on step k + 1.
about who to place a request with or whose request to accept
(1) 1st Transmission: Agent i sends its gossip variable value
can be randomized, in this paper we will examine only completely
xi (t) to its current preferred neighbor. At the same time
deterministic strategies. To do this we will assume that each agent
agent i receives the gossip values from all of those neighbors
orders all its neighbors according to some priorities so when a
which have agent i as their current preferred neighbor.
choice occurs among neighbors, the agent will always choose the
(2) 2nd Transmission: Agent i sends its current gossip value
one with highest priority. The simple example in Liu et al. (2011a)
xi (t) to those neighbors which have agent i as their current
illustrates that fixed priorities can be problematic (see Protocol I
preferred neighbor.
in Liu et al., 2011a and the example which follows). The global
(3) Acceptances:
ordering (Mehyar et al., 2007) and centralized scheduling (Liu et
al., 2011a) are the two ways in the literature to overcome them. (a) If agent i has not placed a request to gossip but has re-
Both global ordering and centralized scheduling require certain ceived at least one request to gossip, then agent i sends an
degree of network-wide coordination which may not be possible to acceptance to that particular requesting neighbor whose
secure in some applications. In what follows we take an alternative label is closest to the front of the queue qi (t).
approach which is fully distributed. (b) If agent i has either placed a request to gossip or has
In the light of Theorem 1, we are interested in devising gossiping not received any requests to gossip, then agent i does not
protocols which generate repetitively complete gossip sequences. send out an acceptance.
Towards this end, let us agree to say that an agent i has completed a
(4) Gossip variable and queue updates:
round of gossiping after it has gossiped with each of its neighbors at
least once. Thus the finite sequence of primitive gossiping matrices (a) If agent i sends an acceptance to or receives an accep-
corresponding to a finite sequence of multi-gossips for the entire tance from neighbor j, then agent i gossips with neighbor
x (t)+x (t)
group of n agents which has occurred over an interval of length j by setting xi (t + 1) = i 2 j . Agent i updates its queue
T , will be complete if each agent in the group completes a round by moving j from its current positions in qi (t) to the end
of gossiping over the same interval. In Section 3.2, the concept of of the queue.
a round of gossiping will be generalized by taking into account (b) If agent i has not sent out an acceptance nor received
virtual gossips. one, then agent i does not update the value of xi (t). In
For the protocols which follow it will be necessary for each addition, qi (t) is not updated except when agent i’s gossip
agent i to keep track of where it is in a particular round. To do value equals that of its current preferred neighbor. In this
this, agent i makes use of a recursively updated neighbor queue qi (t) special case agent i moves the label i∗ (t) from the front to
where qi (·) is a function from T to the set of all possible lists of the the end of the queue.
ni labels in Ni , the neighbor set of agent i. Roughly speaking, qi (t)
is a list of the labels of the neighbors of agent i which defines the It is possible show that this protocol ensures that at each time
queue of neighbors at time t which are in line to gossip with agent i. t, either xi (t) = xi∗ (t) (t) for some agent i or a gossip must take place
In a recent doctoral thesis (Olshevsky, 2010), a clever gos- between two agents whose gossip variables have different values.
siping protocol is proposed which does not require the distinct But the example in Liu and Morse (2012b) shows that this strategy
neighbor event times assumption. The protocol avoids deadlocks will not necessarily lead to a consensus (see Section III in Liu &
and achieves consensus exponentially fast. A disadvantage of the Morse, 2012b).
protocol in Olshevsky (2010) is that it requires each agent to obtain
the values of all of its neighbors’ gossip variables at each clock time. 3.2. A corrected protocol
By exploiting one of the key ideas in Olshevsky (2010) together
with the notion of an agent’s neighbor queue qi (t) defined earlier, It is possible to guarantee an exponentially fast consensus under
it is possible to obtain a gossiping protocol which also avoids all conditions by slightly modifying Protocol I. The modification
deadlocks and achieves consensus exponentially fast but without will be made in step 3 of Protocol I, thereby resulting in Protocol II.
requiring each agent to obtain the values of all of its neighbors’ Comparing Protocol I and Protocol II which follows, the difference
gossip variables at each iteration. between the two only lies in the cases when an agent i whose
In the sequel, we will outline a gossiping algorithm in which at gossip variable value at time t equals that of its current preferred
time t, each agent i has a single preferred neighbor whose label i∗ (t) neighbor i∗ (t), at the same time receives one or more requests
is in the front of queue qi (t). At time t each agent i transmits to
to gossip. Under Protocol I, agent i gossips with that requesting
its preferred neighbor its label i and the current value of its gossip
neighbor whose label is closest to the front of its neighbor queue at
variable xi (t). Agent i then transmits the current value of its gossip
time t; the label i∗ (t) will still be in the front of the queue at time
variable to those agents which have agent i as their preferred
t + 1. Under Protocol II, agent i ignores all incoming requests to
neighbor; these neighbors plus neighbor i∗ (t) are agent i’s receivers
gossip at time t and moves the label i∗ (t) from the front to the end
at time t. They are the neighbors of agent i who know the current
of the queue.
gossip value of agent i. Agent i is presumed to have placed a request
to gossip with its preferred neighbor i∗ (t) if xi (t) > xi∗ (t) (t); agent Protocol II: Between clock times t and t + 1 each agent i performs
i is a requester of agent i∗ (t) whenever this is so. While an agent i the steps enumerated below in the order indicated. Although the
has exactly one preferred neighbor, it may at the same time have agents’ actions need not be precisely synchronized, it is understood
anywhere from zero to ni requesters, where ni is the number of that for each k ∈ {1, 2, 3} all agents complete step k before any
neighbors of agent i. embark on step k + 1.
458 J. Liu et al. / Automatica 93 (2018) 454–461

(1) Same as Protocol I (a) If agent i either sends an acceptance to or receives an

(2) Same as Protocol I acceptance from neighbor j, then agent i gossips with
x (t)+x (t)
(3) Acceptances: neighbor j by setting xi (t + 1) = i 2 j . Agent i
updates its queue by moving j and the labels of all of
(a) If xi (t) < xi∗ (t) (t) and agent i has received at least one
its current receivers k, if any, for which xk (t) = xi (t)
request to gossip, then agent i sends an acceptance to that
from their current positions in qi (t) to the end of the
particular requesting neighbor whose label is closest to
queue while maintaining their relative order.
the front of the queue qi (t).
(b) If agent i has not sent out an acceptance nor received
(b) If xi (t) ≥ xi∗ (t) (t) or agent i has not received any request one, then agent i does not update the value of xi (t).
to gossip, then agent i does not send out an acceptance. In addition, qi (t) is not updated except when agent i’s
(4) Same as Protocol I. gossip value equals that of at least one of its current
receivers. In this special case agent i moves the labels
It is possible to show that Protocol II is deadlock free. of all of its current receivers k for which xk (t) = xi (t)
from their current positions in qi (t) to the end of the
Proposition 1. Suppose that all n agents follow Protocol II. Then queue, while maintaining their relative order.
a gossip must take place within every 2d time steps, where d is the
Protocol III is expected to solve the distributed averaging prob-
maximum vertex degree of A.
lem faster than Protocol II since Protocol III allows agents to ‘‘gossip
It is also possible to show that every sequence of gossip vectors virtually’’ with more than one neighbors at one time while Protocol
generated by Protocol II converges to the desired limit point expo- II dose not. Faster convergence of Protocol III was illustrated in Liu
nentially fast. and Morse (2012b) by simulation (see Section V in Liu & Morse,
2012b).
Theorem 2. Suppose that all n agents follow Protocol II. Then there is It is also possible to derive a worst case bound on the conver-
a finite time T , not depending on the values of gossip variables, such gence rate of Protocol III for general allowable gossip graphs.
that every sequence of gossip vectors x(t), t > 0 generated by Protocol
II is repetitively complete with period no greater than T . Theorem 3. Suppose that all n agents follow Protocol III. Then for any
connected allowable gossip graph A, every sequence of gossip vectors
From Theorem 1, Protocol II can solve the distributed averaging x(t), t > 0 generated by Protocol III is repetitively complete with
problem for all initial conditions. period no greater than the number of edges of A.
A worst case bound of T has so far eluded us except for the From Theorem 1, Protocol III can solve the distributed averaging
special case when A is a tree (see Theorem 3 in Liu, Mou, Morse, problem for all initial conditions.
Anderson, & Yu, 2016). To prove Theorem 3, we need to generalize slightly a few ideas.
First note that step 4 of the protocol stipulates that agent i must
3.3. An accelerated protocol update its queue whenever its current gossip value equals that
of on of its neighbors. We say that agent i gossips virtually with
Note that step 4 of Protocol II stipulates that agent i must neighbor j at time t if the current gossip values of both agents are
update its queue whenever its current gossip value equals that of the same. Note that while an agent can gossip with at most one
its current preferred neighbor. We say that agent i gossips virtually agent at time t, it can gossip virtually with as many as ni at the same
with neighbor j at time t if i∗ (t) = j and the current gossip time. We say that an agent has completed a round of gossiping
values of both agents are the same. It is worth noting that when after it has gossiped or virtually gossiped with each neighbor in
agent i gossips virtually with neighbor j, j may not gossip virtually Ni at least once. Thus the finite sequence of primitive gossiping
matrices corresponding to a finite sequence of multi-gossips and
with i. Also note that each agent can gossip virtually with at most
virtual multi-gossips for the entire group which has occurred over
one neighbor at one clock time. If an agent gossips virtually with
an interval of length T , will be complete if over the same period
its current preferred neighbor, it does not gossip with any other
each agent in the group completes a round. Thus Theorem 3 will
neighbor. Thus each agent can gossip or virtually gossip with at
be true if every agent completes a round in a number of iterations
most one neighbor at one clock time. If agent i gossips or gossips
no larger than the number of edges of A. The following proposition
virtually with neighbor j at time t, then agent i updates its neighbor asserts that this is in fact the case.
queue by moving the label j from its current position in qi (t) to the
end of the queue. Proposition 2. Let m be the number of edges in A. Then within m
An important rule of gossiping is that during a gossiping process iterations every agent will have gossiped or virtually gossiped at least
each agent is allowed to gossip with at most one of its neighbors at once with each of its neighbors.
one clock time. There is no such restriction on virtual gossips. Thus
to improve the convergence rate of the protocol in the preceding To prove this proposition we will make use of the following two
section, a natural idea is to let each agent gossip virtually with as lemmas.
many as neighbors as possible at the same time.
Lemma 1. Suppose that all n agents follow Protocol III. Then at each
Protocol III: Between clock times t and t + 1 each agent i performs time t, at least one gossip or virtual gossip must occur.
the steps enumerated below in the order indicated. Although the
agents’ actions need not be precisely synchronized, it is understood Lemma 2. Let t be fixed and suppose that G is a spanning subgraph
that for each k ∈ {1, 2, 3} all agents complete step k before any of A with at least one edge. For each i ∈ {1, 2, . . . , n} write Ni for the
embark on step k + 1. set of labels of the vertices adjacent to vertex i in A and Mi for the set
of labels of the vertices adjacent to vertex i in G. Let Ni − Mi denote
(1) Same as Protocol I the complement of Mi in Ni . Suppose that for each i ∈ {1, 2, . . . , n},
(2) Same as Protocol I each label in Mi , if any, is closer to the front of qi (t) than are all the
(3) Same as Protocol II labels in Ni − Mi . Then there must be an edge (i, j) within G such that
(4) Gossip variable and queue updates: at time t, neighboring agents i and j either gossip or gossip virtually.
 J. Liu et al. / Automatica 93 (2018) 454–461 459

We will prove Lemma 2 first. To begin, let us note that at each xiw (t) > xij (t) with is impossible because j < w . Therefore at least
time t, each label i ∈ {1, 2, . . . , n} uniquely determines a sequence one agent which has received a request to gossip has not placed a
of labels request to gossip. ■

[i]t = {i1 , i2 , . . . , im(t) } It is worth noting that if G has s connected components, each
with positive minimum degree, then there must be an edge (ai , bi )
such that i1 = i, ij+1 = i∗j (t) for all j ∈ {1, 2, . . . , m(t) − within each component for which neighboring agents ai and bi
1}, i1 , i2 , . . . , im(t)−1 are distinct, and im(t) = ik for some k ∈ either gossip or gossip virtually at time t. This can be proved using
{1, 2, . . . , m(t) − 2}. We call [i]t the sequence of queue leaders gen- an argument similar to the argument use to prove Lemma 2.
erated by i at time t. Note that m(t) is a positive integer depending
on time t and always satisfies the inequalities 2 ≤ m(t) − 1 ≤ Proof of Lemma 1. We claim that A satisfies the hypotheses of
δ + 1 where δ is the length of the longest path of A. We will Lemma 2. Note first that by assumption A is a connected graph with
sometimes simply write [i]t = {i1 , i2 , . . . , im } for convenience with at least two vertices. Thus A has at least one edge. Next observe
the understanding that m depends on time t. The set of all possible that when G = A, we have Mi = Ni , i ∈ {1, 2, . . . , n}. Clearly A
sequences of queue leaders generated by i is a finite set because automatically satisfies hypotheses of Lemma 2. Hence Lemma 1 is
the number of agents in the group is finite. true. ■

Proof of Lemma 2. Let J denote the set of labels of all agents It can be seen that Lemma 1 is a special case of Lemma 2. We are
i for which Mi is nonempty. Since G has at least one edge, J is now in a position to prove Proposition 2 using the two lemmas.
nonempty. Fix i ∈ J . We claim that i∗ (t) must be in Mi . If it were
not, it would have to be further back in qi (t) than the labels in Mi Proof of Proposition 2. See the proof of Proposition 2 in Liu et al.
and this would contradict the fact that i∗ (t) is in the front of qi (t). (2011b). ■
Therefore i∗ (t) ∈ Mi . This implies that (i, i∗ (t)) is an edge in G.
Both analytical results and computer studies show that a
Hence Mi∗ (t) must be nonempty so i∗ (t) must also be in J . From
slightly more complicated queue update rule can lead to signifi-
this it follows that for each i ∈ J , all of the labels in [i]t are also in J . cantly faster convergence.
To proceed, suppose that xi (t) = xi∗ (t) (t) for some i ∈ J . Then
agent i has not placed a request. If agent i receives a request, then
agent i must send an acceptance because of 3a and then gossip 3.3.1. Convergence rate
because of 4a. On the other hand, if agent i has not received a Theorems 1 and 3 imply that every sequence of gossip vectors
request, then agent i must gossip virtually because of 4b. Thus if generated by Protocol III converges to the desired limit point
xi (t) = xi∗ (t) (t) for some i ∈ J , either a gossip or virtual gossip exponentially fast at a rate no worse that some finite number λ < 1
will have taken place between two neighboring agents with an which depends only on A. In the sequel, we will derive a worst case
edge in G. To complete the proof, it is thus enough to consider the bound of λ.
case when xi (t) ̸ = xi∗ (t) (t) for all i ∈ J . We claim that under this It is useful to think of a gossiping process in geometric terms.
condition at least one agent with label i ∈ J , must place a request Associate with agent i’s current gossip variable xi , a corresponding
to gossip. To prove that this is so, suppose the contrary. Then there point xi on the real line which we will henceforth refer to as agent
i’s current position. For agents i and j to gossip then means simply
is no agent with a label in J which is a requester so xi (t) < xi∗ (t) (t)
that each moves to the midpoint between the two. We would
for all i ∈ J . In particular xi1 (t) < xi2 (t) < · · · < xik (t) < xi∗ where
k
{i1 , i2 , . . . , iw } = [i]t and k is the largest integer greater than 1 for like to have a way to keep track of the entire group’s progress
in reaching a consensus. Towards this end, let us agree to call
which the labels i1 , i2 , . . . , ik are all in J . Since the labels in [i]t are
a nonnegative valued function V : Rn → R, an indicator if
all in J , it must be that k = w so xi1 (t) < xi2 (t) < · · · < xiw (t) <
V (t) = 0 just in case all agents are at the same position at time
xi∗w (t). But i∗w (t) must equal some integer ij ∈ {i1 , i2 , . . . , iw−1 } so
t. In the sequel, we will be concerned exclusively with indicators
xiw (t) < xij (t). This is impossible because j < w . Therefore at least
comprised of sums of distances between pairs of points, and for
one agent with a label in J must place a request to gossip.
now we will assume that the specific pairs of points in question
To complete the proof it is enough to show that among the
do not change with iterations. To be more precise, let E be a given
agents with labels in J who receive requests to gossip at time t, at
subset of {1, 2, . . . , n} × {1, 2, . . . , n}; we say that a function V :
least one agent – say agent k – does not place a request to gossip.
Rn → [0, ∞) of the form
For if agent k does not place a request, then agent k must gossip
with that agent with label closest to the front of qk (t) who placed
∑
V (t) = |xi (t) − xj (t)| (4)
a request to gossip with agent k at time t. (i,j)∈E
To prove that at least one agent receiving a gossip request at
time t does not place a request to gossip at time t, assume the is an indicator function if V (t) = 0 implies that all the xi have the
contrary. Therefore suppose that every agent receiving a request same value at time t. There is a natural way to associate with any
to gossip a time t, also places a request to gossip at time t. Let i be such an indicator a simple, undirected graph. Specifically, the graph
the label of any agent receiving a request to gossip at time t and let of V , written GV , is a that graph on n vertices, which has an edge
(i, j) just in case the distance between points i and j is one of the
{i1 , i2 , . . . , iw } = [i]t . Since agent i1 = i and i receives a request to
terms in the sum comprising V .
gossip, it also must place a request to gossip. Hence agent i2 must
Suppose that agents i and j gossip at time t. Let us say that an
receive a request to gossip. Therefore agent i2 must place a request
indicator V is instantaneous if there is a positive number λ such that
to gossip at time t. By this reasoning one concludes that all of the
agents with labels i1 , i2 , . . . , iw place requests to gossip at time t.
V (t + 1) − V (t) ≤ −λ|xi (t) − xj (t)|. (5)
This implies that xi1 (t) > xi2 (t) > · · · > xiw (t) > xi∗w (t) (t). But i∗w (t)
must equal some integer ij ∈ {i1 , i2 , . . . , iw−1 }. This means that Thus if V is instantaneous, there is a definite decrease in its value
460 J. Liu et al. / Automatica 93 (2018) 454–461

whenever any allowable pair of agents not initially in the same 4. Concluding remarks
position, gossip.
One of the problems with the idea of gossiping, which ap-
Proposition 3. A necessary and sufficient condition for V to be an
parently is not widely appreciated, is that it is difficult to devise
instantaneous indicator is that A ⊂ GV and for each edge (i, k) of GV
for which (i, j) is an edge of A, (j, k) is an edge of GV . provably correct gossiping protocols which are guaranteed to avoid
deadlocks without making restrictive assumptions. The research
The proof of this proposition depends on the following result. in this paper and in Mehyar et al. (2007) and Olshevsky (2010)
contributes to our understanding of this issue and how to deal with
Lemma 3. Suppose that agents i and j gossip at time t. Let k be it. For the protocols presented in this paper, it is assumed that the
different than i and j. Then |xi (t + 1) − xk (t + 1)| + |xk (t + 1) − communication between agents is delay-free. Analysis of the effect
xj (t + 1)| ≤ |xi (t) − xk (t)| + |xk (t) − xj (t)|. of transmission delays is a subject for future research.

Proof of Proposition 3. Suppose that V is an indicator with the

properties that A ⊂ GV and each edge (i, k) of GV for which (i, j) Acknowledgments
is an edge of A, (j, k) is an edge of GV . Suppose that agents i and
j gossip in which case (i, j) is an edge of A and thus GV . Let (m, k)
be any edge in GV . If {i, j} and {m, k} are disjoint sets, the distance The work of Liu, Mou and Morse was supported by the US
between agents m and k does not change with the gossip. If {i, j} Air Force Office of Scientific Research and the National Science
and {m, k} are not disjoint sets, then without loss of generality we Foundation. The work of Anderson was supported by the Australian
can take m = i. Thus by hypothesis both (i, k) and (j, k) are edges Research Council’s Discovery Project DP-110100538 and the Na-
in GV . But by Lemma 3 the sum of the distance between agent k tional ICT AustraliaVNICTA. NICTA is funded by the Australian Gov-
and agent i and the distance between agent k and agent j does not ernment as represented by the Department of Broadband, Com-
increase after the gossip. Since this is true for all edges in GV with munications and the Digital Economy and the Australian Research
the exception of (i, j), it must be true that (5) holds with λ = 1. Council through the ICT Centre of Excellence program. The work
Therefore V is instantaneous. The simple proof of the necessity part of Yu was supported by the Australian Research Council through
of this proposition is omitted. ■ a Queen Elizabeth II Fellowship and DP-110100538 and by the
Overseas Expert Program of Shandong Province, China. The work of
Theorem 4. V is instantaneous if and only if GV is complete.
Anderson and Yu was also supported by the U.S. Air Force Research
laboratory Grant FA2386-10-1-4102.
Proof of Theorem 4. Suppose that (i, j) is not an edge in GV .
Since A is connected, there must be a path from i to j in A and
thus GV . Suppose that there are other k > 0 vertices in the
References
path. Then the path consists of k + 1 edges which are denoted
by (i, v1 ), (v1 , v2 ), . . . , (vk−1 , vk ), (vk , j). Since (i, v1 ) is in GV and
(v1 , v2 ) is in A, then by Proposition 3, (i, v2 ) is in GV . Similarly, Bénézit, F., Blondel, V., Thiran, P., Tsitsiklis, J. N., & Vetterli, M. (2010). Weighted
gossip: distributed averaging using non-doubly stochastic matrices. In Proc. IEEE
since (i, v2 ) is in GV and (v2 , v3 ) is in A, then (i, v3 ) is also in GV . By int. symp. inform. theory (pp. 1753–1757).
repeating this argument, one reaches the conclusion that (i, j) is an Boyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006). Randomized gossip algorithms.
edge of GV , which is a contradiction. Thus GV must be a complete IEEE Transaction on Information Theory, 52(6), 2508–2530.
graph. ■ Domínguez-García, A. D., Cady, S. T., & Hadjicostis, C. N. (2012). Decentralized
optimal dispatch of distributed energy resources. In Proc. 51st IEEE conf. decision
By Theorem 4, it is clear that the desired instantaneous indicator control (pp. 3688–3693).
Jadbabaie, A., Lin, J., & Morse, A. S. (2003). Coordination of groups of mobile
must be in the form of autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic
Control, 48(6), 988–1001.
∑
V (t) = |xi (t) − xj (t)| Kempe, D., Dobra, A., & Gehrke, J. (2003). Gossip-based computation of aggregate
(i,j)∈A information. In Proc. 44th annu. IEEE symp. found. comput. sci. (pp. 482–491).
Liu, J., & Morse, A. S. (2012a). Asynchronous distributed averaging using double
where A = {1, 2, . . . , n} × {1, 2, . . . , n}. linear iterations. In Proc. Am. control conf. (pp. 6620–6625).
Liu, J., & Morse, A. S. (2012b). Revisiting request-based gossiping: the effects of
Lemma 4 (See Lemma 2 in Mehyar et al., 2007). Suppose that since queue updates on convergence time. In Proc. 51st IEEE conf. decision control
(pp. 3985–3990).
time t0 , each agent has gossiped or virtually gossiped at least once
Liu, J., Morse, A. S., Nedić, A., & Başar, T. (2014). Internal stability of linear consensus
with
( each ) of its neighbors within T iterations. Then V (t0 + T ) ≤ processes. In Proc. 53rd IEEE conf. decision control (pp. 922–927).
4 Liu, J., Mou, S., Morse, A. S., Anderson, B. D. O., & Yu, C. (2011a). Deterministic
1− n2
V (t0 ).
gossiping. Proceedings of the IEEE, 99(9), 1505–1524.
Liu, J., Mou, S., Morse, A. S., Anderson, B. D. O., & Yu, C. (2011b). Request-based
Let m be the number of edges of A. Since every sequence of
gossiping. In Proc. 50th IEEE conf. decision control (pp. 1968–1973).
gossip vectors generated by Protocol III is repetitively complete Liu, J., Mou, S., Morse, A. S., Anderson, B. D. O., & Yu, C. (2016). Request-based
with period not greater than m (by Theorem 3), it( follows) from gossiping without deadlocks. arXiv:1612.08463 [math.OC].
4 Mehyar, M., Spanos, D., Pongsajapan, J., Low, S. H., & Murray, R. M. (2007).
Lemma 4 that for any time t, there holds V (t + m) ≤ 1 − n2
V (t).
Asynchronous distributed averaging on communication networks. IEEE/ACM
We are thus led to the following result. Transactions on Networking, 15(3), 512–520.
Olfati-Saber, R., & Murray, R. M. (2004). Consensus seeking in networks of agents
with switching topology and time-delays. IEEE Transactions on Automatic Con-
Theorem 5. Suppose that all n agents follow Protocol III. Then
trol, 49(9), 1520–1533.
every sequence of gossip vectors x(t), t > 0 generated converges Olshevsky, A. (2010). Efficient information aggregation strategies for distributed con-
to the desired limit point exponentially fast at a rate no worse than trol and signal processing (Ph.D. thesis), Department of Electrical Engineering
( ) m1 and Computer Science, MIT.
4
1− n2
where m is the number of edges of A. Xiao, L., & Boyd, S. (2004). Fast linear iterations for distributed averaging. Systems &
Control Letters, 53(1), 65–78.
 J. Liu et al. / Automatica 93 (2018) 454–461 461

Ji Liu received the B.S. degree in information engineer- Brian D.O. Anderson was born in Sydney, Australia, and
ing from Shanghai Jiao Tong University, Shanghai, China, educated at Sydney University in mathematics and elec-
in 2006, and the Ph.D. degree in electrical engineering trical engineering, with Ph.D. in electrical engineering
from Yale University, New Haven, CT, USA, in 2013. He from Stanford University in 1966. Following graduation,
is currently an Assistant Professor in the Department of he joined the faculty at Stanford University and worked
Electrical and Computer Engineering at Stony Brook Uni- as Vidar Corporation of Mountain View, California, as staff
versity, Stony Brook, NY, USA. Prior to joining Stony Brook consultant. He then returned to Australia to become de-
University, he was a Postdoctoral Research Associate at partment chair in electrical engineering at the University
the Coordinated Science Laboratory, University of Illinois of Newcastle. He moved to the Australian National Uni-
at Urbana-Champaign, Urbana, IL, USA, and the School of versity in 1982, as the first engineering professor at that
Electrical, Computer and Energy Engineering at Arizona university. He is now Emeritus Professor at the Australian
State University, Tempe, AZ, USA. His current research interests include distributed National University, Distinguished Professor in Hangzhou Dianzi University and
control and computation, distributed optimization and machine learning, multi- Distinguished Researcher in Data61-CSIRO, formerly NICTA. During his period in
agent systems, social networks, epidemic networks, and power networks. academia, he spent significant time working for the Australian Government, with
this service including membership of the Prime Minister’s Science Council under the
chairmanship of three prime ministers. He also served on advisory boards or boards
Shaoshuai Mou has been working as an assistant profes- of various companies, including the world’s major supplier of cochlear implants,
sor at School of Aeronautics and Astronautics at Purdue Cochlear Corporation, where he was a director for ten years. His awards include
University since August 2015. He received his bachelor the IFAC Quazza Medal in 1999, IEEE Control Systems Award of 1997, the 2001
and master degree in Harbin Institute of Technology in IEEE James H Mulligan, Jr Education Medal, and the Bode Prize of the IEEE Control
2006 and 2008, respectively. He completed his Ph.D. study System Society in 1992, as well as IEEE and other best paper prizes, including Au-
at Prof. A. Stephen Morse’s group in Electrical Engineering tomatica. He is a Fellow of the Australian Academy of Science, Australian Academy
at Yale University in 2014. Then he worked as a post-doc of Technological Sciences and Engineering, Royal Society (London), and a foreign
at MIT for a year. During his Ph.D. study, he held a position member of the US National Academy of Engineering. He holds honorary doctorates
of visiting scholar at Australian National University and from a number of universities, including Université Catholique de Louvain, Belgium,
worked part-time for Yale Law School. He has received the and ETH, Zürich. He was IFAC President from 1990 to 1993, having served earlier
Yale University Raymond John Wean Fellowship (2009) in various IFAC roles, including Editor of Automatica. He was President of the
and the Chinese Government Award for Outstanding Students Abroad (2014). Australian Academy of Science from 1998 to 2002. His current research interests
His research interests include distributed optimizations and control, multi-agent are in distributed control, sensor networks and econometric modeling.
networks, and collaborations of UAVs.

A. Stephen Morse was born in Mt. Vernon, New York. Changbin (Brad) Yu received the B.Eng. (Hon 1) de-
He received a BSEE degree from Cornell University, M.S. gree from Nanyang Technological University, Singapore in
degree from the University of Arizona, and a Ph.D. de- 2004 and the Ph.D. degree from the Australian National
gree from Purdue University. He was associated with the University, Australia, in 2008. Since then he has been a
Office of Control Theory and Application {OCTA} at the faculty member at the Australian National University and
NASA Electronics Research Center in Cambridge, Mass. subsequently holding various positions including a spe-
Since 1970 he has been with Yale University where he is cially appointed professorship at Hangzhou Dianzi Univer-
presently the Dudley Professor of Engineering. His main sity.
interest is in system theory, and he has done research in He had won a competitive Australian Post-doctoral
network synthesis, optimal control, multivariable control, Fellowship (APD) in 2007 and a prestigious ARC Queen
adaptive control, urban transportation, vision-based con- Elizabeth II Fellowship (QEII) in 2010. He was also a re-
trol, hybrid and nonlinear systems, sensor networks, and coordination and control cipient of Australian Government Endeavour Asia Award (2005) and Endeavour Ex-
of large groupings of mobile autonomous agents. He is a Life Fellow of the IEEE, an ecutive Award (2015), Chinese Government Outstanding Overseas Students Award
IFAC Fellow, a past Distinguished Lecturer of the IEEE Control System Society, and (2006), Asian Journal of Control Best Paper Award (2006–2009), etc. His current re-
a co-recipient of the Society’s 1993 and 2005 George S. Axelby Outstanding Paper search interests include control of autonomous aerial vehicles, multi-agent systems
Awards. He has twice received the American Automatic Control Council’s Best Paper and human–robot interactions. He is a Fellow of Institute of Engineers Australia, a
Award and is a co-recipient of the Automatica Theory/Methodology Prize. He is the Senior Member of IEEE and a member of IFAC Technical Committee on Networked
1999 recipient of the IEEE Technical Field Award for Control Systems. He is the 2013 Systems. He served as a subject editor for International Journal of Robust and
recipient of the American Automatic Control Council’s Richard E. Bellman Control Nonlinear Control and was an associate editor for System & Control Letters and IET
Heritage Award. He is a member of the National Academy of Engineering and the Control Theory & Applications.
Connecticut Academy of Science and Engineering.