# Distributed averaging for accuracy prediction in networked systems

Christel Sirocchi1 and Alessandro Bogliolo2 1Christel Sirocchi is a PhD
candidate in Research Methods in Science and Technology at the Department of
Pure and Applied Sciences, University of Urbino (Italy)
<EMAIL_ADDRESS>Bogliolo is a Full Professor of
Computer Science at the Department of Pure and Applied Sciences, University of
Urbino (Italy<EMAIL_ADDRESS>
###### Abstract

Distributed averaging is among the most relevant cooperative control problems,
with applications in sensor and robotic networks, distributed signal
processing, data fusion, and load balancing. Consensus and gossip algorithms
have been investigated and successfully deployed in multi-agent systems to
perform distributed averaging in synchronous and asynchronous settings. This
study proposes a heuristic approach to estimate the convergence rate of
averaging algorithms in a distributed manner, relying on the computation and
propagation of local graph metrics while entailing simple data elaboration and
small message passing. The protocol enables nodes to predict the time (or the
number of interactions) needed to estimate the global average with the desired
accuracy. Consequently, nodes can make informed decisions on their use of
measured and estimated data while gaining awareness of the global structure of
the network, as well as their role in it. The study presents relevant
applications to outliers identification and performance evaluation in
switching topologies.

##  I INTRODUCTION

Distributed averaging is an instance of distributed computation aiming to
determine the global average of a set of values by iterating local
calculations. It has been extensively studied as the primary tool for solving
cooperative control problems in multi-agent systems [1] such as distributed
sensor networks, micro-grids, transport networks, power distribution systems,
and biological networks [2]. In these settings, the value of an aggregate
function over the entire network data is often more relevant than individual
data at nodes. Networks of temperature sensors, for instance, are generally
deployed to assess the average temperature in a given area. Similarly, peer-
to-peer systems are primarily interested in calculating the average size of
stored files [3]. Other collective behaviours leveraging distributed averaging
include formation control of autonomous vehicles, network synchronisation,
automated traffic networks, cooperative output regulation, and containment
control [4].
The performance of a distributed averaging protocol is generally evaluated as
the resources required to obtain an estimate of the global average with the
desired level of accuracy. Performance analysis is fundamental to networked
systems, as they typically suffer limitations in terms of communication
bandwidth, memory, and computational power [5]. Previous work has focused on
deriving theoretical performance guarantees in synchronous [6] and
asynchronous [7] models and identified a dependency on the eigenvalues of the
matrix characterising the algorithm. However, these results cannot help make
local and accurate performance predictions, as they identify wide performance
intervals and require knowledge of the entire network structure for
eigenvalues calculations. In contrast, this work proposes a strategy to
estimate global properties of the graph and the performance of the averaging
algorithm in a distributed manner, entailing simple data elaboration and small
message passing. As a result, agents can predict the time (or the number of
interactions) needed to achieve the desired accuracy, make informed decisions
on their use of measured and estimated data, and also gain awareness of the
global network structure.
The remainder of the paper is organised as follows. Section II provides some
relevant background on averaging algorithms, citing previous results on
convergence for synchronous and asynchronous models. The problem is formulated
in Section III, and the proposed strategy is outlined in Section IV. Section V
presents relevant applications, and finally, Section VI provides conclusions
and directions for future work.

##  II BACKGROUND

###  II-A Network Topology

The communication constraints in networked systems can be conveniently
modelled via a graph $G=(V,E)$, where $V$ is the vertex set of $n$ nodes
$v_{i}$, with $i\in I=\\{1,\dots,n\\}$ and $n\in N$, and $E$ is the edge set
$E\subseteq V\times V$ of the pairs $e_{ij}=(v_{i},v_{j})$, so that there is
an edge between nodes $v_{i}$ and $v_{j}$ iff $(v_{i},v_{j})\in E$. In
undirected graphs, edges $e_{ij}\in E$ are unordered pairs ($v_{i}$, $v_{j}$)
of elements of $V$. All nodes that can transmit information to node $v_{i}$
are said to be its neighbours and are represented by the set
$\Omega_{i}=\\{v_{j}:(v_{i},v_{j})\in E\\}$.

###  II-B Distributed average

Let $x_{i}$ denote the value of node $v_{i}$, representing a physical quantity
such as position, temperature, light intensity or voltage, and
$\textbf{x}=(x_{1},...,x_{n})^{T}$ the vector of values so that the $i^{th}$
component of x is the value at node $v_{i}$. The nodes $v_{i}$ and $v_{j}$ are
said to agree in a network iff $x_{i}=x_{j}$. All nodes in $G$ are in
agreement or have reached a consensus iff $x_{i}=x_{j}\,\forall\,i,j\in I$.
This agreement space can also be expressed as $\textbf{x}=\alpha\textbf{1}$
where $\textbf{1}=(1,...,1)^{T}$ and $\alpha\in R$ is the collective decision
value of the nodes. The system is said to reach asymptotic consensus if all
nodes asymptotically converge to $\alpha$, i.e.

$\lim_{t\to+\infty}x_{i}(t)=\alpha,\forall i\in I.$

A consensus algorithm (or protocol) is an interaction rule that specifies the
information exchange between an agent and its neighbours to reach a consensus
[6], i.e. to asymptotically converge to the agreement space [8]. One of the
benefits of using linear iteration-based schemes is that each node only
transmits a single value to each of its neighbours [8]. In discrete time, the
consensus protocol is

$\textbf{x}(k)=\textbf{W}(k)\,\textbf{x}(k-1)$ (1)

where $\textbf{x}(k)$ is the vector of values at the end of time slot $k$, and
W is the $n\times n$ matrix of averaging weights. When the consensus value
corresponds to the average of all initial values, i.e.
$\alpha=\frac{1}{n}\sum_{i=1}^{n}x_{i}(0)$, the system is said to perform
distributed averaging. In consensus protocols with time-invariant weight
matrix W, the linear iteration implies

$\textbf{x}(k)=\textbf{W}^{k}\,\textbf{x}(0).$ (2)

To achieve asymptotic average consensus regardless of the initial values
$\textbf{x}(0)$

$\lim_{t\to+\infty}\textbf{W}^{t}=\frac{\textbf{1}\textbf{1}^{T}}{n}$ (3)

which follows from

$\lim_{t\to+\infty}\textbf{x}(t)=\lim_{t\to+\infty}\textbf{W}^{t}\textbf{x}(0)=\frac{\textbf{1}\textbf{1}^{T}}{n}\;\textbf{x}(0).$
(4)

Eq. 3 holds iff the following three properties are satisfied:

$\textbf{1}^{T}\textbf{W}=\textbf{1}^{T}$ (5)

i.e. 1 is a left eigenvector of W associated with the eigenvalue 1, implying
that $\textbf{1}^{T}\textbf{x}(k+1)=\textbf{1}^{T}\textbf{x}(k)$ $\forall\;k$,
i.e., the sum, and therefore the average, of the vector of node values is
preserved at each step;

$\textbf{W}\;\textbf{1}=\textbf{1}$ (6)

i.e. 1 is also a right eigenvector of W associated with the eigenvalue 1,
meaning that 1, or any vector with constant entries, is a fixed point for the
linear iteration;

$\rho(\textbf{W}-\frac{\textbf{1}\textbf{1}^{T}}{n})<1$ (7)

where $\rho(\cdot)$ denotes the spectral radius of a matrix, which, combined
with the first two conditions, states that 1 is a simple eigenvalue of W, and
all other eigenvalues have a magnitude strictly less than 1 [9].

The disagreement vector $\boldsymbol{\delta}(k)$ quantifies the distance from
consensus at time slot $k$ and can be computed as

$\boldsymbol{\delta}(k)=\textbf{x}(k)-\alpha\textbf{1}.$ (8)

Notably, this vector evolves according to the same linear system as the vector
of values:

$\boldsymbol{\delta}(k)=\textbf{W}(k)\boldsymbol{\delta}(k-1).$ (9)

Iterative distributed averaging algorithms are often classified based on the
adopted time model. Gossip algorithms realise asynchronous averaging schemes
so that a single pair of neighbouring nodes interact at each time $k$, setting
their values to the average of their previous values [10]. In contrast,
consensus algorithms implement a synchronous model where time is commonly
slotted across nodes, and all nodes simultaneously update their values with a
linear combination of the values of their neighbours at discrete times $k$.
Gossip protocols are more suited to model real networks and are generally more
accessible to implement for the lack of synchronisation requirements,
unrealistic for most applications [11], but are harder to characterise
mathematically due to the added randomness of the neighbour selection.

###  II-C Gossip algorithms

In asynchronous gossip protocols, a single node is active at each time slot
$k$ and selects one of its neighbours for interaction according to a given
criterion. The $n\times n$ probability matrix $\textbf{P}=[p_{ij}]$ prescribes
the probability $p_{ij}$ that the node $v_{i}$ selects node $v_{j}$, with
$p_{ij}=0$ if $(v_{i},v_{j})\not\in E$ due to the constraints of only
interacting with neighbours. For instance, in random neighbour selection,
where all neighbours are equally likely to be chosen, the matrix P is
[$p_{ij}$] such that $p_{ij}=1/|\Omega_{i}|$ $\forall v_{j}\in\Omega_{i}$ and
0 otherwise. A node $v_{i}$ interacts with node $v_{j}$ at time slot $k$ with
probability $\frac{p_{ij}}{n}$, which is the joint probability that $v_{i}$ is
active at time slot $k$ ($p=\frac{1}{n}$) and selects node $v_{j}$ for
interaction ($p=p_{ij}$). The weight matrix $\textbf{W}_{ij}$ of this
averaging scheme has elements

$w_{kl}(t)=\begin{cases}\frac{1}{2}&\text{if }k,l\in\\{i,j\\}\\\ 1&\text{if
}k=l,k\not\in\\{i,j\\}\\\ 0&\text{otherwise.}\end{cases}$ (10)

This is equivalent to nodes $v_{i}$ and $v_{j}$ setting their values to the
average of their current values, leaving the others unchanged. The matrix W
generally changes over time, as different pairs interact at each time slot.
The averaging process is thus defined by the sequence of averaging matrices
$\\{\textbf{W}(k)\\}_{k}$ and the vector value at time step $k$ can be
computed as

$\textbf{x}(k)=\textbf{W}(k-1)\textbf{W}(k-2)\text{ ..
}\textbf{W}(0)\textbf{x}(0)=\boldsymbol{\phi}(k-1)\textbf{x}(0)$ (11)

Recalling that for independent real-valued random matrices the expected matrix
of the product is the product of the expected matrices, then

$\mathbb{E}(\boldsymbol{\phi}(k))=\prod_{i=0}^{k}\mathbb{E}(\textbf{W}(i))=\bar{\textbf{W}}^{k}$
(12)

where $\bar{\textbf{W}}$ is the expected weight matrix

$\bar{\textbf{W}}=\sum_{i,j}\frac{p_{ij}}{n}\textbf{W}_{ij}$ (13)

most commonly written as

$\bar{\textbf{W}}=\textbf{I}-\frac{1}{2n}\textbf{D}+\frac{\textbf{P}+\textbf{P}^{T}}{2n},$
(14)

[10] where I is the identity matrix and D is the diagonal matrix with entries

$\textbf{D}_{i}=\sum_{j=1}^{n}[p_{ij}+p_{ji}].$

By definition, $\bar{\textbf{W}}$ is symmetric and doubly stochastic, i.e.,
all rows and columns sum up to 1. If the underlying graph is connected and
non-bipartite, the expected matrix $\bar{\textbf{W}}$ fulfils all three
conditions for convergence (Eq. 5, 6, 7), so the sequence of averaging
matrices $\\{\textbf{W}(k)\\}_{k}$ drawn independently and uniformly and
applied to any initial vector $\textbf{x}(0)$, converges to the vector average
$\frac{\textbf{1}\textbf{1}^{T}}{n}\textbf{x}(0)$ [10]. Notably, the second
largest eigenvalue of the matrix $\bar{\textbf{W}}$ determines the performance
of the gossip scheme [7].

###  II-D Consensus algorithms

Consensus algorithms perform linear iterations where each node updates its
value to a weighted average of its own previous value and those of its
neighbours in a synchronous manner. The simple consensus scheme to reach an
agreement regarding the state of $n$ agents with dynamics $\dot{x}_{i}=u_{i}$
can be expressed as the linear system

$\dot{x}_{i}(k)=\sum_{v_{j}\in\Omega_{i}}a_{ij}(x_{j}(k)-x_{i}(k))$ (15)

where $i\in I$, $k$ is the discrete time index, and $a_{ij}$ is a weight
associated to the edge $(v_{i},v_{j})$ [12]. Setting $a_{ij}=0$ for
$v_{j}\notin\Omega_{i}$, this iteration can be written as Eq. 1 and 2. The
collective dynamics of the group of agents can be expressed in compact form as

$\boldsymbol{\dot{x}}=-\boldsymbol{\mathcal{L}}\;\textbf{x},$ (16)

so that $\textbf{W}=\textbf{I}-\boldsymbol{\mathcal{L}}$, with identical
disagreement dynamics

$\boldsymbol{\dot{\delta}}=-\boldsymbol{\mathcal{L}}\;\boldsymbol{\delta}.$
(17)

A state in the form $\alpha\textbf{1}$, where all nodes agree, is an
asymptotically stable equilibrium of the dynamic system in Eq. 16 because

$-\boldsymbol{\mathcal{L}}\;\alpha\textbf{1}=\textbf{0}.$ (18)

The consensus algorithm asymptotically converges to the agreement space
provided that $\boldsymbol{\mathcal{L}}$ is a positive semidefinite matrix and
$\alpha\textbf{1}$ is the only equilibrium of the system. It was shown that,
in connected undirected graphs, the equilibrium is unique and corresponds to
the vector average. Moreover, the convergence rate of the consensus algorithm
depends on the second smallest eigenvalue of the Laplacian matrix defined on
$G$ [6].

From Eq. 12, it follows that the performance of a gossip protocol with
expected weight matrix $\bar{\textbf{W}}$, as defined in Eq. 14, converges in
expectation with that of a consensus scheme with time-invariant weight matrix
$\bar{\textbf{W}}$. The agents dynamics of such system is

$\dot{x}_{i}(t)=\sum_{v_{j}\in\Omega_{i}}\frac{p_{ij}+p_{ji}}{2n}(x_{j}(t)-x_{i}(t))$
(19)

while the collective dynamics is given by Eq. 16 where

$\boldsymbol{\mathcal{L}}=\frac{\textbf{D}}{2n}-\frac{\textbf{P}+\textbf{P}^{T}}{2n}.$

So defined, $\boldsymbol{\mathcal{L}}$ is positive-semidefinite, as it is
symmetric and diagonally dominant, and has all row-sums and column-sums equal
to zero, so $\boldsymbol{\mathcal{L}}$ always has a zero eigenvalue
corresponding to the eigenvector 1. In connected graphs, the vector average is
a unique equilibrium for the system, and the algorithm asymptotically
converges to the agreement space.

###  II-E Convergence rate and Accuracy

The convergence of the distributed iteration is governed by the product of
matrices, each of which satisfies certain communication constraints imposed by
the graph topology and the consensus/gossip criterion. Let $\hat{\delta}(t)$
be the collective disagreement of the estimates at time $t$ normalised by the
initial values

$\hat{\delta}(t)=\frac{\|\boldsymbol{\delta}(t)\|}{\|\textbf{x}(0)\|},$ (20)

where $\|.\|$ is the $l_{2}$ norm of the vector. Notably, the $l_{2}$ norm of
the disagreement vector $\boldsymbol{\delta}$ corresponds to the standard
deviation of the vector entries scaled by the network size

$\sigma(t)=\frac{\|\boldsymbol{\delta}(t)\|}{\sqrt{n}}.$ (21)

Numerical and theoretical results for synchronous and asynchronous averaging
schemes indicate that the logarithm of the collective disagreement
$\hat{\delta}(t)$ decreases linearly after a faster transient phase, and that
the decreasing rate is deterministic and independent of the initial
measurements $\textbf{x}(0)$ [13]. Hence, a contraction rate $\gamma$ can be
defined as the angular coefficient of the linear stationary regime and used to
characterise the algorithm performance [14]:

$Log(\hat{\delta})=-\gamma\;t.$ (22)

The accuracy $R$ of the estimates at time $t$ indicates by how many times the
collective disagreement is reduced with respect to the initial disagreement

$R(t)=-Log(\frac{\hat{\delta}(t)}{\hat{\delta}(0)})=-Log(\frac{\|\boldsymbol{\delta}(t)\|}{\|\boldsymbol{\delta}(0)\|})$
(23)

so the time taken to achieve the desired level of accuracy can be computed as

$t=R/\gamma$ (24)

If nodes initiate, on average, one interaction per unit of time, the time
parameter $t$ approximates the number of interactions per node. Figure 1 shows
the collective disagreement over time for several realisations of an
asynchronous averaging algorithm and the corresponding synchronous scheme, as
well as the regression line whose angular coefficient is the chosen metric of
convergence rate $\gamma$.

Figure 1: Collective disagreement over time in 100 realisations of an
asynchronous averaging protocol with random neighbour selection and the
corresponding synchronous scheme, simulated on a geometric random graph of
size $n$ = 200 and average degree ${<}\textit{k}{>}$ = 25. The contraction
rate $\gamma$ is estimated as 0.018.

##  III PROBLEM SETUP

Let us consider a network of agents, each with some initial value $x_{i}(0)$
representing an opinion or a measurement, implementing a synchronous or
asynchronous averaging strategy for reaching an agreement on the global
average $\alpha$. Each node is endowed by a parameter $r_{i}$, indicating the
accuracy of its estimated average $x_{i}(t)$ required to confidently use it,
elaborate it, communicate it to a remote server or compare it to its initial
measurement. An accuracy parameter $r_{i}$ equal to $R$ indicates that the
node can only use its estimate when the collective disagreement in the system
is smaller than the initial disagreement divided by $10^{R}$. For instance,
sensor nodes might confidently use their estimates when the group disagreement
has been significantly reduced (e.g. $R$ = 4), but nodes with control
responsibilities might require estimates of many orders of magnitude more
accurate (e.g. $R$ = 8).

##  IV PROPOSED STRATEGY and MAIN RESULTS

In the considered setting, the global structure of the graph is unknown to the
individual nodes and can change over time. However, nodes can exchange
information with their immediate neighbours to gain awareness of their
surroundings and compute local metrics, namely their degree, clustering
coefficient and local efficiency. Simulations deployed on over 12000 graphs
show that a linear combination of averages of local metrics highly predicts
the convergence rate of distributed averaging algorithms in both synchronous
and asynchronous time models. Consequently, it is suggested that nodes compute
local metrics and estimate their average across the network by distributed
averaging, exploiting the same principle used to calculate the average of
measured quantities. Nodes then employ averaged local metrics to estimate the
algorithm convergence rate and make predictions of the time (or number of
interactions) needed to achieve the desired accuracy so that nodes use their
estimate only when confident of their quality. Although a combination of more
local metrics or more complex models could provide higher explanatory power
and better predictions, the limited memory and computational capabilities
available to nodes motivate the choice of a linear model of few parameters.

Besides enabling performance predictions, local metric averages offer nodes a
glimpse into the global properties of the network. The average node degree,
for instance, is known to play a universal role in cooperation and robustness
[15]. Furthermore, by comparing its local metrics with the population
averages, a node gains awareness of its role in the network without computing
costly centrality measures. Nodes having a degree significantly lower than the
average degree recognise that they limit the overall performance of the graph
and are encouraged, if possible, to create new connections. Highly clustered
nodes are known to reduce communication efficiency by propagating redundant
information and can be programmed to remove or rewire some of their
connections to increase performance [16].

###  IV-A Local Graph Metrics

The degree of a node $v_{i}$, here denoted by $k(v_{i})$, is the cardinality
of the neighbour set $\Omega_{i}$ and quantifies its connections within the
network. The clustering coefficient $cl(v_{i})$ is defined as the number of
triangles passing through the node $T(v_{i})$ divided by the number of
possible triangles

$cl(v_{i})=\frac{2T(v_{i})}{k(v_{i})(k(v_{i})-1)},$

and is a measure of the degree to which nodes tend to cluster together. The
local efficiency eff$(v_{i})$ is the average efficiency of all node pairs in
the sub-graph induced by the neighbours of $v_{i}$, where the efficiency of a
node pair is the multiplicative inverse of the shortest path distance. It
quantifies the resistance to failure on a small scale as it measures how
effectively information is exchanged after removing the node [17]. The
computation complexity of local metrics largely depends on network density.
For very sparse graphs, local metrics can be computed by each node in constant
time and in a fully parallel fashion.

###  IV-B Regression Model

The study generated over 12000 sparse fully-connected undirected networks
belonging to different graph families ($\approx$ 1600 Erdős-Rényi graphs [18],
1600 geometric random graphs [19], 4400 small world graphs [20], 4400 scale-
free graphs [21] with adjusted clustering [22]) having sizes ranging from 100
to 1000 nodes and average degree up to 60. Averages of local metrics were
calculated for all graphs, and the convergence rates of the asynchronous
protocol were estimated through simulations. The adopted gossip scheme
realises a random neighbour selection and activates each node at the times of
a rate 1 Poisson process so that $n$ interactions take place on average for
each unit of time. A regression model in the form

$\gamma=a\,{<}\textit{k}{>}+b\,{<}\textit{cl}{>}+c{<}\,\textit{eff}{>}+d,$
(25)

where ${<}{>}$ indicates the average of the corresponding local metric,
records an r-squared of 0.92, confirming that local metrics alone predict the
algorithm convergence rate with high accuracy. The negative coefficient $b$
suggests that highly clustered areas of the graph are less effective in
propagating estimates because nodes are more likely to have shared neighbours
passing redundant information. The positive coefficients $a$ and $c$ confirm
the intuitive notions that more connections and more efficient information
flows promote convergence.

The proposed approach can be implemented with any probability matrix P as long
as the corresponding expected weight matrix satisfies the abovementioned
convergence criteria. As seen in Section II, results for the asynchronous
averaging scheme extend to the synchronous counterpart as the two algorithms
converge in expectation for certain choices of W. A faster initial phase
characterises the consensus protocol, as seen in Figure 1, so regression
models based on asynchronous simulations might offer conservative estimates
for the synchronous case.

Figure 2: Distribution of node predictions of time needed to achieve accuracy
$R$ = 3 in a geometric random graph (size $n$ = 1000, radius $r$ = 0.07) at
different time points (150, 200, 250, 300), and the corresponding best-fit
normal distributions. The vertical black line indicates the average time at
which the desired level of accuracy was achieved in 100 runs of the
asynchronous averaging protocol ($t$ = 650). Predictions are accurate and
timely as 95% of them are found in the 650$\pm$50 interval at time $t$ = 300.

###  IV-C Prediction accuracy

Node predictions of the time needed to achieve the desired accuracy $R$ are
reliable and improve with time, as they normally distribute around a value
very close to the actual time, with variance decreasing over time.
Necessarily, the accuracy of predictions, like that of the estimates, depends
on the algorithm performance, so faster convergence results in more precise
time predictions. However, the numerical experiments found that accurate
predictions come in a timely manner, as they stabilise to a value of $t$ well
before that time elapses, even in the least performing graphs. In Figure 2,
already at $t=300$, most predictions fall in a narrow interval around the
actual value $t=650$.

Figure 3: Distribution of node predictions in small world graphs, generated
according to the Watts-Strogatz model with size $n$ = 800, average degree
${<}\textit{k}{>}$ = 16, and increasing rewiring probability $p_{r}$. For all
graphs, 80% of nodes have $R$ = 4, while the remaining 20% $R$ = 8, modelling
a network of agents with different accuracy requirements. The vertical lines
represent the average times at which the desired level of accuracy was
achieved in 100 realisations of the asynchronous averaging protocol. Figure 4:
Distribution of node predictions in Erdős-Rényi graphs having fixed size $n$ =
500 and decreasing average degree ${<}\textit{k}{>}$ due to link failure (from
50 to 15). The vertical lines represent the average times at which the desired
level of accuracy was achieved in 100 realisations of the asynchronous
averaging protocol.

##  V ILLUSTRATIVE EXAMPLES

###  V-A Topology changes

Distributed averaging algorithms have been widely investigated in static
topologies, characterised by fixed and reliable communication links throughout
the observed time. This assumption is generally unrealistic for real networks,
where the topology can differ in subsequent executions of the algorithm due to
communication interference or agents changing positions [23]. However, agents
are generally notified solely of changes in their immediate neighbourhood and
are unable to assess topology changes on a large scale. The propagation and
averaging of local metrics constitute a valuable tool for nodes to evaluate
convergence rate in the current communication network, especially in the event
of rewiring and link failure, which significantly affects performance.

####  V-A1 Rewiring

The convergence rate of averaging protocols can be dramatically increased
without adding new links or nodes by means of random rewiring [20], leading to
the design of small-world networks for ultra-fast consensus [24]. The proposed
approach enables nodes to estimate the convergence rate of a network
undergoing random rewiring at any given time. Figure 3 shows subsequent time
predictions computed on a small world graph with increasing probability of
random rewiring.

####  V-A2 Link failure

Erdős-Rényi graphs are generally adopted to model scenarios where edges fail
with equal probability $f$ [25]. If the failure probability varies over time
due to changes in the network communication medium, the graph topology is
defined by a series of Erdős-Rényi graphs, each with edge probability $1-f$.
The proposed method offers nodes a tool to compute the convergence rate and,
thus, assess the communication efficiency at any given time. Figure 4 shows
how predictions capture the lower convergence rate of a network that has lost
over 70% of its links.

###  V-B Anomaly detection

Distributed averaging in networked systems allows individual nodes to evaluate
how their sensing environment differs from that of the other nodes by
comparing their measured value with their estimate of the group average. An
anomalous value or outlier for the population can be defined as any measured
quantity that is distant from the global average of a given amount $M$ or a
certain number of standard deviations $m$. The corresponding node can then
raise an alarm to inform a remote control centre of the unexpected
measurement, perform a corrective action, limit its interactions, or signal
the neighbouring nodes of the lower reliability of its value.

####  V-B1 Alarm system

In networks of sensing devices, any measurement distant at least $M$ from the
global average $\alpha$ can be considered anomalous by the system and trigger
an alarm. Each node can deploy the proposed approach to evaluate the time $t$
needed to attain its desired accuracy $r_{i}$ and only then compare its
measured value $x_{i}(0)$ with its estimated average $x_{i}(t)$. If
$|x_{i}(0)-x_{i}(t)|>M$, the measurement is labelled as anomalous, and the
node activates a response. This procedure is subject to false negatives, which
do not detect anomalous measurements, and false positives, where regular
values are erroneously detected as anomalous, because of the differences
between the actual global average $\alpha$ and its local estimate at time $t$,
$x_{i}(t)$. Notably, nodes face a trade-off between timely detection and
classification error, meaning that a lower value of $r_{i}$ enables faster but
less accurate feedback. Figure 5 exemplifies how classification errors
decrease as accuracy requirements increase for two initial distributions of
$x_{i}(0)$.

Figure 5: (a) Distribution of initial values $x_{i}(0)$ sampled from a normal
distribution ($\mu=1$, $\sigma=1$) and considered anomalous if $|\alpha-
x_{i}(0)|>M$, with $M=2$. (b) Percentage of nodes making a classification
error (false positive or false negative) at time $t$ when comparing their
measured value $x_{i}(0)$ with their average estimate $x_{i}(t)$. The vertical
dotted lines indicate the time at which levels of accuracy $R=1,2,3$ are
attained. All nodes evaluate their measurement correctly at $R=3$. (c)
Distribution of initial values $x_{i}(0)$ sampled from a gamma distribution
(shape $k=1$, scale $\theta=1$) with $M=2$, (d) and corresponding
classification errors over time. The communication network is an Erdős-Rényi
graph ($n=1000,{<}\textit{k}{>}=10$), and the convergence rate of the
averaging gossip algorithm is $\gamma\approx$ 1/5, so that the collective
disagreement is reduced by a factor 10 every 5 units of time.

####  V-B2 Outlier identification

In sensing systems where measurements are expected to distribute normally with
standard deviation $\sigma$, an outlier can be defined as any value distant
more than $m$ standard deviations from the group average $\alpha$. From Eq.
21, 23 and 24, it follows that

$-Log(\frac{\sigma(t)}{\sigma(0)})=t\gamma$ (26)

so that, at any time $t$, the standard derivation of the estimates $\sigma(t)$
can be derived from the initial deviation $\sigma(0)$ and the convergence rate
of the graph $\gamma$, which can be estimated using the proposed methods. Each
node $v_{i}$ can then keep track of a confidence interval where the group
average $\alpha$ is likely to be found. Since estimates are normally
distributed, $v_{i}$ has a high probability of finding the group average
within three standard deviations from its estimate, i.e. $\mathbb{P}(\alpha\in
ci_{i})\approx 0.997$, where
$ci_{i}=[x_{i}(t)-3\sigma(t),x_{i}(t)+3\sigma(t)]$. If the node initial value
$x_{i}(0)$ is distant at least $m$ standard deviations from this confidence
interval, formally

$\min_{\forall\,c\,\in\,ci_{i}}|x_{i}(0)-c|>m\;\sigma(0),$

the measurement is detected as an outlier for the group, and the corresponding
node initiate a response. Figure 6 shows that the standard deviation of the
estimates evolves according to Eq. 26, allowing nodes to evaluate whether
their initial value is an outlier for the population.

Figure 6: (a) Distribution of the estimates $x_{i}$ and (b) visual
representation of outlier detection at times $t$ = 0, 6, 12. The communication
network is a scale-free graph ($n=200,{<}\textit{k}{>}=10,cl=0.01$) with nodes
assigned initial values $x_{i}(0)$ from a normal distribution
($\mu=0,\sigma=1$). The convergence rate of the averaging gossip algorithm is
$\gamma\approx 1/6$, so the standard deviation of the estimates is expected to
become 10 times smaller every 6 units of time. In this scenario, all outliers
are detected by $t$ = 12.

##  VI CONCLUSIONS

The study proposes a distributed approach to estimate the convergence rate of
an averaging scheme deployed on a network. The key idea is to approximate the
graph convergence rate with a linear combination of averages of local metrics.
Nodes can then be programmed to estimate these parameters by distributed
averaging and to implement the regression model in order to compute the
convergence rate and the time needed to achieve the desired level of accuracy.
The approach enables nodes to make informed decisions on their use of measured
and estimated data and gain awareness of the global structure of the network
as well as their role in it. Future efforts will be directed toward
identifying models able to provide more accurate predictions without
increasing memory requirements or communication costs.

## References

  * [1] L. Martinović, Ž. Zečević, and B. Krstajić, “Cooperative tracking control of single-integrator multi-agent systems with multiple leaders,” _European Journal of Control_ , vol. 63, pp. 232–239, 2022.
  * [2] N. Loizou and P. Richtárik, “Revisiting randomized gossip algorithms: General framework, convergence rates and novel block and accelerated protocols,” _IEEE Transactions on Information Theory_ , vol. 67, no. 12, pp. 8300–8324, 2021.
  * [3] D. Kempe, A. Dobra, and J. Gehrke, “Gossip-based computation of aggregate information,” in _44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings._ IEEE, 2003, pp. 482–491.
  * [4] M. H. Trinh and H.-S. Ahn, “Theory and applications of matrix-weighted consensus,” _arXiv preprint arXiv:1703.00129_ , 2017.
  * [5] C. Sirocchi and A. Bogliolo, “Community-based gossip algorithm for distributed averaging,” in _IFIP International Conference on Distributed Applications and Interoperable Systems_. Springer, 2023, pp. 37–53.
  * [6] 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.
  * [7] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Gossip algorithms: Design, analysis and applications,” in _Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies._ , vol. 3. IEEE, 2005, pp. 1653–1664.
  * [8] S. Sundaram and C. N. Hadjicostis, “Distributed function calculation and consensus using linear iterative strategies,” _IEEE journal on selected areas in communications_ , vol. 26, no. 4, pp. 650–660, 2008.
  * [9] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” _Systems & Control Letters_, vol. 53, no. 1, pp. 65–78, 2004.
  * [10] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” _IEEE transactions on information theory_ , vol. 52, no. 6, pp. 2508–2530, 2006.
  * [11] G. Oliva, S. Panzieri, R. Setola, and A. Gasparri, “Gossip algorithm for multi-agent systems via random walk,” _Systems & Control Letters_, vol. 128, pp. 34–40, 2019.
  * [12] R. Olfati-Saber and R. M. 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.
  * [13] P. Denantes, F. Bénézit, P. Thiran, and M. Vetterli, “Which distributed averaging algorithm should i choose for my sensor network?” in _IEEE INFOCOM 2008-The 27th Conference on Computer Communications_. IEEE, 2008, pp. 986–994.
  * [14] C. Sirocchi and A. Bogliolo, “Topological network features determine convergence rate of distributed average algorithms,” _Scientific Reports_ , vol. 12, no. 1, p. 21831, 2022.
  * [15] I. Shames, T. Charalambous, C. N. Hadjicostis, and M. Johansson, “Distributed network size estimation and average degree estimation and control in networks isomorphic to directed graphs,” in _2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2012, pp. 1885–1892.
  * [16] M. R. Brust and S. Rothkugel, “Small worlds: Strong clustering in wireless networks,” _arXiv preprint arXiv:0706.1063_ , 2007.
  * [17] V. Latora and M. Marchiori, “Efficient behavior of small-world networks,” _Physical review letters_ , vol. 87, no. 19, p. 198701, 2001.
  * [18] P. Erdős, A. Rényi, _et al._ , “On the evolution of random graphs,” _Publ. Math. Inst. Hung. Acad. Sci_ , vol. 5, no. 1, pp. 17–60, 1960.
  * [19] M. Penrose, _Random geometric graphs_. OUP Oxford, 2003, vol. 5.
  * [20] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,” _nature_ , vol. 393, no. 6684, pp. 440–442, 1998\.
  * [21] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” _science_ , vol. 286, no. 5439, pp. 509–512, 1999.
  * [22] P. Holme and B. J. Kim, “Growing scale-free networks with tunable clustering,” _Physical review E_ , vol. 65, no. 2, p. 026107, 2002.
  * [23] S. Patterson, B. Bamieh, and A. El Abbadi, “Convergence rates of distributed average consensus with stochastic link failures,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 4, pp. 880–892, 2010.
  * [24] R. Olfati-Saber, “Ultrafast consensus in small-world networks,” in _Proceedings of the 2005, American Control Conference, 2005._ IEEE, 2005, pp. 2371–2378.
  * [25] Y. Hatano and M. Mesbahi, “Agreement over random networks,” _IEEE Transactions on Automatic Control_ , vol. 50, no. 11, pp. 1867–1872, 2005.