# DYNAMICS OF A PARTICLE IN THE GENERALISED ELLIS-BRONNIKOV WORMHOLE ON THE
ROTATING ARCHIMEDE’S SPIRAL

N. GIORGADZE  School of Physics, Free University of Tbilisi
Tbilisi, 0159, Georgia
<EMAIL_ADDRESS>Z.N. OSMANOV  School of Physics, Free University of
Tbilisi
Tbilisi, 0159, Georgia
Kharadze Georgian National Astrophysical Observatory
Abastumani, 0301, Georgia
<EMAIL_ADDRESS>
(Day Month Year; Day Month Year)

###### Abstract

A particle moving on curved magnetic field lines in the wormhole metrics is
considered. The dynamics of a single particle is studied on a co-rotating
parameterized magnetic field line. Being interested in the force-free dynamics
we choose the rotating Archimedes’ spiral embedded in the generalized Ellis-
Bronnikov metrics. By analysing the phase space, we explore how the physical
parameters affect the motion of the particle and it is shown that the
particles may reach the force free regime, eventually escaping the wormhole.

###### keywords:

Wormhole; Motion on rotating channels.

PACS numbers:

##  1 Introduction

Existence of wormholes (WH) has frequently been discussed in the scientific
community. It is argued that WHs might be created during the inflation period
of the early evolution of the universe (Refs. Wheeler1-Hawking). It is also
assumed that there is accreting matter in the central region of WHs (Ref.
Harko). Moreover It has been considered that some astrophysical objects may be
or had been entrances to WHs (Ref. Kardashev). Such astrophysical objects not
only may provide magnetic field of extreme strength of order $10^{13}$ G,
(Ref. Kardashev), but often they also are characterized by rotation,
therefore, on the one hand extremely strong magnetic field may guarantee the
frozen-in condition and on the other hand, particles will slide along field
lines, experiencing relativistic centrifugal force.

The motion of matter may be studied either as fluid dynamics of an ensemble of
particles (Ref. Butb) or as dynamics of a single particle (Refs.
Ars,Bakh,Gud,AR MG,AR GD ZO). In this paper we will be examining motion of a
charged particle in the presence of magnetic field. As we have already
mentioned, the super-strong magnetic field will result in the frozen-in
condition of a particle on ”field lines”, causing it to slide across them. In
particular, one can straightforwardly estimate that the gyroradius of a proton
$\gamma mc^{2}/eB$ with the relativistic factor $\gamma\simeq 10^{7}$ is of
the order of $1$ cm for $B\simeq 10^{13}$ Gauss, which for electrons is even
less. Taking rotation of the magnetic field lines into account holds
particularly interesting results as particle is subject to the relativistic
centrifugal acceleration.

Dynamics of particles on rotating channels has been studied in a series of
papers (Refs. Ars-ZO FR). Problem becomes interesting near the light cylinder
(LC) region, where the velocity of rotation coincides with the speed of light.
In a simplified model considering the motion of the particle in rectilinear
rotating tube it has been shown that near the LC zone the particle changes the
sign of the radial acceleration (Ref. AR MG). This is not a realistic
behaviour because in the the study the maintainance of the rigid rotation has
been assumed. However, in real astrophysical situations field lines are
curvilinear as they tend to lag behind the rotation near the LC surface. We
take special interest in field lines having the configuration of the
Archimede’s spiral, because, as it has been shown, the force-free regime may
be established, enabling particles to reach infinity with finite velocity
(Refs. Ars,Bakh).

In (Ref. Ars) the simplest form of WH metrics proposed by Ellis (Refs. Ellis)
and Bronnikov (Refs. Bronnikov) was considered. In the most simplified Ellis-
Bronnikov (EB) WH metrics rotating Archimede’s spiral was embedded and it was
shown that particles can escape the WH with finite velocity. In this paper we
will be considering motion of the particle on rotating spiral in the
generalized Ellis-Bronnikov (GEB) metrics showing that the particles will
still reach the force-free regime and escape the WH.

The outline of the paper will be following: In section 2 we consider a
theoretical model for motion of the particle on any curve in any given
metrics; in section 3 we reduce our problem to GEB wormhole and Archimede’s
spiral and consider results.

##  2 Main Consideration

Let us first consider, without specifying dimensions and characteristics of
the space, a most general form of metrics

$ds^{2}=g_{\alpha\beta}dq^{\alpha}dq^{\beta}$ (1)

with the metric tensor components $g_{\alpha\beta}=g_{\alpha\beta}(q^{\mu})$
being functions of the coordinates in the laboratory frame of reference
$q^{\mu}$.

Lagrangian of the particle moving in such space is given by

$L=-\frac{1}{2}g_{\alpha\beta}\dot{q}^{\alpha}\dot{q}^{\beta},$ (2)

where $\dot{q}^{\mu}\equiv\frac{dq^{\mu}}{d\tau}$ and $\tau$ \- a parameter of
evolution, is the proper time of the particle.

From the Euler-Lagrange equations

$\frac{\partial L}{\partial q^{\alpha}}=\frac{d}{d\tau}\biggl{(}\frac{\partial
L}{\partial\dot{q}^{\alpha}}\biggl{)},$ (3)

one can straightforwardly obtain the well known geodesic equations of motion:

$\ddot{q}^{\beta}=-\Gamma^{\beta}_{\mu\nu}\dot{q}^{\mu}\dot{q}^{\nu}$ (4)

with
$\Gamma^{\beta}_{\mu\nu}=\frac{1}{2}g^{\alpha\beta}\bigr{[}\partial_{\mu}g_{\alpha\nu}+\partial_{\nu}g_{\alpha\mu}-\partial_{\alpha}g_{\mu\nu}\bigl{]}$.

Note that here we have not yet made any assumptions about the space or
introduced any constraints on the particle. As already mentioned above, we
will be discussing motion of the particle on rotating field lines. We seek to
constrain a particle on a certain field line, i.e. to constrain it on one-
dimensional curve embedded in three-dimensional space. In other words we aim
to describe the motion in 1+1 rather than 1+3 formalism. Having Parameterized
the motion alongside the field line, equation of motion expressed by Eq. (4)
would carry the idea that particle moves on geodesic lines in derived 1+1
metrics.

Parameterization of a field line is achieved through expressing all the
coordinates as a function of lab-time and one spatial coordinate we wish to
examine.

$q^{2}=q^{2}(q^{0},q^{1})\qquad\text{and}\qquad q^{3}=q^{3}(q^{0},q^{1}),$ (5)

reducing the metric tensor to the following form

$ds^{2}=\tilde{g}_{\alpha\beta}dq^{\alpha}dq^{\beta}=\tilde{g}_{00}(dq^{0})^{2}+2\tilde{g}_{01}dq^{0}dq^{1}+\tilde{g}_{11}(dq^{1})^{2}.$
(6)

Here $\tilde{g}_{\alpha\beta}$ is given by the general transformation rule of
tensors when changing the coordinate system and henceforth, we will be
referring to it as $g_{\alpha\beta}$. From Eq. (3), through the
straightforward calculations we obtain the equation of motion for one
remaining spatial coordinate

$\frac{d^{2}q^{1}}{dt^{2}}=\frac{1}{2\Delta
g}\bigr{[}A_{0}+A_{1}v+A_{2}v^{2}+A_{3}v^{3}\bigl{]},$ (7)

where the coefficients $A_{i}$ are the functions of metrics and depend only on
the spatial coordinates

$A_{0}=g_{00}\partial_{1}g_{00},$ (8) $A_{1}=3g_{01}\partial_{1}g_{00},$ (9)
$A_{2}=2g_{01}\partial_{1}g_{01}+g_{11}\partial_{1}g_{00}-g_{00}\partial_{1}g_{11},$
(10) $A_{3}=g_{11}\partial_{1}g_{01}-g_{01}\partial_{1}g_{11},$ (11)

and $\Delta g$ denotes the determinant of the derived metric tensor and
$v\equiv\frac{dq^{1}}{dt}$ is the velocity of the particle alongside the field
line as it is observed from the laboratory frame of reference. Deriving the
acceleration as a function of coordinates and velocities enables us to further
examine motion of the particle that will be explored in next section.

We can examine the dynamics of a particle by finding the conserved quantity of
the Lagrangian given by Eq. (2). Since the latter does not depend on time the
corresponding quantity, associated to the energy of the particle writes as

$E=-\gamma(g_{00}+g_{01}v)=const$ (12)

where by definition the Lorentz factor is given by

$\gamma=(-g_{00}-2g_{01}v-g_{11}v^{2})^{\frac{1}{2}},$ (13)

Solving Eqs. (12,13) with respect to $v$ one obtains:

$v=\frac{\sqrt{g_{00}+E^{2}}}{g_{01}^{2}+E^{2}g_{11}}\biggl{[}-g_{01}\sqrt{g_{00}+E^{2}}\pm
E\sqrt{g_{01}^{2}-g_{00}g_{11}}\biggr{]},$ (14)

which formally is the similar expression derived in (Refs. Gud,AR GD ZO)).

##  3 Generalized Ellis-Bronnikov Wormhole

In this section we consider motion of the particle on rotating field lines in
a particular metrics: Generalized Ellis-Bronnikov WH

$ds^{2}=-dt^{2}+dl^{2}+r^{2}(l)[d\theta^{2}+sin^{2}(\theta)d\phi^{2}]$ (15)

where

$r(l)=(b_{0}^{m}+l^{m})^{\frac{1}{m}}$ (16)

with $m$ taking only even values to ensure smoothness of $r(l)$ over the
entire domain. $\theta$ and $\phi$ are spherical coordinates,
$l\in(-\infty,\infty)$ is the proper radial coordinate and $b_{0}$ denotes the
radius of a throat of the WH. Henceforth we use notations $c=1$.

Examining a scenario when there is an accreting matter inside the WH (Ref.
Harko) and by taking strong magnetic field into account (Ref. Kardashev), it
is clear that any charged particle entering such an ambient will very soon
lose the perpendicular momentum via the strong synchrotron emission process.
As a result the particles will transit to the ground Landau level and will
slide along the co-rotating field lines. Generally speaking, the particles
which escape the regions of their origin, become force-free. From very general
considerations, one can show that the only trajectory, that enables such a
behaviour is the Archimede’s spiral. Significance of such a rotating field
line is that it leads to the possibility of achieving the terminal velocity as
the radial coordinate approaches infinity (Ref. AR GD ZO). We examin conical
spirals having the property of the Archimede’s spiral

$\theta=const\qquad\text{and}\qquad\Phi=\alpha l+\omega t,$ (17)

We see that $d\Phi=0$ when the radial velocity equals
$-\frac{\omega}{\alpha}$. This means that in the laboratory frame of reference
the angle of rotation does not change and therefore, the trajectory will be a
straight line. We can analyse such a kinematical picture by means of the
effective angular velocity, $\Omega\equiv d\Phi/dt=\omega+\alpha v$, thus the
angular velocity of the particle seen by the laboratory observer. In
particular, when the radial velocity equals the terminal velocity, the
effective angular velocity vanishes, leading to the rectilinear trajectories
in the laboratory frame of reference. It is worth noting that for a particle
to have terminal velocity less than the speed of light, the field line can not
have an arbitrary shape and the following condition has to be satisfied:
$|\omega|<|\alpha|$. However, if perchance this condition is violated, as
velocity gets closer to one that of light, i.e. gamma factor increases, we
would expect the charged particle to become energetic enough to start bending
the field lines, since it is physically impossible for absolutely rigid
rotations to exist. However, we will be examining cases when this criterion is
well met, thus considering rotation of trajectories rigid.

