A Double-Layered Framework for Distributed Coordination in
Solving Linear Equations

arXiv:1711.10947v1 [cs.SY] 29 Nov 2017

Xuan Wang, Shaoshuai Mou, and Brian. D. O. Anderson

∗

November 30, 2017

Abstract
This paper proposes a double-layered framework (or form of network) to integrate two mechanisms, termed consensus and conservation, achieving distributed solution of a linear equation.
The multi-agent framework considered in the paper is composed of clusters (which serve as a
form of aggregating agent) and each cluster consists of a sub-network of agents. By achieving
consensus and conservation through agent-agent communications in the same cluster and clustercluster communications, distributed algorithms are devised for agents to cooperatively achieve
a solution to the overall linear equation. These algorithms outperform existing consensus-based
algorithms, including but not limited to the following aspects: first, each agent does not have
to know as much as a complete row or column of the overall equation; second, each agent only
needs to control as few as two scalar states when the number of clusters and the number of
agents are sufficiently large; third, the dimensions of agents’ states in the proposed algorithms
do not have to be the same (while in contrast, algorithms based on the idea of standard consensus inherently require all agents’ states to be of the same dimension). Both analytical proof and
simulation results are provided to validate exponential convergence of the proposed distributed
algorithms in solving linear equations.

1

Introduction

Distributed control of multi-agent networks has recently received a significant amount of research attention, the goal of which is to accomplish global objectives through local coordinations [1]. Consensus, which drives all agents in the network to reach an agreement regarding a certain quantity [2–7],
has served as a basis in deriving many distributed algorithms for optimization [8–12], synchronization of coupled oscillators [13], multi-robot formation control [14], cooperative sensing [15], and so
on. Most recently consensus has motivated distributed algorithms for solving linear algebraic equations [16–20], which achieve efficiency by decomposing a large system of linear equations into smaller
ones that can be cooperatively solved by a network of agents. Elegant as the idea of consensus is, it
has also limited application of consensus-based algorithms into situations when coordination among
agents requires more than reaching consensus, especially when conservation requirements are involved. Different from consensus, conservation is a constraint that the sum of functions of agents’
states needs to be constant. Various types of conservations arise in many engineering applications
including conservation of labor in ant colony [21], conservation of total energy in controlling hybrid
vehicles [22], conservation of flows in traffic control [23], conservation of linear and angular momentum in formation control [24], and so on. The idea of conservation has motivated researchers to
∗ X. Wang and S. Mou are with the School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN
47906 USA (e-mail: wang3156@purdue.edu, mous@purdue.edu). B. D. O. Anderson is with Hangzhou Dianzi University, Hangzhou, China, The Australian National University and Data-61 CSIRO (formerly NICTA), Canberra, ACT
2600 Australia, e-mail: Brian.Anderson@anu.edu.au; his work is supported by Data-61, CSIRO, and by the Australian
Research Council’s Discovery Projects DP-130103610 and DP-160104500. Corresponding Author: Shaoshuai Mou.

develop algorithms for distributed resource allocations [25–27], in which all agents aim to maximize
an objective function subject to a conservation constraint. Recognition of the potential of conservation in complementing consensus motives us to integrate both consensus and conservation together
in one framework with the goal of combining their advantages together for achieving efficiency of
distributed coordination.
One natural way to achieve such integration is by layered coordination [28], which has proved to
be a powerful tool in many similar situations. For example, practical tasks involving a large number
of robots can be achieved by coordination in the planning layer, executive layer and/or behavior
layer. [29, 30]. Complicated optimization problems can be solved by coordination through layers,
each of which iterates on its own subsets of decision variables using local information to achieve
individual optimality [31]. Deep learning algorithms can be established by grouping neural nodes
into multiple layers to achieve different functions including feature extraction, collection, comparison,
and fusion [32]. Compared with single-layered networks, double-layered networks (which also known
multiplex networks or networks of networks [33]), provide a natural description for quantifying
the interconnectivity between different categories of connections [34], improve accuracy [35], lead
to faster convergence [36, 37] and efficiency [38]. This has motivated us to employ double-layered
frameworks for the integration of consensus and conservation.
Similar to the architecture of mixing macro-cells and low-power nodes in mobile communication
networks [39, 40], we consider a double-layered multi-agent network composed of clusters and each
cluster consists of a network of agents. As a base station’ role in communication networks, a cluster
is able to communicate with other clusters and distribute information among agents within the
cluster. Without losing generality we still consider communication constraints on the information
flow among agents in each cluster. Such a double-layered multi-agent network allows the possibility
that consensus is taken care of either by the layer of clusters, or the layer of agents within the same
clusters, and conservation is taken care of by the other layer of the network. This architecture is
the basis for us to develop distributed algorithms for solving linear equations, which outperform
existing consensus-based distributed linear equation solvers [16–20] including but not limited to the
following aspects: first, each agent does not have to know as much as a complete row or column
of the overall equation; second, each agent only needs to control as few as two scalar states, this
being achieved when the number of clusters and the number of agents are equal to the number of
rows and columns of the overall equation, respectively; third, the dimensions of state vectors of all
agents in the proposed algorithms do not have to be the same, which is in contrast to algorithms
based on the idea of standard consensus. These consensus-based algorithms inherently require all
agents’ states to be of the same dimension. Further and differently from algorithms in [36–38], which
perform updates from lower layers to high layers in hierarchical networks for achieving consensus,
the proposed algorithms do not require updates in a hierarchical order, or multi-hop communications
among agents. Moreover, the layer of clusters is only responsible for communications without any
burden of computations.
The rest of this paper is organized as follows. In Section 2 we describe the structure and
information flow of a double-layer framework, and formulate the problem of solving linear equation.
According to different goals in the cluster layer and the agent layer, we then present two different
types of distributed algorithms for solving linear equations in Section 3 and Section 4, respectively.
Both algorithms are distributed and converge exponentially fast. Analytical proofs and simulations
are provided in these two sections. We finally conclude in Section 5 and provide proofs of lemmas
in Section 6.
Notation: Throughout this paper, we let 1r denote a vector in Rr with all its components equal
to 1; let Ir denote the r × r identity matrix. Let M 0 , ker M and image M denote the conjugate
transpose, the kernel and the image of a matrix M , respectively (Most but not all matrices and
vectors will be real). Let col {A1 , A2 , · · · , Ar } denote a column stack of matrices Ai , i = 1, 2, ..., r,

