# Stability and Resilience of Distributed Information Spreading in Aggregate
Computing

Yuanqiu Mo, , Soura Dasgupta, and Jacob Beal  This work has been supported by
the Defense Advanced Research Projects Agency (DARPA) under Contract No.
HR001117C0049. The views, opinions, and/or findings expressed are those of the
author(s) and should not be interpreted as representing the official views or
policies of the Department of Defense or the U.S. Government. This document
does not contain technology or technical data controlled under either U.S.
International Traffic in Arms Regulation or U.S. Export Administration
Regulations. Approved for public release, distribution unlimited (DARPA DISTAR
case 33519, 10/14/20).Y. Mo is with the Institute of Advanced Technology,
Westlake Institute for Advanced Study, Westlake University, Hangzhou 310024,
China (email: moyuanqiu@@westlake.edu.cn). S. Dasgupta is with the University
of Iowa, Iowa City, Iowa 52242 USA (e-mail: soura-dasgupta@uiowa.edu). S.
Dasgupta is also a Visiting Professor at Shandong Computer Science Center,
Shandong Provincial Key Laboratory of Computer Networks, China.J. Beal is with
Raytheon BBN Technologies, Cambridge, MA, USA 02138 USA (e-mail:
<EMAIL_ADDRESS>
###### Abstract

Spreading information through a network of devices is a core activity for most
distributed systems. As such, self-stabilizing algorithms implementing
information spreading are one of the key building blocks enabling aggregate
computing to provide resilient coordination in open complex distributed
systems. This paper improves a general spreading block in the aggregate
computing literature by making it resilient to network perturbations,
establishes its global uniform asymptotic stability and proves that it is
ultimately bounded under persistent disturbances. The ultimate bounds depend
only on the magnitude of the largest perturbation and the network diameter,
and three design parameters trade off competing aspects of performance. For
example, as in many dynamical systems, values leading to greater resilience to
network perturbations slow convergence and vice versa.

###### Index Terms:

aggregate computing, multi-agent systems, distributed graph algorithms,
nonlinear stability, ultimate bounds.

##  I Introduction

Complex networked distributed systems are rapidly becoming a feature of many
engineering systems. Their stability, dynamics and reliability has acquired
paramount importance. Control theorists have embraced this challenge through
extensive research on the stability of networked control systems, most
typically “closed” systems in which a good model of the system is available at
design time e.g. [1, 2, 3, 4, 5, 6, 7, 8, 9].

An emerging set of alternative challenges is posed by the analysis and design
of complex open systems like tactical information sharing, smart cities, edge
computing, personal and home area networks, and the Internet of Things (IoT)
[10]. These systems also disperse services to local devices, require devices
to interact _safely and seamlessly_ with nearby brethren through peer to peer
information exchange, and to share tasks. As they are _open_ , however, they
must support frequent non-centralized changes in the applications and services
that they host. Current modes of device interactions restrict their potential
by being typically either highly constrained and inflexible (e.g. single-
purpose devices) or by relying on remote infrastructure like cloud services.
The former impairs reusability and prevents devices from contributing to
multiple overlapping applications. The latter is centralized with high latency
and lacks the agility to exploit local communication, services and devices.

_Aggregate computing_ , on the other hand, addresses device coordination in
open systems with a layered approach [10], separating systems into abstraction
layers that decomposing systems engineering into separable tasks, much like
the OSI model does for communication networks, [11]. The layers span from
applications to a field calculus (providing distributed scoping of shared
information), and an abstract device model (for services such as neighborhood
discovery). Between these, a middle layer facilitates resilient device
interactions and comprises three classes of basis set modules that are
themselves distributed graph algorithms: (i) $G$-blocks that spread
information through a network of devices, (ii) $C$-blocks that summarize
salient information about the network to be used by interacting units, and
(iii) $T$-blocks that maintain temporary state. Prior work [12, 13, 14], has
shown _that a broad class of device interactions can be realized by
interconnections of these three blocks_. Our long term research goal is
analyze the stability of compositions of these blocks including in feedback.
This paper is concerned with a rigorous analysis of the most general $G$-block
of [14], _after making it resilient to network perturbations_.

While the empirical assessment of compositions of the $G$-block with other
blocks is encouraging[15, 16, 17], the formal analysis of its most general
case has been confined to self-stablization [14], and that under the
assumption that all states lie in Noetherian rings and are thus _a priori
bounded_. Unlike global uniform asymptotic stability (GUAS) [18, 19], self-
stabilization has no notion of robustness to perturbations, while
perturbations are to be expected in any feedback composition. Thus we improve
the generalized $G$-block to allow removal of the Noetherian assumption, proof
of GUAS, and (under an additional Lipschitz condition) ultimate boundedness in
face of persistent perturbations. Finding ultimate bounds further anticipates
the development of sophisticated variants of the small gain theorem [20], [18]
for closed loop analysis.

Previously, in [21] and [22], we have performed such an analysis of the
simplest $G$-block, the Adaptive Bellman-Ford (ABF) algorithm, which estimates
distances of nodes from a source set in a distributed manner and (unlike the
classical Bellman-Ford algorithm [23]) accommodates underestimates. In [24] we
have analyzed _without proof_ another special case, which generalizes ABF by
allowing non-Euclidean distance metrics, e.g., those that penalize certain
routes, and permits _broadcast_ , where each source broadcasts a value like a
diameter estimate it holds to nearest devices. More features are given Section
II.

A further problem that must be considered in this context is the _rising value
problem_. All $G$-block algorithms generate estimates $\hat{x}_{i}(t)$ that
must converge to a value $x_{i}$. The rising value problem is when
underestimates ( i.e. $\hat{x}_{i}(t)<x_{i}$) may rise very slowly, and this
problem affects the $G$-blocks analyzed in [22] and [24]. The most general
$G$-block given in [14] removes this problem by treating the estimate
generated by the algorithm in [24] as an auxiliary state $\tilde{x}_{i}(t)$.
The actual estimate $\hat{x}_{i}(t)$ is increased by a fixed amount of at
least $\delta>0$ unless $\tilde{x}_{i}(t+1)$ equals either $\hat{x}_{i}(t)$ or
the maximal element in the Noetherian ring. If either of these two conditions
is violated then $\hat{x}_{i}(t+1)=\tilde{x}_{i}(t+1).$ The increase by
$\delta$ or more, removes the rising value problem. However the equality
requirement of $\tilde{x}_{i}(t+1)=\hat{x}_{i}(t)$ introduces fragility to
disturbances, since $\tilde{x}(t+1)=\hat{x}_{i}(t)$ rarely occurs under
perturbations and thus $\hat{x}_{i}(t)$ must persistently rise to the maximal
element.

We deal with real non-negative numbers rather than Noetherian rings and _do
not assume prior estimate bounds_. Instead we modify the algorithm in [14] by
introducing two additional parameters, a modulation threshold $M$ and a dead
zone value $D$, that together define regions for improved perturbation
tolerance versus regions for fast convergence with $\delta$, and that reduce
to the algorithm in [24] when $M=0$ and/or $D=\infty.$ We show that the
improved algorithm is GUAS for all non-negative $M$ and $D$ _without the
assumption_ that $M$ _is a maximal element_. In the case of persistent bounded
perturbations, we show that the estimates are ultimately bounded provided that
the dead zone parameter $D$ exceeds a value proportional to the disturbance
bound. A larger $D$, however, is also less effective at mitigating the rising
value problem, indicating a trade-off between speed and robustness that is
common to most dynamical systems.

In the remainder of the paper, Section II provides the algorithm, assumptions
and motivating applications. Section III characterizes stationary points,
while Section IV proves GUAS. Section V gives ultimate bounds _which are
determined only by the magnitude of the perturbations and the graph._ Section
VI discusses design choices, which are affirmed via simulation in Section VII,
and Section VIII concludes.

##  II Algorithm

In this section, we present a general $G$-block that spreads information
through a network in a distributed fashion. Originally provided in [25] using
the language of field calculus, we translate it here to one more appropriate
of this journal. Section II-A describes a special case shown to be GUAS in
[24], with proofs omitted, plus examples and a shortcoming. Section II-B then
presents a more general algorithm that removes this deficiency, and Section
II-C provides assumptions and definitions that will be used for proofs in
subsequent sections.

###  II-A The Spreading block of[24]

Consider an undirected graph ${\cal G}=(V,E)$ with nodes in
$V=\\{1,2,\cdots,N\\}$ and edge set $E$. Nodes $i$ and $k$ are _neighbors_ if
they share an edge. The goal of the algorithm is to spread the state $x_{i}$
to node $i.$ Denote ${\cal N}(i)$ as the set of neighbors of $i$. With
$\hat{x}_{i}(t)$ an estimate of $x_{i}$, in the $t$-th iteration, the
information spreading in [24], proceeds as:

$\hat{x}_{i}(t+1)=\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(\hat{x}_{k}(t),e_{ik}\right)\right\\},s_{i}\right\\},\forall
t\geq t_{0}.$ (1)

The $e_{ik}$ define the structural aspects of ${\cal G}$; e.g. they may be the
edge lengths between neighbors; $s_{i}\geq 0$, which may be either finite or
infinite, is the _maximum value_ that $\hat{x}_{i}(t)$ can acquire after the
initial time. Further, $\hat{x}_{i}(t_{0})\geq 0,$ for all $i\in V.$

Function $f(\cdot,\cdot)$ must be _progressive_ i.e. for some $\sigma>0$,

$f(a,b)>a+\sigma$ (2)

and _monotonic_ in the first variable, i.e.

$f(a_{1},b)\geq f(a_{2},b),\mbox{ if }a_{1}\geq a_{2}.$ (3)

and is finite for finite $a$ and $b$. The initialization in (1) ensures that
$\hat{x}_{i}(t)\geq 0$, for all $t\geq t_{0}.$ Define ${\cal S}^{*}$ as the
set of nodes with _finite maximum values_ $s_{i}$:

${\cal S}^{*}=\\{i\in V|s_{i}<\infty\\}.$ (4)

We will assume that this set is nonempty. Evidently, the information $x_{i}$
to be spread to node $i$ must be an element of the vector of _stationary_
values of (1), i.e. obeys

$x_{i}=\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(x_{k},e_{ik}\right)\right\\},s_{i}\right\\},\forall~{}i\in
V.$ (5)

We will prove the less than evident fact that this stationary point is unique,
finite, and that at least one $x_{i}=s_{i}$.

The simplest example, whose Lyapunov analysis is in [21], [22], is ABF where
$f(a,b)=a+b$ and $s_{i}=0$ or infinity. The set of $i$ for which $s_{i}=0$ are
called sources, $e_{ik}>0$ is the edge length between nodes $i$ and $k$,
$x_{i}$ represents the distance $d_{i}$ from the set of sources, and with
$\hat{x}_{i}=\hat{d}_{i}$, (1) becomes

$\hat{d}_{i}(t+1)=\left\\{\begin{matrix}0&s_{i}=0\\\ \min_{k\in{\cal
N}(i)}\left\\{\hat{d}_{k}(t)+e_{ik}\right\\}&s_{i}\neq 0\end{matrix}\right..$
(6)

Figure 1: Non-zero $s_{i}$ representing external gateways of a tactical
wireless network: red and purple nodes are high and low speed external links,
respectively, while blue are nodes without external links. Black numbers
represent edge weights $e_{ik}$, green numbers represent state estimates
$\hat{x}_{i}$. After 3 rounds, all nodes, including the low-speed link, have
converged to route through the high-speed link.

We may observe that an ABF stationary point must have all nodes with $s_{i}=0$
also having $d_{i}=0.$ If we allow other values of $s_{i}$, then not all
members of ${\cal S}^{*}$ necessarily have stationary states $s_{i}$. Figure 1
shows one such example, in which $s_{i}$ represents transport lag for external
gateways in a tactical wireless network. In this example, as with (6),

$f(\hat{x}_{k}(t),e_{ik})=\hat{x}_{k}(t)+e_{ik}.$ (7)

Here, node A (red) is a high-speed gateway with $s_{A}=1$, node D (purple) is
a low-speed gateway with $s_{D}=5$, and the others are non-gateways with
$s_{i}=\infty$. Through (1), all nodes try to route to external networks
through the shortest effective path. After 3 rounds, all nodes, including the
low-speed link, converge to route through the high-speed link. In this case
the stationary state of the low speed link is $x_{D}=4$ and does not equal
$s_{i}=5$ even though $s_{i}$ is finite. Should the high speed link
represented by node A disappear, then the state estimate of D does converge to
its maximum value 5, while those of nodes B and C converge to 7 and 6,
respectively, i.e. nodes reroute through the still available low speed link.

Figure 2: Illustration of the spreading block. In this example, node in red
represents the source with a maximum value of 0, while nodes in blue have a
maximum value of 1. The edge value $e_{ik}$ reflects the success rate of
delivery. After 5 rounds, each node finds a path with the smallest failure
rate of delivery to the source.

While in the prior examples $f(a,b)$ is linear and increasing in $b$, this
need not be the case. A specialization of (1) violating both these properties
finds the _most probable path_ (MPP) from each node in a network to a source.
In this case $e_{ik}$ represents the probability of successful traversal or
delivery between neighbors $i$ and $j$. The stationary value $x_{i}$ is the
_smallest_ probability of failure in movement from node $i$ to the source. In
this case $x_{i}=0$ for sources. For all other nodes

$x_{i}=\min_{k\in{\cal N}(i)}\\{1-(1-x_{k})e_{ik}\\},\forall~{}i\neq 1.$

The sequence of minimizing nodes $k$ then indicates the MPP from node $i$ to
any source and can be computed using (1) with

$f(\hat{x}_{k}(t),e_{ik})=1-(1-\hat{x}_{k}(t))e_{ik}.$ (8)

If $0<\sigma\leq e_{ik}<1-\sigma,$ this is progressive and increasing in
$\hat{x}_{k}(t),$ though _decreasing in $e_{ik}$._ Figure 2 illustrates an
example execution, with node A (red) as the source, in which each state
estimate converges within 5 rounds.

A key shortcoming of (1), however, is that underestimates can rise very slowly
in the presence of small $e_{ik}$. Consider for example (6) with nodes 1 and 2
having the smallest estimates and sharing a short edge $e.$ At successive
instants $\hat{d}_{1}(t+1)=\hat{d}_{2}(t)+e$ and
$\hat{d}_{2}(t+1)=\hat{d}_{1}(t)+e$, i.e. each rises in small increments of
$e$ (and as shown in [22]) converge slowly. The generalization below
accelerates this slow convergence.

###  II-B A more general spreading block

The most general $G$-block, given in [25], is a generalization of (10) in that
state estimates are updated as

$\hat{x}_{i}(t+1)=F\left(\tilde{x}_{i}(t+1),\hat{x}_{i}(t),v_{i}\right)$ (9)

with $\tilde{x}_{i}(t+1)$ obeying

$\tilde{x}_{i}(t+1)=\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(\hat{x}_{k}(t),e_{ik}\right)\right\\},s_{i}\right\\},\forall
t\geq t_{0},$ (10)