Let us further examine restrictions that are imposed on moving the particle
along such rotating spiral field lines with parameterization given by Eq.
(17). We consider total velocity at any given time, not just near its terminal
value

$v_{tot}^{2}=g_{ll}\biggl{(}\frac{d^{2}l}{dt^{2}}\biggr{)}^{2}+g_{\theta\theta}\biggl{(}\frac{d^{2}\theta}{dt^{2}}\biggr{)}^{2}+g_{\Phi\Phi}\biggl{(}\frac{d^{2}\Phi}{dt^{2}}\biggr{)}^{2}.$
(18)

By taking the fundamental principle of general relativity ($v_{tot}<1$ for
massive particles) and Eqs. (17,18) into account, we arrive at

$v^{2}+sin^{2}(\theta)(b_{0}^{m}+l^{m})^{\frac{2}{m}}(\alpha v+\omega)^{2}<1.$
(19)

Eq. (19) imposes a restriction on trajectories in the phase space, namely that
they should lie in the region shown in Fig. 1 determined by the above
equation. In other words pairs of initial radial velocity and coordinate can
only be chosen from within those regions and motion that follows should
completely lie in it as well. Note that the allowed region of motion is the
function of the characteristics of the WH as well. Moreover, if we aim to
derive the equations of motion for the radial coordinate, possible initial
values of the the radial coordinate and velocity become important to describe
any motion. Let us consider the possible maximum and minimum values of the
initial radial velocities at $l_{0}=0$. From Eq. (19) one obtains

$v^{max}_{min}=\frac{-sin^{2}(\theta)b_{0}^{2}\omega\alpha\pm\sqrt{1+sin^{2}(\theta)b_{0}^{2}(\alpha^{2}-\omega^{2})}}{1+sin^{2}(\theta)b_{0}^{2}\alpha^{2}}.$
(20)

We see that since $|\omega|<|\alpha|$, $v_{max}$ will always be less than one
and any possible motion will be bounded by it. It is also evident from Fig. 1
that as the proper radial coordinate increases, possible velocities should
tend to the terminal value.

Figure 1: Allowed pairs of the radial velocity and the proper coordinate in
the phase space for different $\alpha$. $\omega=1$, $b=1$, $m=2$,
$\theta=\pi/2$ with $\alpha=-1.25$ (left panel) and $\alpha=-2$ (right panel).

To examine the actual motion we plug in the parameterisation given by Eq. (19)
into Eq. (17) leading to the following metric tensor

$\displaystyle
g_{\alpha\beta}=\begin{bmatrix}-1+\sin^{2}(\theta)(b^{m}+l^{m})^{\frac{2}{m}}\omega^{2}&\sin^{2}(\theta)(b^{m}+l^{m})^{\frac{2}{m}}\omega\alpha\\\
\sin^{2}(\theta)(b^{m}+l^{m})^{\frac{2}{m}}\omega\alpha&1+\sin^{2}(\theta)(b^{m}+l^{m})^{\frac{2}{m}}\alpha^{2}\end{bmatrix}$
(21)

Since the GEB WH metrics is asymptotically Minkowskian and for
$|\omega|<|\alpha|$, we expect the radial velocity to reach the terminal
value. Such a behavior in dynamics can be verified by expanding Eq. (14) for
$l>>b_{0}$, leading to (the same expression as in (Ref. Ars))

$v=-\frac{\omega}{\alpha}+\frac{1+E^{2}\pm
E\sqrt{\alpha^{2}-\omega^{2}}}{\omega\sin^{2}(\theta)}\frac{1}{l^{2}}.$ (22)

As it is clear from the above equation as radial coordinate tends to infinity,
the radial velocity approaches its terminal value determined solely by the
properties of the field line to which it is constrained. The fact that the
radial velocity tends to the terminal value at infinities ensures that the
numerator in Eq. (7) tends to zero there. Since the numerator is a smooth
function of coordinates with no singularities, acceleration will have finite
value if the metrics is non-degenerate, i.e. determinant appearing in the
denominator of the aforementioned equation is always nonzero. That is easily
verified by considering the metric tensor given by

$\Delta
g=-\biggl{(}1+sin^{2}(\theta)(\alpha^{2}-\omega^{2})(b_{0}^{m}+l^{m})^{\frac{2}{m}}\biggr{)}.$
(23)

Since $|\omega|<|\alpha|$ and $m$ only taking even values, we see that the
determinant always has a non-zero value and hence, the equation of motion will
have no singularities in the middle region of the motion either.

Initial velocity fixes the conserved energy by Eq. (12), that we choose to
compute for $l_{0}=0$ and use it in Eq. (14). In Fig. 2 we see the
trajectories of particles in the phase space for different values of the
radial velocity at $l_{0}=0$. On both panels the shaded area is the allowed
region of motion given by Eq. (19) and lines show the trajectories for
different values of energy. It is seen that all trajectories lie within the
aforementioned region for different initial velocities and different values of
$m$ characterizing WH.

Figure 2: Radial velocity dependence on the radial proper coordinate. The set
of parameters is: $\omega=1$, $\alpha=-2$, $b_{0}=1$, $\theta=\pi/2$ with
$m=2$ (left panel) and $m=10$ (right panel).

Although we are using $l_{0}=0$ and velocity there to calculate conserved
energy (Eq. (14)), this method of solution with Eq. (14) fixes all the points
in the phase space with the given energy from $l_{0}=-\infty$ to
$l_{0}=\infty$. That is of particular interest since we are interested in
particles entering the WH from one side region and then leaving it from the
other.

From Fig. 2 we see that while increasing the parameter $m$, the particle
undergoes acceleration further away from the origin. To study the dynamics of
the particle in terms of the acceleration in a more detailed way we consider
Eq. (7) for the metrics given by Eq. (21). The radial acceleration then, as a
function of the radial coordinate and velocity, is easily derived

$\frac{d^{2}l}{dt^{2}}=-\frac{\sin^{2}(\theta)(\omega+\alpha
v)(b_{0}^{m}+l^{m})^{\frac{2}{m}-1}l^{m-1}[\alpha v-\omega+2\omega
v^{2}+\sin^{2}(\theta)(\omega+\alpha v)^{2}\omega
r^{2}(l)]}{1+\sin^{2}(\theta)(\alpha^{2}-\omega^{2})r^{2}(l)}$ (24)

As expected, when the radial velocity tends to its critical value, the
acceleration vanishes due to the effective angular velocity
$\Omega=\omega+\alpha v$. Putting $m=2$ and thus reducing to the simplest form
of GEB, we repeat the result derived in Ref Ars. Therefore, we have found that
vanishing of the acceleration when $\Omega=0$ is a general property of the GEB
metrics.

Figure 3: Radial acceleration (top panel), radial velocity (middle panel) and
the total velocity (bottom panel) dependence on laboratory time. The set of
parameters is: $\omega=1$, $\alpha=-1.25$, $b_{0}=1$, $\theta=\pi/2$,
$l_{0}=0$, $m={2,4,6,8,10}$ with $v_{0}=0.1$ (left) and $v_{0}=0.95$ (right).

From Eq. (24) one can see that for $l<<b_{0}$ and $m>>1$ the term
$(b_{0}^{m}+l^{m})^{\frac{2}{m}-1}l^{m-1}$ is significantly reducing the value
of acceleration, thus resulting in the initial plateaus in the right panel of
Fig. 2. The same behaviour is evident graphically from Eq.( 24) that allows us
to plot dependence of the radial acceleration on the laboratory time as shown
in Fig. 3 111It is worth noting that the corresponding figure in Ref. Ars for
$m=0$ is not correctly plotted.. It is clear that the bigger the value of
parameter $m$, later the particle experiences acceleration. It is evident from
the top two graphs in Fig. 3 that as the acceleration tends to zero, the
radial velocity must reach the terminal value as shown in the bottom part of
the Fig. 3 for different values of $m$.

Figure 4: Vector field for the differential equation given by Eq. (24) The set
of parameters is: $\omega=1$, $\alpha=-2$, $b_{0}=1$, $\theta=\pi/6$, with
$m=2$ (left panel) and $m=10$ (right panel).

From Eq. (24), we construct the vector field shown on Fig. 4. As it is
evident, outside the shaded region, the solutions are unstable - arrows are
pointing outwards and become vertical, which means that acceleration changes
very rapidly.

We saw from Fig. 2 that for certain initial values of the radial velocity the
particle may come from negative value of the initial radial coordinate, that
is from the other side of the WH. In Fig. 5 we see dependence of the radial
velocity on the radial coordinate for two different values of m. Note that the
trajectory does not leave the allowed region of motion as it comes from
$l=-20$, passes through the origin and then leaves WH.

Figure 5: Radial velocity versus the radial coordinate from Eq.( 24). The set
of parameters is: $\omega=1$, $\alpha=-1.25$, $b_{0}=1$, $\theta=\pi/2$, with
$m=2$ (left panel) and $m=10$ (right panel)

Figure 6: Trajectory of Motion of a single particle as observed from the
laboratory frame of reference (left panel) and for the jet of particles (right
panel). The set of parameters is: $\omega=1$, $\alpha=-2$, $b_{0}=1$,
$\theta=\pi/6$, $m=2$, $l_{0}=0$ and $v_{0}=0.9$.

Figure 7: Trajectories of a single particle as seen from the local frame of
reference (left panel) and the jet of particles observed from the laboratory
frame of reference (right panel) $\omega=1$, $\alpha=-1.25$, $b_{0}=1$,
$\theta=\pi/6$, $m=2$, $l_{0}=-30$ and $v_{0}=0.827$.

Figure 8: Radia velocityl (left panel) and total velocity (right panel) versus
time. The set of parameters is: $\omega=1$, $\alpha=-1.25$, $b_{0}=1$,
$\theta=\pi/6$, $m=2$.

In many astrophysical scenarios jets of ionised matter is emitted alongside
the axis of rotation. In our case, since it is considered that in the central
region of WHs some certain astrophysical objects might be located, we consider
motion of the particle when $\theta<\pi/2$. In Fig. 6 on the left panel we see
the parametric plot for a position of a single particle as seen from the
laboratory frame of reference and on the right panel we see how it would look
like for the jet of numerous particles with phase shifts in the azimuth
coordinate $\phi$.

We see that in the beginning of the motion trajectory is curved, however,
further from the origin, when the force-free regime is achieved the particle
slides on the spiral so that from the laboratory frame of reference its
trajectory is rectilinear.

In Fig. 7 we plot jets of particles entering the WH from the one side and then
leaving it from the other. On the left panel we plot the trajectory of a
single particle as seen from the local (rotating) frame of reference and on
the right panel we show the jets of particles observed from the laboratory
frame of reference. Here as well we notice that from laboratory frame of
reference, we observe that, before particles enter and as they leave the
intermediate region of WH their trajectory as observed form laboratory is
linear.