0
which is A01 A02 · · · A0r . Let diag {A1 , A2 , · · · , Ar } denote the block diagonal matrix with

Ai the ith diagonal block entry, i = 1, 2, · · · , r. Let ⊗ denote the Kronecker product.

2

Problem formulation

Consider a double-layer multi-agent network consisting of a number of c clusters, the i-th of which
is composed of a number of ci agents. Suppose each cluster i, i = 1, · · · , c, is able to receive
information from certain clusters which are called i’s cluster-neighbors denoted by Ni , specially we
assume i ∈ Ni . The neighbor relations of clusters can be characterized by a c-node graph G, in
which there is an arc from ī to i if and only if ī ∈ Ni . Within each cluster i, i = 1, · · · , c, each
agent ij , j = 1, · · · , ci , is able to receive information from certain agents, which are called agent
ij ’s agent-neighbors denoted by Nij , specially ij ∈ Nij . The neighbor relations in cluster i can be
characterized by a ci -node graph Gi , in which there is an arc from ij̄ to ij if and only if ij̄ ∈ Nij .
Suppose all Gi , i = 1, 2, ..., c and G are connected and bidirectional. 1 One example of such a
double-layer multi-agent network is shown in Fig. 1.

Cluster 1

11

12

13

14

Cluster 2

21
22

31

32

Cluster 3

23

𝑖𝑗

Agent 𝒋 of Cluster 𝒊
Agent communication
Cluster communication

Figure 1: An Example of a Double-layered Multi-Agent Network
Consider an overall linear equation
Ax = b
where A ∈ Rm×n and b ∈ Rm . Suppose Ax = b has at least one solution. Suppose each agent ij
knows part of the overall linear equation, which might not be as much as a complete row or column
of A, say. Let each agent ij control a state vector xij (t), while each cluster here does not control
any state and only plays the role of communications. The problem of interest is to develop a
distributed update for each agent such that all xij (t) converge to constant vectors x∗ij , j = 1, 2, ..., ci
and i = 1, 2, ..., c, which jointly form a solution to Ax = b.

3

Global-Consensus and Local-Conservation

Suppose each agent ij in a cluster i knows Aij ∈ Rmi ×nij and bij ∈ Rmi such that the collection of
them
ci
X


Ai1 Ai2 · · · Aici = Ai ∈ Rmi ×n ,
bij = bi ∈ Rmi
(1)
j=1
1 Here

we use bidirectional instead of undirected to emphasize the two-way information flows.

are a block row of the overall equation, where
 
A1
A2 
 
A =  . ,
 .. 

 
b1
b2 
 
b =  . .
 .. 

Ac

(2)

bc

Here, one has
ci
X

nij = n, i = 1, 2, ..., c,

j=1

c
X

mi = m.

(3)

i=1

Note that nij = 1 and mi = 1 are permitted, but are of course not required. Consistent with the
set-up of Fig. 1, an example of how each agent’s locally available information Aij , bij is related to
the overall equation Ax = b is shown in Fig. 2.

Figure 2: An example of the relation between agents’ locally available information and the overall
equation
Suppose each agent ij controls a state vector xij (t) ∈ Rnij . In this section, we aim to devise a
distributed update for each agent ij ’s state xij (t) to converge exponentially fast to a constant vector
x∗ij such that:
• All x∗ij , j = 1, 2, ..., ci within each cluster i, i = 1, 2, ..., c, satisfy the following
Local Conservation:

ci
X
(Aij x∗ij − bij ) = 0.

(4)

j=1

• All x∗i = col {x∗i1 , · · · , x∗ici }, i = 1, 2, ..., c, among all clusters in the network reach a consensus
x∗ , that is,
Global Consensus:
x∗1 = x∗2 = · · · = x∗c = x∗
(5)
From (1) and (4) one has Ai x∗i = bi . This and the global consensus in (5) imply Ax∗ = b. All
x∗ij satisfying the local conservation (4) and the global consensus (5) are said to form a consensusconservation solution x∗ to Ax = b.

3.1

The Update

Let xi (t) ∈ Rn denote a column collection of agent states in cluster i, i = 1, 2, ..., c, that is,
xi (t) = col {xi1 (t), · · · , xici (t)}.

(6)

To achieve a consensus-conservation solution x∗ , it is sufficient to achieve Ai xi (t) = bi while all
xi (t), i = 1, 2, ..., c, reach a consensus. In order to decompose the global consensus of xi (t) into
relations involving agents’ states, we let Eij ∈ Rnij ×n denote a matrix consisting of rows from In
such that col {Eij , j = 1, 2, ..., ci } = In and
0
Aij = Ai Eij
.

Then one has
xij (t) = Eij xi (t).
It follows that all xi (t) reaching a consensus is equivalent to requiring that ∀i = 1, · · · , ci and
∀k ∈ Ni ,
xij (t) → Eij xk (t).

(7)

To achieve the local conservation (4), one also introduces an additional coordination state zij (t) ∈
Rmi associated with and stored by each agent ij .
Suppose each cluster i is able to access xk (t), k ∈ Ni through cluster-cluster communications and
then distribute Eij xk (t) to each agent ij within the cluster i. Within each cluster i, each agent ij is
able to access its neighbors’ coordination state zik , ik ∈ Nij , through agent-agent communication in
cluster i. Then we propose the following update for each agent ij , i = 1, 2, ..., c and j = 1, 2, ..., ci ,
at time t:


X
ẋij = − A0ij Aij xij − bij −
(zij − zik )
ik ∈Nij

−

X

(xij − Eij xk )

(8)

k∈Ni

żij =Aij xij − bij −

X

(zij − zik )

(9)

ik ∈Nij