where $v_{i}$ are environmental variables and $f(\cdot,\cdot)$ remains
progressive and monotonic. The function $F(\ell_{1},\ell_{2},v)$ is _raising_
, i.e. for finite $M\geq 0$, $\delta>0$ and $D\geq 0,$ obeys

$F(\ell_{1},\ell_{2},v)=\begin{cases}\ell_{1}&\ell_{2}\geq M\mbox{ or
}|\ell_{2}-\ell_{1}|\leq D\\\ g(\ell_{2})&\mbox{otherwise}\end{cases},$ (11)

where $g(x)$ is finite for finite $x$ and obeys

$g(x)\geq x+\delta.$ (12)

Invocation of the second bullet of (11), speeds the initial ascent of
$\hat{x}_{i}(t)$, ameliorating the problem of the slow rise in underestimates
experienced by (1). On the other hand, the first bullet renders (10) identical
to (1). As the second bullet of (11) changes $\hat{x}_{i}(t)$, the stationary
point of (10-12) is identical to that of (5). Thus this algorithm spreads the
same information as (1), while _accelerating the rise of underestimates_.
Observe also that $D=\infty$ and/or $M=0$, reduces (10-12) to (1).

The version of (10-12) in [25] sets the _dead zone_ variable as $D=0$. In face
of persistent structural perturbations in $e_{ik}$, $l_{2}=l_{1}$ cannot be
sustained. Consequently, regardless of the size of perturbations, with $D=0$,
$\hat{x}_{i}$ will regularly rise to the limit of the modulation threshold
$M$, then fall, and then rise again. On the other hand we will show that if
$D$ is sufficiently greater than $\epsilon$, the bound on the perturbation,
then (10-12) will have ultimate bounds proportional to $\epsilon.$ _This
raises an essential trade-off_. Too large a $D$ slows convergence though
imparts greater robustness to perturbations. Such a compromise is inherent to
most dynamic systems. Slower convergence improves noise performance.

Another key difference is that [25] assumes that $\hat{x}_{i}$ belong to a
Noetherian ring with $M$ its _maximal element._ This implicitly assumes that
the algorithm is _a priori_ bounded. For distance estimation this means a
prior assumption on the diameter, which is unappealing in the context of open
systems.

Figure 3: Illustration of GABF and sets ${\cal A}(t),{\cal E}(t),{\cal R}(t)$
and ${\cal U}(t)$. Each edge length in the graph is 1, $M=4,\delta=1$, $D=0$,
$s_{i}=0$ for $i=A,E$ and $s_{i}=\infty$ otherwise. In this case, ${\cal
R}(1)={\cal A}(1)=\\{A,B,E\\}$, ${\cal U}(1)={\cal E}(1)=\\{C,D\\}$.

inline]Consider dropping Figure 3, as we don’t use it for much, along with the
examples that reference it.

The generalized Adaptive Bellman-Ford algorithm (GABF), presented and analyzed
_without proofs_ in [26], is a specific example of (9), that is an accelerated
ABF. In GABF, $f(\hat{x}_{k}(t),e_{ik})$ follows (7) with $e_{ik}$ the edge
length between $i$ and $k$, $\hat{x}_{k}(t)$ the distance estimate of $k$ at
time $t$, $s_{i}=0$ if $i$ is a source while $s_{i}=\infty$ if $i$ is a non-
source node. In Figure 3, nodes in red are sources, each edge length in the
graph is 1, and numbers in green represent the state estimates. Variables
$M,D$ and $\delta$ in (11) and (12) are set as $4,0$ and $1$ respectively.
Convergence occurs in four rounds.

###  II-C Definitions and Assumptions

We define ${\cal S}(t)$ as comprising nodes in ${\cal S}^{*}$ that acquire
their maximum values at time $t$,

${\cal S}(t)=\\{i\in{\cal S}^{*}~{}|~{}\hat{x}_{i}(t)=s_{i}\\},$ (13)

and we say $i$ is a source at time $t$ if $i\in{\cal S}(t)$. The following
assumption holds in this paper.

######  Assumption 1.

Graph ${\cal G}$ is connected, $\infty>e_{ik}=e_{ki}\geq e_{\min}>0$, ${\cal
S}^{*}$ defined in (4) in nonempty and

$s_{\min}=\underset{j\in{\cal S}^{*}}{\min}\\{s_{j}\\}\geq 0,~{}\forall i\in
V.$ (14)

Further

${\cal S}_{\min}=\\{i\in V|s_{i}=s_{\min}\\}.$ (15)

As in any given iteration the estimated state of a node is obtained by one of
the bullets in (11), at each _t_ , we partition _V_ into two sets defined
below.

######  Definition 1.

The set ${\cal A}(t)$ (ABF type nodes) comprises all nodes that use the first
case in (11) to obtain $\hat{x}_{i}(t)$, i.e. in (10),
$\hat{x}_{i}(t)=\tilde{x}_{i}(t)$. Define the set of extraordinary nodes
${\cal E}(t)=V\setminus{\cal A}(t)$ to be those that use the second case in
(11).

The next definition defines a _(current) constraining node_.

######  Definition 2.

For $i\in{\cal A}(t)$, if $\hat{x}_{i}(t)=s_{i}=x_{i}$ then $i$ is its own
current constraining, or constraining node at $t$. Otherwise the minimizing
$k\neq i$ in (10) used to find $\hat{x}_{i}(t)$, is $i$’s constraining node at
$t$. If $i\in{\cal E}(t)$, then $i$ is its own constraining node at $t$. The
constraining node of $i$ at $t$ is said to constrain $i$ at $t.$

##  III Characterizing Stationary Points

This section characterizes the stationary point of (10-12) which as explained
in Section II is identical to the stationary point of (1) given in (5).
Observe that these comprise two sorts of values. Those where $x_{i}=s_{i}.$
Those where $x_{i}<s_{i}.$ We call the former _sources_ and their set is
defined as

${\cal S}_{\infty}=\\{i|x_{i}=s_{i}\\}.$ (16)

Evidently

$x_{i}=\begin{cases}s_{i}&i\in{\cal S}_{\infty}\\\ \underset{k\in{\cal
N}(i)}{\min}\\{f(x_{k},e_{ik})\\}&i\notin{\cal S}_{\infty}\end{cases}$ (17)

As shown by example in Section II-A, not all members of ${\cal S}^{*}$ are
sources. To establish the existence of at least one stationary point we make a
definition.

######  Definition 3.

As the graph is connected, there is a path from every node to every other
node. Define ${\cal P}_{ji}$ to be the set of all paths from $j$ to $i$,
including $j=i$. Denote such a path ${\cal P}\in{\cal P}_{ji}$, e.g.
$l_{0}\rightarrow l_{1}\rightarrow\cdots,\rightarrow l_{L}=i$, by the ordered
set ${\cal P}=\\{j=l_{0},l_{1},\cdots,l_{L}=i\\}$. In particular the path from
$i$ to $i$, will be the solitary node:

${\cal P}_{ii}=\\{\\{i\\}\\}.$ (18)

Consider the recursion,

$x^{*}_{l_{k}}({\cal P})=\begin{cases}s_{l_{k}}&k=0\\\ f(x^{*}_{l_{k-1}}({\cal
P}),e_{l_{k-1}l_{k}})&k\in\\{1,\cdots,L\\}\end{cases}.$ (19)

Define $x_{ji}$ as the smallest value $x^{*}_{i}({\cal P})$ can have among all
the paths from $j$ to $i$, i.e.

$x_{ji}=\min_{{\cal P}\in{\cal P}_{ji}}\\{x^{*}_{i}({\cal P})\\}.$ (20)

Further define

$\bar{x}_{i}=\min_{j\in V}\\{x_{ji}\\}.$ (21)

This sequence mimics the second case of (17) sans minimization. The
$\bar{x}_{i}$ are uniquely determined by the structure of the graph and will
provide a characterization of ${\cal S}_{\infty}$ and the $x_{i}.$ Key points
stemming from the fact that $f(a,b)>a$ are:

  * (i)

Only sequences that commence at a node with finite maximum values yield finite
$x_{k}^{*}$, i.e. $x_{ji}=\infty$ iff $j\notin{\cal S}^{*}.$

  * (ii)

One has $x_{ij}=s_{i}$ iff $j=i$ and further

$\bar{x}_{i}=s_{i},\mbox{ iff }x_{ji}\geq s_{i},~{}\forall~{}j\neq i.$ (22)

  * (iii)

Given an $\bar{x}_{i}\neq s_{i}$ there is a $j\neq i$, ${\cal
P}_{i}\in\\{{\cal P}_{ji}\\}$ and $k\in{\cal N}(i)$, the penultimate node in
${\cal P}_{i}$ such that

$\bar{x}_{i}=f(x_{k}^{*}(P_{i}),e_{ik}).$ (23)

Either for this $k,$ $\bar{x}_{k}=s_{k}$ or there are $m$, ${\cal
P}_{k}\in\\{{\cal P}_{mk}\\}$ and $l\in{\cal N}(k)$, the penultimate node in
${\cal P}_{k}$ such that

$\bar{x}_{k}=f(x_{l}^{*}(P_{k}),e_{lk}).$ (24)

  * (iv)

Because $f(\cdot,\cdot)$ is progressive, in the sequence (19),
$x_{l_{k}}^{*}({\cal P})>x_{l_{k-1}}^{*}({\cal P})$.

The next lemma concerns the scenario in (iii).

######  Lemma 1.

Under assumption 1 consider the quantities defined in (iii) above. Suppose
$\bar{x}_{i}\neq s_{i}$ and $\bar{x}_{k}\neq s_{k}$. Then $i\notin{\cal
P}_{k}.$

###### Proof.

To establish a contradiction suppose $i\in{\cal P}_{k}.$ Then because of
(19-21) $\bar{x}_{i}\leq x_{i}^{*}(P_{k})<\bar{x}_{k}\leq x_{k}^{*}(P_{i}).$
On the other hand as $k\in{\cal P}_{i}$, $\bar{x}_{i}>x_{k}^{*}(P_{i})$
leading to a contradiction. ∎

We now show that $\bar{x}_{i}$ obey a recursion like (5), thus proving that
they represent a stationary point.

######  Lemma 2.

Under Assumption 1, then $\bar{x}_{i}$ in Definition 3 obeys:

$\bar{x}_{i}=\min\left\\{\min_{k\in{\cal
N}(i)}f\left(\bar{x}_{k},e_{ik}\right),s_{i}\right\\},\forall~{}i\in V.$ (25)

###### Proof.

From Definition 3, in particular, (20) and (22) and the recursion in (19), and
the fact that $s_{i}=x_{ii}$ there holds:

$\displaystyle\bar{x}_{i}=$ $\displaystyle\min\left\\{\min_{j\in
V\setminus\\{i\\}}\\{x_{ji}\\},s_{i}\right\\}$ $\displaystyle=$
$\displaystyle\min\left\\{\min_{j\in V\setminus\\{i\\}}\left\\{\min_{{\cal
P}\in{\cal P}_{ji}}\\{x^{*}_{i}({\cal P})\\}\right\\},s_{i}\right\\}$
$\displaystyle=$ $\displaystyle\min\left\\{\min_{j\in
V\setminus\\{i\\}}\left\\{\min_{{\cal P}\in{\cal
P}_{ji}}\left\\{\min_{k\in{\cal N}(i)}\\{f(x_{k}^{*}({\cal
P}),e_{ki})\\}\right\\}\right\\},s_{i}\right\\}.$ (26)

The nature of the recursion in (19) ensures that for every $k\in{\cal N}(i)$
and ${\cal P}\in{\cal P}_{ji}$ there is a $\bar{{\cal P}}\in{\cal P}_{jk}$
such that in (26), the minimizing $x_{k}^{*}({\cal P})$ equals the minimizing
$x_{k}^{*}(\bar{{\cal P}})$. Thus,

$\bar{x}_{i}=\min\left\\{\min_{j\in V\setminus\\{i\\}}\left\\{\min_{{\cal
P}\in{\cal P}_{jk}}\left\\{\min_{k\in{\cal N}(i)}\\{f(x_{k}^{*}({\cal
P}),e_{ki})\\}\right\\}\right\\},s_{i}\right\\}.$