For the same parameters as in Fig. 7 we plot the radial velocity and the total
velocity versus time in Fig. 8 and as it is evident, the particle’s velocity
remains less than the speed of light and at the end it tends to it’s terminal
value.

##  4 Summary

In this paper we considered the GEB WH and studied a single particle dynamics
moving along a co-rotating magnetic field lines. For this purpose we rewrote
the metrics for this particular case, reducing it to the $1+1$ scenario.

We have specified the characteristics of the phase space, the regions in which
the motion is physically possible. By means of the energy method (conserved
quantity) it has been shown that every motion lies within that area.

Later, having derived acceleration as a function of time in the laboratory
frame of reference, we constructed the vector field. It has been shown that
any motion lying outside the ”allowed region” is unstable, thus not possible.
It has been shown that particles may enter and then leave the WH, reaching the
terminal velocity.

Within this paper we aimed to investigate the motion of the particle in GEB WH
and to show that under some special circumstances, such as choosing
Archimede’s spiral, the particles may enter and leave it. However, it is also
interesting to study the same problem for different types of WHs. For future
works to come we intend to examine different kinds of realistic field
topologies for another WH metrics that might allow the force-free regime
asymptotically to be established and the particle to escape.

## References

  * [1] Wheeler, J.A., 1955, Phys. Rev. 97, 511
  * [2] Misner, C. W. and Wheeler, J. A., 1957, Ann. Phys. (N.Y.), 2, 525
  * [3] Wheeler, J. A., 1957, Ann. Phys. (N.Y.), 2, 604
  * [4] Hawking, S. W. Black Holes and the Structure of the Universe, eds. C. Teitelboim and J. Zanelli (World Scientific, Singapore, 2000)
  * [5] Harko, T., Kovács, Z. and Lobo, F. S. N., 2008, Phys. Rev. D, 78, 084005
  * [6] Kardashev, N. S., Novikov, I. D. and Shatskiy, A. A., 2007, IJMPD, 16, 909
  * [7] Butbaia, G., and Osmanov, Z., 2021, IJMPD, 30, 2150072.
  * [8] Arsenadze, G. and Osmanov, Z., 2017, IJMPD, 26, 1750153
  * [9] Bakhtadze G. G., V. I. Berezhiani, and Z. Osmanov., IJMPD 28.11 (2019): 1950141.
  * [10] Gudavadze, I., Osmanov, Z. and Rogava, A., 2015, IJMPD, 24, 1550042
  * [11] Machabeli, G. Z., and Rogava, A. D. ,1994, Phys. Rev. A, 50, 98
  * [12] Rogava, A. D., Dalakishvili, G., and Osmanov, Z. N., 2003, Gen. Rel. and Grav., 35, 1133
  * [13] Osmanov, Z. and Rieger, F. M., 2017, MNRAS, 464,1347; Osmanov, Z., 2010, New Ast., 15, 351; Osmanov, Z. and Rieger, F. M., 2009, A&A, 502, 15; Osmanov, Z., Rogava, A. and Bodo, G., 2007, A&A, 470, 395
  * [14] H.G. Ellis, J. Math. Phys. 14, 104 (1973)
  * [15] K.A. Bronnikov, Acta Phys. Pol. B 4, 251 (1973)


# Greedy Shapley Client Selection for Communication-Efficient Federated
Learning