where the first line of update (8) and (9) aim to achieve the local conservation (4) while the second line
of update (8) aims to achieve the global-consensus (5). One natural generalization to the proposed
updates (8)-(9) is achievable by assigning different weights to controls for the local conservation and
the global consensus, respectively, with the aim of achieving faster convergence. Optimal choice
of such weights might however require more than locally available information, which will not be
discussed in this paper.
Note immediately that the proposed updates (8)-(9) are distributed in the sense that implementation of them only require communications of states xk (t) among cluster-neighbors and
communications of coordination states zik (t) among neighbor agents within the same cluster. Moreover, compared with existing consensus-based distributed linear equation solvers [16–20], distributed
updates (8)-(9)
• require much less knowledge of the overall equation and control states of much smaller
dimension. For a given A ∈ Rm×n of fixed size, each agent ij knows Aij ∈ Rmi ×nij and
bij ∈ Rmi , and controls states xij (t) ∈ Rnij , and zij (t) ∈ Rmi . Sizes of all these locally
available matrices and state vectors might change with respect to the number of clusters and
the number of agents in each cluster. To see why this is so, we note from (3) and partitions
in Fig. 2 that increasing c and ci leads to the decreases of mi and nij , respectively. Specially,
when the number of clusters is m and the number of agents within each cluster is n, that is,
c = m and ci = n, each agent only needs to know two scalar entries Aij ∈ R, bij ∈ R and
updates two scalar states, namely xij (t) ∈ R, zij (t) ∈ R.

• allow all agents’ state vectors to be of different dimensions while in contrast consensusbased distributed linear equation solvers require all agents to control states of the same size.
Thus the proposed updates might be applied in networks of heterogeneous agents with different
capability of storage.

3.2

Main result

Before proceeding, we first derive a compact form of (8)-(9). Towards this end, we let zi (t) ∈ Rci mi
denote the column collection of all agents’ coordination states in cluster i, that is,
zi (t) = col {zi1 (t), · · · , zici (t)},

i = 1, 2, ..., c.

(10)

Let
Āi = diag {Ai1 , · · · , Aici },

b̄i = col {bi1 , · · · , bici }

(11)

i = 1, 2, ..., c

(12)

and
L̄Gi = LGi ⊗ Imi ,

with LGi the Laplacian matrix of the ci -node connected and bidirectional graph Gi . Recalling
col {Eij , j = 1, 2, ..., ci } = In and (6), one can write equations (8) and (9) as:
 X
ẋi = − Ā0i Āi xi − b̄i − L̄Gi zi −
(xi − xk )
(13)
k∈Ni

żi =Āi xi − b̄i − L̄Gi zi

(14)

for i = 1, 2, ..., c. Each equation pair in the above describes what is occurring at a particular cluster.
Now let x = col {x1 , · · · , xc }, z = col {z1 , · · · , zc },
Â = diag {Āi , · · · , Āc },

b̂ = col {b̄i , · · · , b̄c },

L̂ = diag {L̄G1 , · · · , L̄Gc },

L̂G = LG ⊗ In

(15)
(16)

with LG Laplacian matrix of the c-node connected graph G. Equations (13)-(14) can be further
rewritten in the following compact form, which describes the behavior of the whole network:


ẋ = − Â0 Âx − b̂ − L̂z − L̂G x
(17)
ż = Âx − b̂ − L̂z

(18)

which is
 
   0 
ẋ
x
Â b̂
=Q
+
ż
z
−b̂

(19)

with

−Â0 Â − L̂G
Q=
Â


Â0 L̂
.

(20)

−L̂

To analyze the convergence of (19) we need the following lemma to characterize eigenvalues of Q.
Lemma 1 Let


−M10 M1 − M2
M =
M1

M10 M3




−M3

where the Mi are real, i = 1, 2, 3, and M2 and M3 are positive semi-definite. Then all eigenvalues
of M are real negative or 0. Moreover, if 0 is an eigenvalue of M , it must be non-defective2 .
The proof of Lemma 1 will be given in the Appendix. By this lemma and by establishing the
convergence of the linear time-invariant system (19) to a constant steady state, one has the following
main result.
Theorem 1 Suppose Ax = b has at least one solution, and the graphs Gi , i = 1, 2, ..., c, G are
connected and bidirectional. Then under the distributed updates (8)-(9), all xij (t) with i = 1, 2, · · · , c
and j = 1, 2, ..., ci converge exponentially fast to constant vectors x∗ij satisfying (4)-(5), which form
a consensus-conservation solution x∗ to Ax = b.
Proof of Theorem 1: We first prove that there exists a constant vector col {x̂, ẑ} which is an
equilibrium of (19). Recall there exists a constant vector y ∈ Rn such that Ay = b. From the
definitions of Aij , bij in (1)-(2) and Eij , one has
ci
X

(Aij Eij y − bij ) = 0,

i = 1, 2, ..., c,

j=1

This equation and definitions of Āi , b̄i in (11) lead to


10ci ⊗ Imi Āi y − b̄i = 0,

i = 1, 2, ..., c.

(21)

Note that L̄Gi = LGi ⊗ Imi , where LGi is the Laplacian matrix of a ci -node connected and bidirectional graph Gi . Then

image L̄Gi = ker 10ci ⊗ Imi , i = 1, 2, ..., c
(22)
From (21) and (22), one has

Āi y − b̄i ∈ image L̄Gi ,

i = 1, 2, ..., c.

(23)

Then there exists a constant vector ẑi ∈ Rci mi such that
Āi y − b̄i − L̄Gi ẑi = 0,

i = 1, 2, ..., c.

(24)

Let x̂ = 1c ⊗ y. Note that L̂G = LG ⊗ In with LG the Laplacian matrix of the c-node connected and
bidirectional graph G. Then
L̂G x̂ = 0
(25)
Let ẑ = {ẑ1 , ẑ2 , ..., ẑc }. From (24) and definitions of Â, b̂ in (15), one has
Âx̂ − b̂ − L̂ẑ = 0,
This equation and (25) imply that col {x̂, ẑ} is an equilibrium of (19).
Second, we analyze the convergence of the error

  
x(t)
x̂
e(t) =
−
.
z(t)
ẑ

(26)

(27)

From (19) and the fact that col {x̂, ẑ} is an equilibrium of (19), one has
ė = Qe