As from Lemma 1, the minimizing path ${\cal P}_{jk}$ cannot include $i,$

$\bar{x}_{i}=\min\left\\{\min_{j\in V}\left\\{\min_{{\cal P}\in{\cal
P}_{jk}}\left\\{\min_{k\in{\cal N}(i)}\\{f(x_{k}^{*}({\cal
P}),e_{ki})\\}\right\\}\right\\},s_{i}\right\\}.$

As $f(\cdot,\cdot)$ is monotonically increasing in the first argument, from
(20) and (22), (25) is proved by

$\displaystyle\bar{x}_{i}=$ $\displaystyle\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(\min_{j\in V,{\cal P}\in{\cal
P}_{jk}}\left\\{x_{k}^{*}({\cal
P})\right\\},e_{ki}\right)\right\\},s_{i}\right\\}$ $\displaystyle=$
$\displaystyle\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(\bar{x}_{k},e_{ki}\right)\right\\},s_{i}\right\\}.$ (27)

∎

Thus we have established the existence of at least one stationary point. To
establish its uniqueness we make a definition.

######  Definition 4.

In (17), if $x_{i}=s_{i}$, then we say that $i$ is its own true constraining
node. Otherwise, any minimizing $k$ in the second bullet of (17) is a true
constraining node of $i$. As $i$ may have more than one true constraining
node, its set of true constraining nodes is designated as ${\cal C}(i)$.

As $f(\cdot,\cdot)$ is progressive we have that,

$x_{i}>x_{k},~{}\forall k\in{\cal C}(i)\mbox{ and }i\notin{\cal S}_{\infty}.$
(28)

The following lemma catalogs some crucial properties of true constraining
nodes and their implications to stationary points.

######  Lemma 3.

Consider $x=[x_{1},\cdots,x_{n}]^{T}$ whose elements obey (5). Then the
following hold under Assumption 1. (A) Consider any sequence of nodes, without
loss of generality $\\{1,2,\cdots,l\\}$ such that $i+1\in{\cal C}(i)$ as
defined in Definition 4. Then this sequence is finite and its last element is
in ${\cal S}_{\infty},$ defined in (16). (B) The set ${\cal S}_{\infty}$ is
nonempty. (C) The set ${\cal S}_{\min}\subset{\cal S}_{\infty}.$ (D) All
$x_{i}$ are finite.

###### Proof.

Due to (28) the chain in (A) cannot have cycles. As there are only $N$ nodes
it must end, and the last element $l$ must be its own true constraining node
i.e. $l\in{\cal S}_{\infty}.$ This proves (A), and also (B). Without loss of
generality suppose $s_{1}=s_{\min}$. To establish a contradiction, suppose
$1\notin{\cal S}_{\infty}.$ Then from (A) there is a sequence of nodes
starting from 1 and terminating in $j\in{\cal S}_{\infty}$, such that each is
the true constraining node of its predecessor. Thus from (28)
$x_{j}=s_{j}<s_{1}=s_{\min}$, violating the definition of $s_{\min},$ proving
(C). To prove (D) consider $i\neq 1.$ As the graph is connected there is a
path from $1$ to $i$, comprising nodes $\\{1=l_{1}\rightarrow
l_{2}\rightarrow\cdots l_{k}=i.\\}$ Then from (17) for each
$n\in\\{2,\cdots,k\\}$ there holds

$x_{l_{n}}\leq f(x_{l_{n-1}},e_{l_{n},l_{n-1}}).$

Due to the fact that $f(a,b)$ is finite for finite $a,b,$ $x_{l_{n}}$ is
finite if $x_{l_{n-1}}$ is finite. The result follows as $x_{1}$ is finite. ∎

We make another definition for proving uniqueness of the stationary point and
convergence of the algorithm.

Figure 4: Illustration of graph where ${\cal S}_{\infty}$ is not a subset of
${\cal F}_{0}$. Here $s_{1}=0$, $s_{2}=1$ and $s_{3}=\infty$. All edge lengths
are $1$ and $f(a,b)=a+b.$ In this case $x_{1}=0,x_{2}=1$ and $x_{3}=1.$ Here
$2\in{\cal S}_{\infty}$ as $x_{2}=s_{2}.$ However, as $x_{2}=x_{1}+1,$
$2\in{\cal F}_{1}.$

######  Definition 5.

We call a path from a node $i$ to $j\in{\cal S}_{\infty}$ a shortest path, if
it starts at $i$, ends with $j\in{\cal S}_{\infty}$, and each node in the path
is a true constraining node of its predecessor. We call a shortest path from
$i$ the longest shortest path if it has the most nodes among all shortest
paths of $i$. The set ${\cal F}_{i}$ is the set of nodes whose longest
shortest paths to the source set have $i+1$ nodes. We call ${\cal D}({\cal
G})$ the effective diameter of ${\cal G}$ if the longest shortest path among
all $i\in V$ has ${\cal D}({\cal G})$ nodes.

From Lemma 3, the effective diameter is always finite. If a node $i$ has two
shortest paths, one with two and the other with three nodes, then
$i\notin{\cal F}_{1}$ but $i\in{\cal F}_{2}$. It is tempting to believe that
${\cal F}_{0}={\cal S}_{\infty}$. However, the scenario of Figure 4 provides a
counterexample. In this case $s_{1}=0$, $s_{2}=1$ and $s_{3}=\infty$. All edge
lengths are $1$ and $f(a,b)=a+b.$ In this case $x_{1}=0,x_{2}=1$ and
$x_{3}=1.$ Here $2\in{\cal S}_{\infty}$ as $x_{2}=s_{2}.$ However, as
$x_{2}=x_{1}+1,$ $2\in{\cal F}_{1}.$

The following lemma exposes a key property of the sets ${\cal F}_{i}.$

######  Lemma 4.

Under the conditions of Lemma 3, consider ${\cal F}_{i}$ given in Definition
5. If for some $k\in\\{1,\cdots,{\cal D}({\cal G})-1\\}$, ${\cal F}_{k}$ is
nonempty then every node in ${\cal F}_{k}$ has a true constraining node in
${\cal F}_{k-1}$. Further ${\cal S}_{\min}\subset{\cal F}_{0}\subset{\cal
S}_{\infty}.$

###### Proof.

Consider any $i\in{\cal F}_{k}.$ From Definition 5, starting from $i$ there is
a sequence containing $k+1$ nodes to a $j\in{\cal S}_{\infty}$ in which each
node is the true constraining node of its predecessor. Suppose the second node
in this sequence is $l$. By definition $l$ is a true constraining node of $i.$
Also by definition $l\in{\cal F}_{m},$ where $m\geq k-1.$ If $m>k-1$, then for
some $M>k$, $i\in{\cal F}_{M}.$ This contradicts the assumption that
$i\in{\cal F}_{k}.$ Thus $l\in{\cal F}_{k-1}$. By definition, every node in
${\cal F}_{0}$ is its own true constraining node as otherwise it will belong
to some ${\cal F}_{i}$, $i>0$. Thus from Definition 4, ${\cal
F}_{0}\subset{\cal S}_{\infty}.$

Finally consider $j\in{\cal S}_{\min}.$ By definition $s_{j}=s_{\min}\leq
s_{i}$ for all $i.$ If $j\in{\cal F}_{k},$ with $k>0$, then there is a
sequence starting from $j$ to an $l\in{\cal S}_{\infty}$, such that each node
is the true constraining of its predecessor. Thus from the progressive
property of $f(\cdot,\cdot)$, $s_{\min}=s_{j}\geq x_{j}>s_{l},$ establishing a
contradiction. Thus $j\in{\cal F}_{0}$ and ${\cal S}_{\min}\subset{\cal
F}_{0}.$ ∎

######  Lemma 5.

Under the conditions of Lemma 3, with ${\cal F}_{i}$ defined in Definition 5,

${\cal F}_{i}\neq\emptyset,~{}\forall~{}i\in\\{0,1,\cdots,{\cal D}({\cal
G})-1\\},$ (29)

and for all $i\in\\{0,1,\cdots,{\cal D}({\cal G})-2\\}$ each node in ${\cal
F}_{i+1}$ has a true constraining node in ${\cal F}_{i}$.

###### Proof.

We first show by induction that for each $k\in\\{1,\cdots,{\cal D}({\cal
G})-1\\}$, ${\cal F}_{k}$ is nonempty. From Definition 5, ${\cal F}_{{\cal
D}({\cal G})-1}\neq\emptyset$, initiating the induction. Now suppose for some
$L\in\\{1,\cdots,{\cal D}({\cal G})-1\\}$, ${\cal F}_{L}\neq\emptyset.$ Then
from Lemma 4 every member of ${\cal F}_{L}$ has a true constraining node in
${\cal F}_{L-1}$, making ${\cal F}_{L-1}\neq\emptyset$. Further, again from
Lemma 4 every member of ${\cal F}_{1}$ has a true constraining node in ${\cal
F}_{0}$ making the latter nonempty. Then Lemma 4 proves the result. ∎

We can now prove the uniqueness of the stationary point.

######  Theorem 1.

Under the conditions of Lemma 3, $x_{i}=\bar{x}_{i},$ defined in Definition 3,
represents the unique stationary point obeying (5). Further the source set is
given by:

${\cal S}_{\infty}=\\{i\in V|\bar{x}_{i}=s_{i}\\}.$ (30)

###### Proof.

From Lemma 2 $x_{i}=\bar{x}_{i}$ is a stationary point and from (16), (30) is
the corresponding source set.

Call $\bar{x}=[\bar{x}_{1},\cdots,\bar{x}_{n}]^{T}$ and consider a potentially
different stationary point $x=[x_{1},\cdots,x_{n}]^{T}.$ As constraining
nodes, source sets and the sets ${\cal F}_{i}$ depend on the stationary point,
in this proof we will distinguish them with the additional argument of the
stationary point, e.g. ${\cal C}(i,x)$.

We first assert that for all $i,$ $x_{i}\geq\bar{x}_{i}.$ To establish a
contradiction suppose for some $x_{i}<\bar{x}_{i}.$ From Lemma 3, there is a
$j\in{\cal S}_{\infty}(x)\subset{\cal S}^{*}$ and a sequence of nodes
$i=l_{1}\rightarrow\cdots\rightarrow l_{L}=j$ such that

$x_{l_{k+1}}=f\left(x_{l_{k}},e_{l_{k},l_{k+1}}\right).$ (31)

From Definition 3 this means

$x_{ij}\leq x_{i}<\bar{x}_{i},$

violating the definition of $\bar{x}_{i}.$ Thus indeed $x_{i}\geq\bar{x}_{i}.$

As from Lemma 4 for all $j\in\\{0,\cdots,{\cal D}({\cal G})-1\\}$, ${\cal
F}_{j}(\bar{x})\neq\emptyset$, we use induction to show that
$x_{i}=\bar{x}_{i}$, for all $i\in{\cal F}_{j}(\bar{x}).$ Consider any
$i\in{\cal F}_{0}(\bar{x}).$ As ${\cal F}_{0}(\bar{x})\subset{\cal
S}_{\infty}(\bar{x})$, $\bar{x}_{i}=s_{i}.$ As by definition, $s_{i}\geq
x_{i}\geq\bar{x}_{i}=s_{i}$, one must have $x_{i}=s_{i}.$

To sustain the induction assume that for some $0\leq L<{\cal D}({\cal G})-1$,
$x_{k}=\bar{x}_{k},$ for all $k\in{\cal F}_{L}(\bar{x}).$ To establish a
contradiction suppose for some $i\in{\cal F}_{L+1}(\bar{x})$,
$x_{i}\neq\bar{x}_{i}.$ By Lemma 5 there is a $k\in\\{{\cal
C}(i,\bar{x})\bigcap{\cal F}_{L}(\bar{x})\\}$, By the induction hypothesis,
$\bar{x}_{k}=x_{k}.$ Then as $k$ is a neighbor of $i$, from (17)

$\displaystyle x_{i}=\min_{l\in{\cal N}(i)}\\{f(x_{l},e_{il})\\}\leq
f(x_{k},e_{ik})=f(\bar{x}_{k},e_{ik})=\bar{x}_{i}.$ (32)

As $x_{i}\geq\bar{x}_{i}$, one obtains, $x_{i}=\bar{x}_{i}.$

∎

Thus we have characterized the stationary point given by (5) and proved its
uniqueness.

##  IV Global uniform asymptotic stability

Having established the existence and uniqueness of the stationary point
$x_{i}$, in this section, we prove that the state estimates $\hat{x}_{i}(t)$
yielded by (9)-(12), globally, uniformly converge to these $x_{i}$, in graphs
without perturbations i.e. when $e_{ik}$ and $s_{i}$ do not change. The key
steps of the proof are:

  * (a)

We show that all underestimates are eventually eliminated, i.e. for all $i,$
and sufficiently large $t,$ $\hat{x}_{i}(t)\geq x_{i}.$ This is done by using
the progressive property of $f(\cdot,\cdot)$ and the second case of (11),
which causes $\hat{x}_{i}$ to increase.

  * (b)

We show that once underestimates are eliminated, the moment a source node
$i\in{\cal S}_{\infty}\supset{\cal F}_{0}$ invokes the first bullet of (11),
i.e. lies in ${\cal A}(t)$, it converges to $s_{i}.$ Similarly if at a time
$t^{\prime}$ and beyond, ${\cal F}_{0}$ to ${\cal F}_{L}$ defined in
Definition 5 have converged, if $i\in{\cal F}_{L+1}$ invokes the first case of
(11) then $\hat{x}_{i}(t)$ converges to $x_{i}.$

  * (c)