Pranava Singhal, Shashi Raj Pandey, IEEE Member, and Petar Popovski, IEEE
Fellow Pranava Singhal is with the Electrical Engineering Department, IIT
Bombay, Mumbai, India Email<EMAIL_ADDRESS>Raj Pandey
and Petar Popovski are with the Connectivity Section, Department of Electronic
Systems, Aalborg University, Denmark. Email: {srp<EMAIL_ADDRESS>work
was supported in parts by the Villum Investigator Grant “WATER” from the Velux
Foundation, Denmark, and the European Union’s Horizon project 6G-XCEL
(101139194).

###### Abstract

The standard client selection algorithms for Federated Learning (FL) are often
unbiased and involve uniform random sampling of clients. This has been proven
sub-optimal for fast convergence under practical settings characterized by
significant heterogeneity in data distribution, computing, and communication
resources across clients. For applications having timing constraints due to
limited communication opportunities with the parameter server (PS), the client
selection strategy is critical to complete model training within the fixed
budget of communication rounds. To address this, we develop a biased client
selection strategy, GreedyFed, that identifies and greedily selects the most
contributing clients in each communication round. This method builds on a fast
approximation algorithm for the Shapley Value at the PS, making the
computation tractable for real-world applications with many clients. Compared
to various client selection strategies on several real-world datasets,
GreedyFed demonstrates fast and stable convergence with high accuracy under
timing constraints and when imposing a higher degree of heterogeneity in data
distribution, systems constraints, and privacy requirements.

###### Index Terms:

client selection, data heterogeneity, federated learning, Shapley value,
timing constraints

##  I Introduction

Federated Learning (FL) [1] is a paradigm for distributed training of neural
networks where a resourceful parameter server (PS) aims to train a model using
the privately held data of several distributed clients. This is done through
iterative interaction between the PS and clients providing the output of their
local compute, i.e., local models, instead of raw data; hence, FL is often
described as privacy-preserving model training. In such an approach, the
communication bottleneck constrains the PS to (1) communicate with a few
clients and (2) complete training in the fewest possible communication rounds.
Our work focuses on developing a client selection strategy by which the PS can
minimize communication overhead and speed up model convergence.

The conventional scheme for FL, FedAvg [1], involves uniform random sampling
of a subset of clients in each communication round to perform local computing
over their private data. Upon receiving the local models from the selected
clients, the PS then aggregates the updates by uniformly averaging model
weights (or in proportion to local training data quantity) and initiates the
next communication round. FedAvg proposes to reduce the total number of
communication rounds through multiple epochs of client-side training in each
round before model averaging. However, averaging model updates from uniformly
sampled clients may lead to poor convergence of the PS model in typical FL
settings with a high degree of heterogeneity in client data distribution,
computational resources, and communication bandwidth.

To overcome these challenges with FedAvg several biased client selection
strategies have been proposed for FL, focusing on improving the convergence
rate and reducing total communication rounds while ensuring robustness to
heterogeneity.

###  I-A Prior Work

To minimize the communication overhead, existing works focus on either of the
two approaches: (1) model compression through techniques such as quantization,
pruning, or distillation [2, 3, 4], where client updates are compressed to
reduce the bandwidth usage in each round of communication with the PS, and (2)
reduction of the total number of communication rounds to achieve satisfactory
accuracy (or convergence). This is done through modification of the local
update scheme, such as in FedProx [5] and SCAFFOLD [6], or using biased client
selection strategies, such as Power-Of-Choice [7] and IS-FedAvg [8].
Algorithms like FedProx introduce a squared penalty term in the client loss to
improve personalization in a communication-efficient manner, and SCAFFOLD uses
control variates to prevent the client models from drifting away from the PS
model. Most modifications to develop an efficient client selection strategy
allow performing local updates in the same way as FedAvg. For instance, Power-
Of-Choice selects clients with the highest local loss after querying all
models for loss in each round, and IS-FedAvg modifies client selection and
local data subset selection probabilities to minimize gradient noise. Our
algorithm GreedyFed focuses on developing a novel biased client selection
strategy adopting game-theoretic data valuation principles to improve
communication efficiency in FL.

Many prior works have modeled client participation in FL as a cooperative game
and looked at the Shapley-Value (SV) [9] as a measure of client contribution
to training. SV is an attractive choice due to its unique properties of
_fairness_ , _symmetry_ , and _additivity_. While related works have used SV
for client valuation and incentivizing participation [10, 11] for
collaborative training, a few works have also used SV for client selection
[12, 13, 14] to improve robustness and speed up training. Two key works using
SV for client selection are: [12], in which the authors propose an Upper-
Confidence Bound (UCB) client selection algorithm, and [13], which biases the
client selection probabilities as softmax of Shapley values. A key limitation
of these works is a lack of performance analysis of SV-based client selection
in the presence of timing constraints and heterogeneity in data, systems, and
privacy requirements, which are essential considerations for the practical
deployment of FL algorithms.

###  I-B Main Contributions

In this paper, we develop a novel greedy SV-based client selection strategy
for communication-efficient FL, called GreedyFed. It requires fewer
communication rounds for convergence than state-of-the-art techniques in FL,
including SV-based strategies, by involving the most contributing clients in
training. Our algorithm builds on [12] and [13] with two essential
modifications to enhance training efficiency:
(1) Purely greedy client selection (motivated in Section III-B)
(2) Integration of a fast Monte Carlo Shapley Value approximation algorithm
GTG-Shapley [15] making SV computation tractable for practical applications
with several clients.

We demonstrate that GreedyFed alleviates the influence of constrained
communication opportunities between clients and the PS, addressing practical
deployment challenges due to premature completion of model training and its
impact on model accuracy, and is robust towards heterogeneity in data, system
constraints, and privacy requirements.

_Organization:_ The rest of the paper is organized as follows. In Section II,
we describe the client selection problem and set up notation. Section III
outlines the details of our GreedyFed algorithm. In section IV, we describe
the experiments, and in Section V we analyze the results. Section VI concludes
the paper with directions for future work.

##  II Problem Setup

Consider a resourceful parameter server (PS) collaboratively training a
machine learning model leveraging the local data and compute of $N$ resource-
constrained clients. Each client $k\in[N]=\\{1,\,2,\,\cdots,\,N\\}$ holds a
private dataset $\mathcal{D}_{k}$ with $n_{k}$ samples. Our goal is to design
a client selection strategy that selects a subset of $M$ clients, denoted
$S_{t}$, in each communication round $t$ to train the PS model $w$ that gives
the best prediction $f(\boldsymbol{x},w)$ while generalizing well on a test
set $\mathcal{D}_{\textrm{test}}$ in the fewest communication rounds. Let
$\mathcal{D}_{\textrm{train}}$ denote the union of all client datapoints
$\bigcup_{k\in[N]}\mathcal{D}_{k}$ with total training samples
$n_{\textrm{train}}=\sum_{k\in[N]}n_{k}=|\mathcal{D}_{\textrm{train}}|$. The
model $w$ is then obtained such as it minimizes the overall training loss,
defined as

$\displaystyle\text{Training loss:
}\mathcal{L}(w;\mathcal{D}_{\textrm{train}})=\frac{1}{n_{\textrm{train}}}\sum_{(\boldsymbol{x},y)\in\mathcal{D}_{\textrm{train}}}\ell(y,f(\boldsymbol{x},w))$
$\displaystyle=\sum_{k\in[N]}\frac{n_{k}}{n_{\textrm{train}}}\sum_{(\boldsymbol{x},y)\in\mathcal{D}_{k}}\frac{1}{n_{k}}\ell(y,f(\boldsymbol{x},w))=\sum_{k\in[N]}q_{k}\mathcal{L}(w;\mathcal{D}_{k}),$

where $\ell(y,f(\boldsymbol{x},w))$ is the loss for a single datapoint. In
round $t$, the server aggregates the updated model parameters $w_{k}^{(t+1)}$
from selected clients $k\in S_{t}$ and obtains the model $w^{(t+1)}=\sum_{k\in
S_{t}}\lambda_{k}w_{k}^{(t+1)}$, with weights $\lambda_{k}$ proportional to
the size of the client’s dataset $n_{k}$ and summing to one.

In our method, the server utilizes the SV to quantify selected clients’
average contribution for selection in further rounds. Our method operates in
two stages: initial client valuation and greedy client selection (c.f. Section
III-A, III-B).

In the following, we first discuss data valuation principles to quantify
client valuation.

_Shapley-Value for Client Valuation:_ We model FL as an $N$ player cooperative
game. When a subset $S_{t}$ of $M<N$ clients are selected in round $t$,
Shapley-Value [9] measures each player’s average marginal contribution over
all subsets $S$ of $S_{t}$. $U$ denotes a utility function on
$2^{[M]}\to\mathbb{R}$, which associates a reward/value with every subset of
clients. In FL, a natural choice for the utility function is negative of
validation loss, which can be evaluated at the server from aggregated client
updates $\\{w_{k}^{(t+1)}\\}_{k\in S_{t}}$ and a validation dataset
$\mathcal{D}_{\textrm{val}}$ held at the server. This choice aligns with our
objective of minimizing model loss. Thus, for a subset of clients $S$, utility
$U(S)$ is computed on the weighted average of client model updates in $S$.
Then, the Shapley Value of client $k$ is defined as follows:

$\displaystyle SV_{k}=\frac{1}{M}\sum_{S\in[M]\setminus k}\frac{U(S\cup
k)-U(S)}{\binom{M-1}{|S|}}.$

Due to the combinatorial nature of SV computation, it becomes infeasible for
many clients, and several Monte Carlo (MC) sampling approximations have been
proposed [15][16]. [15] shows that Monte Carlo SV approximation in a single
round suffers from computational complexity of $\mathcal{O}(M\log M)$. GTG-
Shapley reduces complexity by truncating MC sampling, achieving upto
$\mathcal{O}(\log M)$ in the case of IID clients, and outperforms other SV
approximation schemes in practice.

Client contributions in round $t$, denoted $SV_{k}^{(t)}$, are used to update
the value of clients $k\in S_{t}$. Since practical FL settings only have
partial client participation (selecting $M$ out of $N$ clients), we need to
compute a cumulative Shapley-Value to compare all clients. [11] proposes to
compute the cumulative Shapley Value as $SV_{k}=\sum_{t=1}^{T}SV_{k}^{(t)}$
with $SV_{k}^{(t)}=0$ for rounds where client $k$ is not selected. However,
this will unfavourably value clients that were selected less often. Client
selection algorithms S-FedAvg[13] and UCB[12] use the mean of $SV_{k}^{(t)}$
over $t$ where client $k$ was selected, to define cumulative SV, and we borrow
this choice for our algorithm. We introduce a greedy selection strategy using
cumulative SV incorporating a fast approximation algorithm GTG-Shapley [15] to
make SV computation tractable.

##  III Proposed Method

This section discusses the proposed client selection algorithm for FL,
GreedyFed, which greedily selects clients based on cumulative SV.

###  III-A Client Selection Strategy

GreedyFed greedily selects the $M$ clients with the largest cumulative
Shapley-Value $SV^{(t)}$ in each communication round $t$. Our selection scheme
has no explicit exploration in the selection process. In contrast, the
previous approach UCB [12] proposed an Upper-Confidence Bound client selection
criterion with an explicit exploration term added to the cumulative SV. In
S-FedAvg [13], client selection probabilities are assigned as a softmax over a
value vector. This value vector is computed as an exponentially weighted
average of the cumulative Shapley Values. The softmax sampling in S-FedAvg
allows for exploration by sometimes sampling clients with lower past
contributions with non-zero probability.

Our client selection procedure undergoes two operations: (1) Initialise
Shapley Values using round-robin sampling for $M$ clients per round until
$SV_{k}$ is initialised for all clients $k\in[N]$, and (2) subsequently
perform greedy selection of top $M$ clients based on $SV_{k}$. We consider two
variants for cumulative SV with exponentially weighted and standard averaging.

Round-robin sampling allows initial valuation of all clients, and subsequent
greedy selection allows for rapid convergence, minimising communication
overhead. Next, we discuss the exploration-exploitation tradeoff motivating
our design.

###  III-B Exploration-Exploitation Tradeoff

This design is motivated by two reasons: _First_ , Round-robin (RR) sampling
ensures that every client is selected at least once before comparing client
qualities. Exploiting early leads to longer discovery times for unseen high-
quality clients, especially without prior knowledge of the client reward
distribution. This is experimentally observed in the case of S-FedAvg, which
starts exploiting early but is rapidly superseded by UCB and GreedyFed after
RR sampling is over. _Second_ , a client’s valuation in FL decreases as it is
selected more often. $SV_{k}^{(t)}$ is bounded by the decrease in validation
loss in round $t$ due to the additivity property of SV that gives $\sum_{k\in
S_{t}}{SV_{k}^{(t)}}=\mathcal{L}(w^{(t)};\mathcal{D}_{\textrm{val}})-\mathcal{L}(w^{(t+1)};\mathcal{D}_{\textrm{val}})$.
Thus, as the model converges, the validation loss gradient approaches zero,
and thus $SV_{k}^{(t)}$ obeys a decreasing trend in $t$, and the clients
selected frequently and recently experience a decrease in average value
$SV_{k}$. This leads GreedyFed to fall back to other valuable clients after
exploiting the top-$M$ clients and not the less explored clients like UCB.
This explains the experimentally observed performance improvement of GreedyFed
over UCB, despite identical RR initialisation.

The client selection and fast SV computation algorithms are outlined in Alg. 1
and Alg. 2. The ModelAverage$(n_{k},w_{k})$ subroutine computes a weighted
average of models $w_{k}$ with weights proportional to $n_{k}$, and
ClientUpdate performs training on client data $\mathcal{D}_{k}$ starting from
the current server model.

Algorithm 1 Greedy Shapley-based Client Selection
$\text{GreedyFed}(\\{\mathcal{D}_{k}\\},\,\mathcal{D}_{\textrm{val}},\,w^{(0)},\,T)$

Input: $N$ clients with datasets $\\{\mathcal{D}_{k}\\}_{k=1}^{N}$, server
with validation dataset $\mathcal{D}_{\textrm{val}}$, initial model weight
$w^{(0)}$, number of communication rounds $T$, client selection budget $M$
Hyperparameters: Training epochs per round $E$, Mini-batches per training
epoch $B$, learning rate $\eta$, momentum $\gamma$, exponential averaging
parameter $\alpha$
Output: Trained model $w^{(T)}$
Initialise: Client selections $N_{k}=0,\,\forall\,k\in[N]$

1:for $t=0,\,1,\,2,\,\cdots,\,T-1$ do

2: if $t<\lceil\frac{N}{M}\rceil$ then Round-Robin (random order)

3: $S_{t}=\\{t,\,t+1,\,\cdots,\,t+M-1\\}$

4: else Greedy Selection

5: $S_{t}=M\text{ largest SV clients}$

6: for client $k$ in $S_{t}$ do

7: $w_{k}^{(t+1)}=$
ClientUpdate$(\mathcal{D}_{k},\,w^{(t)};\,E,\,B,\,\eta,\,\gamma)$

8: $N_{k}\leftarrow N_{k}+1$

9: $w^{(t+1)}=$ ModelAverage$(n_{k},\,w_{k}^{(t+1)}:k\in S_{t})$

10: $\\{SV_{k}^{(t)}\\}_{k\in S_{t}}=$ GTG-
Shapley$(w^{(t)},\,\\{w_{k}^{(t+1)}\\},\,\mathcal{D}_{\textrm{val}})$

11: for client $k$ in $S_{t}$ do

12: $SV_{k}\leftarrow\frac{(N_{k}-1)SV_{k}\,+\,SV_{k}^{(t)}}{N_{k}}$ (Mean) OR

13: $SV_{k}\leftarrow\alpha\cdot SV_{k}\,+\,(1-\alpha)\cdot SV_{k}^{(t)}$
(Exponential)

14:return $w^{(T)}$

Algorithm 2 Server-Side Shapley Value Approximation $\text{GTG-
Shapley}(w^{(t)},\,\\{w_{k}^{(t+1)}\\}_{k\in
S_{t}},\,\mathcal{D}_{\textrm{val}})$

Input: Current server model $w^{(t)}$, client updated models
$\\{w_{k}^{(t+1)}\\}$, validation dataset at server
$\mathcal{D}_{\textrm{val}}$
Hyperparameters : Error threshold $\epsilon$, maximum iterations $T$
Output : Shapley Values $\\{SV_{k}\\}_{k\in S_{t}}$
Initialise : $SV_{k}=0,\,\forall\,k\in S_{t}$

1:Compute $w^{(t+1)}=$ ModelAverage$(n_{k},\,w_{k}^{(t+1)}:k\in S_{t})$

2:$v_{0}=\mathcal{U}(w^{(t)}),\,v_{M}=\mathcal{U}(w^{(t+1)}),\,\mathcal{U}(w):=-\mathcal{L}(w;\,\mathcal{D}_{\textrm{val}})$

3:if $|v_{M}-v_{0}|<\epsilon$ then

4: return $SV_{k}^{(0)}=0,\,\forall\,k$ (between round truncation)

5:else

6: for $\tau=0,\,1,\,\dots,\,T-1$ do

7: for client $k\in S_{t}$ do

8: permute $S_{t}\setminus\\{k\\}$: $\pi_{\tau}[0]=k,\,\pi_{\tau}[1:M]$

9: $v_{j}=v_{0}$

10: for $j=1,\,2,\,\cdots,\,M$ do

11: if $|v_{M}-v_{j}|<\epsilon$ then

12: $v_{j+1}=v_{j}$ (within round truncation)

13: else

14: Client Subset $S^{*}=\pi_{\tau}[:j]$

15: $w^{{}^{\prime}}=$ ModelAverage$(n_{k},\,w_{k}^{(t+1)},\,S^{*})$

16: $v_{j+1}=\mathcal{U}(w^{{}^{\prime}})$

17:
$SV_{\pi_{\tau}[j]}^{(\tau)}=\frac{\tau-1}{\tau}SV_{\pi_{\tau}[j]}^{(\tau-1)}+\frac{1}{\tau}(v_{j+1}-v_{j})$

18: $v_{j}=v_{j+1}$

19: break if converged

20:return ${SV_{k}^{(\tau)}},\,k\in S_{t}$

##  IV Experiments

We evaluate our algorithm GreedyFed on several real-world classification tasks
against six algorithms: FedAvg [1], Power-Of-Choice [7], FedProx [5], S-FedAvg
[13], UCB [12] and centralized training at the server (as an upper bound), and
demonstrate faster and more stable convergence with higher accuracies under
timing constraints from the communication network, especially under
heterogeneous settings111Our code is publicly available at:
https://github.com/pringlesinghal/GreedyFed

We consider public image datasets MNIST [17], FashionMNIST (FMNIST) [18], and
CIFAR10 [19]. For MNIST and FMNIST, we implement an MLP classifier, while
CIFAR10 uses a CNN. For all datasets, we split the original test set into a
validation and test set of 5000 images each at the server.

Data Heterogeneity: We distribute training samples across clients according to
the Dirichlet($\alpha$) distribution, where $\alpha$ controls the degree of
label distribution skew across clients. The number of data points at each
client $n_{k}=q_{k}n_{\textrm{train}}$ is distributed according to a power law
with $q_{k}$ sampled from $P(x)=3x^{2},\,x\in(0,1)$ and normalised to sum 1,
as done in [7]. We present results for different values of
$\alpha\in\\{10^{-4},0.1,100\\}$.

Timing Constraints: We impose a fixed budget on the number of communication
rounds $T$ for model training. For smaller $T$, model training may be stopped
well before convergence if satisfactory performance is achieved. In the real
world, such timing constraints may arise for several reasons, like limited
communication opportunities with the PS, mobility scenarios, constraints on
data usage and power consumption of edge devices, or the need for real-time
deployment of models. We compare over $T\in\\{150,250,350\\}$ for MNIST and
FashionMNIST and $T\in\\{100,150,200\\}$ for CIFAR10.

Systems Heterogeneity: FL is characterized by heterogeneity in client-side
computing resources. Assuming the presence of another timing constraint for
transmitting results to the server within each round, some clients with lower
computing or communication resources (stragglers) cannot complete the globally
fixed $E$ epochs of training and, thus, transmit partial solutions. We
simulate stragglers by selecting $x$ fraction of clients and setting the
number of epochs for local training $E_{k}$ to a uniform random integer in $1$
to $E$, similar to [5]. We present results for $x\in\\{0,0.5,0.9\\}$.

Privacy Heterogeneity: To protect their data, clients can obfuscate
transmitted gradients with noise [20]. We simulate varying client privacy
requirements with a different noise level for each client. We assign noise
level $\sigma_{k}=(k-1)\frac{\sigma}{N}$ to client $k$ in a random permutation
of $[N]$. In each communication round, we add IID Gaussian noise from
$\mathcal{N}(0,\sigma_{k}^{2})$ to the updated model parameters of client
$k\in S_{t}$ before transmitting to the PS. We compare over
$\sigma\in\\{0,0.05,0.1\\}$.

Other Hyperparameters: We report the mean and standard deviation of test
accuracies over five seeds after $T$ communication rounds with $N$ clients and
$M$ selections per round. We report $N,M,T$ in each table. We fix
$E=5,\,B=5,\,\text{learning rate }\eta=0.01,\,\text{momentum }\gamma=0.5$
across experiments. Data heterogeneity $\alpha=10^{-4}$ unless specified. We
vary FedProx parameter $\mu\in\\{0.01,0.1,1,10\\}$. For Power-Of-choice [7],
we set an exponential decay rate of $0.9$ on the size of the client query set.
For GreedyShap, we consider exponential averaging over
$\alpha\in\\{0,0.1,0.5,0.9\\}$ and standard averaging, and report results for
the best parameters. For GTG-Shapley [15] $\epsilon=10^{-4},T=50\times|S|$ for
subset $S$, with the default convergence criterion.

Figure 1: Test Accuracy versus Communication Rounds comparison on CIFAR10,
data heterogeneity $\alpha=10^{-4}$. GreedyFed surpasses all baselines with
the fastest convergence and lowest standard deviation, achieving an accuracy
close to centralized training.

##  V Analysis

GreedyFed consistently achieves higher accuracies and lower standard deviation
than all baselines, demonstrating the superiority of our method. All Shapley-
Value based methods outperform the other baselines, indicating that this is a
promising direction for designing client selection strategies.

Data Heterogeneity: In Table I, GreedyFed consistently outperforms baselines
in heterogeneous environments ($\alpha=10^{-4},0.1$) and exhibits only a
slight performance dip when the data distribution is nearly uniform
($\alpha=100$).

Timing Constraints: In Table II GreedyFed achieves faster convergence, with
performance saturating for small $T$ (also see Fig. 1). For instance,
GreedyShap shows only a $4\%$ increase in accuracy on CIFAR10 from
$T=150\text{ to }350$, while FedAvg shows an $8\%$ increase.

Systems Heterogeneity: In Table III, GreedyFed shows a smaller drop in
performance with a large proportion of stragglers. On FashionMNIST, GreedyFed
only experiences a $1\%$ drop in accuracy with $90\%$ stragglers while FedAvg
and FedProx experience a $6\%$ drop. More importantly, the standard deviation
of other baselines increases drastically in the presence of stragglers,
indicating highly unstable training.

Privacy Heterogeneity: In Table IV, GreedyFed shows excellent robustness to
noisy clients. On FashionMNIST, GreedyFed only experiences an $8\%$ drop in
accuracy for $\sigma=0.1$ while FedAvg incurs a drastic $20\%$ drop. GreedyFed
also shows a much smaller $0.5$ point increase in standard deviation compared
to baselines with noise.

##  VI Conclusion

We highlight the benefit of greedy client selection using cumulative Shapley
Value in heterogeneous, noisy environments with strict timing constraints on
communication. For future work, one can explore how the quality of client
selection depends on the distribution of validation data at the server. While
our experiments assume similar validation and training distributions, real-
world scenarios may involve clients with unique data classes. Previous studies
indicate that SV can be unfair to Mavericks (clients with unique data
classes), suggesting the need to address distribution mismatches in SV
computation and client selection. Future work may also explore providing
clients with Shapley Values as feedback encouraging less relevant clients to
drop out to reduce communication overhead, similar to [12].

TABLE I: Data Heterogeneity

Dataset Algorithm $\alpha=10^{-4}$ $\alpha=0.1$ $\alpha=100$ MNIST T = 400 N =
300 M = 3 GreedyFed $\mathbf{94.06\pm 0.19}$ $88.83\pm 0.74$ $93.98\pm 0.33$
UCB $93.39\pm 0.72$ $87.70\pm 3.19$ $94.12\pm 0.28$ S-FedAvg $91.94\pm 0.95$
$86.26\pm 2.10$ $94.77\pm 0.29$ FedAvg $92.19\pm 1.40$ $\mathbf{88.86\pm
2.09}$ $\mathbf{94.79\pm 0.29}$ FedProx $92.18\pm 1.39$ $88.84\pm 2.12$
$94.78\pm 0.32$ Power-Of-Choice $91.58\pm 1.52$ $88.27\pm 2.12$ $94.72\pm
0.29$ Centralized $95.37\pm 0.26$ $95.20\pm 0.24$ $95.32\pm 0.22$ FMNIST T =
400 N = 300 M = 3 GreedyFed $\mathbf{85.18\pm 0.33}$ $\mathbf{79.16\pm 0.62}$
$84.83\pm 0.42$ UCB $84.41\pm 0.68$ $77.24\pm 1.24$ $83.80\pm 0.73$ S-FedAvg
$81.04\pm 6.09$ $71.77\pm 5.87$ $85.38\pm 0.38$ FedAvg $82.84\pm 1.29$
$72.68\pm 5.79$ $85.37\pm 0.49$ FedProx $82.86\pm 1.21$ $73.62\pm 5.72$
$85.29\pm 0.52$ Power-Of-Choice $69.46\pm 7.34$ $73.28\pm 3.45$
$\mathbf{85.41\pm 0.22}$ Centralized $86.16\pm 0.32$ $85.75\pm 0.37$ $85.95\pm
0.24$ CIFAR10 T = 200 N = 200 M = 20 GreedyFed $\mathbf{50.26\pm 0.95}$
$\mathbf{43.90\pm 1.04}$ $50.80\pm 0.96$ UCB $48.89\pm 1.84$ $43.02\pm 2.75$
$51.86\pm 0.62$ S-FedAvg $40.71\pm 4.54$ $41.85\pm 1.59$ $\mathbf{51.92\pm
0.58}$ FedAvg $41.04\pm 5.54$ $41.67\pm 3.85$ $51.74\pm 0.85$ FedProx
$42.00\pm 3.45$ $41.66\pm 3.84$ $51.74\pm 0.83$ Power-Of-Choice $42.54\pm
3.23$ $42.27\pm 1.22$ $51.78\pm 0.80$ Centralized $51.48\pm 1.86$ $52.36\pm
1.82$ $53.22\pm 1.06$

TABLE II: Timing Constraints

Dataset Algorithm $T=150$ $T=250$ $T=350$ MNIST N = 300 M = 3 GreedyFed
$\mathbf{91.12\pm 0.32}$ $\mathbf{92.90\pm 0.28}$ $\mathbf{93.78\pm 0.09}$ UCB
$90.26\pm 0.83$ $90.91\pm 1.05$ $92.40\pm 1.28$ S-FedAvg $87.33\pm 3.24$
$91.26\pm 1.44$ $89.22\pm 3.11$ FedAvg $87.56\pm 2.23$ $90.20\pm 3.21$
$89.50\pm 0.88$ FedProx $87.57\pm 2.14$ $90.22\pm 3.18$ $89.53\pm 0.85$ Power-
Of-Choice $85.26\pm 1.74$ $89.09\pm 2.25$ $91.20\pm 2.38$ Centralized
$92.77\pm 0.28$ $94.27\pm 0.27$ $95.04\pm 0.23$ FMNIST N = 300 M = 3 GreedyFed
$\mathbf{82.06\pm 0.51}$ $\mathbf{84.02\pm 0.37}$ $\mathbf{84.75\pm 0.29}$ UCB
$80.53\pm 2.34$ $82.53\pm 1.16$ $83.04\pm 1.67$ S-FedAvg $76.25\pm 4.95$
$75.04\pm 6.75$ $80.23\pm 5.86$ FedAvg $72.07\pm 9.28$ $72.64\pm 12.22$
$77.69\pm 7.64$ FedProx $73.37\pm 7.10$ $73.47\pm 10.06$ $78.94\pm 5.66$
Power-Of-Choice $70.13\pm 5.94$ $71.74\pm 9.18$ $74.93\pm 12.11$ Centralized
$83.44\pm 0.38$ $84.83\pm 0.55$ $85.64\pm 0.41$ $T=100$ $T=150$ $T=200$
CIFAR10 N = 200 M = 20 GreedyFed $\mathbf{46.36\pm 1.65}$ $\mathbf{49.38\pm
1.02}$ $\mathbf{50.26\pm 0.95}$ UCB $43.75\pm 1.44$ $46.94\pm 1.74$ $48.89\pm
1.84$ S-FedAvg $34.38\pm 7.00$ $36.31\pm 5.78$ $40.71\pm 4.54$ FedAvg
$33.22\pm 6.08$ $40.67\pm 2.62$ $41.04\pm 5.54$ FedProx $34.88\pm 2.48$
$40.80\pm 0.94$ $42.00\pm 3.45$ Power-Of-Choice $36.58\pm 5.22$ $38.36\pm
6.18$ $42.54\pm 3.23$ Centralized $46.59\pm 1.14$ $49.91\pm 1.10$ $51.48\pm
1.86$

TABLE III: Systems Heterogeneity

Dataset Algorithm $x=0$ $x=0.5$ $x=0.9$ MNIST T = 400 N = 300 M = 3 GreedyFed
$\mathbf{94.06\pm 0.19}$ $\mathbf{93.70\pm 0.33}$ $\mathbf{92.94\pm 0.22}$ UCB
$93.39\pm 0.72$ $92.62\pm 0.65$ $91.84\pm 0.64$ S-FedAvg $91.94\pm 0.95$
$91.57\pm 1.27$ $92.05\pm 0.29$ FedAvg $92.19\pm 1.40$ $91.03\pm 1.15$
$88.44\pm 5.74$ FedProx $92.18\pm 1.39$ $91.05\pm 1.14$ $88.45\pm 5.77$ Power-
Of-Choice $91.58\pm 1.52$ $89.60\pm 3.43$ $90.24\pm 2.19$ Centralized
$95.37\pm 0.26$ $95.37\pm 0.26$ $95.37\pm 0.26$ FMNIST T = 400 N = 300 M = 3
GreedyFed $\mathbf{85.18\pm 0.33}$ $\mathbf{84.66\pm 0.55}$ $\mathbf{84.19\pm
0.19}$ UCB $84.41\pm 0.68$ $83.58\pm 1.15$ $81.86\pm 2.56$ S-FedAvg $81.04\pm
6.09$ $82.23\pm 2.11$ $74.66\pm 10.17$ FedAvg $82.84\pm 1.29$ $78.93\pm 5.20$
$76.20\pm 6.53$ FedProx $82.86\pm 1.21$ $79.35\pm 4.61$ $76.31\pm 6.01$ Power-
Of-Choice $69.46\pm 7.34$ $81.49\pm 3.12$ $79.03\pm 4.63$ Centralized
$86.16\pm 0.32$ $86.16\pm 0.32$ $86.16\pm 0.32$ CIFAR10 T = 200 N = 200 M = 20
GreedyFed $\mathbf{50.26\pm 0.95}$ $\mathbf{48.74\pm 1.34}$ $\mathbf{47.58\pm
0.77}$ UCB $48.89\pm 1.84$ $47.98\pm 1.71$ $46.51\pm 0.87$ S-FedAvg $40.71\pm
4.54$ $38.55\pm 5.93$ $34.88\pm 3.54$ FedAvg $41.04\pm 5.54$ $43.16\pm 2.57$
$37.23\pm 4.47$ FedProx $42.00\pm 3.45$ $43.26\pm 2.54$ $37.21\pm 4.35$ Power-
Of-Choice $42.54\pm 3.23$ $36.92\pm 8.51$ $37.39\pm 3.41$ Centralized
$51.48\pm 1.86$ $51.52\pm 1.85$ $51.52\pm 1.94$

TABLE IV: Privacy Heterogeneity

Dataset Algorithm $\sigma=0$ $\sigma=0.05$ $\sigma=0.1$ MNIST T = 400 N = 300
M = 3 GreedyFed $\mathbf{94.06\pm 0.19}$ $\mathbf{90.79\pm 0.45}$
$\mathbf{87.33\pm 0.68}$ UCB $93.39\pm 0.72$ $87.23\pm 1.82$ $75.36\pm 4.67$
S-FedAvg $91.94\pm 0.95$ $79.17\pm 5.88$ $62.78\pm 4.37$ FedAvg $92.19\pm
1.40$ $83.98\pm 2.45$ $63.63\pm 6.34$ FedProx $92.18\pm 1.39$ $83.95\pm 2.42$
$63.33\pm 6.31$ Power-Of-Choice $91.58\pm 1.52$ $83.87\pm 1.85$ $58.22\pm
4.55$ Centralized $95.37\pm 0.26$ $95.37\pm 0.26$ $95.37\pm 0.26$ FMNIST T =
400 N = 300 M = 3 GreedyFed $\mathbf{85.18\pm 0.33}$ $\mathbf{81.23\pm 0.55}$
$\mathbf{77.17\pm 0.73}$ UCB $84.41\pm 0.68$ $76.11\pm 2.28$ $67.26\pm 7.29$
S-FedAvg $81.04\pm 6.09$ $75.45\pm 3.72$ $57.67\pm 7.49$ FedAvg $82.84\pm
1.29$ $74.77\pm 2.12$ $62.18\pm 4.39$ FedProx $82.86\pm 1.21$ $74.81\pm 2.06$
$62.79\pm 4.71$ Power-Of-Choice $69.46\pm 7.34$ $69.47\pm 5.08$ $56.08\pm
8.06$ Centralized $86.16\pm 0.32$ $86.16\pm 0.32$ $86.16\pm 0.32$ CIFAR10 T =
200 N = 200 M = 20 GreedyFed $\mathbf{50.26\pm 0.95}$ $\mathbf{48.44\pm 1.06}$
$\mathbf{47.64\pm 1.02}$ UCB $48.89\pm 1.84$ $47.86\pm 1.87$ $44.76\pm 2.19$
S-FedAvg $40.71\pm 4.54$ $39.41\pm 4.07$ $31.89\pm 12.33$ FedAvg $41.04\pm
5.54$ $39.74\pm 6.30$ $36.34\pm 5.53$ FedProx $42.00\pm 3.45$ $39.66\pm 6.27$
$36.16\pm 5.52$ Power-Of-Choice $42.54\pm 3.23$ $38.55\pm 2.82$ $36.19\pm
1.87$ Centralized $51.48\pm 1.86$ $51.44\pm 1.83$ $51.46\pm 1.93$

## References

  * [1] B. McMahan et al., “Communication-efficient learning of deep networks from decentralized data,” in Artificial intelligence and statistics, pp. 1273–1282, PMLR, 2017.
  * [2] J. Konečnỳ et al., “Federated learning: Strategies for improving communication efficiency,” arXiv preprint arXiv:1610.05492, 2016\.
  * [3] S. U. Stich et al., “Sparsified sgd with memory,” Advances in Neural Information Processing Systems, 2018.
  * [4] Y. Cheng et al., “Model compression and acceleration for deep neural networks: The principles, progress, and challenges,” IEEE Signal Processing Magazine, vol. 35, no. 1, pp. 126–136, 2018.
  * [5] T. Li et al., “Federated optimization in heterogeneous networks,” Proceedings of Machine learning and systems, vol. 2, pp. 429–450, 2020.
  * [6] S. P. Karimireddy et al., “Scaffold: Stochastic controlled averaging for federated learning,” in International conference on machine learning, pp. 5132–5143, PMLR, 2020.
  * [7] Y. J. Cho et al., “Towards understanding biased client selection in federated learning,” in International Conference on Artificial Intelligence and Statistics, 2022.
  * [8] E. Rizk et al., “Optimal importance sampling for federated learning,” in ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3095–3099, IEEE, 2021.
  * [9] L. S. Shapley, “Cores of convex games,” International journal of game theory, vol. 1, pp. 11–26, 1971.
  * [10] G. Wang et al., “Measure contribution of participants in federated learning,” in 2019 IEEE international conference on big data (Big Data), pp. 2597–2604, IEEE, 2019.
  * [11] T. Wang et al., “A principled approach to data valuation for federated learning,” Federated Learning: Privacy and Incentive, pp. 153–167, 2020\.
  * [12] S. R. Pandey et al., “Goal-oriented communications in federated learning via feedback on risk-averse participation,” in 2023 IEEE 34th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), pp. 1–6, 2023.
  * [13] L. Nagalapatti and R. Narayanam, “Game of gradients: Mitigating irrelevant clients in federated learning,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 9046–9054, 2021.
  * [14] J. Huang et al., “Maverick matters: Client contribution and selection in federated learning,” in Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2023.
  * [15] Z. Liu et al., “Gtg-shapley: Efficient and accurate participant contribution evaluation in federated learning,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 13, no. 4, pp. 1–21, 2022.
  * [16] A. Ghorbani and J. Zou, “Data shapley: Equitable valuation of data for machine learning,” in International conference on machine learning, pp. 2242–2251, PMLR, 2019.
  * [17] Y. LeCun et al., “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, 1998.
  * [18] H. Xiao et al., “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” arXiv preprint arXiv:1708.07747, 2017.
  * [19] A. Krizhevsky, G. Hinton, et al., “Learning multiple layers of features from tiny images,” 2009.
  * [20] M. Abadi et al., “Deep learning with differential privacy,” in Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308–318, 2016.