(28)

2 An eigenvalue is non-defective if any only if its algebraic multiplicity equals its geometric multiplicity. In other
words, the Jordan block corresponding to a non-defective eigenvalue is diagonal.

From Lemma 1, the structure of Q in (20) and the fact that the Laplacian matrices L̂ and L̂G are
symmetric and positive semi-definite, one concludes that all eigenvalues of Q are real negative or
0. Moreover, if 0 is an eigenvalue of Q, it must be non-defective. Thus there exists a constant
vector q ∈ ker Q such that e(t) of the linear time-invariant system (28) converges to q exponentially
fast [41]. Thus col {x̂(t), ẑ(t)} converges exponentially fast to a constant vector col {x̂∗ , ẑ ∗ }, where
 ∗  
x̂
x̂
=
+ q, q ∈ ker Q.
(29)
ẑ ∗
ẑ
Partition the constant vector x̂∗ such that
x̂∗ = col {x∗1 , · · · , x∗c }

(30)

where x∗i ∈ Rn is further partitioned as
x∗i = col {x∗i1 , x∗i2 , ..., x∗ici }

(31)

with x∗ij ∈ Rnij . Evidently, we have that xij (t) converges to x∗ij exponentially fast. In the following
one only needs to show that all these x∗ij satisfy the local conservation in (4) and the global consensus
in (5).
From (29) and the property that col {x̂, ẑ} is an equilibrium of (19), one concludes that col {x̂∗ , ẑ ∗ }
is also an equilibrium of (19). It follows that


0 = − Â0 Âx̂∗ − b̂ − L̂ẑ ∗ − L̂G x̂∗
(32)
0 = Âx̂∗ − b̂ − L̂ẑ ∗

(33)

Partition ẑ ∗ = col {z1∗ , z2∗ , ..., zc∗ } with zi∗ ∈ Rci mi . From (33) and the definitions of Â, b̂, L̂ in
(15)-(16), one has
Āi x∗i − b̄i − L̄Gi zi∗ = 0, i = 1, 2, ..., c.
(34)
From the definitions of Āi , b̄i , L̄Gi in (11)-(12), one can rewrite (34) as

  
Ai1 x∗i1
bi1
 Ai2 x∗i2   bi2 

  

 −  ..  − (LGi ⊗ Imi )zi∗ = 0.
..

  . 
.
Aici x∗ici

(35)

bici

Premultiplying by 10ci ⊗ Imi on both sides of (35), one has
ci
X

(Aij x∗ij − bij ) − [(10ci LGi ) ⊗ Imi ]zi∗ = 0.

j=1

Since LGi is the Laplacian of ci -node connected bidirectional graph Gi , one has 10ci LGi = 0. Thus
ci
X
(Aij x∗ij − bij ) = 0.

(36)

j=1

In addition, from (32)-(33), one has
L̂G x̂∗ = 0
where L̂G = LG ⊗ Im with LG the Laplacian matrix of the c-node connected and bidirectional graph
G. Thus there exists a constant vector x∗ such that
x̂∗ = 1c ⊗ x∗

(37)

Together with (30), this implies
x∗1 = x∗2 = · · · = x∗c = x∗

(38)

with x∗i a collection of x∗ij as defined in (31). From (36) and (38) one concludes that all x∗ij satisfy
the local conservation in (4) and the global consensus in (5).
Therefore, the xij (t) converge exponentially fast to constant vectors x∗ij which form a consensusconservation solution x∗ to Ax = b. This completes the proof.

3.3

Simulation

We utilize the double-layer network as in Fig. 1 to solve the linear equation Ax = b, which is
partitioned according to the structure as in Fig. 2 with details as follows:

Suppose each agent ij knows Aij and bij , and employ the updates (8) and (9) with arbitrary
initializations. Let


2
xi1 (t)
c
X
1
 .. 
∗
V (t) =
 . −x
2 i=1
xici (t)
2


0
where x∗ = 1.27 3.23 2.02 −0.88 −0.43 is a solution to Ax = b. Thus V (t) measures
the closeness of all agent states to forming a consensus-conservation solution. Simulations shown
in Fig. 3 suggest that V (t) converges exponentially fast to 0, which indicates all xij (t) converge
exponentially fast to constant vectors that form a consensus-conservation solution x∗ . This is in
accord with Theorem 1.
8

6

4

V (t)
2

0
0

10

20

30

40

50

60

70

80

90

100

t

Figure 3: Evolution of V (t) under the proposed updates (8)-(9)

4

Global-Conservation and Local-Consensus

In the previous section, agents in the same cluster jointly know a block row of the overall matrix A
as indicated in Fig. 2. In this section, we consider a different situation in which agents in the same
cluster jointly know a block column of A, for which different coordination will be required in the
cluster-layer and the agent-layer as will be shown later.

Suppose each agent ij in cluster i knows Aij ∈ Rmij ×ni , bij ∈ Rmij such that the collection of
them
 


bi1
Ai1
 bi2 
 Ai2 
 


(39)
 ..  = bi ∈ Rm
 ..  = Ai ∈ Rm×ni
 . 
 . 
bici
Aici
are parts of the overall linear equation Ax = b, where

A = A1

A2

···


Ac ,

b=

c
X

bi .

(40)

i=1

Then one has
ci
X

mij = m, i = 1, 2, ..., c,

j=1

c
X

ni = n.

(41)

i=1

An example of the relation between agents’ locally available information Aij , bij and the overall
equation Ax = b is shown in Fig. 4. Note that the symbols Aij and bi here are used differently from
their use in previous sections but the notation is convenient.

Figure 4: An example of the relation between agents’ locally available information and the overall
equation.
Suppose each agent each agent ij controls a state vector xij (t) ∈ Rni . In this section, we aim
to devise a distributed update for each agent ij ’s state xij (t) to converge exponentially fast to a
constant vector x∗ij , i = 1, 2, ..., c and j = 1, 2, ..., ci , such that
• All x∗ij , j = 1, 2, ..., ci , within each cluster i reach a consensus x∗i , that is,
Local Consensus:

x∗i1 = x∗i2 = · · · = x∗ici = x∗i