We then show that over every finite interval, the first bullet of (11) must be
invoked at least once as each invocation of the second case of (11) by $i$
increases $\hat{x}_{i}$ by $\delta,$. Thus the repeated use of the second
bullet by $i$ will eventually induce $\hat{x}_{i}>M$, forcing $i$ to use the
first bullet of (11).

  * (d)

To show (a) we define two time varying sets that partition $V$. The first,
${\cal R}(t),$ the set of nodes _rooted_ to sources, comprises elements of
${\cal S}(t)$, the source set at time $t$, and all nodes constrained by
elements of ${\cal R}(t-1).$ We show that for all $i\in{\cal R}(t)$,
$\hat{x}_{i}(t)\geq x_{i}.$ Nodes in the second _unrooted_ set ${\cal U}(t)$
must also eventually have no state estimates that are underestimates.

###  IV-A Key lemmas underlying (b,c)

This section is dedicated to key lemmas that underlie (b) and (c). The first
lemma provides and proves a key mechanism behind (b). Specifically, should
after a time $t_{1}$ no neighbor of a node $i$ ever carry underestimates and
its true constraining node converges, then for all $t>t_{1}$
$\tilde{x}_{i}(t)$ in (10) equals $x_{i}$.

######  Lemma 6.

Consider (10) and (11) under Assumption 1 and a node $i$ and a time $t_{1}$
such that the following hold for all $t\geq t_{1}.$ If $i\in{\cal
S}_{\infty}$, $\hat{x}_{j}(t)\geq x_{j}$ for all $j\in{\cal N}(i)$. If
$i\notin{\cal S}_{\infty}$, (i) m $\hat{x}_{j}(t_{1})\geq x_{j}$ for all
$j\in{\cal N}(i)$; and (ii) with $k$ a true constraining node of $i,$
$\hat{x}_{k}(t)=x_{k}$. Then for all $t>t_{1},$ $\tilde{x}_{i}(t)$ defined in
(10) equals $x_{i}.$

###### Proof.

Suppose $i\in{\cal S}_{\infty}$, then $i$ is its own true constraining node.
Then from Definition 2 and (5), and the fact that $f(a,b)$ is strictly
increasing in $a$, from (10) there holds for all $t\geq t_{1}$

$\displaystyle\tilde{x}_{i}(t+1)$ $\displaystyle=\min\left\\{\min_{j\in{\cal
N}(i)}\\{f(\hat{x}_{j}(t),e_{ij})\\},s_{i}\right\\}$
$\displaystyle=\min\left\\{\min_{j\in{\cal
N}(i)}\\{f(x_{j},e_{ij})\\},s_{i}\right\\}=s_{i}=x_{i}.$

If $i\notin{\cal S}_{\infty}$ then from Definition 2 and (ii)

$\displaystyle x_{i}$ $\displaystyle=\min_{j\in{\cal
N}(i)}\\{f(x_{j},e_{ij})\\}=f(x_{k},e_{ik})$
$\displaystyle=f(\hat{x}_{k}(t),e_{ik}),~{}\forall~{}t\geq t_{1}.$

Further from (i)

$\min_{j\in{\cal N}(i)}\\{f(x_{j},e_{ij})\\}\leq\min_{j\in{\cal
N}(i)}\\{f(\hat{x}_{j}(t),e_{ij})\\}~{}\forall~{}t\geq t_{1}.$

As $k\in{\cal N}(i)$ one thus has that

$\displaystyle\min_{j\in{\cal
N}(i)}\\{f(\hat{x}_{j}(t),e_{ij})\\}=f(x_{k},e_{ik}),=x_{i}~{}t\geq t_{1}.$

By definition $i\notin{\cal S}_{\infty}$ implies that $x_{i}<s_{i}.$ Thus from
(10) for all $t\geq t_{1},$ $\tilde{x}_{i}(t+1)$ equals

$\displaystyle\min\left\\{\min_{j\in{\cal
N}(i)}\\{f(\hat{x}_{j}(t),e_{ij})\\},s_{i}\right\\}=\min\left\\{x_{i},s_{i}\right\\}=x_{i}.$

∎

In view of Definition 1 under the conditions of Lemma 6, if at any $t>t_{1}$,
$i\in{\cal A}(t)\bigcap{\cal S}_{\infty}$, then
$\hat{x}_{i}(t)=\tilde{x}_{i}(t)=s_{i}.$ The next lemma shows that if after
$t_{1}$ defined in Lemma 6, $i$ ever enters ${\cal A}(t)$ then
$\hat{x}_{i}(t)$ converges immediately to $x_{i}.$

######  Lemma 7.

Consider (9-12). Suppose the conditions of Lemma 6 hold, and for some
$t_{2}>t_{1}$, $i\in{\cal A}(t_{2})$ defined in Definition 1. Then for all
$t\geq t_{2}$, $\hat{x}_{i}(t)=x_{i}.$

###### Proof.

In view of Lemma 6, we need to show that for all $t\geq t_{2}$, $i\in{\cal
A}(t).$ Use induction. By hypothesis, $i\in{\cal A}(t_{2}).$ Now suppose for
some $t\geq t_{2}>t_{1}$ , $i\in{\cal A}(t).$ Then from Definition 1 and Lemma
6, $\hat{x}_{i}(t)=\tilde{x}_{i}(t)=x_{i}.$ Further, also from Lemma 6,
$\tilde{x}_{i}(t+1)=x_{i}=\hat{x}_{i}(t).$ Thus from (10) and the first bullet
of (11), $\hat{x}_{i}(t+1)=\tilde{x}_{i}(t+1),$ i.e. $i\in{\cal A}(t+1).$

∎

Thus under the conditions of Lemma 6 all it takes for $\hat{x}_{i}(t)$ to
converge after $t_{1}$ is for $i$ to enter the ABF set. The next lemma bounds
the time, described in (c), for this to happen.

######  Lemma 8.

Under the conditions of Lemma 6, consider (9)-(12). Suppose
$\hat{x}_{i}(t_{2})=m_{i}$ for some $t_{2}>t_{1}$. Define

$t_{3}=t_{2}+1+\min\left\\{\left\lceil\frac{M-m_{i}}{\delta}\right\rceil,0\right\\}.$

Then for all $t>t_{3}$, $\hat{x}_{i}(t)=x_{i}.$

###### Proof.

Suppose $\hat{x}_{i}(t_{2})\neq x_{i}.$ Then from Lemma 7, $i\in{\cal
E}(t_{2})$. Now suppose $i\in{\cal E}(t)$ for all $t_{2}\leq t\leq
t^{\prime}$. In this case from the second bullet of (11), $t^{\prime}\leq
t_{3}.$ From the first bullet of (12) this means $i\in{\cal A}(t_{3}+1).$ Then
Lemma 7 proves the result. ∎

So if no neighbor of a non-source $i$ carries an underestimate and at least
one of its true constraining nodes has converged, then $\hat{x}_{i}(t)$
converges the moment $i$ enters ${\cal A}(t),$ which it must in a time
quantified in Lemma 8. The same is true if the states of all neighbors of a
source $i$ have exceeded $s_{i}$, albeit under a weaker condition. The next
subsection proves a key property that facilitates this convergence: the
eventual removal of underestimates noted in (a) at the start of this section.

###  IV-B Disappearance of underestimates

We first define the two time varying sets ${\cal U}(t)$ and ${\cal R}(t)$
mentioned in (d) at the beginning of the section.

######  Definition 6.

The set of nodes rooted to sources is ${\cal R}(t+1)={\cal S}(t+1)\bigcup
P(t+1)$ with ${\cal S}(t+1)$ as in (13) and $P(t+1)$ comprising those whose
constraining node at $t+1$ is in ${\cal R}(t)$. Further ${\cal R}(t_{0})={\cal
S}(t_{0})$. The unrooted set is ${\cal U}(t)=V\setminus{\cal S}(t)$.

Evidently, ${\cal U}(t+1)\bigcap{\cal S}(t+1)=\emptyset.$ As every node must
have a constraining node at every $t$, and members of ${\cal R}(t+1)$ are
either in ${\cal S}(t+1)$ or are constrained by members of ${\cal R}(t)$, each
member of ${\cal U}(t+1)$ must be constrained at time $t+1$ by one of ${\cal
U}(t)$. Thus

${\cal U}(t)=\emptyset\implies{\cal U}(t+1)=\emptyset.$ (33)

Sets in definitions 1 and 6 are exemplified through GABF in Figure 3. In this
case, ${\cal S}(0)=\\{A,E\\}$ as $\hat{x}_{i}(0)=0=s_{i}$ for $i=A$ or $E$. At
$t=1$, $\tilde{x}_{B}(1)=\hat{x}_{A}(0)+e_{AB}=\hat{x}_{B}(0)=1$, as $D=0$,
node $B$ will take $A$ as the current constraining node and use the first
bullet of (11) to update its estimate, leading to $B\in{\cal A}(1)\cap{\cal
R}(1)$. Meanwhile, as
$\tilde{x}_{D}(1)=\hat{x}_{E}(0)+e_{DE}=1\neq\hat{x}_{4}(0)$, $D=0$ and
$\hat{x}_{D}(0)<M$, node $D$ will update its estimate using the second bullet
of (11) and take itself as the current constraining node, then $D\in{\cal
E}(1)\cap{\cal U}(1)$.

We will now show that underestimates in ${\cal U}(t)$ must eventually
disappear. To this end define

$\hat{x}_{\min}(t)=\underset{j\in{\cal
U}(t)}{\min}~{}\\{\hat{x}_{j}(t)\\}~{}\mathrm{if}~{}{\cal U}(t)\neq\emptyset,$
(34)

Define:

$x_{\max}=\underset{k\in V}{\max}~{}\\{x_{k}\\},$ (35)

and

$T=\bigg{\lceil}\frac{x_{\max}-\hat{x}_{\min}(t_{0})}{\min\\{\sigma,\delta\\}}\bigg{\rceil}.$
(36)

######  Lemma 9.

Consider (9)-(11) under Assumption 1, with ${\cal U}(t)$, $\hat{x}_{\min}(t)$,
$x_{\max}$ and $T$ defined in Definition 1, (34), (35) and (36), respectively.
Then (37) and (38) hold while ${\cal U}(t)\neq\emptyset$:

$\hat{x}_{i}(t)\geq\hat{x}_{\min}(t_{0})+\min\\{\sigma,\delta\\}(t-t_{0}),~{}\forall
i\in{\cal U}(t)$ (37) $\hat{x}_{i}(t)\geq x_{\max}\geq x_{i},~{}\forall
i\in{\cal U}(t)\mbox{ and }\forall t\geq t_{0}+T.$ (38)

###### Proof.

Because of (33), ${\cal U}(t)$ is nonempty only on a single contiguous time
interval commencing at $t_{0}$. Thus, from (35) and (36), (38) will hold if
(37) holds.

We prove (37) by induction in $t\geq t_{0}.$ It clearly holds for $t=t_{0}$.
Thus suppose it holds at some $t\geq t_{0}.$ If ${\cal U}(t+1)$ is empty then
it remains so for all future values. So assume ${\cal U}(t+1)\neq\emptyset$
i.e. ${\cal U}(t)\neq\emptyset$. Suppose $i\in{\cal U}(t+1)$ is such that
$\hat{x}_{i}(t+1)=\hat{x}_{\min}(t+1)$. From the remark after Definition 6,
$j$ the current constraining node of $i$ is in ${\cal U}(t)$. Suppose
$i\in{\cal E}(t+1)$ defined in Definition 1, then from Definition 2, $j=i$.
The induction hypothesis and (12) yield:

$\displaystyle\hat{x}_{i}(t+1)$ $\displaystyle=$
$\displaystyle\hat{x}_{\min}(t+1)$ $\displaystyle\geq$
$\displaystyle\hat{x}_{j}(t)+\delta\geq\hat{x}_{\min}(t)+\min\\{\sigma,\delta\\}$
$\displaystyle\geq$
$\displaystyle\hat{x}_{\min}(t_{0})+\min\\{\sigma,\delta\\}(t+1-t_{0}).$

If $i\in{\cal A}(t+1)$, then, $i\notin{\cal S}(t+1)$, i.e.
$\hat{x}_{i}(t+1)\neq s_{i}.$ Thus,

$\displaystyle\hat{x}_{i}(t+1)=$
$\displaystyle\hat{x}_{\min}(t+1)=f(\hat{x}_{j}(t),e_{ij})$
$\displaystyle\geq$
$\displaystyle\hat{x}_{j}(t)+\sigma\geq\min\\{\sigma,\delta\\}(t+1-t_{0}).$

∎

We now show that after $t_{0}+T$ _all_ $\hat{x}_{i}(t)$ are overestimates.

######  Lemma 10.

Under the conditions of Lemma 9,

$\hat{x}_{i}(t)\geq x_{i},~{}\forall~{}i\in V,\mbox{ and }t\geq T+t_{0}.$ (40)

###### Proof.

We will first show by induction that whenever ${\cal R}(t)$ given in
Definition 6 is nonempty, $\hat{x}_{i}(t)\geq x_{i}$ for all $i\in{\cal
R}(t).$ Then as ${\cal U}(t)=V\setminus{\cal R}(t)$, the result will follow
from Lemma 9. If ${\cal R}(t^{\prime})\neq\emptyset$, then there is a
$t_{0}\leq t_{4}\leq t^{\prime}$ such that ${\cal R}(t)\neq\emptyset$, for all
$t_{4}\leq t\leq t^{\prime}$ and ${\cal R}(t_{4})={\cal S}(t_{4}).$ Clearly by
definition of ${\cal S}(t)$, $\hat{x}_{i}(t_{4})=s_{i}\geq x_{i},$ for all
$i\in{\cal S}(t_{4})={\cal R}(t_{4})$. If $t^{\prime}=t_{4},$ then all
elements of ${\cal R}(t^{\prime})$ carry overestimates.