# Bipartite Consensus in the Presence of Denial of Service Adversary

Gopika R1, Ankita Sharma2 and Rakesh R Warier3 1 Gopika R. is a PhD student in
the Department of Electrical, Electronics and Instrumentation engineering,
BITS Pilani, KK Birla Goa Campus, Zuari Nagar, Goa, India<EMAIL_ADDRESS>pilani.ac.in2 Ankita Sharma is an Assistant Professor in School of Basic
Science (Mathematics), Indian Institute of Information Technology, Una,
Himachal Pradesh, India<EMAIL_ADDRESS>Rakesh R Warier is an
Assistant Professor in the Department of Electrical, Electronics and
Instrumentation engineering, BITS Pilani, KK Birla Goa Campus, Zuari Nagar,
Goa, India<EMAIL_ADDRESS>
###### Abstract

Attacks on a set of agents with cooperative and antagonistic interactions
attempting to achieve linear bipartite consensus are considered here. In
bipartite consensus, two clusters are formed, agents in each cluster
converging to a final state which is negative of the other cluster’s final
state. The adversary seeks to slow down the bipartite consensus by a Denial of
Service (DoS) type attack where the attacker has the capability to break a
specific number of links at each time instant. The problem is formulated as an
optimal control problem and the optimal strategy for the adversary is
determined.