(42)

• All x∗i , i = 1, 2, ..., c among all clusters in the network satisfy the following
Global Conservation:

c
X

(Ai x∗i − bi ) = 0

(43)

i=1

Let x∗ = col {x∗1 , x∗2 , ..., x∗c } be the column collection of the consensus value to which all agents in
the same cluster converge. From (40) and (43) one has Ax∗ = b. Thus the x∗ij satisfying the local
consensus (42) and the global conservation (43) are said to form a conservation-consensus solution
x∗ to Ax = b.
Note that here all x∗ij in the same cluster are the same, which is part of the solution to the overall
equation, while, in contrast, in the consensus-conservation solution defined in the previous section,
the x∗ij in each cluster i jointly form a solution to the overall equation Ax = b.

4.1

The Update

In order to achieve the global conservation, we introduce an additional state zij (t) ∈ Rmij at each
agent ij . Let Eij ∈ Rmij ×m consist of rows of the identity matrix Im such that col {Eij , j =
1, 2, ..., ci } = Im and
Aij = Eij Ai .
Let zi (t) ∈ Rm denote the column of all coordination states in cluster i, i = 1, 2, ..., ci , that is,
zi = col {zi1 , zi2 , ..., zici }.
Then
zij = Eij zi .
Suppose each cluster i is able to access its neighbor cluster’s coordination state zk (t), k ∈ Ni
through cluster-cluster communication and then distributes Eij zk (t) to each agent ij within cluster
i. Within each cluster i, each agent ij is able to access to its neighbors’ state xik , ik ∈ Nij , through
agent-agent communication in cluster i. Then one proposes the following update for each agent ij ,
i = 1, 2, ..., c and j = 1, 2, ..., ci , at time t:
!
X
0
ẋij = − Aij Aij xij − bij −
(zij −Eij zk )
k∈Ni

−

X

(xij − xik )

(44)

ik ∈Nij

żij = Aij xij − bij −

X

(zij − Eij zk )

(45)

k∈Ni

where the first line of update (44) and (45) aim to achieve global conservation in (43) while the
second line of (44) aims to achieve the local consensus in (42).
Note immediately that the proposed updates (44)-(45) are distributed in the sense that implementation of them only require communication of coordination states zk (t) among cluster-neighbors
and communication of states xij (t) among neighbor agents within the same cluster. Moreover, compared with existing consensus-based distributed linear equation solvers [16–20], distributed updates
(44)-(45) proposed in this paper
• require much less knowledge of the overall equation and control states of much smaller
dimension. For a given overall linear equation with A ∈ Rm×n , each agent ij knows Aij ∈
Rmij ×ni and bij ∈ Rmij , and controls states xij (t) ∈ Rni , and zij (t) ∈ Rmij . Sizes of these
locally available matrices and state vectors could change with respect to the number of clusters
and the number of agents in each cluster. From (41) and partitions in Fig. 4, one has that
increasing ci and c leads to the decreases of mij and ni , respectively. Specially, when the
number of clusters is n and the number of agents within each cluster is m, that is, c = n and
ci = m, each agent only needs to know two scalar entries Aij ∈ R, bij ∈ R and updates two
scalar states, namely xij (t) ∈ R, zij (t) ∈ R.
• allow all agents’ state vectors to be of different dimensions, which is the same as the
distributed updates (8)-(9) in previous section.

4.2

Main result

Before proceeding, we first derive a compact form of (44)-(45). Towards this end, we let xi ∈ Rci ni
denote the column collection of all agents’ states in cluster i, i = 1, 2, ..., c, that is,
xi = col {xi1 , xi2 , ..., xici }.

Let
Āi = diag {Ai1 , · · · , Aici },

L̄Gi = LGi ⊗ Ini

(46)

with LGi the Laplacian matrix of the ci -node connected graph Gi . From equations (44)-(45) and
col {Eij , j = 1, 2, ..., ci } = Im , one has
!
X
0
(zi − zk ) − L̄Gi xi
ẋi = − Āi Āi xi − bi −
(47)
k∈Ni

żi =Āi xi − bi −

X

(zi − zk )

(48)

k∈Ni

for i = 1, 2, ..., c. Let x = col {x1 , · · · , xc } and z = col {z1 , · · · , zc },
Â = diag {Āi , · · · , Āc },

b̂ = col {bi , · · · , bc },

L̂ = diag {L̄G1 , · · · , L̄Gc },

L̂G = LG ⊗ Im

(49)
(50)

with LG the Laplacian matrix of the c-node connected graph G. Equations (47)-(48) can be written
in the following compact form:


ẋ = − Â0 Âx − b̂ − L̂G z − L̂x
(51)
ż = Âx − b̂ − L̂G z

(52)

which is
   0 
 
Â b̂
ẋ
x
=Q
+
ż
z
−b̂

(53)

with


−Â0 Â − L̂ Â0 L̂G
.
Q=
Â

(54)

−L̂G

Theorem 2 Suppose Ax = b has at least one solution, and the graphs Gi , i = 1, 2, ..., c and G
are connected and bidirectional. Then under the distributed updates (44) and (45), all xij (t) with
i = 1, 2, · · · , c and j = 1, 2, ..., ci converge exponentially fast to constant vectors x∗ij which satisfy
the local consensus (42) and the global conservation (43) and thus form a conservation-consensus
solution x∗ to Ax = b.
Proof of Theorem 2: We first prove that there exists a constant vector col {x̂, ẑ} which is an
equilibrium of (53). Since there exists a constant vector y ∈ Rn such that Ay = b, using the
definition of Ai , bi in (40), one has


A1

A2

···

c
X

Ac y =
bi
i=1

Partition y = col {y1 , · · · , yc } with yi ∈ Rni . Then one has
c
X
i=1

(Ai yi − bi ) = 0

It follows from this and (39) that
 


bi1
Ai1
c
X
 .. 
 .. 
y
−
 .  i  .  = 0
i=1
bici
Aici
This and the definitions of Āi in (46) imply
c
X

(Āi yi − bi ) = 0

(55)

i=1

with yi = 1ci ⊗ yi . Let x̂ = col {y1 , · · · , yc }. From (55) and the definitions of Â, b̂ in (49), one has