If $t^{\prime}>t_{4}$ then use induction on $t_{4}\leq t\leq t^{\prime}.$
Suppose $x_{i}\leq\hat{x}_{i}(t)$ for some $t_{4}\leq t<t^{\prime},$ and all
$i\in{\cal R}(t).$ Consider any $i\in{\cal R}(t+1)$. Then from Definition 6,
either $i\in{\cal S}(t+1)$, in which case the result holds, or $j$ the current
constraining node of $i$ is in ${\cal R}(t).$ Then by the induction
hypothesis, $\hat{x}_{j}(t)\geq x_{j}.$ As $\hat{x}_{i}(t+1)\neq s_{i}$, and
$f(a,b)$ is increasing in $a,$ if $i\in{\cal A}(t+1)$, there follows:

$\displaystyle\hat{x}_{i}(t+1)$ $\displaystyle=f(\hat{x}_{j}(t),e_{ij})\geq
f(x_{j},e_{ij})\geq x_{i}.$

If $i\in{\cal E}(t+1)$ then it is its own true constraining node and
$i\in{\cal R}(t).$ Thus by the induction hypothesis, $\hat{x}_{i}(t)\geq
x_{i}.$ Thus from (12) $\hat{x}_{i}(t+1)\geq\hat{x}_{i}(t)+\delta>x_{i}.$

∎

Thus we have established (a) described at the beginning of this section. In
the next section we prove GUAS.

###  IV-C Proof of convergence

Define the smallest stationary value in ${\cal F}_{i}$ as

$x_{i\min}=\underset{j\in{\cal F}_{i}}{\min}~{}\\{x_{j}\\}.$ (41)

From Lemma 5, we have $x_{0\min}=s_{\min}$. Define a sequence

$T_{i}=\max\bigg{\\{}0,\bigg{\lceil}\frac{M-x_{i\min}}{\delta}\bigg{\rceil}\bigg{\\}}+2.$
(42)

We then have the main result of this section, proving the convergence of each
$\hat{x}_{i}(t)$ to $x_{i}.$ Specifically, we will show by induction that with
$T$ defined in (36), for all $i\in\\{0,\cdots,{\cal D}({\cal G})-1\\}$, the
elements of ${\cal F}_{0},\cdots,{\cal F}_{i}$, defined in Definition 5,
converge by the time $T+\sum_{j=0}^{i}T_{j}.$

######  Theorem 2.

Consider (9) - (11) under Assumption 1, with $T_{i}$ and $T$ defined in (42)
and (36), respectively. Then $\forall$ $i\in V$,

$\hat{x}_{i}(t)=x_{i},~{}\forall t>t_{0}+T+\sum_{i=0}^{{\cal D}({\cal
G})-1}T_{i}.$ (43)

###### Proof.

We will prove by induction that for every $L\in\\{0,\cdots,{\cal D}({\cal
G})-1\\},$

$\hat{x}_{i}(t)=x_{i},~{}\forall~{}t\geq t_{0}+T+\sum_{j=0}^{L}T_{j}\mbox{ and
}i\in\bigcup_{j=0}^{L}{\cal F}_{j}$ (44)

Then the result will follow as the ${\cal F}_{j}$ partition $V.$

Consider $i\in{\cal F}_{0}$ and $t>t_{0}+T+T_{0}.$ From Lemma 4, $i\in{\cal
S}_{\infty}.$ As from Lemma 10, $\hat{x}_{k}(t)\geq x_{k}$, for all
$t>t_{0}+T$ and $k\in V$, $i$ satisfies the conditions of Lemma 6 and thus of
Lemma 8. Thus, from Lemma 8, (44) holds for $L=0$.

Suppose (44) holds for some $N\in\\{0,\cdots,{\cal D}({\cal G})-2\\}$.
Consider $i\in{\cal F}_{N+1}.$ By Lemma 5, $i$ has a true constraining node
$k\in{\cal F}_{N}.$ By the induction hypothesis $\hat{x}_{k}(t)=x_{k}$ for all
$t>t_{0}+T+\sum_{j=0}^{N}T_{j}$, and $\hat{x}_{l}(t)\geq x_{l}$, for all $l\in
V$. Thus from Lemma 10, this $i$ satisfies the conditions of Lemma 6 and thus
of Lemma 8. Thus, from Lemma 8, (44) holds for $L=N+1$, completing the proof.
∎

In fact one can show that this theorem also holds with

$T_{0}=\max\bigg{\\{}0,\bigg{\lceil}\frac{M-\min\\{\delta+s_{\min},x_{\max}\\}}{\delta}\bigg{\rceil}\bigg{\\}}+2,$
(45)

as $\hat{x}_{i}(t_{0}+T)\geq\min\\{\delta+s_{\min},x_{\max}\\}$ for all
$i\in{\cal F}_{0}$. The fact that the time elapsed between the initial time
$t_{0}$ and the time to converge is independent of $t_{0}$ proves GUAS.

##  V Robustness under perturbations

In this section, we prove that (9) is ultimately bounded under persistent
perturbations in the $e_{ij}$, albeit with some additional assumptions. In
particular, the dead zone parameter $D$ must exceed a value proportional to
the magnitude of the perturbation. Otherwise, with probability one
$\hat{x}_{i}(t)$ will persistently rise to $M.$ This value is provided in this
section. Proofs of this section are in the appendix.

The first additional assumption extends the monotonicity property to the
second argument of $f(\cdot,\cdot)$. Given that this argument represents edge
lengths in most applications, this is a reasonable assumption. As is also
standard in most robustness analysis, we also impose a Lipschitz condition.

######  Assumption 2.

The function $f(\cdot,\cdot)$ is monotonically increasing with respect to its
second argument, i.e. $f(a,b)$ obeys

$f(a,b_{1})\geq f(a,b_{2}),~{}\mbox{if}~{}b_{1}\geq b_{2}.$ (46)

Further, there exist $L_{i}>0$, such that

$|f(a,b_{1})-f(a,b_{2})|\leq L_{1}|b_{1}-b_{2}|$ (47)

and

$|f(a_{1},b)-f(a_{2},b)|\leq L_{2}|a_{1}-a_{2}|$ (48)

The perturbations on $e_{ij}$ are modeled as,

$e_{ij}(t)=e_{ij}+\epsilon_{ij}(t)$ (49)

with

$|\epsilon_{ij}(t)|\leq\epsilon<e_{\min},$ (50)

where $e_{\min}$ is defined in Assumption 1. Notice that the perturbations
need not be symmetric, i.e. we permit

$\epsilon_{ij}(t)\neq\epsilon_{ji}(t).$ (51)

Such perturbations could reflect noise, localization error, or (if coherent)
movement of devices. In this case, (10) becomes

$\tilde{x}_{i}(t+1)=\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(\hat{x}_{k}(t),e_{ik}(t)\right)\right\\},s_{i}\right\\}.$
(52)

We define a _shrunken graph_ , for deriving bounds on underestimates. It
corresponds to the smallest possible values of $e_{ij}$.

######  Definition 7.

Given a graph ${\cal G}$, define ${\cal G}^{-}$ as a shrunken version of
${\cal G}$ such that, $\forall i\in V$ and $j\in{\cal N}(i)$ in ${\cal G}$,
$e_{ij}$ becomes $e_{ij}^{-}$ in ${\cal G}^{-}$: With $\epsilon$ defined in
(50)

$e_{ij}^{-}=e_{ij}-\epsilon.$ (53)

Also consider (9) implemented on this shrunken graph, i.e.

$\hat{X}_{i}(t+1)=F(\tilde{X}_{i}(t+1),\hat{X}_{i}(t),v_{i}),~{}\hat{X}_{i}(0)\leq\hat{x}_{i}(0).$
(54)

with $\tilde{X}_{i}(t+1)$ obeying

$\tilde{X}_{i}(t+1)=\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(\hat{X}_{k}(t),e_{ik}^{-}\right)\right\\},s_{i}\right\\}$
(55)

As ${\cal G}^{-}$ satisfies the same assumptions as ${\cal G}$ and is
perturbation free, we define $X=[X_{1},\cdots,X_{N}]$ as the unique stationary
point in ${\cal G}^{-}$ to which (54) converges. Further, ${\cal
S}_{\infty}^{-}$ and ${\cal D}({\cal G}^{-})$ denote the source set and the
effective diameter of ${\cal G}^{-}$.

The unique stationary point in ${\cal G}^{-}$ obeys

$X_{i}=\min\left\\{\min_{k\in{\cal
N}(i)}f\left(X_{k},e_{ik}^{-}\right),s_{i}\right\\},\forall~{}i\in V.$ (56)

Specifically, from (16) and (17), the source set in ${\cal G}^{-}$ obeys

${\cal S}_{\infty}^{-}=\\{i|X_{i}=s_{i}\\},$ (57)

and the stationary point obeys:

$X_{i}=\begin{cases}s_{i}&i\in{\cal S}_{\infty}^{-}\\\ \underset{k\in{\cal
N}(i)}{\min}~{}\\{f(X_{k},e_{ik}^{-})\\}&i\notin{\cal
S}_{\infty}^{-}.\end{cases}$ (58)

Evidently, the following holds in ${\cal G}^{-}$:

$s_{\min}\leq X_{i}\leq s_{i},~{}\forall i\in V.$ (59)

Define

$X_{\max}=\underset{k\in V}{\max}~{}\\{X_{k}\\},$ (60)

and

$T^{-}=\bigg{\lceil}\frac{X_{\max}-\hat{x}_{\min}(t_{0})}{\min\\{\delta,\sigma\\}}\bigg{\rceil}$
(61)

The next lemma shows that the lower bound in ${\cal U}(t)$ will exceed
$X_{\max}$ after $t_{0}+T^{-}$.

######  Lemma 11.

Consider (9), (11) and (52), with ${\cal U}(t)$, $\hat{x}_{\min}(t)$,
$X_{\max}$ and $T^{-}$ defined in Definition 6, (34), (60) and (61),
respectively. Then (62) and (63) hold while the set ${\cal
U}(t)\neq\emptyset$:

$\hat{x}_{i}(t)\geq\hat{x}_{\min}(t_{0})+\min\\{\sigma,\delta\\}(t-t_{0}),~{}\forall
i\in{\cal U}(t)$ (62) $\hat{x}_{i}(t)\geq X_{\max}\geq X_{i},~{}\forall
i\in{\cal U}(t)\mbox{ and }\forall t\geq t_{0}+T^{-}$ (63)

We now turn to ${\cal R}(t)$ and prove that under perturbations all estimates
in ${\cal R}(t)$ are lower bounded by their corresponding stationary values in
${\cal G}^{-}$.

######  Lemma 12.

Consider (9), (11) and (52), with ${\cal A}(t)$, ${\cal E}(t)$, ${\cal R}(t)$
and $X_{i}$ as in definitions 1, 6 and 7, respectively. There holds:

$\hat{x}_{i}(t)\geq X_{i},~{}\forall i\in{\cal R}(t).$ (64)

Consequently, with Lemma 11 and Lemma 12, there holds:

$\hat{x}_{i}(t)\geq X_{i},~{}\forall i\in V,~{}\forall t\geq t_{0}+T^{-}.$
(65)

By quantifying the relation between the stationary point in ${\cal G}^{-}$ and
that in ${\cal G}$ in the next lemma, we will show that after $t_{0}+T^{-}$
all estimates are lower bounded.

To this end we define the following function:

$W(L_{2},D)=\sum_{i=0}^{D-1}L_{2}^{i}=\begin{cases}\frac{L_{2}^{D}-1}{L_{2}-1}&L_{2}\neq
1\\\ D&L_{2}=1\end{cases},$ (66)

and the summation is zero if the lower limit exceeds the upper.

######  Lemma 13.

Under Assumption 2, with $\epsilon$, $W(\cdot)$ and ${\cal D}({\cal G}^{-})$
defined in (50), (66) and Definition 7, respectively. Then for all $i\in V$
and $t\geq T^{-}+t_{0}$, there holds:

$x_{i}\leq X_{i}+W(L_{2},{\cal D}({\cal G}^{-})-1)L_{1}\epsilon.$ (67)

With ${\cal F}_{i}$ defined in Definition 5, define $X_{i\min}$ as

$X_{i\min}=\underset{j\in{\cal F}_{i}}{\min}~{}\\{X_{j}\\}$ (68)

Note that ${\cal S}_{\min}$ is a subset of ${\cal S}_{\infty}^{-}$ as well as
${\cal F}_{0}$, thus $X_{0\min}=s_{\min}$. Define a sequence

$T_{i}^{-}=\max\left\\{0,\bigg{\lceil}\frac{M-X_{i\min}}{\delta}\bigg{\rceil}\right\\}+2.$
(69)

Then we have the following lemma that recognizes that to behave acceptable
under perturbations the dead zone $D$ in (11) must be sufficiently large.

######  Lemma 14.

Consider (9), (11) and (52) under Assumption 2, with $\epsilon$, $W(\cdot)$
defined in (50), (66), respectively. Suppose $D$ in (11) obeys

$D\geq(W(L_{2},{\cal D}({\cal G}^{-})-1)+W(L_{2},{\cal D}({\cal
G})-1))L_{1}\epsilon$ (70)