##  I INTRODUCTION

Networked systems form the backbone of critical infrastructures such as power
grids, transportation systems, home automation systems. Other examples of
interconnected networked systems include robotic systems and autonomous aerial
systems. These are interconnected by design separated geographically and
functionally. Distributed coordination of multiple robotic vehicles, including
unmanned aerial vehicles, unmanned ground vehicles, and unmanned underwater
vehicles, has been a very active research subject by the systems and control
community [1, 2]. The distributed control of multiple agents can offer more
flexibility, scalability, adaptivity, and more robustness to individual
failure. Additionally, they find applications in distributed networks
including smart grids [3], autonomous under water vehicles, unmanned aerial
vehicles, etc.

Consensus problems normally deal with cooperative systems. In these types of
cooperative systems, the consensus is achieved through the communication of
agents which are characterized by edge weights that are non-negative. There
can be situations wherein the agents in a system need to repel each other or
maintain a certain formation in which we will be forced to use a negative
weight for interaction. Therefore, in short, non-negative weights corresponds
to a system with cooperative interactions and negative weights implies
antagonistic interactions. The formation of several clusters is generally
referred to as a multi-partite consensus. If the number of clusters in a
multi-partite consensus is two, then they are referred to as bipartite
consensus where the agent forms two different clusters and they converge to a
point which is different only in the sign of the value [4, 5]. We consider the
problem of a set of agents trying to achieve bipartite consensus in the
presence of an adversary.

The networked multi-agent system can suffer from malicious interference which
can disrupt the performance of the system. The robust performance of a
networked multi-agent system requires physical attacks and cyber-attacks to be
detected and countermeasures to be taken. Several attacks on networked control
systems have been reported in the near past. These attacks can be classified
as denial-of-service attacks, replay attacks, and fault data injection attacks
[6]. The authors in [7] overview the existence of several categories of
attacks on power and transportation fields on a control-theoretic framework.
The study was conducted on the basis of prevention, resilience, and detection
$\&$ isolation of the different types of attacks. Authors in [8] studied the
problem of security on a linear dynamical system that is prone to DoS attacks
and design a controller that minimizes the effect of this attack. A more
comprehensive attack and system model considering fault detector mechanism and
model uncertainties were proposed by [6]. The work by Pasqualetti et. al. [9]
explored the challenges of detection and identification of attack, using a
descriptor system model.