(10c ⊗ Im ) Âx̂ − b̂ = 0
(56)
Recall that L̂G = LG ⊗ Im with LG the Lapalacian matrix of a c-node connected, bidirectional graph
G. Then
image L̂G = ker (10c ⊗ Im )

(57)


Âx̂ − b̂ ∈ image L̂G .

(58)

which with (56) implies


Then there exists a constant vector ẑ such that
Âx̂ − b̂ − L̂G ẑ = 0

(59)

In addition, since L̄Gi = LGi ⊗ Ini with LGi ⊗ Ini the Laplacian matrix of the ci -node connected
graph Gi , and since yi = 1ci ⊗ yi , one has
L̄Gi yi = 0,

i = 1, 2, ..., c.

Then because L̂ = diag {L̄G1 , · · · , L̄Gc } and x̂ = col {y1 , · · · , yc }, one has
L̂x̂ = 0
together with (59), this implies that col {x̂, ẑ} is an equilibrium of (53).
Second, we analyze the convergence of the error

  
x(t)
x̂
e(t) =
−
.
z(t)
ẑ

(60)

(61)

From (53) and the fact that col {x̂, ẑ} is an equilibrium of (53), one has
ė = Qe

(62)

From Lemma 1, the structure of Q in (54) and the fact that Laplacian matrices L̂ and L̂G are
symmetric and positive semi-definite, one has all eigenvalues of Q are real negative or 0. Moreover,
if 0 is an eigenvalue of Q, it must be non-defective. Thus there exists a constant vector q ∈ ker Q
such that e(t) of the linear time-invariant error system (62) converges to q exponentially fast [41].
Thus col {x̂(t), ẑ(t)} converges exponentially fast to a constant vector col {x̂∗ , ẑ ∗ }, where
 ∗  
x̂
x̂
=
+ q, q ∈ ker Q.
(63)
ẑ ∗
ẑ

Partition the constant vector x̂∗ such that
x̂∗ = col {x̄∗1 , · · · , x̄∗c }

(64)

where x̄∗i ∈ Rci ni is further partitioned as
x̄∗i = col {x∗i1 , x∗i2 , ..., x∗ici }

(65)

with x∗ij ∈ Rni . Evidently, xij (t) converges to x∗ij exponentially fast. In the following one only needs
to show that all these x∗ij satisfy the local consensus (42) and the global conservation (43).
From (63) and the property that col {x̂, ẑ} is an equilibrium of (53), one has col {x̂∗ , ẑ ∗ } is an
equilibrium of (53). Then


0 = − Â0 Âx̂∗ − b̂ − L̂G ẑ ∗ − L̂x̂∗
(66)
0 = Âx̂∗ − b̂ − L̂G ẑ ∗

(67)

It follows that
L̂x̂∗ = 0

(68)

From this, (64) and the definition of L̂, one has
L̄Gi x̄∗i = 0,

i = 1, 2, ..., c.

(69)

Note that L̄Gi = LGi ⊗ Ini with LGi the Laplacian matrix of a connected bidirectional graph Gi .
Then there must be a constant vectors x∗i ∈ Rni such that
x̄∗i = 1ci ⊗ x∗i .

(70)

x∗i1 = x∗i2 = · · · = x∗ici = x∗i

(71)

This and (65) imply
for i = 1, 2, ..., c.
From (70), the partition of Ai in (39) and Āi = diag {Ai1 , · · · , Aici } in (46), one has
Āi x̄∗i = Ai x∗i
From (67) and the definitions of Â, b̂, L̂G , one has

  
Ā1 x̄∗1
b1
Ā2 x̄∗2  b2 

  
 ..  −  ..  − (LG ⊗ Im )ẑ = 0
 .  .
Āc x̄∗c

(72)

(73)

bc

This equality and (72) imply

  
A1 x∗1
b1
A2 x∗2  b2 

  
 ..  −  ..  − (LG ⊗ Im )ẑ = 0
 .  .
Ac x∗c

(74)

bc

Premultiplying by 10c ⊗ Im on both sides of (74), one has
c
X
i=1

(Ai x∗i − bi ) − [(10c LG ) ⊗ Im ]ẑ = 0.

(75)

Note that LG is the Laplacian matrix of a c-node connected and bidirectional graph G, one has
10c LG = 0. Thus
c
X
(Ai x∗i − bi ) = 0.
(76)
i=1

x∗ij

From (71) and (76), one sees all
satisfy the local consensus (42) and the global conservation
(43). Therefore all xij (t) converge to constant vectors and thus form a conservation-consensus
solution x∗ to Ax = b. This completes the proof.

4.3

Simulations

We utilize the double-layer network as in Fig. 1 to solve the linear equation Ax = b, which is
partitioned according to the structure in Fig. 4 with details as follows:

Suppose each agent ij knows Aij and bij , and employ the updates (44) and (45) with arbitrary
initializations . Let x∗ = col {x∗1 , x∗2 , x∗3 } where x∗1 = col {0.84, 2.87}, x∗2 = col {1.99, −1.07}, and
x∗3 = 0.25. Then x∗ is a solution to Ax = b. Let
3

V (t) =

c

i
1 XX
kxij (t) − x∗i k22
2 i=1 j=1

Then V (t) measures the closeness of all agent states to forming a conservation-consensus solution.
Simulations shown in Fig. 5 suggest that V (t) converges exponentially fast to 0, which indicates all
xij (t) converge exponentially fast to constant vectors that form a consensus-conservation solution
x∗ . This is consistent with Theorem 2.
6
5
4

V (t)

3
2
1
0
0

10

20

30

40

50

60

70

80

90

100

t

Figure 5: Evolution of V (t) under distributed updates (44)-(45)

5

Conclusion

This paper has devised distributed algorithms in a double-layered multi-agent framework for solving
linear equations, which consists of clusters and each cluster is composed of a network of agents.

In these distributed algorithms, each agent is not required to know as much as a complete row or
column of the overall linear equation. Both analytical proof and simulation results are provided to
validate exponential convergence. Future work includes generalization of the proposed algorithms
to time-varying directed networks, application to achieving least square solutions, investigation of
the impact when different weights are assigned to the conservation and consensus, and distributed
algorithms in networks of more than two layers.