and at a time $t^{\prime}\geq t_{0}+T^{-}$ defined in (61), for some
$L\in\\{0,1,\cdots,{\cal D}({\cal G})-2\\}$

$\hat{x}_{i}(t)\leq x_{i}+W(L_{2},L)L_{1}\epsilon,~{}\forall i\in{\cal
F}_{L},~{}\forall t\geq t^{\prime}.$ (71)

Then with $T_{i}^{-}$ define in (69), there holds:

$\hat{x}_{i}(t)\leq x_{i}+W(L_{2},L+1)L_{1}\epsilon,~{}\forall~{}i\in{\cal
F}_{L+1},~{}t\geq t^{\prime}+T_{L+1}^{-}.$

The next theorem proves that the algorithm is ultimately bounded under bounded
persistent perturbations and provides an upper bound on the time to attain the
ultimate bound.

######  Theorem 3.

Under the conditions of Lemma 14, for all $i\in V$ and $t\geq
t_{0}+T^{-}+\sum_{i=0}^{{\cal D}({\cal G})-1}T^{-}_{i}$,

$|\hat{x}_{i}(t)-x_{i}|\leq\epsilon L_{1}\max\left\\{W(L_{2},{\cal D}({\cal
G})-1),W(L_{2},{\cal D}({\cal G}^{-})-1)\right\\}.$

This is a classical ultimate bound with the bound proportional to $\epsilon$,
the magnitude of the disturbance. Define

$T_{0}^{-}=\max\bigg{\\{}0,\bigg{\lceil}\frac{M-\min\\{\delta+s_{\min},X_{\max}\\}}{\delta}\bigg{\rceil}\bigg{\\}}+2.$
(72)

One can show that Theorem 3 holds for a tighter time bound if one uses
$T_{0}^{-}$ defined in (72). This is so as one can prove that
$\hat{x}_{i}(t_{0}+T^{-})\geq\min\\{\delta+s_{\min},X_{\max}\\}$ for all
$i\in{\cal F}_{0}$.

##  VI Design choices and discussion

Theorem 3 verifies the intuitively clear requirement that the dead zone $D$
should grow proportionally to the disturbance bound $\epsilon.$ However, as
this is a worst-case analysis, it masks the full effects of parameters $M$,
$\delta$, and $D.$ Looking beyond worst-case analysis, however, we can find
that choosing these parameters involves tradeoffs between the convergence
speed of underestimates and overestimates.

The convergence of underestimates is upper bounded by $T$ in (36), which is in
turn determined by (37), and thus conservatively by the smaller of $\sigma$
and $\delta$. In practice, if $\sigma$ is small and the first bullet of
raising is invoked too often then underestimates rise slowly, i.e. the rising
value problem will persist. If the second bullet of (11) is invoked at most
times and $\delta\gg\sigma$ then underestimates decline fast. Large $D$ or
small $M$ makes this less likely and slows convergence, while a large
$\delta\geq M$ speeds convergence by reducing $T$ and $T_{i}.$

For the convergence of overestimates, $T_{i}$ gives the worst case time to
invoke the first case of (11), whereupon all elements in ${\cal F}_{i}$
converge forthwith. The worst case analysis quantifies $T_{i}$ by how long it
takes for $\hat{x}_{i}(t)$ to exceed $M$ and assumes that the second clause of
(11) is invoked until this happens. With a large $D$, however, this time
shortens as the first bullet is likely to be invoked more quickly.

In most cases, the need to alleviate the rising value problem is more
compelling as overestimates in algorithms like plain ABF converge in at most
${\cal D}({\cal G})-1$ steps. Accordingly, the desirability of a smaller dead
zone $D$ competes with the requirement of resilience to persistent
perturbations as quantified by (70). This of course is common to most
dynamical systems where faster convergence generally comes at the price of
reduced resilience. We note, however, the following appealing fact: _both the
ultimate bound and the required $D$ are determined exclusively by the
perturbation magnitude $\epsilon$ and the effective diameters of the original
and shrunken graph._

Complementarily, note that in the special case of the algorithm in [24], we
effectively have $M=0$ and $D=\infty$. In this case the second bullet of (11)
is never invoked. Accordingly, a small $\sigma$ leads to large $T$ and $T^{-}$
and the rising value problem. In particular, the algorithm remains GUAS with
the same ultimate bound as (70) is automatically satisfied. Overestimates
however, converge quickly as $T_{i}=T_{i}^{-}=2.$

##  VII Simulations

In this section, we empirically confirm the results presented in the prior
sections through simulations. We first investigate the effect of parameters in
the general spreading block configured as GABF, then compare with the
performance of ABF in the presence of persistent perturbations. Finally, we
illustrate the applicability of the general spreading block to more complex
cases with an example of a non-Euclidean distance metric. Except where
otherwise noted, all simulations use 500 nodes, randomly distributed in a 4 km
$\times$ 1 km area, and communicating via broadcast within a 0.25 km radius.
One node is designated as a source and initial distance estimates of all nodes
follow a uniform distribution between 0 and $\sqrt{17}$ km (i.e., the longest
possible distance for the simulated space).

###  VII-A Effect of parameters

We begin with an empirical investigation of the design choices and parameter
effects discussed in Section VI, using GABF, as defined in Section II-B, as an
example to demonstrate the impact of these parameters on convergence speed.

Progress toward convergence may be measured using the greatest overestimate
$\Delta^{+}(t)$ and least underestimate $\Delta^{-}(t)$:

$\displaystyle\Delta^{+}(t)$ $\displaystyle=$
$\displaystyle\max\left[0,\max_{i}\left\\{\Delta_{i}(t)\right\\}\right]$ (73)
$\displaystyle\Delta^{-}(t)$ $\displaystyle=$
$\displaystyle\max\left[0,-\min_{i}\left\\{\Delta_{i}(t)\right\\}\right].$
(74)

where $\Delta_{i}(t)=\hat{d}_{i}(t)-d_{i}$ the distance estimation error of
node $i$. Then $\Delta^{+}(t)=\Delta^{-}(t)=0$ indicates that all distance
estimates converge to their true distances at time $t$.

(a) $\Delta^{+}(t)$ (b) $\Delta^{-}(t)$

Figure 5: Convergence time for (a) the greatest overestimate $\Delta^{+}(t)$
and (b) the least underestimate $\Delta^{-}(t)$ without perturbations, with
$M=5$, $D=0$ and $\delta$ is varying from $0.2M$ to $M$ in steps of $0.2M$.
The solid line represents the average value of 100 trials, the dotted and
dashed lines represent upper and lower envelopes, respectively. In (b) solid
and dotted lines of $\delta=0.8M$ and $\delta=M$ overlap, and dashed lines of
$\delta=0.4M$, $\delta=0.6M$, $\delta=0.8M$ and $\delta=M$ overlap.

We start with $\delta$, which controls how quickly $M$ is reached. Figure 5
shows the results of 100 runs using $M=5$, $D=0$, and $\delta$ varying from
$0.2M$ to $M$ in steps of $0.2M$. The average ${\cal D}({\cal G})$ is 18.8.
With a fixed $M$, both $\Delta^{+}(t)$ and $\Delta^{-}(t)$ converge slower
with a smaller $\delta$, since a smaller $\delta$ means estimates exceed $M$
later. The corresponding average convergence times are 61.2, 54.1, 38.1, 32.6
and 24.1.

(a) $\Delta^{+}(t)$ (b) $\Delta^{-}(t)$

Figure 6: Convergence time for (a) the greatest overestimate $\Delta^{+}(t)$
and (b) the least underestimate $\Delta^{-}(t)$ without perturbations, with
$\delta=M=5$ and $D=0,0.01K,0.1K,K$ and $4K$, using $K=({\cal D}({\cal
G})+{\cal D}({\cal G}^{-})-2)\epsilon$. The solid line represents the average
value of 100 trials, the dotted and dashed lines represent upper and lower
envelopes, respectively. In (b) dashed lines of $D=0,0.01K$ and $0.1K$
overlap.

The dead zone value $D$, on the other hand, has opposing effects on
$\Delta^{+}(t)$ and $\Delta^{-}(t)$. Figure 6 shows the results of 100 runs
using $\delta=M=5$ and $D=0,0.01K,0.1K,K$ and $4K$, using $K=({\cal D}({\cal
G})+{\cal D}({\cal G}^{-})-2)\epsilon$. In these simulations, the average
value of $\epsilon$ is $2.5\times 10^{-3}$ km and the average values of ${\cal
D}({\cal G})$ and ${\cal D}({\cal G}^{-})$ are 17.9 and 26.8, respectively.
For $\Delta^{+}(t)$, a large $D$ (e.g., $D=4K$) or a small $D$ (e.g., $D=0$)
accelerates convergence. In the former case GABF acts more like ABF in which
case ${\cal D}({\cal G})$ will converge within ${\cal D}({\cal G})-1$ rounds
[22]. In the latter case the second bullet of (11) will be frequently invoked
such that underestimates will be eliminated more quickly with a large $M$, and
thus $T$ defined in (36) becomes smaller. Both of these phenomena are seen in
these simulations, with the average convergence time of $\Delta^{+}(t)$ being
23.2, 67.9, 99.3, 34.0 and 6.5. As for $\Delta^{-}(t)$, A large $D$ always has
a negative impact on the convergence speed of $\Delta^{-}(t)$ since the
behavior of GABF is more like ABF in this situation, where the _rising value
problem_ [22, 24] will cause the underestimates rise very slowly. Here, the
average convergence time is 2, 49.3, 310.0, 535.9 and 631.7. Note that these
underestimates are more vulnerable to the change of $D$: while the time to
convergence of $\Delta^{+}(t)$ is roughly 60 rounds faster by increasing $D$
from $0.1K$ to $K$, that of $\Delta^{-}(t)$ may be hundreds of rounds slower
under such a change. Overall convergence time is thus regulated by
$\Delta^{+}(t)$ for small $D$ and by $\Delta^{-}(t)$ for large $D$, with the
joint average convergence time of 23.2, 67.9, 310.0, 535.9 and 631.7.

(a) $\Delta^{+}(t)$ (b) $\Delta^{-}(t)$

Figure 7: Convergence time for (a) the greatest overestimate $\Delta^{+}(t)$
and (b) the least underestimate $\Delta^{-}(t)$ without perturbations, with
$D=0$, $\delta=M$, and $M$ varying from 4.108 to 4.124. The solid line
represents the average value of 100 trials, the dotted and dashed lines
represent upper and lower envelopes, respectively. In (b) dashed lines of all
different M overlap, and dotted lines of $M=4.108$ and $4.112$ overlap.

Finally, the impact of $M$ may be separated out from the other two parameters
by setting $D=0$ and $\delta=M$. In this condition, small changes in $M$ can
result in large changes in convergence rate. Figure 7 illustrates this for 100
runs of GABF, with $D=0$, $\delta=M$, and $M$ increasing from 4.108 to 4.124
in steps of 0.004. In these simulations, the average ${\cal D}({\cal G})$ is
18.5. Here, convergence unconditionally improves with higher $M$: the average
convergence times of $\Delta^{+}(t)$ are 92.9, 72.6, 55.1, 32.0 and 23.7
rounds, while those of $\Delta^{-}(t)$ are 87.3, 63.0, 43.5, 14.4 and 2
rounds. Even though $T_{i}$ defined in (42) satisfies $T_{i}=3$ for all
different $M$, as we have set $\delta=M$, overestimates disappear more quickly
with larger $M$ because a larger $\delta$ helps the time $T$ defined in (36),
after which all states are overestimates becoming smaller by (IV-B) in Lemma
9. Underestimates converge more quickly once $M$ is greater than both the
largest true distance and initial distance estimate. In this case, all nodes
acquire overestimates in the first round by invoking the second bullet of
(11), and thus the underestimates converge in only 2 rounds.

###  VII-B Robustness against persistent perturbations

(a) $\Delta^{+}(t)$ and $({\cal D}({\cal G})-1)\epsilon$ (b) $\Delta^{-}(t)$
and $({\cal D}({\cal G}^{-})-1)\epsilon$

Figure 8: Robustness against perturbation for GABF with various values of $D$,
compared over 100 trials with ultimate bounds and with ABF: (a) mean values of
$\Delta^{+}(t)$ and mean value of ultimate bound $({\cal D}({\cal
G})-1)\epsilon$, and (b) mean values of $\Delta^{-}(t)$ and mean value of
ultimate bound $({\cal D}({\cal G}^{-})-1)\epsilon$. Edge lengths are
perturbed by measurement errors uniformly distributed between 0 and
$e_{\min}$. Parameters for GABF are set as $\delta=M=\sqrt{17}$,
$D=0,0.02K,0.05K,0.2K,0.4K,K$ and $2K$, where $K=({\cal D}({\cal G})+{\cal
D}({\cal G}^{-})-2)\epsilon$. In (a), lines of $D=0,0.02K$ and $0.05K$
overlap.

As discussed in Section VI, robustness against perturbation should be
controlled primarily by parameter $D$. In particular, $({\cal D}({\cal
G})-1)\epsilon$ and $({\cal D}({\cal G}^{-})-1)\epsilon$ are the ultimate
bounds of $\Delta^{+}(t)$ and $\Delta^{-}(t)$ under perturbations,
respectively [22] (i.e., $L_{1}W(L_{2},{\cal D}({\cal G})-1)$ and
$L_{1}W(L_{2},{\cal D}({\cal G}^{-})-1)$ in Theorem 14, respectively), and
thus $({\cal D}({\cal G})+{\cal D}({\cal G}^{-})-2)\epsilon$ is the minimum
value of $D$ to guarantee the robustness of GABF under perturbations.