Preliminary work in the area of linear consensus of multi-agent systems under
DoS attack was considered in [10]. They model the problem with cooperative
interactions among the agents and finds the optimal strategy to slow down the
consensus. The extension of the work was made in [11] by introducing the
effects caused by the presence of a defender. This system was also modeled
based on Pontryagin’s Maximum Principle and discussed the existence of saddle
point equilibrium. In [11] the authors considered only the cooperative
interactions among the agents.

To the best of our knowledge, the performance of a network with cooperative
and antagonistic interactions in the presence of an adversary remains
unexplored. Here, we consider a set of agents that are interconnected by a
signed graph that is structurally balanced. The set of agents are trying to
achieve bipartite consensus. This system is disrupted by an external adversary
which can cut links between agents. There is a constraint on the maximum
number of links that can be broken at a certain time instant. The adversary
has the ability to break both positive and negative links. The problem is
formulated as an optimal problem and the optimal attack strategy for the
adversary for slowing down the bipartite consensus is derived. The results are
illustrated by numerical simulations.

The rest of the paper is organized as follows, section II talks about the
basic preliminaries and section III is about the problem formulation used in
this article. Section IV presents the simulation results with a numerical
example and the article is concluded by section V which also provides the
future scope of the work.

##  II BIPARTITE CONSENSUS

When a group of agents interacts over a signed graph, they can form a
bipartite consensus where values of agents converge to two clusters. In this
section we summarize some fundamental results on bipartite consensus from
works [4] and [5].

Consider a signed graph $G=\left(V,E,A\right)$, where
$V=\left\\{v_{1},v_{2},\ldots,v_{n}\right\\}$ is the set of nodes or agents,
$E$ is the set of edges and $A$ is the adjacency matrix that contains or
represents the interconnection between the agents. The non-diagonal elements
in the matrix $A$ represent the weights between the agents and the diagonal
entries in the matrix are considered to be zero. The Laplacian matrix for the
system can be defined as $L^{G}=C-A$, where $C$ is the connectivity matrix
which will be a diagonal matrix with the values as the sum of the absolute
value of the adjacent links connected to that particular node. Therefore, the
Laplacian matrix $L^{G}$ can be represented as