6

Appendix

Proof of Lemma 1: Let λ denote any eigenvalue of M with a non-zero eigenvector col {u, ū}.
Then
 
 
u
u
M
=λ
(77)
ū
ū
with


I
Let M̄ =
0


−M10 M1 − M2

M=
M1

M10 M3


.

−M3



0
M . Then one has
M30

−M10 M1 − M2

M̄ =
M30 M1

which can be written as

M10 M3
−M30 M3





M10 
M1
−M30






M2 0
−M3 −
.
(78)
0 0
 0 

u
I
0
on both sides of (77), one has
Thus M̄ is negative semi-definite. Premultiplying by
ū
0 M30
 0 
 
 0  
u
u
I
0
u
u
M̄
=λ
(79)
ū
ū
0 M3 ū
ū
M̄ = −

First, we prove that λ must be real by contradiction. Suppose λ = α + βi where β 6= 0. Since
M̄ is negative semi-definite, then the imaginary part of the left-hand side of (79) is 0. So therefore
is the imaginary part of the right-hand side. It follows that
 0 
 
u
I
0
u
β
=0
ū
0 M3 ū
Since β 6= 0 there follows
u0 u + ū0 M3 ū = 0.
Recall that M3 positive semi-definite. Hence
u = 0,

M3 ū = 0

Taken with (77) and noting λ 6= 0 since β 6= 0, one has ū = 0. This and the assumption that u = 0
contradict to the fact that col {u, ū} is non-zero. Thus β = 0. Therefore, λ is real. From this, (79),
M̄ is negative semi-definite and M3 is positive semi-definite, one has
λ ≤ 0.

Second, if λ = 0 is an eigenvalue of M , we prove that it must be non-defective by contradiction.
Suppose λ = 0 is defective, then there exists a non-zero vector col {v, v̄} such that
   
v
u
M
=
(80)
v̄
ū
and
 
u
M
=0
ū
 0 
u
I
Premultiplying by
ū
0


0
on both sides of (80), one has
M30
 0  
u
v
M̄
= (u0 u + ū0 M30 ū)
ū
v̄

Premultiplying by


I
0

(81)

(82)


0
on both sides of (81), one has
M30
M̄

 
u
=0
ū

(83)

This and the fact that M̄ is symmetric imply that the left hand side of (82) is 0. Then
(u0 u + ū0 M30 ū) = 0

(84)

from which, using the fact that M3 is positive semi-definite, one has
u = 0,
Premultiplying by

 0 
v
I
v̄
0

M30 ū = 0.

(85)


0
on both sides of (80) one has
M30
 0    0 
v
v
vu
M̄
= 0 0
v̄
v̄
v̄ M3 ū

The right-hand side is 0 by (85). Thus
 0  
v
v
M̄
= 0,
v̄
v̄

(86)

Together with (76), this yields
M1 v − M3 v̄ = 0,

M2 v = 0.

(87)

From this and the definition of M , one has
 
v
= 0,
M
v̄
By (80), this yields col {u, ū} = 0, contradicting the assumption that col {u, ū} is a non-zero
eigenvector. Thus, λ = 0 is non-defective.

References
[1] F. Bullo, J. Cortes, and S. Martinez, Distributed Control of Robotic Networks.
University Press, 2009.

Princeton

[2] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents
using nearest neighbor rules,” IEEE Transactions on Automatic Control, vol. 48, no. 6, pp.
988–1001, 2003, also in Proc. 41st IEEE CDC, pages 2953 - 2958, 2002.
[3] M. Cao, A. S. Morse, and B. D. O. Anderson, “Reaching a consensus in a dynamically changing
enviornment: a graphical approach,” SIAM Jounal on Control and Optimization, vol. 47, no. 2,
pp. 575–600, 2008.
[4] R.Olfati-Saber and R. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1520–1533,
2004.
[5] W. Ren and R. W. Beard, “Consensus seeking in multiagent systems under dynamically changing interaction topologies,” IEEE Transactions on Automatic Control, vol. 50, no. 5, pp. 655–
661, May 2005.
[6] M. Cao, A. S. Morse, and B. D. O. Anderson, “Agree asychronously,” IEEE Transactions on
Automatic Control, vol. 53, no. 8, pp. 1826–1838, 2008.
[7] J. Qin, W. Zheng, and H. Gao, “Consensus of multiple second-order vehicles with a time-varying
reference signal under directed topology,” Automatica, pp. 1983–1991, Sep. 2011.
[8] A. Nedic and A. Ozdaglar, “Distributed sub-gradient methods for multi-agent optimization,”
IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009.
[9] J. C. Duchi, A. Agarwal, and M. J. Wainwright, “Dual averaging for distributed optimization:
Convergence analysis and network scaling,” IEEE Transactions on Automatic Control, vol. 57,
no. 3, pp. 592–606, 2012.
[10] T. Chang, A. Nedic, and A. Scaglione, “Distributed constrained optimization by consensusbased primal-dual perturbation method,” IEEE Transactions on Automatic Control, vol. 59,
no. 6, pp. 1524–1538, 2014.
[11] X. Zeng, P. Yi, and Y. Hong, “Distributed continuous-time algorithm for constrained convex
optimizations via nonsmooth analysis approach,” IEEE Transactions on Automatic Control,
vol. 62, no. 10, pp. 5227–5233, 2017.
[12] Q. Liu, S. Yang, and Y. Hong, “Constrained consensus algorithms with fixed step size for
distributed convex optimizations over multiagent networks,” IEEE Transactions on Automatic
Control, vol. 62, no. 8, pp. 4259–4265, 2017.
[13] F. Dorfler, M. Chertkov, and F. Bullo, “Synchronization in complex oscillator networks and
smart grids,” Proceedings of the National Academy of Sciences, vol. 110, no. 6, pp. 2005–2010,
2013.
[14] J. A. Fax and R. M. Murray, “Information flow and cooperative control of vehicle formations,”
IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1465–1476, 2004.
[15] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,” IEEE Transactions on Robotics and Automation, vol. 20, no. 2, pp. 243–255, 2004.