Figure 8 illustrates this for 100 runs of GABF, comparing this ultimate
boundedness with ABF and with GABF using $\delta=M=\sqrt{17}$ and
$D=0,0.02K,0.05K,0.2K,0.4K,K$ or $2K$, where $K=({\cal D}({\cal G})+{\cal
D}({\cal G}^{-})-2)\epsilon$, $\epsilon=0.05e_{\min}$. Perturbation is
injected as asymmetric noise in the estimated $e_{ij}$, such that measurement
errors $\epsilon_{ij}(t)$ defined in (49) follow a uniform distribution
between 0 and $0.05e_{\min}$ in each round. In these simulations, the average
value of $e_{\min}$ defined in (50) is $2.9\times 10^{-3}$ km, ${\cal D}({\cal
G})=18.6$ and ${\cal D}({\cal G}^{-})=20.0$ on average.

The results show the tradeoffs in $\Delta^{+}(t)$ versus $\Delta^{-}(t)$ with
GABF. For $\Delta^{-}(t)$, ABF is constrained by the _rising value problem_
[22, 24] such that $\Delta^{-}(t)$ needs a much longer time than
$\Delta^{+}(t)$ to drop below than its ultimate bound. With GABF, lower values
of $D$ increase the speed of convergence, with $D=0$ achieving the fastest
time. For $\Delta^{+}(t)$, on the other hand, ABF converges extremely quickly,
while GABF does not converge at all for low values of $D$. In this case, GABF
with $D=0,0.02K,0.05K,0.2K$ and $0.4K$ will not be ultimately bounded, while
the average time for ABF and GBAF with $D=K$ and $2K$ to drop below the
ultimate bounds follows 859.3, 196.5 and 300.1 rounds. Further, the average
time for ABF and GABF with $D=K$ or $2K$ to reach the bottom is 5750 and 2406
rounds, respectively. Combining both, we find that GABF outperforms ABF under
perturbations when the dead zone value $D$ is equal to or slightly larger than
the minimum required value defined in (70). Thus, when the general spreading
block is under perturbation, $D$ should be set as $(W(L_{2},{\cal D}({\cal
G}^{-})-1)+W(L_{2},{\cal D}({\cal G})-1))L_{1}\epsilon$ defined in (70) of
Lemma 14 in order to guarantee robustness and meanwhile attain a fast
convergence speed. Observe though the floor is much below the theoretical
ultimate bound, and even with $D=.04K$, $\Delta^{+}(t)$ though persistently
rising from the floor rises only up to the unltimate bound.

###  VII-C Non-Euclidean Distance

(a) The spreading block of (1) (b) The more general spreading block of
(9)-(11)

Figure 9: In this example, 400 nodes are randomly located in a $4\times 4$
$\mathrm{km}^{2}$ field. There is a source at the red asterisk located at
(0.3, 0.3), and the middle of the field is a $2.5\times 2.5$ $\mathrm{km}^{2}$
radiation zone. Color represents degree of contamination, with a logarithmic
scale. While both spreading block and the general spreading block can achieve
the shortest available path, the fast convergence of the general spreading
block greatly reduces total contamination.

Finally, we illustrate how the general spreading block can accommodate non-
Euclidean distance metrics. Figure 9 shows example of a nonlinear
$f(\cdot,\cdot)$ in (1), for nodes to compute paths minimizing exposure to a
hazard. In this scenario, 500 nodes are randomly distributed in a $4\times 4$
$\mathrm{km}^{2}$ field, and communicate over a 0.6 km radius. A source is
located at (0.3, 0.3). In the middle of the area, there exists a $2.5\times
2.5$ $\mathrm{km}^{2}$ _radiation zone_ centered at (1.95, 1.95). Define
$\mathcal{M}$ as the set of nodes in the radiation zone, a node $i$ is
radioactive if $i\in\mathcal{M}$ or $i$ has ever taken a radioactive node as
its constraining node. $f(\hat{x}_{k}(t),e_{ik})$ in (1) obeys
$f(\hat{x}_{k}(t),e_{ik})=\hat{x}_{k}(t)+e_{ik},k\notin\mathcal{M}$, where
$e_{ik}$ is the edge length between node $i$ and $k$. When $k\in\mathcal{M}$,
$f(\hat{x}_{k}(t),e_{ik})=h(\hat{x}_{k}(t)+1000e_{ik})$, where $h(a)=a^{1.5}$
if $a>1$ and $a$ otherwise. Further, $s_{i}$ defined in (1) is 0 if $i$ is a
source and $\infty$ otherwise. In each round a node $i$ will receive
100$\sim$120 units of radiation dose if it is radioactive and 0$\sim$1 unit
otherwise. Figure 9(a) shows the result of using the spreading block defined
in (1), while Figure 9(b) shows the result from setting
$D=0,\delta=M>x_{\max}$ in the general spreading block. In both cases, nodes
outside the radiation zone never cross the zone due to the high cost, and
nodes inside the zone take the shortest path to exit the zone. However, the
degree of contamination is greatly reduced when using the general spreading
block with appropriately chosen parameters, due to the much faster time of
convergence to a safe path.

##  VIII Conclusion

We have improved a general algorithm for spreading information across a
network of devices by making it resilient to perturbations and by removing a
prior boundedness assumption. This algorithm, a key building block for
aggregate computing and applicable to a wide range of distributed systems, has
parameters that remove the rising value problem that appears in some of its
special cases, such as ABF. Unlike ABF, however, the general spreading
algorithm covers a much wider class of uses and application, such as dealing
with non-Euclidean distance metrics. We have proven global uniform asymptotic
stability for this algorithm and provide ultimate bounds in face of persistent
network disturbances using an additional Lipschitz condition. Notably, the
ultimate bounds depend only on the largest perturbation and structural network
properties. Finally, we provide design guidelines for the three new
parameters, demonstrating how algorithm parameters have competing effects on
performance.

These results are a crucial stepping stone in our long term goal of
determining stability conditions for feedback interconnections of aggregate
computing blocks, using possibly new small gain theorems, [20], or equivalent
techniques, [27], like the passivity theorem and its variants, [28]. Progress
in this program has broad applicability for the engineering of resilient
distributed systems.

## References

  * [1] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” _Proceedings of the IEEE_ , vol. 95, no. 1, pp. 215–233, 2007.
  * [2] J. Baillieul and A. Suri, “Information patterns and hedging brockett’s theorem in controlling vehicle formations,” in _42nd IEEE International Conference on Decision and Control (IEEE Cat. No. 03CH37475)_ , vol. 1, 2003, pp. 556–563.
  * [3] T. H. Summers, C. Yu, B. D. Anderson, and S. Dasgupta, “Formation shape control: Global asymptotic stability of a four-agent formation,” in _Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference_ , 2009, pp. 3002–3007.
  * [4] T. H. Summers, C. Yu, S. Dasgupta, and B. D. Anderson, “Control of minimally persistent leader-remote-follower and coleader formations in the plane,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 12, pp. 2778–2792, 2011.
  * [5] M. Arcak, “Passivity as a design tool for group coordination,” _IEEE Transactions on Automatic Control_ , vol. 52, no. 8, pp. 1380–1390, 2007.
  * [6] T. Hatanaka, N. Chopra, M. Fujita, and M. W. Spong, _Passivity-based control and estimation in networked robotics_. Springer, 2015.
  * [7] S. Güler, B. Fidan, S. Dasgupta, B. D. Anderson, and I. Shames, “Adaptive source localization based station keeping of autonomous vehicles,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 7, pp. 3122–3135, 2016.
  * [8] B. Fidan, S. Dasgupta, and B. D. Anderson, “Adaptive range-measurement-based target pursuit,” _International Journal of Adaptive Control and Signal Processing_ , vol. 27, no. 1-2, pp. 66–81, 2013.
  * [9] T. H. Summers, C. Yu, S. Dasgupta, and B. D. Anderson, “Control of minimally persistent leader-remote-follower and coleader formations in the plane,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 12, pp. 2778–2792, 2011.
  * [10] J. Beal, D. Pianini, and M. Viroli, “Aggregate programming for the internet of things,” _Computer_ , vol. 48, no. 9, pp. 22–30, 2015.
  * [11] A. Russel, “Osi: The internet that wasn’t,” _IEEE Spectrum_ , vol. 50, no. 8.
  * [12] J. Beal and M. Viroli, “Building blocks for aggregate programming of self-organising applications,” in _2014 IEEE Eighth International Conference on Self-Adaptive and Self-Organizing Systems Workshops_ , 2014, pp. 8–13.
  * [13] M. Viroli and F. Damiani, “A calculus of self-stabilising computational fields,” in _International Conference on Coordination Languages and Models_. Springer, 2014, pp. 163–178.
  * [14] M. Viroli, G. Audrito, J. Beal, F. Damiani, and D. Pianini, “Engineering resilient collective adaptive systems by self-stabilisation,” _ACM Transactions on Modeling and Computer Simulation_ , pp. 16:1–16:28, 2018.
  * [15] A. Kumar, J. Beal, S. Dasgupta, and R. Mudumbai, “Toward predicting distributed systems dynamics,” in _2015 IEEE International Conference on Self-Adaptive and Self-Organizing Systems Workshops_ , 2015, pp. 68–73.
  * [16] M. Viroli, J. Beal, F. Damiani, and D. Pianini, “Efficient engineering of complex self-organising systems by self-stabilising fields,” in _2015 IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems_ , 2015, pp. 81–90.
  * [17] J. Beal, J. Bachrach, D. Vickery, and M. Tobenkin, “Fast self-healing gradients,” in _Proceedings of the 2008 ACM symposium on Applied computing_ , 2008, pp. 1969–1975.
  * [18] H. K. Khalil, “Nonlinear systems,” _Upper Saddle River_ , 2002.
  * [19] W. Hahn, _Stability of motion_. Springer, 1967, vol. 138.
  * [20] Z.-P. Jiang, I. M. Mareels, and Y. Wang, “A lyapunov formulation of the nonlinear small-gain theorem for interconnected iss systems,” _Automatica_ , vol. 32, no. 8, pp. 1211–1215, 1996.
  * [21] S. Dasgupta and J. Beal, “A Lyapunov analysis for the robust stability of an Adaptive Bellman-Ford Algorithm,” in _Proceedings of IEEE 55th Conference on Decision and Control (CDC)_ , 2016, pp. 7282–7287.
  * [22] Y. Mo, S. Dasgupta, and J. Beal, “Robustness of the Adaptive Bellman-Ford Algorithm: Global stability and ultimate bounds,” _IEEE Transactions on Automatic Control_ , pp. 4121–4136, 2019.
  * [23] R. Bellman, “On a routing problem,” _Quarterly of applied mathematics_ , vol. 16, no. 1, pp. 87–90, 1958.
  * [24] Y. Mo, S. Dasgupta, and J. Beal, “Robust stability of spreading blocks in aggregate computing,” in _2018 IEEE Conference on Decision and Control (CDC)_ , 2018, pp. 6007–6012.
  * [25] M. Viroli, G. Audrito, J. Beal, F. Damiani, and D. Pianini, “Engineering resilient collective adaptive systems by self-stabilisation,” _ACM Transactions on Modeling and Computer Simulation (TOMACS)_ , vol. 28, pp. 16:1–16:28, 2018.
  * [26] Y. Mo, S. Dasgupta, and J. Beal, “Global uniform asymptotic stability of a generalized adaptive bellman-ford algorithm,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_ , 2019, pp. 1868–1873.
  * [27] B. D. Anderson, “The small-gain theorem, the passivity theorem and their equivalence,” _Journal of the Franklin Institute_ , vol. 293, no. 2, pp. 105–115, 1972.
  * [28] M. Fu, S. Dasgupta, and Y. C. Soh, “Integral quadratic constraint approach vs. multiplier approach,” _Automatica_ , vol. 41, no. 2, pp. 281–287, 2005.

Proof of Lemma 11: From Definition 6, (33) still holds if (10) is replaced by
(52). Thus ${\cal U}(t)$ can be nonempty only on a single contiguous time
interval commencing at $t_{0}$.

We prove (62) by induction. As it holds for $t=t_{0}$, suppose (62) holds for
some $t\geq t_{0}$. Consider $i\in{\cal U}(t+1)$ with
$\hat{x}_{i}(t+1)=\hat{x}_{\min}(t+1)$. Then ${\cal U}(t)\neq\emptyset$ and
$j$ the constraining node of $i$ is in ${\cal U}(t)$. If $i\in{\cal E}(t+1)$
in Definition 1 then from Definition 2, $j=i$. From the induction hypothesis
and (12)

$\displaystyle\hat{x}_{i}(t+1)$ $\displaystyle=$
$\displaystyle\hat{x}_{\min}(t+1)$ $\displaystyle\geq$
$\displaystyle\hat{x}_{j}(t)+\delta\geq\hat{x}_{\min}(t)+\min\\{\sigma,\delta\\}$
$\displaystyle\geq$
$\displaystyle\hat{x}_{\min}(t_{0})+\min\\{\sigma,\delta\\}(t+1-t_{0}).$

If $i\in{\cal A}(t+1)\cap{\cal U}(t+1)$, then, $i\notin{\cal S}(t+1)$, i.e.
$\hat{x}_{i}(t+1)\neq s_{i}.$ From the induction hypothesis and (52) we have