$\displaystyle l^{G}_{ik}=\left\\{\begin{array}[]{ll}\sum_{j\rightsquigarrow
i}\lvert{a_{ij}}\rvert&k\ =\ i\\\ -a_{ij}&k\ \neq\ i.\\\ \end{array}\right.$
(3)

The dynamics of $n$ agents $x_{i}\in\mathbb{R}$ connected by the graph $G$ is
given by,

$\displaystyle\dot{x}=-L^{G}x(t)$ (4)

where $x=[x_{1},\cdots,x_{n}]^{\top}$ and $L_{G}$ is calculated as in (3). The
idea of structurally balanced graph is defined below.

###### Definition 1

[4] A graph $G$ is structurally balanced if and only if

  1. 1.

All cycles of $G$ are positive

  2. 2.

$0$ is an eigenvalue of $L^{G}$ which is the Laplacian matrix of the graph $G$
as defined in (3).

A structurally balanced graph that satisfies the properties as in definition 1
corresponds to the partitioning of a signed graph into two sub-communities in
such a manner all the edges within a sub-community have positive weights and
all the edges connecting these sub-communities with other sub-communities has
a negative weight.

###### Lemma 1

The system (4) admits a bipartite consensus solution if and only if the graph
$G$ is structurally balanced [4].

Here, bipartite consensus implies $\lim_{t\to\infty}x_{i}=|\beta|$ where
$\beta\neq 0$, for all $i=1,\cdots,n$.

###### Proof:

The proof is provided in [4] and is omitted here for brevity. ∎

Consider the example in fig 1. The system has $11$ agents that form two
different groups. The agents within a sub-community have positive weights thus
showing cooperative interaction and the weights between the agents of sub-
community A and sub-community B are negative thus showing an antagonistic
interaction. As shown in [4], the agents of two sub-communities ’repel’ each
other, while moving towards agents of the same sub-community forming a
bipartite consensus, essentially two clusters.

Figure 1: Bipartite consensus of a multi-agent system; The black circles
indicate the different agents, blue connections (links) represent the
cooperative interactions and the red connections indicate the antagonistic
interaction

In the next section we consider the problem of bipartite consensus under
attack.

##  III PROBLEM FORMULATION

Consider a network of interconnected systems of weighted undirected graphs
with $n$ agents or nodes. This can be represented using $G=(V,E)$ where $V$
represents the vertices which are agents $\left[v_{1},v_{2},...,v_{n}\right]$
and $E$ represents the edges. It is important that the network graph must be
structurally balanced as in definition 1. It is assumed that the adversary has
complete knowledge of the system.

The state of the nodes at time $t$ is represented as
$x=\left[x_{1}(t),x_{2}(t),...,x_{n}(t)\right]^{T}$. Let the dynamics of the
system be

$\displaystyle\dot{x}=-L^{G}(t)x(t)$ (5)

where $L^{G}$ is defined as the difference between the connectivity matrix $C$
and the adjacency matrix $A$. The matrix $A$ contains the weights of that
particular links which are any scalar values and the self loops such as
$a_{11}$ or $a_{22}$, etc are not considered. These values are considered in
the connectivity matrix $C$. Therefore, as a result the matrix $C$ will be a
diagonal matrix with the values being the sum of the absolute values of
adjacent links connected to that node, $C_{ii}=\sum_{j\in
adj(i)}\lvert{a_{ij}}\rvert$. The weights of the system can be either zero,
positive value or a negative value based on the following condition wherein
$C_{k}$ and $C_{l}$ represents the set of nodes that belongs to the two
different clusters such that $C_{k}\cup C_{l}=V$ and $C_{k}\ \cap\ C_{l}\ =\
\emptyset$. $a_{ij}$ follows the standard rules if $(i,j)\in E$ and if $(i,j)$
belong to the same cluster, then $a_{ij}>0$ and if $(i,j)$ belongs to
different cluster, then $a_{ij}<0$. $a_{ij}=0$ if $(i,j)\notin E$. From
Definition 1 when the graph is structurally balanced, the agents of the same
cluster will have positive connections and the connection between the inter-
cluster agents will be negative. From Lemma 1, this will result in agents
achieving bipartite consensus, where each cluster of agents converging to
values differing only in sign. Let us consider a structurally balanced network
graph with the system dynamics as

$\dot{x}=-L^{G}(t)x(t)$ (6)

where $L^{G}=C-A$.

$\displaystyle l^{G}_{ik}=\left\\{\begin{array}[]{ll}\sum_{j\rightsquigarrow
i}\lvert{a_{ij}}\rvert&k\ =\ i\\\ -a_{ij}&k\ \neq\ i.\\\ \end{array}\right.$
(9)

where $j\rightsquigarrow i$ implies $j$ is connected to $i$.

$L^{G}$ is a matrix that represents the system before the attack. The
adversary aims to slow down the consensus by breaking the links that connect
different agents. Let $\alpha$ be the maximum number of links that the
adversary can disrupt at each time instant. The control is given by
$u(t)=[u_{12}(t),u_{23}(t),...,u_{(n-1)n}(t)]^{T}$, where
$u_{ij}(t)\in\\{0,1\\}$. When $u_{ij}(t)=1$, the link $(i,j)$ is broken at
time $t$. The weight of each link $(i,j)$ can be redefined as
$a^{a}_{ij}=a_{ij}(1-u_{ij})$ and the graph under attack can be modelled as

$\displaystyle l^{Ga}_{ik}=\left\\{\begin{array}[]{ll}\sum_{j\rightsquigarrow
i}\lvert{a_{ij}(1-u_{ij})}\rvert&k\ =\ i\\\ -a_{ij}(1-u_{ij})&k\ \neq\ i.\\\
\end{array}\right.$ (12)

The objective function of the adversary can be defined as

$J(u)=\int^{T}_{0}k(t)\ x(t)^{T}M(t)\ x(t)\ dt,$ (13)

where $k(t)$ is the positive kernel integrable over $[0,T]$ and $M$ is the
connection matrix which indicates all the connections between the sub-
communities of the bipartite network graph.

$\displaystyle
M_{ij}=\left\\{\begin{array}[]{cll}-\operatorname{sgn}(a_{ij})&;&i\ \neq\ j\\\
n-1&;&i\ =\ j\\\ \end{array}\right.$ (16)

The problem can be formulated in a optimal control framework as follows

$\displaystyle\underset{u(t)\in U}{\max}\ J(u)$ $\displaystyle s.t.\ \ \ $
$\displaystyle\dot{x}(t)\ =\ -L^{G}(t)x(t).$ (17)

The Hamiltonian is defined as

$\displaystyle H(x,p,u)=k(t)x(t)^{T}Mx(t)-p(t)^{T}L^{G}(t)x(t)$ (18)

Considering the first order necessary conditions for optimality [12] can be
formulated wherein the state and co-state dynamics becomes

$\displaystyle\frac{\partial H}{\partial p}$
$\displaystyle=\dot{x}(t)=-L_{G}(t)x(t)$ (19) $\displaystyle\frac{-\partial
H}{\partial x}$ $\displaystyle=\dot{p}(t)=-k(t)Mx(t)+L_{G}(t)^{T}p(t)$ (20)
$\displaystyle\frac{\partial H}{\partial u}$ $\displaystyle=0$ (21)

The optimal control can be obtained as

$\displaystyle u^{*}$ $\displaystyle=\underset{u\in U}{\arg\max}\ H(x,p,u)$
(22)

To solve for $u^{*}$, we need to maximize the $H$. Solving for $p^{T}L^{G}x$
and substituting in (18)

$\displaystyle p^{T}L^{G}x$ $\displaystyle=$
$\displaystyle\sum_{j=2}^{n}\sum_{i=1}^{n-1}\lvert{a_{ij}}\rvert(1-u_{ij})f_{ij}$
(23)

where
$f_{ij}=\big{(}p_{i}-\operatorname{sgn}(a_{ij})p_{j}\big{)}\big{(}x_{i}-x_{j}\big{)}$.

$\max
H(x,p,u)=k(t)x(t)^{T}Mx(t)-\sum_{j=2}^{n}\sum_{i=1}^{n-1}(1-u_{ij})f_{ij}$
(24) $\displaystyle
u^{*}_{ij}=\left\\{\begin{array}[]{cll}\\{0,1\\}&;&\text{if}\ f_{ij}=0\\\
1&;&\text{if}\ (i,j)\ \in I_{t}\\\ 0&;&\text{if}\ f_{ij}>0.\end{array}\right.$
(28)

where $I_{t}$ is the ordered set of values of $f_{ij}$ that are less than zero
and can be attacked, that is,

$\displaystyle I_{t}$ $\displaystyle=\big{\\{}(i,j)\in V:f_{ij}<0,\text{ and
}f_{ij}<f_{\alpha+1}\big{\\}}$ (29)

The function $f_{ij}$ depends on both the state $x(t)$ and co-state $p(t)$
variables. The objective of the adversary is to slow down the consensus and
for this he can break the links that connect these agents with each other.
Therefore, we need to find an optimal strategy for the adversary so that the
$J(u)$ increases because of the disruption caused by him. We need to look at
the cost function of the adversary to determine the optimal strategy which is
explained using the following theorem.

###### Theorem 1

For a particular time $t$, the optimal strategy of the adversary is to break
the $\alpha$ number of links with the highest $w_{ij}$ value where
$w_{ij}=\lvert{a_{ij}}\rvert\big{(}x_{j}-\operatorname{sgn}(a_{ij})x_{i}\big{)}^{2}.$

Proof. Let us consider $\alpha$ be the number of links that are break by the
adversary at time instant $t$. The value of $f_{ij}$ cannot change in a finite
interval as it solely depends on $x(t)$ and $p(t)$ which does not change in
that interval which results in the control to remain unchanged.

Let $[s,s+\Delta s]$ be a sub-interval of $[0,T]$ in which the adversary
applies the strategy $u^{A}$ with a system matrix as $L_{1}$. Therefore, the
state trajectory is given as

$\displaystyle x(t)=e^{-L_{1}(t-s)}x(s)\ ;\ \ t\in[s,s+\Delta s]$

Let $P(t)$ be $e^{-L_{1}t}$. Let $\nu$ be the eigenvector corresponding to
eigenvalue $0$ of the matrix $L_{1}$. Let $\nu\nu^{T}$ be $K$. Then the
connection matrix $M$ can be expressed as $(nI-K)$ where $n$ is the number of
agents in the network. Let $u^{B}$ be the strategy that is similar to the
$u^{A}$ except at link $(i,j)$ with a system matrix as $L_{2}$. At $(i,j)$,
$u^{A}_{ij}=0$ where as $u^{B}_{ij}=1$. Let $Q(t)$ be a doubly stochastic
matrix such that $Q(t)=e^{-L_{2}t}$, $t\geq$0\. We need to show that strategy
$u^{B}$ is better than $u^{A}$. The aim of the adversary is to maximize the
cost function. We can obtain the conditions for which the cost for $u^{A}$
greater than the cost for $u^{B}$.

$\displaystyle\int_{s}^{s+\Delta s}k(t)x(s)^{T}P(t-s)MP(t-s)x(s)dt$
$\displaystyle<\int_{s}^{t^{*}}k(t)x(s)^{T}P(t-s)MP(t-s)x(s)dt+\int_{t^{*}}^{s+\Delta
s}k(t)$ $\displaystyle
x(s)^{T}P(t^{*}-s)Q(t-t^{*})MQ(t-t^{*})P(t^{*}-s)x(s)dt.$ (30)

The cost of strategy corresponding to $u^{B}-u^{A}$ can be written as

$\begin{array}[]{l}\int_{s}^{s+\Delta
s}kx^{T}[P(t^{*}-s)Q(t-t^{*})MQ(t-t^{*})P(t^{*}-s)-\\\ P(t-s)MP(t-s)]xdt>0\\\
\end{array}$ $\int_{s}^{s+\Delta s}kx(s)^{T}\Lambda(t,t^{*})x(s)dt>0\ ,$ (31)

where $\Lambda=P(t^{*}-s)Q(t-t^{*})MQ(t-t^{*})P(t^{*}-s)-P(t-s)MP(t-s)$. As
$t$ decreases, $P(t)=I+tL_{1}+\mathcal{O}(t^{2})$ and
$Q(t)=I+tL_{2}+\mathcal{O}(t^{2})$. Substituting for $P(t),Q(t)$ and $M$, the
$\Lambda(t,t^{*})$ can be simplified as,

$\Lambda(t,t^{*})=-2n(t-t^{*})(L_{2}-L_{1})+\mathcal{O}(t^{2}).$ (32)

For sufficiently small $t$ and $t^{*}$, the first term is very much larger
than the second term, therefore it dominates. At the link $(i,j)$,
$L_{1_{ij}}>L_{2_{ij}}=0$, and at all the links $L_{1_{kl}}=L_{2_{kl}}$ where
$(k,l)\neq(i,j)$.

$\begin{array}[]{lll}h(t,x(s))&=&2n(t-t^{*})\times\\\
&&\sum_{l=1}^{n}\sum_{k=1}^{l-1}(L_{1kl}-L_{2kl})(x_{k}-\operatorname{sgn}(L_{ij})x_{l})^{2}\\\
&=&2n(t-t^{*})L_{1ij}(x_{i}-\operatorname{sgn}(L_{ij})x_{j})^{2}\end{array}$
(33)

In a bipartite consensus, the adversary can either break the link with a
positive weight or he can break the link with a negative weight. When the link
with a positive weight is attacked, (32) becomes
$h(t,x(t))=2n(t-t^{*})\lvert{a_{ij}}\rvert(x_{i}-x_{j})^{2}$ and if the link
with a negative weight is attacked, then
$h(t,x(t))=2n(t-t^{*})\lvert{a_{ij}}\rvert(x_{i}+x_{j})^{2}$. This is possible
only when the graph has multiple connected components and at least one link
exists between them. If the graph at time $s$ is a single connected component,
then the breaking of the link by the adversary to slow down the convergence is
not possible as the system has already reached bipartite consensus. This proof
provides an easy way of calculating optimal strategy and picturing the DoS
attack. In the cost $J(u)$, each term corresponds to the value of $w_{ij}$.
Therefore, it is inferred that the optimal strategy for the attacker to break
the bipartite consensus and thus increase or maximize the cost function is by
breaking the link with the highest value of $w_{ij}$. The attacker has
complete knowledge of the system and that he is able to disconnect a link for
the entire process. It will be interesting to see how the solution would
change if there was a constraint on the amount of time an attacker can break a
link.

##  IV SIMULATION RESULTS

We consider a structurally balanced graph with $n=4$ as shown in fig 2(a) for
illustration.

Figure 2: (a) Example of a four agent structurally balance graph with
cooperative and antagonistic interactions; (b) The graph under attack of the
adversary where the link $(3,4)$ was attacked and therefore the weight of that
particular link was changed to $0$.

Therefore, according to the theory discussed above, the Laplacian matrix
$L_{1}$ of the system can be written as,

$\displaystyle L_{1}=\left[\begin{array}[]{cccc}0.2&0.1&0&-0.1\\\
0.1&0.2&-0.1&0\\\ 0&-0.1&0.2&0.1\\\ -0.1&0&0.1&0.2\end{array}\right]$

The initial conditions are chosen randomly between any interval. Here, let the
initial conditions be $[-20,-5,25,10]^{T}$. This is the bipartite consensus
where the four agents formed two different clusters. Now the adversary acts
upon. In order for the adversary to give the best attack, he tries to attack
that link that has the highest $w_{ij}$ value. Now, the $w_{ij}$ value is
calculated for all the links. This value is found to be the highest for the
link $(3,4)$, with $w_{34}=122.5$. Therefore, the optimal strategy of the
adversary to slow the bipartite consensus is to break this link at that
particular time. Therefore, the $L_{1}$ matrix changes to a new matrix
$L_{2}$.

Figure 3: (a) Simulation result of the graph before and after the attack by
the adversary; (b) The cost of the bipartite consensus $(J)$ with and without
the attack

From fig 3(a), we can infer that before the presence of an adversary the four
agent network graph described in the illustration moves to bipartite
consensus. These converging values are only different in sign. The speed of
convergence can be adjusted by changing the weight of each link. After the
attack by the adversary at the link $(3,4)$, the bipartite consensus is
slowed. From the simulation results, it is clear that the agents $1$ and $2$
still moves to the said consensus point whereas the adversary fails the
bipartite consensus by breaking the link $(3,4)$. The agents $3$ and $4$
deviates from the original trajectory. From 3(b), it is clear that the cost of
the bipartite consensus $J(u)$ before the presence of the attack is nearly
zero but when the adversary acts upon the graph by breaking the link $(3,4)$,
the cost increases. The cost of bipartite consensus is thus maximized, slowing
down the bipartite consensus.

##  V CONCLUSION

When a set of agents interact with each other using both cooperative and
antagonistic interactions, and the interaction graph is structurally balanced,
the agents end up with a bipartite consensus. The effect of the denial of
service attack on a bipartite consensus problem was studied here. The optimal
plan of action that can be followed by an adversary at the time of the attack
on a structurally balanced multi-agent system was found out. It has been
demonstrated by MATLAB simulation results. The future work will explore the
case of having an attacker with incomplete knowledge and the additional
constraint on time.

## References

  * [1] W. Ren, R. W. Beard, and E. M. Atkins, “A survey of consensus problems in multi-agent coordination,” in _Proceedings of the 2005, American Control Conference, 2005._ IEEE, 2005, pp. 1859–1864.
  * [2] Y. Cao, W. Yu, W. Ren, and G. Chen, “An overview of recent progress in the study of distributed multi-agent coordination,” _IEEE Transactions on Industrial informatics_ , vol. 9, no. 1, pp. 427–438, 2012.
  * [3] F. Dörfler, M. Chertkov, and F. Bullo, “Synchronization in complex oscillator networks and smart grids,” _Proceedings of the National Academy of Sciences_ , vol. 110, no. 6, pp. 2005–2010, 2013.
  * [4] C. Altafini, “Consensus problems on networks with antagonistic interactions,” _IEEE Transactions on Automatic Control_ , vol. 58, no. 4, pp. 935–946, 2012\.
  * [5] ——, “Dynamics of opinion forming in structurally balanced social networks,” _PloS one_ , vol. 7, no. 6, p. e38135, 2012.
  * [6] A. Teixeira, I. Shames, H. Sandberg, and K. H. Johansson, “A secure control framework for resource-limited adversaries,” _Automatica_ , vol. 51, pp. 135–148, 2015.
  * [7] S. M. Dibaji, M. Pirani, D. B. Flamholz, A. M. Annaswamy, K. H. Johansson, and A. Chakrabortty, “A systems and control perspective of cps security,” _Annual Reviews in Control_ , vol. 47, pp. 394–411, 2019.
  * [8] S. Amin, A. A. Cárdenas, and S. S. Sastry, “Safe and secure networked control systems under denial-of-service attacks,” in _International Workshop on Hybrid Systems: Computation and Control_. Springer, 2009, pp. 31–45.
  * [9] F. Pasqualetti, F. Dorfler, and F. Bullo, “Control-theoretic methods for cyberphysical security: Geometric principles for optimal cross-layer resilient control systems,” _IEEE Control Systems Magazine_ , vol. 35, no. 1, pp. 110–127, 2015.
  * [10] A. Khanafer, B. Touri, and T. Başar, “Consensus in the presence of an adversary,” _IFAC Proceedings Volumes_ , vol. 45, no. 26, pp. 276–281, 2012\.
  * [11] ——, “Robust distributed averaging on networks with adversarial intervention,” in _52nd IEEE Conference on Decision and Control_. IEEE, 2013, pp. 7131–7136.
  * [12] D. S. Naidu, _Optimal control systems_. CRC press, 2002.