[16] S. Mou, J. Liu, and A. S. Morse, “A distributed algorithm for solving a linear algebraic equation,” IEEE Transactions on Automatic Control, vol. 60, no. 11, pp. 2863–2878, 2015.
[17] S. Mou, Z. Lin, L. Wang, D. Fullmer, and A. S. Morse, “A distributed algorithm for efficiently
solving linear equations and its applications (special issue jcw),” Systems & Control Letters,
vol. 91, pp. 21–27, 2016.
[18] B. D. O. Anderson, S. Mou, U. R. Helmke, and A. S. Morse, “Decentralized gradient algorithm
for solution of a linear equation,” Numerical Algebra, Control and Optimization, vol. 6, no. 3,
pp. 319–328, 2016.
[19] X. Wang, S. Mou, and D. Sun, “Improvement of a distributed algorithm for solving linear
equations,” IEEE Transactions on Industrial Electronics, no. 4, pp. 3113–3117, 2017.
[20] G. Shi, B. D. O. Anderson, and U. Helmke, “Network flows that solve linear equations,” IEEE
Transactions on Automatic Control, vol. 62, no. 6, pp. 2659–2674, June 2017.
[21] G. E. Robinson, “Regulation of division of labor in insect societies,” Annual review of entomology, vol. 37, no. 1, pp. 637–665, 1992.
[22] J. Liu and H. Peng, “Modeling and control of a power-split hybrid vehicle,” IEEE Transactions
on Control Systems Technology, vol. 16, no. 6, pp. 1242–1251, Nov 2008.
[23] M. Treiber and A. Kesting, Traffic flow dynamics: data, models and simulation.
Science & Business Media, 2012.

Springer

[24] Z. Sun, S. Mou, B. D. O. Anderson, and C. Yu, “Conservation and decay laws in distributed
coordination control systems,” Automatica, pp. 1–7, 2018.
[25] E. Bonabeau, A. Sobkowski, G. Theraulazy, and J. L. Deneubourg, “Adaptive task allocation
inspired by a model of division of labor in social insects.” in BCEC, 1997, pp. 36–45.
[26] C. Li, X. Yu, T. Huang, and X. He, “Distributed optimal consensus over resource allocation
network and its application to dynamical economic dispatch,” IEEE Transactions on Neural
Networks and Learning Systems, vol. PP, no. 99, pp. 1–12, 2017.
[27] Y. Xu, Y. Hu, Q. Chen, R. Chai, and G. Li, “Distributed resource allocation for cognitive
hetnets with cross-tier interference constraint,” in 2017 IEEE Wireless Communications and
Networking Conference (WCNC), March 2017, pp. 1–6.
[28] M. D. Domenico, A. Solé-Ribalta, E. Cozzo, M. Kivelä, Y. Moreno, M. A. Porter, S. Gómez,
and A. Arenas, “Mathematical formulation of multilayer networks,” Physical Review X, vol. 3,
no. 4, p. 041022, 2013.
[29] R. Simmons, T. Smith, M. D. Dias, D. Goldberg, D. Hershberger, A. Stentz, and R. Zlot, “A
layered architecture for coordination of mobile robots,” Multi-Robot Systems: From Swarms to
Intelligent Automata, pp. 103–112, 2002.
[30] R. Fierro, A. Das, J. Spletzer, J. Esposito, V. Kumar, J. P. Ostrowski, G. Pappas, C. J. Taylor,
Y. Hur, R. Alur, I. Lee, G. Grudic, and B. Southall, “A framework and architecture for multirobot coordination,” The International Journal of Robotics Research, vol. 21, no. 10-11, pp.
977–995, 2002.
[31] M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle, “Layering as optimization decomposition: A mathematical theory of network architechtures,” Proceedings of the IEEE, vol. 95,
no. 1, pp. 255–312, 2007.

[32] J. Schmidhuber, “Deep learning in neural networks: An overview,” Neural networks, vol. 61,
pp. 85–117, 2015.
[33] Q. Guo, E. Cozzo, Z. Zheng, and Y. Moreno, “Levy random walks on multiplex networks,”
Scientific reports, vol. 6, 2016.
[34] S. Gomez, A. Diaz-Guilera, J. Gomez-Gardenes, C. J. Perez-Vicente, Y. Moreno, and A. Arenas,
“Diffusion dynamics on multiplex networks,” Physical review letters, vol. 110, no. 2, p. 028701,
2013.
[35] J. M. Jeanne and R. I. Wilson, “Convergence, divergence, and reconvergence in a feedforward
network improves neural speed and accuracy,” Neuron, vol. 88, no. 5, pp. 1014–1026, 2015.
[36] M. Epstein, K. Lynch, K. H. Johansson, and R. M. Murray, “Using hierarchical decomposition
to speed up average consensus,” Proceedings of the 17th IFAC World Congress, vol. 41, no. 2,
pp. 612–618, 2008.
[37] I. Trpevski, A. Stanoev, A. Koseska, and L. Kocarev, “Discrete-time distributed consensus on
multiplex networks,” New Journal of Physics, vol. 16, no. 11, p. 113063, 2014.
[38] K. I. Tsianos and M. G. Rabbat, “Multiscale gossip for efficient decentralized averaging in
wireless packet networks,” IEEE Transactions on Signal Processing, vol. 61, no. 9, pp. 2137–
2149, 2013.
[39] A. Damnjanovic, J. Montojo, Y. Wei, T. Ji, T. Luo, M. Vajapeyam, T.Yoo, O. Song, and
D. Malladi, “A survey on 3gpp heterogeneous networks,” IEEE Wireless Communications,
vol. 18, no. 3, pp. 10–21, 2011.
[40] G. Mao, Z. Zhang, and B. D. O. Anderson, “Cooperative content dissemination and offloading
in heterogeneous mobile networks,” IEEE Transactions on Vehicular Technology, vol. 65, no. 8,
pp. 6573–6587, 2016.
[41] M. H. H. Trentelman, A. A. Stoorvogel, Control theory for linear systems. Springer Science &
Business Media, 2012.