$\displaystyle\hat{x}_{i}(t+1)=$
$\displaystyle\hat{x}_{\min}(t+1)=f(\hat{x}_{j}(t),e_{ij}(t))$
$\displaystyle\geq\hat{x}_{j}(t)+\sigma\geq\min\\{\sigma,\delta\\}(t+1-t_{0}).$

Further with (60) and (61), (63) follows.

Proof of Lemma 12: If ${\cal R}(t)\neq\emptyset$, then $\exists~{}t_{5},t_{6}$
such that $\forall t_{0}\leq t_{5}\leq t\leq t_{6}$ and ${\cal R}(t_{5})={\cal
S}(t_{5})$. As $\hat{x}_{i}(t_{5})=s_{i}$ for all $i\in{\cal S}(t_{5})={\cal
R}(t_{5})$, from (59) the result holds for $t=t_{5}$.

Suppose $\hat{x}_{i}(t)\geq X_{i}$ for some $t_{5}\leq t<t_{6}$ and all
$i\in{\cal R}(t)$. Consider any $i\in{\cal R}(t+1)$. From Definition 6, either
$i\in{\cal S}(t+1)$ in which case the rsult holds, or or $i$ is constrained by
some $j\in{\cal R}(t).$ If $i\in{\cal A}(t+1)$, then by the induction
hypothesis, $\hat{x}_{j}(t)\geq X_{j}$. As $i\notin{\cal S}(t+1)$, there
follows:

$\displaystyle\hat{x}_{i}(t+1)$ $\displaystyle=$ $\displaystyle
f(\hat{x}_{j}(t),e_{ij}(t))$ (75) $\displaystyle\geq$ $\displaystyle
f(X_{j},e_{ij}^{-})$ $\displaystyle\geq$ $\displaystyle X_{i}$ (76)

where (75) uses $e_{ij}(t)\geq e_{ij}^{-}$ for all $t$ and the fact that
$f(\cdot,\cdot)$ is increasing in each argument, and (76) uses (58). If
$i\in{\cal E}(t+1)$, then $i$ is its own constraining node and $i\in{\cal
R}(t)$. Thus by our induction hypothesis, $\hat{x}_{i}(t)\geq X_{i}$. From
(12),

$\hat{x}_{i}(t+1)\geq\hat{x}_{i}(t)+\delta>X_{i}.$ (77)

Proof of Lemma 13: Consider nodes $n_{0},n_{1},\cdots,n_{T}$ such that
$n_{0}\in{\cal S}_{\infty}^{-}$, and for all $i\in\\{0,\dots,T-1\\}$, $n_{i}$
is a true constraining node of $n_{i+1}$ in ${\cal G}^{-}$. Each node in
${\cal G}^{-}$ is in one such sequence. As from Definition 7, $T\leq{\cal
D}({\cal G}^{-})-1$, the result will follow if

$x_{n_{i}}-X_{n_{i}}\leq W(L_{2},i)L_{1}\epsilon,~{}\forall
i\in\\{0,\cdots,T\\}.$ (78)

Evidently, $x_{n_{0}}\leq s_{n_{0}}=X_{n_{0}}$. Suppose (78) holds for some
$i\in\\{0,\cdots,T-1\\}$. As $n_{i}$ and $n_{i+1}$ are neighbors in both
${\cal G}$ and ${\cal G}^{-}$, $n_{i}$ is a true constraining node of
$n_{i+1}$ in ${\cal G}^{-}$ and $x_{n_{i}}\leq
X_{n_{i}}+W(L_{2},i)L_{1}\epsilon$ by our induction hypothesis,

$\displaystyle x_{n_{i+1}}$ $\displaystyle\leq f(x_{n_{i}},e_{n_{i}n_{i+1}})$
$\displaystyle\leq f(X_{n_{i}}+W(L_{2},i)L_{1}\epsilon,e_{n_{i}n_{i+1}})$
$\displaystyle\leq f(X_{n_{i}},e_{n_{i}n_{i+1}})+L_{2}W(L_{2},i)L_{1}\epsilon$
(79)
$\displaystyle=f(X_{n_{i}},e_{n_{i}n_{i+1}}^{-}+\epsilon)+L_{2}W(L_{2},i)L_{1}\epsilon$
(80) $\displaystyle\leq
f(X_{n_{i}},e_{n_{i}n_{i+1}}^{-})+L_{1}\epsilon+L_{2}W(L_{2},i)L_{1}\epsilon$
(81) $\displaystyle=X_{n_{i+1}}+W(L_{2},i+1)L_{1}\epsilon$ (82)

where (79) uses (48), (80) uses (53), (81) uses (47), and (82) uses the fact
that $n_{i}$ is a true constraining node of $n_{i+1}$ in ${\cal G}^{-}$.

Proof of Lemma 14: Consider any $i\in{\cal F}_{L+1}$. Because of (11) and
(12), there is a $t^{\prime}<t\leq t^{\prime}+T_{L+1}^{-}$ such that
$i\in{\cal A}(t)$. This is so as $i\in{\cal E}(t)$ implies
$\hat{x}_{i}(t+1)\geq\hat{x}_{i}(t)+\delta$ and at some time in the interval
$(t^{\prime},t^{\prime}+T_{L+1}^{-}]$, $\hat{x}_{i}(\cdot)>M$. From Lemma 5,
there is a $j\in{\cal F}_{L}$ that is a true constraining node of $i$ in
${\cal G}$. Thus $\hat{x}_{j}(t-1)\leq x_{j}+W(L_{2},L)L_{1}\epsilon$ by (71).
Then

$\displaystyle\hat{x}_{i}(t)$ $\displaystyle=\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(\hat{x}_{k}(t-1),e_{ik}(t-1)\right)\right\\},s_{i}\right\\}$
$\displaystyle\leq f(\hat{x}_{j}(t-1),e_{ij}(t-1))$ $\displaystyle\leq
f(x_{j}+W(L_{2},L)L_{1}\epsilon,e_{ij}+\epsilon)$ (83) $\displaystyle\leq
f(x_{j},e_{ij})+L_{2}W(L_{2},L)L_{1}\epsilon+L_{1}\epsilon$ (84)
$\displaystyle=x_{i}+W(L_{2},L+1)L_{1}\epsilon$ (85)

where (83) uses (49), (50) and (71), (84) uses (47) and (48). Similarly, as
(71) holds for all $t\geq T^{-}+t_{0}$ for all $j\in{\cal F}_{L}$,

$\tilde{x}(t+1)\leq x_{i}+W(L_{2},L+1)L_{1}\epsilon.$ (86)

As $t>t_{0}+T^{-}$, (65) implies that $\hat{x}_{k}(t)\geq X_{k}$ for all $k\in
V$. As $f(\cdot,\cdot)$ is monotonically increasing in both its arguments and
$X_{i}\leq s_{i}$, (56) implies that

$\displaystyle\tilde{x}_{i}(t+1)=\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(\hat{x}_{k}(t),e_{ik}(t)\right)\right\\},s_{i}\right\\}$
$\displaystyle\geq\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(X_{k},e_{ik}^{-}\right)\right\\},s_{i}\right\\}=X_{i},$

i.e. $\left[X_{i},x_{i}+W(L_{2},L+1)L_{1}\epsilon\right]$ contains both
$\hat{x}_{i}(t)$ and $\tilde{x}_{i}(t+1)$. Then (70) and Lemma 13 yield

$\displaystyle|\tilde{x}_{i}(t+1)-\hat{x}_{i}(t)|$ $\displaystyle\leq$
$\displaystyle|x_{i}+W(L_{2},L+1)L_{1}\epsilon-X_{i}|$ $\displaystyle\leq$
$\displaystyle W(L_{2},{\cal D}({\cal G}^{-})-1)L_{1}\epsilon+$ $\displaystyle
W(L_{2},L+1)L_{1}\epsilon\leq D,$

i.e, $\hat{x}_{i}(t+1)=\tilde{x}_{i}(t+1)$. An induction proves the result.

Proof of Theorem 3: From Lemma 13 and (65)

$\hat{x}_{i}(t)-x_{i}\geq-W(L_{2},{\cal D}({\cal
G}^{-})-1)L_{1}\epsilon~{}\forall~{}t\geq t_{0}+T^{-},$ (87)

proving the lower bound on $\hat{x}_{i}(t)-x_{i}$ implicit in the theorem
statement. To prove the upper bound we will first show that

$\hat{x}_{i}(t)\leq x_{i}=x_{i}+W(L_{2},0),~{}\forall i\in{\cal
F}_{0},~{}t\geq t_{0}+T^{-}+T_{0}^{-}.$ (88)

Then the repeated application of Lemma 14 will prove that

$\hat{x}_{i}(t)-x_{i}\leq W(L_{2},{\cal D}({\cal
G})-1)L_{1}\epsilon~{}\forall~{}t\geq t_{0}+T^{-}+\sum_{i=0}^{{\cal D}({\cal
G})-1}T^{-}_{i}$

and thus the theorem.

Consider $i\in{\cal F}_{0}.$ As $i\in{\cal E}(t)$ implies
$\hat{x}_{i}(t+1)\geq\hat{x}_{i}(t)+\delta$ from (11), (12) and (69), there is
a $t_{0}+T^{-}<t\leq t_{0}+T^{-}+T_{0}^{-}$ such that $i\in{\cal A}(t)$. As
${\cal F}_{0}\subset{\cal S}_{\infty}$, from (17)

$\displaystyle\hat{x}_{i}(t)=\tilde{x}_{i}(t)$ $\displaystyle\leq
s_{i}=x_{i}.$ (89)

As $t>t_{0}+T^{-}$, it follows from (65) that $\hat{x}_{k}(t)\geq X_{k}$ for
all $k\in V$. As $f(\cdot,\cdot)$ is monotonically increasing in both its
arguments and $X_{i}\leq s_{i}$, we obtain

$\displaystyle\tilde{x}_{i}(t+1)=\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(\hat{x}_{k}(t),e_{ik}(t)\right)\right\\},s_{i}\right\\}$
$\displaystyle\geq\min\left\\{\min_{k\in{\cal
N}(i)}\left\\{f\left(X_{k},e_{ik}^{-}\right)\right\\},s_{i}\right\\}=X_{i}$
(90)

where (90) uses (56). Therefore, $\left[X_{i},x_{i}\right]$ contains both
$\hat{x}_{i}(t)$ and $\tilde{x}_{i}(t+1)$. Then (70) and Lemma 13 yield

$\displaystyle|\tilde{x}_{i}(t+1)-\hat{x}_{i}(t)|$
$\displaystyle\leq|x_{i}-X_{i}|$ $\displaystyle=W(L_{2},{\cal D}({\cal
G}^{-})-1)L_{1}\epsilon$ $\displaystyle<D$

From (9-11), $\hat{x}_{i}(t+1)=\tilde{x}_{i}(t+1)$. Am induction proves (88).

|  Yuanqiu Mo was born in Yangzhou, China, in 1991. He received the Ph.D.
degree in electrical and computer engineering at the University of Iowa, in
2019. He is currently a postdoc with the Westlake University. His research
interests include distributed algorithm design and stability theory. Dr. Mo
has been awarded the 2018 CDC Outstanding Student Paper Award. He was a
finalist of the Young Author Award in the IFAC World Congress 2020.
---|---
|  Soura Dasgupta, (M’87, SM’93, F’98) was born in 1959 in Calcutta, India. He
received the B.E. degree (Hons. I) in Electrical Engineering from the
University of Queensland (Australia) in 1980, and the Ph.D. in Systems
Engineering from the Australian National University, in 1985. He is currently
F. Wendell Miller Distinguished Professor in the Department of Electrical and
Computer Engineering at the University of Iowa, U.S.A and holds a visiting
appointment in the Shandong Academy of Sciences. In 1981, he was a Junior
Research Fellow at the Indian Statistical Institute, Calcutta. He has held
visiting appointments at the University of Notre Dame, University of Iowa,
Universite Catholique de Louvain-La-Neuve, Belgium, Tata Consulting Services,
Hyderabad, the Australian National University and National ICT Australia. From
1988 to 1991, 1998 to 2009 and 2004 to 2007 he respectively served as an
Associate Editor of the IEEE TRANSACTIONS ON AUTOMATIC CONTROL, IEEE Control
Systems Society Conference Editorial Board, and the IEEE TRANSACTIONS ON
CIRCUITS AND SYSTEMS- II. He is a co-recipient of the Gullimen Cauer Award for
the best paper published in the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS in
the calendar years of 1990 and 1991, a past Presidential Faculty Fellow, a
past subject editor for the International Journal of Adaptive Control and
Signal Processing, and a member of the editorial board of the EURASIP Journal
of Wireless Communications. In 2012 he was awarded the University Iowa
Collegiate Teaching award. In the same year he was selected by the graduating
class for excellence in teaching and commitment to student success. From
2016-18 he was a 1000 Talents Scholar in the People’s Republic of China. His
research interests are in Controls, Signal Processing, Communications and
Parkinson’s Disease. He was elected a Fellow of the IEEE in 1998.
---|---
|  Jacob Beal is a scientist at Raytheon BBN Technologies in Cambridge,
Massachusetts. His research focuses on the engineering of robust adaptive
systems, particularly on the problems of aggregate-level modeling and control
for spatially distributed systems like pervasive wireless networks, robotic
swarms, and natural or engineered biological cells. Dr. Beal received a PhD in
electrical engineering and computer science from MIT. He is an associate
editor of ACM Transactions on Autonomous and Adaptive Systems, is on the
steering committee of the IEEE International Conference on Self-Adapting and
Self-Organizing Systems (SASO), and is a founder of the Spatial Computing
Workshop series. He is a Senior Member of IEEE. Contact him at
<EMAIL_ADDRESS>
---|---