#  One-Shot Online Testing of Deep Neural Networks Based on Distribution Shift
Detection

Soyed Tuhin Ahmed, Mehdi B. Tahoori  Department of Computer Science, Karlsruhe
Institute of Technology (KIT)
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Neural networks (NNs) are capable of learning complex patterns and
relationships in data to make predictions with high accuracy, making them
useful for various tasks. However, NNs are both computation- and memory-
intensive methods, making them challenging for edge applications. To
accelerate the most common operations (matrix-vector multiplication) in NNs,
hardware accelerator architectures such as computation-in-memory (CiM) with
non-volatile memristive crossbars are utilized. Although they offer benefits
such as power efficiency, parallelism, and nonvolatility, they suffer from
various faults and variations, both during manufacturing and lifetime
operations. It can lead to faulty computations and, in turn, degradation of
post-mapping inference accuracy, which is unacceptable for many applications,
including safety-critical ones. Therefore, proper testing of NN hardware
accelerators is required. In this paper, we propose a _one-shot_ testing
approach that can test NNs accelerated on memristive crossbars with only one
test vector, making it very suitable for online testing applications. Our
approach has can can consistently achieve $100\%$ fault coverage consistently
across several large topologies and challenging tasks. Nevertheless, compared
to existing methods, the fault coverage is improved by up to $24\%$, the
memory overhead is only $0.0123$ MB, a reduction of up to $19980.48\times$
$19980\times$ and the number of test vectors is reduced by $10000\times$.
Consequently, the testing latency and energy are reduced linearly to the
number of test vectors.

###### Index Terms:

one-shot testing, single-shot testing, functional testing, Memristor

##  I Introduction

Deep learning algorithms have been the driving force behind substantial
advancements in various domains, such as computer vision, natural language
processing, and speech recognition. Recently, deep learning algorithms have
been increasingly deployed in safety- and security-critical domains such as
autonomous driving, medical imaging, and malware detection. At the heart of
deep learning systems are multi-layered neural networks (NNs) that learn
hierarchical representations from the training dataset and make actionable
predictions on inference data. Despite the algorithmic success of NNs, they
are computationally demanding, and their conventional hardware implementation
suffers from a memory bottleneck due to von Neumann architectures, where
memory and processing units are physically separated, leading to significant
data movement and energy consumption.

Therefore, several specialized architectures and hardware accelerators, such
as computation-in-memory (CiM) architectures [yu2018neuro], have been explored
to accelerate NNs in hardware. CiM leverages emerging non-volatile memory
(NVM) technologies, such as Resistive Random-Access Memory (ReRAM)
[akinaga2010resistive], Phase Change Memory (PCM) [wong2010phase], and Spin
Transfer Torque Magnetic Random Access Memory (STT-MRAM) [apalkov2013spin], to
perform computations directly in memory, mitigating the memory bottleneck.
Emerging NVM technologies offer benefits such as zero leakage power, non-
volatility, high switching speed, and endurance when compared to conventional
CMOS-based memories.

However, emerging NVM technologies exhibit several post-manufacturing and
online non-idealities, such as read disturb error [7035342], retention faults
[hofmann2014comprehensive], manufacturing variations, and online thermal
variations [niu2010impact]. These non-idealities can adversely impact the
online functionality of memristive chips for deep learning applications and
negatively impacts the prediction ability of the NNs [ahmed2022process].
Therefore, testing such hardware systems is crucial to ensuring their
reliability and correct functionality, especially in safety-critical
applications.

Figure 1: Flow diagram of our proposed one-shot testing approach. A KL-
divergence value greater than a predefined threshold indicates faults or
variation in the memristive NN.

Nevertheless, testing NN hardware accelerators present a unique set of
challenges due to the complexity, inherent non-linearity, and a large number
of layers and parameters. Unlike traditional hardware or software testing
approaches, NNs cannot be exhaustively tested with all possible input
combinations, as they can be millions, leading to high testing overhead. In
addition, due to specialized CiM-based NN hardware accelerators, they do not
contain conventional digital Design for Test (DfT) infrastructure such as scan
chains. A testing approach that does not require access to training data,
treats the NN as an intellectual property (IP), that is it does not require
access to the intermediate results or backdoors to the model (non-invasive)
but nevertheless can test the NN in a _one-shot_ is desired.

One-shot testing, which is the extreme form of test compaction, can test an NN
model and its hardware realization with a single test vector and forward pass.
It can minimize testing time, the computation required, and system downtime to
a minimum. Even memristor chip-specific testing approaches can lead to long
system downtime due to the large number of test vectors [ahmedETS23]. Longer
system downtime can be unacceptable for many applications, including ”always-
on” scenarios, e.g., real-time object detection and tracking, voice
assistants, anomaly detection, and predictive maintenance, particularly in
mission-critical applications.

In this paper, we propose a comprehensive _one-shot_ testing framework for
CiM-based memristive deep learning hardware accelerators that treat NNs as a
black box and do not require access to training datasets or intermediate
results. Our approach is capable of testing large-scale NNs with hundreds of
layers using a single testing vector, significantly reducing the number of
forward passes and computational overhead during testing. We evaluate our
approach on several large CNN topologies with up to $201$ layers and several
difficult tasks, e.g., ImageNet classification with $1000$ classes, and
semantic segmentation on real-world biomedical segmentation, and unsupervised
generative adversarial networks (GANs). Nevertheless, we were able to
consistently achieve $100\%$ test coverage of different fault types and fault
severeness.

The rest of the paper is organized as follows: Section II provides background
information on deep learning, NVM technologies, and their non-idealities.
Section III describes our proposed one-shot testing method in detail, Section
IV describes the fault injection framework, evaluates our approach, and
presents the results, and finally, Section V concludes the paper.

##  II Preliminaries

###  II-A Memristor Devices and Non-idealities

TABLE I: Notations used in this paper.

Symbol | Explanation | Symbol | Explanation
---|---|---|---
$t$ | Threshold for fault detection | $\hat{\mathcal{N}}$ | Output distribution of a memristive NN
$D_{\mathrm{KL}}(\hat{\mathcal{N}}\parallel\mathcal{N})$ | KL divergence between $\hat{\mathcal{N}}$ and $\mathcal{N}$ | $\mathcal{N}$ | Expected output distribution
$\mathbf{W}$ | Weight matrix | $\bar{x}$ | One-shot test vector
$\mathbf{b}$ | Bias vector | $\mathcal{L}$ | Loss function
$\hat{y}$ | Output of the Memristive NN | $\mathcal{F}$ | Pre-trained NN
$Q$ | Learning rate decay rate | $\alpha$ | Learning rate
$\nabla\mathcal{L}$ | Gradient from backpropagation | $\eta_{0}$ | Noise scale for variations
$\mathcal{P}_{flip}$ | Percentage of faults | $y^{\prime}$ | The ground truth for optimization
$\mathbf{z}$ | Intermediate activations | $\theta$ | Learable parameters of a NN
$\mu$ | Mean | $\sigma^{2}$ | Variance

Memristor technology including ReRAM [akinaga2010resistive], PCM
[wong2010phase], and STT-MRAM [apalkov2013spin] are two-terminal nanoscale
devices that are the basic building block of in-memory computing for the
acceleration of NNs. The number of stable states varies from technology, e.g.,
STT-MRAM can be programmed to Low Resistance State $LRS$/High Conductance
State $G_{off}$ or High Resistance State $HRS$/Low Conductance State $G_{on}$
but ReRAM can be programmed into multiple stable states [aziza2021multi].
Multilevel cells can also be designed using multiple STT-MRAM devices.

Despite their promising characteristics, due to a number of factors,
memristive devices exhibit a number of non-idealities [nair2020defect,
chen2014rram, le2020overview, nair2017vaet, bishnoi2014read, zhou2020noisy,
kim2020efficient] that can be broadly categorized as either permanent or soft
faults.

Permanent faults refer to those that irreversibly alter the conductance state
of memristor cells, preventing them from being programmed to the desired
resistance/conductance state for encoding NN parameters. Cells with permanent
faults cannot be restored to their original fault-free values.

On the contrary, soft faults refer to those that temporarily alter the
conductance state of memristor cells but can still cause deviations in NN
parameters. Faulty memristor cells can, however, be restored to their original
values.

Irrespective of the specific type of fault, it is possible for faults to arise
they occur during both the manufacturing process and in-field operation. As a
result, the model parameters and activations of NNs can deviate from their
expected values after their hardware mapping (post-mapping) due to
manufacturing faults and post-deployment (online) due to infield due to
runtime faults. In this section, common memristor device faults and their
corresponding fault models are discussed.

##### Stuck-at faults

Among all kinds of hard faults, stuck-at faults appear more frequently in
memristive crossbars. Suck-at faults are modelled as the memristor cell
conductance can become stuck at high conductance (stuck-at-$G_{on}$) or low
conductance (stuck-at-$G_{off}$). Depending on the occurrence factor, stuck-at
faults can be categorized as either soft faults or permanent faults. Stuck-at
faults caused by limited endurance from repeated reading are categorized as
soft faults, whereas the manufacturing defects that cause stuck-at faults are
categorized as permanent faults. In a memristive crossbar array, stuck-at
faults are randomly distributed and can be as high as 10% [chen2014rram].
Defects like stuck-open or short can also be modeled as stuck-at-$G_{off}$ and
stuck-at-$G_{on}$[nair2020defect, chen2014rram]. Consequently, the parameters
of the memristive NN implementation deviate from their initial values. The
parameter bit change, depending on encoding, can be represented as either
stuck-at-0 or stuck-at-1.

##### Manufacturing and In-field Variations

Device Variability occurs when the conductance of memristors exhibits
distribution rather than a fixed value due to factors such as manufacturing
process variations. In-field variations, on the other hand, emerge from the
dynamic changes in the memristor’s environment, including temperature or other
environmental factors, which can fluctuate the conductance. The effect of both
types of variations can cause variations in the current sum in the bit-line in
the crossbar and a reduction in the sensing margin, leading to incorrect
sensed values.

##### Read/write disturbance

Memristor reading (inference) and writing (parameter mapping) can both be
affected by read and write currents impacting other memristor cells sharing
the same bit-line in the crossbar array. Such faults can lead to unintentional
switching of memristor conductance states during read operations. Moreover,
write disturbance faults influence the data (NN parameters) stored in
memristor cells[chen2014rram, bishnoi2014read].

##### Slow-Write Fault

During NN parameter mapping, defective memristor cells might experience longer
write delays, referred to as slow-write faults. In ReRAM, slow-write faults
can emerge from repeated write operations. Switching in MTJ and PCM is
inherently stochastic, causing non-deterministic write delays even when the
environmental factors remain constant. A write failure can happen if the MTJ
does not switch within a specified time or the switching pulse is truncated
before the switching operation is completed [nair2017vaet, le2020overview].

###  II-B Neural Networks (NNs)

Neural Networks (NNs) are computational models inspired by the structure and
operation of biological neural networks. NNs comprised of multiple layers of
neurons organized into a single input, single output, and multiple hidden
layers. The input layer does not perform any computation, but only receives
the input data. However, the hidden layers compute intermediate activations
$\mathbf{z}$, and the output layer generates the final results $\mathbf{y}$.
The basic computation of a layer $l$ consists of the weighted sum of inputs
$\mathbf{x}$ and the element-wise addition of bias. Afterwards, a non-linear
activation function $\phi(\cdot)$ is applied. The overall mathematical
computation of the NNs is as follows:

$\displaystyle\mathbf{z}^{(0)}$ $\displaystyle=\mathbf{x},$ (1)
$\displaystyle\mathbf{z}^{(l)}$
$\displaystyle=\phi^{(l)}\left(\mathbf{W}^{(l)}\mathbf{h}^{(l-1)}+\mathbf{b}^{(l)}\right),\quad
l=1,2,\dots,L-1,$ (2) $\displaystyle\mathbf{\hat{y}}$
$\displaystyle=\bar{\phi}^{(L)}\left(\mathbf{W}^{(L)}\mathbf{h}^{(L-1)}+\mathbf{b}^{(L)}\right),$
(3)

where, $\mathbf{W}$, $L$, and $\bar{\phi}$ represents denotes the weight
matrix, the total number of layers, and the final transformation, e.g.,
SoftMax, respectively. SoftMax rescales the output values between 0 and 1.

NNs can be categorized based on their layer types and arrangements within the
network. One popular type is the Convolutional Neural Network (CNN), which
incorporates convolutional and linear layers. Another type is the Multi-layer
Perceptron (MLP), which solely uses linear layers. CNNs are particularly
powerful and are commonly applied in tasks that involve image, audio, and
video. Thus, our methodology is assessed using state-of-the-art (SOTA) CNN
architectures.

Normalization technique, such as batch normalization, is increasingly utilized
to enhance the convergence speed and stability of the learning process. Batch
normalization normalized the activations of each neuron during training prior
to the application of two learnable parameters $\beta$ and $\gamma$ that scale
and adjust the normalized activations as follows:

$\mathbf{\bar{z}}^{(l)}=\frac{\mathbf{W}^{(l)}\mathbf{x}^{(l-1)}+\mathbf{b}^{(l)}-\mathbf{\mu}^{(l)}}{\sqrt{\mathbf{\sigma}^{2(l)}+\epsilon}}\beta+\gamma,$
(4)

where, the batch mean and variance are denoted by $\mathbf{\mu}^{(l)}$ and
$\mathbf{\sigma}^{2(l)}$, respectively. Also, $\epsilon$ is a small constant
added for stability.

The NN training procedure consists of learning the parameters $\theta$
summarizing all the learnable parameters given the training dataset
$\mathcal{D}\subset(\mathbf{x},\mathbf{y})$ with $N$ training examples by
minimizing a task-specific loss function $\mathcal{L}$:

$\operatorname*{arg\,min}{\bm{\theta}}=\frac{1}{N}\sum_{i=1}^{N}\mathcal{L}_{\theta}(\mathbf{y}_{i},\mathbf{\hat{y}}_{i}).$
(5)

###  II-C Deep Learning Acceleration with Memristor-based Crossbars

Memristive devices can be arranged into crossbar arrays, with each cross point
consisting of a memristive device, as depicted in Figure 2. Therefore, the
weighted sum computation required for the inference stage of the NN can be
carried out directly in the memory by leveraging Ohm’s Law (V = IR) and
Kirchhoff’s Current Law at a constant $O(1)$ time without any data movement
between the processing element and the memory.

Figure 2: Mapping a layer of NN into a memristor-based crossbar array.

Due to the finite number of conductance states of memristors, the trained
parameters $\theta$ are first quantized to signed 8-bit precision using a
post-training quantization approach, with negligible performance penalties.
However, quantization-aware training should be performed for lower-bit
precision quantization.

Afterwards, the quantized parameters $\theta$ of the NN are mapped to the
memristor-based crossbar arrays with NVM technology-specific encoding. For
emerging NVM technology with two stable states, e.g., STT-MRAM, each bit of a
parameter is encoded as high $G_{off}$ or low conductance $G_{on}$. Therefore,
each cell in the crossbar array represents a single-bit ($0$ or $1$). For
multilevel NVM technology, e.g., ReRAM or PCM with 128 resistance states, the
sign can be represented with a single bit, $G_{off}$ (0) for positive,
$G_{on}$ (1) for negative and the magnitude (0 to 127) can be represented with
multi-level cells. A look-up table can be used to map the magnitudes to the
conductance values of the ReRAM cells.

The input vector $x$ is converted to continuous voltages and then streamed
into the word-lines of the crossbar array for inference. Multiple word-lines
of the crossbar are activated simultaneously for parallel computation, and the
current that flows into the bit-line of the crossbar represents the result of
the weighted sum operation. Ultimately, an Analog-to-Digital Converter (ADC)
circuit digitizes the sensed currents. After that, other computations in the
digital domain, e.g., bias addition, batch normalization, and non-linear
activation operations are undertaken. Note that, ADC circuits are also subject
to variations. However, we consider them to be robust to variations and do not
add any noise to the NN activation.

Note that popular CNN topologies use skip connections, which allow information
to bypass a few intermediate layers and add to the output of another layer. It
can be implemented in a memristive crossbar NN by routing output signals
through specific crossbars and adding the resulting outputs using digital
summing circuits. However, since the NN computations are done sequentially,
signals for the skip connections can be stored in the buffer memory.

###  II-D Related Works

In the literature, several testing approaches have been proposed for testing
memristor-based crossbar arrays. March-based algorithms serially program and
read the memristor cells under test to a specified conductance level to
identify faults [liu2016efficient]. However, March-based algorithms are not
practical for memristor-mapped NN applications due to their large number of
memory cells, which results in extended test times. Additionally, testing
multi-level cells requires setting the memristive cells to all possible
levels, further increasing test time.

An alternative approach for fault detection involves analyzing the deviation
in the inference accuracy of either original training data or synthetic
testing data in the presence of faults [chen2021line, li2019rramedy,
luo2019functional]. Synthetic testing data can be generated using adversarial
examples [li2019rramedy], watermarking the training data, and re-training the
NN on the testing data to create a backdoor [chen2021line]. Although such
methods efficiently detect deviations, they necessitate a large amount of
testing data, on-chip storage (depending on the availability of on-chip
retraining data), and an invasive test generation process. The performance of
backdooring when common data-augmentation data augmentation techniques, such
as corner padding and center-cropping, are used is unclear, since data-
augmentation data augmentation can either partially or completely remove the
watermarks. Additionally, watermarking relies on the translation invariance
feature of CNN to achieve high accuracy on the test dataset and similar
performance on the original task. However, since MLPs are not translation
invariant, this method may not be suitable for MLPs. The work in
[luo2019functional] proposed back-propagating to the input image and using the
gradient of the input image as standalone testing data or combining it with
training data as a perturbation, similar to [li2019rramedy] which employs the
fast gradient sign method (FGSM). However, their ”pause-and-test” method leads
to long periods of system downtime. The work presented in [9693118] proposes
monitoring the dynamic power consumption of crossbar arrays to detect faults.
To achieve this, an adder tree is implemented to continuously monitor the
dynamic power consumption, which adds hardware overhead.

A compact functional testing method has been studied in the work by
[ahmed2022compact]. Their method can achieve high testing coverage with a
sufficiently large number of testing vectors, typically ranging from 16 to 64.
However, it has been observed that their method does not work well when the
number of testing vectors is small, i.e., less than 10. Furthermore, their
method relies on access to the training dataset.

In contrast, our one-shot vector generation and testing method  a) do not
require access to training data,  b) is non-invasive,  c) generalizable across
different classes of NN,  d) requires only single testing queries,  e) needs
negligible storage, power, and testing time, and  f) can achieve high fault
coverage.

##  III One-shot Testing of Memristive NNs

###  III-A Motivation and hypothesis of our approach

As discussed earlier, in the presence of faults or variations in the
parameters of memristor-mapped NNs, their representation changes from the
expected (trained) parameters, resulting in degradation in their performance.
According to Equation 1, non-ideal parameters will directly affect the
weighted sum and in turn activation of a layer. Since , the activation of a
layer becomes the input to the following layer, the cascading effect of non-
ideal parameters is likely to ultimately flow to the overall output $\hat{y}$
of the NNs. Therefore, the distribution $y$ is also expected to change, as
shown in the Fig. 3(c).

Figure 3:  a) Change in output distribution depicted for different NN models
but on the same test vector, b) comparison of the change in the output
distribution for two different test vectors but on the same NN model
(ResNet-18). While the conventional method reveals a change in output
distribution across different models and test vectors, our approach ensures
standardized output distributions (distributions overlap) irrespective of
models or test vectors. c) We compared the relative change in output
distribution for the same noise level between the proposed and conventional
test vectors. The output distribution is more sensitive to noise for our
proposed one-shot test vector. In the conventional method, the test vectors
are randomly sampled from the ImageNet validation dataset.

Based on the observation and hypothesis that the distribution of $\hat{y}$ of
memristive NN is affected by faults and variations in its parameters, we
propose a one-shot testing _one-shot testing_ method that aims at detecting
distribution shifts at to detect distribution shifts in the model output with
using a single test vector. Our method specifically designs a test vector for
our purpose that can produce two distinct output distributions for faulty and
fault-free cases. Therefore, the faults and variations can be easily detected
by evaluating the output distribution of a memristive NN after applying the
one-shot test vector.

However, there are several challenges associated with this approach. We
discuss them in the following section with their respective solutions.

###  III-B Proposed deviation detection method

Since the expected distribution of a model is unknown and likely varies from
one model to another and from one test vector to another (as shown in the top
half of Fig 3(a) and (b)), it is difficult to estimate the change in
distribution for a pre-trained model. Therefore, we propose standardizing the
output distribution of each _model under test_ (MUT) and test vector to a unit
Gaussian distribution, $\hat{y}\sim\mathcal{N}(\mu\approx
0,\,\sigma^{2}\approx 1)\,$, which means zero mean $\mu\approx 0$ and unit
variance $\sigma^{2}\approx 1$. Without this standardization, the likelihood
of false-positive deviation detection is significantly increased.

Let $\hat{y}\sim\hat{\mathcal{N}}(\mu,\,\sigma^{2})\,$ be the output
distribution of a memristive NN model. Faults and variations in the parameters
of memristive NN NNs can be detected by evaluating the Kullback–Leibler (KL)
divergence between the expected output distribution $\mathcal{N}$ and the
output distribution of memristive NNs as:

$D_{\mathrm{KL}}(\hat{\mathcal{N}}\parallel\mathcal{N})=\sum_{i=1}^{n}\hat{\mathcal{N}}(i)\log\frac{\hat{\mathcal{N}}(i)}{\mathcal{N}(i)}$
(6)

which can be simplified for two normal distributions as:

$D_{\mathrm{KL}}(\hat{\mathcal{N}}\parallel\mathcal{N})=\log\frac{\sigma_{\mathcal{N}}}{\sigma_{\hat{\mathcal{N}}}}+\frac{\sigma_{\hat{\mathcal{N}}}^{2}+(\mu_{\hat{\mathcal{N}}}-\mu_{\mathcal{N}})^{2}}{2\sigma_{\mathcal{N}}^{2}}-\frac{1}{2}.$
(7)

We assumed that the distributions $\hat{\mathcal{N}}$ and $\mathcal{N}$ were
discrete, since we quantized the parameters of the memristive NN. Here, we
denote the mean and standard deviation of the output distribution
$\hat{\mathcal{N}}$ of the memristive NN $\hat{\mathcal{N}}$ as
$\mu_{\hat{\mathcal{N}}}$ and $\sigma_{\hat{\mathcal{N}}}$, respectively.
Similarly, $\mu_{\mathcal{N}}$ and $\sigma_{\mathcal{N}}$ represent the mean
and standard deviation of the expected output distribution $\mathcal{N}$.
Since $\mu_{\mathcal{N}}$ and $\sigma_{\mathcal{N}}$ are defined as 0 and 1,
respectively, the equation can be further simplified as:

$D_{\mathrm{KL}}(\hat{\mathcal{N}}\parallel\mathcal{N})=\log\frac{1}{\sigma_{\hat{\mathcal{N}}}}+\frac{\sigma_{\hat{\mathcal{N}}}^{2}+\mu_{\hat{\mathcal{N}}}^{2}}{2}-\frac{1}{2}.$
(8)

The KL divergence measures how one probability distribution differs from
another. A larger value of
$D_{\mathrm{KL}}(\hat{\mathcal{N}}\parallel\mathcal{N})$ indicates that the
output distribution of the memristive NN is different from the expected
distribution due to non-idealities in the parameters. Specifically, a
threshold $t$ can be defined, where
$D_{\mathrm{KL}}(\hat{\mathcal{N}}\parallel\mathcal{N})\geq t$ indicates non-
ideal parameters in the memristive NN. The specific choice of $t$ depends on
several factors, which will be discussed later. The overall flow diagram of
our one-shot testing approach is depicted in Fig. 1.

Please note that other distance functions, such as the Jensen-Shannon
divergence (which is a symmetrized version of the KL divergence), can also be
used. Alternatively, for simplicity, evaluating only the
$\mu_{\hat{\mathcal{N}}}$ and $\sigma_{\hat{\mathcal{N}}}$ values may be
sufficient for fault and variation detection.

The test vector (stored in the hardware) can be applied periodically during
online operation, and the deviation from the expected distribution can be used
as an indicator for faults and variation in the memristive NN. The overall
flow diagram of our one-shot testing approach is depicted in Fig. 1.

###  III-C Proposed test vector generation method

In order to make the proposed one-shot testing method possible, the
distribution of $\hat{y}$ should not only be standardized but also done with a
single test vector, i.e., _one-shot_. We generate a special test vector for
this purpose with a specific learning objective. However, there are several
challenges associated with this.

####  III-C1 Learning objective

Since our learning objective is to produce a standard Gaussian distribution of
$\hat{y}$, several loss functions can be designed to encourage the $\hat{y}$
distribution $\mathcal{N}$ to have a mean of $0$ and a standard deviation of
$1$. For example:

$\operatorname*{arg\,min}_{\mu_{\mathcal{N}}\rightarrow
0,\sigma_{\mathcal{N}}\rightarrow
1}\frac{1}{N}\sum_{i=1}^{N}\hat{y}_{i}\log\frac{\hat{y}_{i}}{y^{\prime}_{i}},$
(9)

minimizes pointwise KL-divergence loss between NN output $\hat{y}$ and ground
truth value $y^{\prime}$. Alternatively,

$\operatorname*{arg\,min}_{\mu_{\hat{\mathcal{N}}}\rightarrow
0,\sigma_{\hat{\mathcal{N}}}\rightarrow
1}(\mu_{\hat{\mathcal{N}}})^{2}+(1-\sigma_{\hat{\mathcal{N}}})^{2},$ (10)

encourages $\mu_{\hat{\mathcal{N}}}$ and $\sigma_{\hat{\mathcal{N}}}$ to be
close to 0, and 1, respectively. Regression losssuch as: , such as

$\operatorname*{arg\,min}_{\mu_{\hat{\mathcal{N}}}\rightarrow
0,\sigma_{\hat{\mathcal{N}}}\rightarrow
1}\frac{1}{N}\sum_{i=1}^{N}(\hat{y}_{i}-y^{\prime}_{i})^{2}),$ (11)

can also be used.

The ground truth $y^{\prime}$ for the training can be defined as :

$y^{\prime}=\frac{\hat{y}-\mu_{\hat{\mathcal{N}}}}{\sigma_{\hat{\mathcal{N}}}},$
(12)

or can be sampled from a unit Gaussian distribution. Our learning objective
can be considered supervised learning.

The proposed one-shot test vector produces a standardized output distribution
across different models and generated test vectors, as shown in the bottom
half of Fig. 3(a) and (b). Additionally, the relative deviation of the output
distribution for the one-shot test vector is significantly higher, as
demonstrated in Fig. 3(c). As a result, our one-shot test vector is
considerably more sensitive to non-ideal parameters.

####  III-C2 Initialization

Let $\bar{x}$ be the learnable one-shot testing vector with shape [H, W, C]
(assuming a colored image) that is optimized based on the loss function (6).
Here, H, W, and C denote height, width, and number of channels, respectively.
Initializing $\bar{x}$ properly is crucial for proper learning, where initial
values are assigned to each pixel of $\bar{x}$ before training. The
convergence speed and final loss value greatly depend on proper
initialization. Additionally, appropriate initialization is essential for
deeper networks, as the gradient is propagated all the way back to the input.

We initialize $\bar{x}$ element-wise with random values drawn from a unit
Gaussian distribution as follows:

$\bar{x}_{i\rightarrow H,j\rightarrow W,k\rightarrow C}\sim N(0,1)$ (13)

Here, i, j, and k are the indices of the elements in the input tensor.
Element-wise initialization enables fine-grained control over the
initialization process and is commonly used in deep learning.

Alternatively, initialization from out-of-distribution data, i.e. data that
does not belong to the training set, also works well. This means that stock
images from the internet can also be used for initialization. Therefore,
access to training data is still not necessary. Figure 4 shows some examples
of generated test vectors with their initial images. Our optimization
procedure makes minute adjustments to the stock photos. Therefore, they are
visually indistinguishable.

Figure 4: An example Some examples of the proposed one-shot test vector for
the DenseNet-121 topology. To the naked eye, optimized stock images appear
identical to their original images. Nevertheless, they differ marginally.

The overall algorithm for the proposed one-shot test vector generation is
summarized in the Algorithm 1. We propose to optimize To accelerate the
learning process, we propose optimizing the test vector with an exponential
learning rate decay of decay learning rate for every $Q$ iterationto
accelerate the learning process.

0: Pre-trained network $\mathcal{N}$$\mathcal{F}$, loss function
$\mathcal{L}(\hat{y},y^{\prime})$, initial
---
learning rate $\alpha_{0}$, number of iterations $K$, Decay rate
$Q$, and shape of the test vector $\bar{x}$ [H, W, C].

0: One-shot test vector $\bar{x}$

11: Initialize $\bar{x}$ element-wise with random values from a

unit Gaussian distribution

2: for $k=1\ldots K$ do

3: Perform forward pass through $\mathcal{N}$ $\mathcal{F}$ with input
$\bar{x}$ to obtain output $\hat{y}$

4: Compute loss $\mathcal{L}(\hat{y},y^{\prime})$

5: Calculate gradient $\nabla\mathcal{L}$ with respect to $\bar{x}$

6: Compute the current learning rate $\alpha_{t}$:
$\alpha_{t}=\begin{cases}\alpha_{0}&\text{if}\ t\bmod Q\neq 0\\\
\alpha_{t-1}/10&\text{if}\ t\bmod Q=0\end{cases}$

7: Update $\bar{x}$ using gradient descent with the current learning rate:
$\bar{x}\leftarrow\bar{x}-\alpha_{t}\nabla\mathcal{L}$

8: end for

Algorithm 1 One-shot Test Vector Generation test vector generation using
Gradient Descent gradient descent with Exponential Decaying Learning Ratean
exponential decaying learning rate

##  IV Simulation Results

###  IV-A Fault Modelling and Injection Framework

####  IV-A1 Modelling Conductance Variations

Memristive technology and external environmental conditions influence
conductance variation during online operations and in the manufacturing
process. In this paper, we employ the variation model proposed in
[ahmed2022compact] which considers both device-to-device manufacturing
variations (spatial fluctuation) and thermal variations (temporal
fluctuation). This model injects multiplicative and additive Gaussian noise
into the weight matrix of all layers as random noise, with a noise scale of
$\eta_{0}$ used to control the severity of the noise. For each fault run, a
different random sample is taken from the variation model.

####  IV-A2 Modelling Online and Manufacturing Faults

We consider two different kinds of fault models depending on the mapping
employed: bit-wise and level-wise. As mentioned in Section II, NN parameters
can be encoded bit-wise, with eight memristive cells representing a single
parameter. Our bit-wise fault model targets this kind of parameter encoding
and can be expressed as:

$W_{flip}=f(\mathcal{P}_{flip},W_{orig})$ (14)

Here, $\mathcal{P}_{flip}$ and $f(\cdot)$ represent the percentage of bit-flip
faults injected and the fault model function, respectively. Specifically, the
fault model $f(\cdot)$ randomly samples $\mathcal{P}_{flip}$% of the bits of
weights in each layer and flips their bits from $1$ to $0$ and vice versa.
However, for parameter mapping with multi-level memristive cells, the (level-
wise) fault model $f(\cdot)$ randomly sets the weights to a value between
$-127$ and $127$. The ultimate effect of permanent faults is flipping the
affected memristive cell from its desired level into another one. Therefore,
the fault model $f(\cdot)$ considers read/write disturbance as well as
permanent faults, including stuck-at faults.

###  IV-B Simulation Setup

In this paper, we have abstracted circuit-level details and evaluated our
proposed one-shot approach using PyTorch-based simulation. We target _hard-to-
detect_ deviations in memristive crossbars. As the name suggests, detecting
these kinds of deviations is hard, as they cause subtle changes in the output
distribution and, in turn, inference accuracy. On the contrary, we have found
that a large change in accuracy correlates to a large relative shift in the
output distribution and is easier to detect with our approach in comparison.

Furthermore, instead of a simpler dataset like MNIST, we evaluated our method
on larger pre-trained topologies, with up to 201 layers, trained on the more
challenging ImageNet dataset [deng2009imagenet], which is a large-scale image
recognition dataset with 1000 classes, approximately 13 million training data
points, and 50,000 validation data points. Additionally, we tested our
approach on popular semantic segmentation topologies trained on both real-
world brain MRI datasets and Microsoft’s COCO benchmark dataset
[buda2019association, lin2014microsoft]. Semantic segmentation is considerably
more challenging than image classification, since it involves assigning labels
to individual pixels in an image. Table II summarizes all the evaluated pre-
trained models, their accuracy, and the number of parameters. All the pre-
trained models are accessible through PyTorch Hub.

TABLE II: Showing the evaluated (pre-trained) models for classification and
semantic segmentation tasks, along with their respective information such as
inference accuracy, number of parameters, layers, and dataset used for
training.

Model | Classification
---|---
Inference Acc. | Parameters | Layers | Dataset
ResNet-18 [he2016deep] | 69.76% | 11.7$\times 10^{6}$ | 18 | Imagenet [deng2009imagenet]
ResNet-50 [he2016deep] | 76.13% | 25.6$\times 10^{6}$ | 50
ResNet-101 [he2016deep] | 81.89% | 44.5$\times 10^{6}$ | 101
DenseNet-121 [huang2017densely] | 74.43% | 8$\times 10^{6}$ | 121
DenseNet-201 [huang2017densely] | 76.89% | 20$\times 10^{6}$ | 201
MobileNet-V3 [sandler2018mobilenetv2] | 71.87% | 3.5$\times 10^{6}$ | 52
| Semantic Segmentation
| Pixelwise Acc. | Parameters | Layers | Dataset
U-Net [ronneberger2015u] | 93.2% | 11$\times 10^{6}$ | 23 | Brain MRI [buda2019association]
DeepLab-V3 [chen2017rethinking] | 91.2% | 13$\times 10^{6}$ | 60 | COCO [lin2014microsoft]

For the fault coverage analysis, we have done the Monte Carlo simulation to
simulate the effect of per-chip and online variations, as well as various
faults modeled as bit-flip. Specifically, $1000$ memristive crossbars
instances are evaluated for each noise level for variations and fault
percentages.

We report fault coverage as the ratio between detected faults
($D_{\mathrm{KL}}(\hat{\mathcal{N}}\parallel\mathcal{N})\geq t$) and overall
faults runs ($\mathcal{M}$) and can be described as

$\text{fault coverage}=\frac{\text{\\# of
}D_{\mathrm{KL}}(\hat{\mathcal{N}}\parallel\mathcal{N})\geq
t}{\mathcal{M}}\times 100.$ (15)

Note that, although we inject variation and faults into all parameters that
are mapped to memristive cells, our fault coverage does not necessarily imply
all possible faults that may occur.

###  IV-C Detecting Variations in a One-Shot

For classification tasks using the ImageNet dataset, Table III evaluates the
fault coverage achieved by a proposed one-shot method on multiplicative and
additive variations. The six state-of-the-art (SOTA) models consistently
achieve 100% $100\%$ fault coverage across various noise scales ($\eta_{0}$).
Our result results indicate the robustness of the one-shot method in adapting
to diverse levels of noise.

Similarly, for semantic segmentation tasks, as shown in Table IV, the proposed
one-shot method on multiplicative and additive variations with a range of
noise scales ($\eta_{0}$) consistently achieve achieves 100% fault coverage.
This further underscores the robustness of our one-shot method across
different tasks.

TABLE III: The fault coverage (%) achieved by the proposed one-shot method on
multiplicative and additive variations with different noise scales $\eta_{0}$.
All the model is trained on the ImageNet dataset.

Model | Multiplicative Variations | Additive Variations
---|---|---
$\eta_{0}=0.01$ | $\eta_{0}=0.02$ | $\eta_{0}=0.04$ | $\eta_{0}=0.06$ | $\eta_{0}=0.08$ | $\eta_{0}=0.10$ | $\eta_{0}=0.0001$ | $\eta_{0}=0.0002$ | $\eta_{0}=0.00025$ | $\eta_{0}=0.0003$ | $\eta_{0}=0.00035$
ResNet-18 | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100%
ResNet-50 | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100%
ResNet-101 | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100%
DenseNet-121 | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100%
DenseNet-201 | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100%
MovileNet-V2 | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100%

TABLE IV: Fault coverage of semantic segmentation models utilizing the
proposed one-shot testing method. The models are evaluated under
multiplicative and additive variations with different the noise scales
$eta_{0}$ $\eta_{0}$ to underscore the robustness of the models across
different scenarios.

Model | Additive Variations
---|---
$\eta_{0}=0.00002$ | $\eta_{0}=0.00004$ | $\eta_{0}=0.00006$ | $\eta_{0}=0.00008$ | $\eta_{0}=0.00010$ | $\eta_{0}=0.00012$
U-Net | 100% | 100% | 100% | 100% | 100% | 100%
| $\eta_{0}=0.02$ | $\eta_{0}=0.04$ | $\eta_{0}=0.06$ | $\eta_{0}=0.08$ | $\eta_{0}=0.1$ | $\eta_{0}=0.12$
DeepLab-V3 | 100% | 100% | 100% | 100% | 100% | 100%
| Multiplicative Variations
| $\eta_{0}=0.01$ | $\eta_{0}=0.02$ | $\eta_{0}=0.04$ | $\eta_{0}=0.06$ | $\eta_{0}=0.08$ | $\eta_{0}=0.08$
U-Net | 100% | 99.9% | 100% | 100% | 100% | 100%
| $\eta_{0}=0.01$ | $\eta_{0}=0.02$ | $\eta_{0}=0.04$ | $\eta_{0}=0.06$ | $\eta_{0}=0.08$ | $\eta_{0}=0.08$
DeepLab-V3 | 100% | 100% | 100% | 100% | 100% | 100%

###  IV-D Detecting Faults in a one-shotOne-Shot

For ImageNet classification on various SOTA topologies, Table VI demonstrates
a similarly high level of fault coverage under both bit-flip and level-flip
fault conditions. For each model, as the fault rate increases, the percentage
of fault coverage generally improves. At higher fault rates, such as 0.05% and
0.1%, most of the models achieved 100% fault coverage. At lower fault rates,
the shift in the output distribution is very low, resulting in a few false-
negative cases. However, by reducing the threshold to a value closer to the
KL-divergence value on a fault-free model, the number of false-negative cases
can be reduced (see Table IV-D). Nevertheless, our results indicate the
resilience of our one-shot approach to various types of faults at different
rates.

TABLE V: The effect of threshold $t$ on false-negative test cases. As the
threshold is reduced, the fault coverage increases.

Threshold | % of faults
---|---
$\eta_{0}=0.02$ | $\eta_{0}=0.025$ | $\eta_{0}=0.33$
$1x10^{-4}$ | 99.7% | 99.2% | 99.1%
$1x10^{-5}$ | 99.4% | 99.8% | 99.8%
$1x10^{-6}$ | 99.9% | 99.8% | 100%
$1x10^{-7}$ | 100% | 100% | 100%

Similarly, our proposed method can achieve a high fault-coverage on both bit-
flip and level-flip fault conditions for semantic segmentation tasks on two
state-of-the-art (SOTA) topologies, as demonstrated in Table VII. The trend in
fault-coverage percentage for each model is similar to that of the models used
for ImageNet classification. We also found that lowering the threshold can
have a similar effect on fault-coverage, as observed in the ImageNet
classification models.

TABLE VI: Evaluation of the fault coverage of SOTA ImageNet classification
models under different fault scenarios, including Bit-flip and Level-flip
faults, and varying fault rates.

Model | Bit-flip | Level-flip
---|---|---
% of faults | % of faults
0.02% | 0.025% | 0.033% | 0.05% | 0.1% | 0.02% | 0.025% | 0.033% | 0.05% | 0.1%
ResNet-18 | 98.6% | 99.3% | 99.6% | 100% | 100% | 99.9% | 99.9% | 100% | 100% | 100%
ResNet-50 | 99.6% | 99.9% | 100% | 99.9% | 100% | 100% | 100% | 100% | 100% | 100%
ResNet-101 | 98.9% | 99.6% | 99.5% | 99.9% | 100% | 99.7% | 100% | 100% | 100% | 100%
DenseNet-121 | 99.9% | 99.6% | 100% | 100% | 100% | 99.9% | 100% | 99.9% | 100% | 100%
DenseNet-201 | 99.1% | 99.7% | 99.8% | 100% | 100% | 99.1% | 100% | 100% | 100% | 100%
MobileNet-V2 | 99.8% | 99.8% | 100% | 100% | 100% | 99.4% | 99.8% | 99.8% | 100% | 100%

TABLE VII: Fault coverage performance of semantic segmentation models U-Net
and DeepLab-V3 under Bit-flip and Level-flip fault scenarios with varying
fault rates.

Model | Bit-flip | Level-flip
---|---|---
% of faults | % of faults
0.02% | 0.025% | 0.033% | 0.05% | 0.1% | 0.02% | 0.025% | 0.033% | 0.05% | 0.1%
U-Net | 100% | 100% | 100% | 100% | 100% | 99.9% | 99.9% | 100% | 100% | 100%
DeepLab-V3 | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100% | 100%

###  IV-E Comparison with State of the Art and Overhead Analysis

Our proposed method is compared against the related work that uses the
functional test generation method and focuses on test pattern compaction. With
only one test vector and test query, the proposed one-shot testing method
outperforms existing methods [chen2021line], [li2019rramedy],
[luo2019functional], and [ahmed2022compact] on all metrics listed in Table
VIII. Therefore, the proposed method requires significantly fewer test vectors
and queries compared to other methods. Furthermore, the proposed approach
consistently achieves 100% fault coverage, outperforming methods
[chen2021line, li2019rramedy, luo2019functional] which range from 76% to
99.27% coverage. Additionally, the proposed method is the most memory-
efficient, requiring only 0.012288 MB, which is much lower than the other
methods, regardless of whether re-training data is stored in hardware or not.
Moreover, our method does not rely on storing re-training data in hardware to
reduce memory consumption, unlike methods proposed by [chen2021line], and
[ahmed2022compact].

Latency, the number of matrix-vector operations, and power consumption for
testing directly correlate The test application time (latency) and test energy
are directly proportional to the number of test vectors used for testing. For
example, the testing method [li2019rramedy] requires $1024$ test vectors,
therefore, their method requires $1024\times$ more matrix-vector operations
and power consumption. We In our comparisons, we assume the hardware
implementation, NN topology, and NVM technology is are the same.

The analysis presented in Table VIII is based on the numbers reported in
related works. To calculate memory consumption, we utilized the bit-width
reported in [chen2021line] for the images and test labels. Note that our
approach does not require storing any labels.

TABLE VIII: Compares the proposed approach with the existing methods using
four performance metrics: fault coverage, memory storage overhead (with and
without re-training data), number of test queries required, and fault-
detection resolution. To ensure a fair comparison, the analysis of our
approach is conducted on the CIFAR-10 dataset.

| [chen2021line] | [li2019rramedy] | [luo2019functional] | [ahmed2022compact] | Proposed
---|---|---|---|---|---
Size of | 10000 | 1024 | ${10}$-${50}$ | $16$-$64$ | $\bm{1}$
test vectors
# of test queries | 10000 | 1024 | 10-50 | ${17}$ | $\bm{1}$
(normalized)
Memory |  0.0151 |  234.421 |  0.1541 |  ${0.000256}$1 |  $\bm{0.012288}$1
overhead (MB) |  245.7752 |  234.422 |  0.1542 |  ${0.1966}$2 |  $\bm{0.012288}$2
Coverage (%) |  99.273 |  983 |  763 / 844 |  ${100}$4 |  $\bm{100}$3

  * 1

Re-training data is stored in hardware.

  * 2

Re-training data is not stored in hardware.

  * 3

Synthetic testing data

  * 4

Original training data used as testing data

###  IV-F Discussion and Future Works

Our one-shot test method estimates the output distribution by calculating the
mean and standard deviation. Therefore, the output sample size is essential
and must be sufficiently large. If the sample size is small, the mean and
variance may be biased; for instance, outliers may have a disproportionate
effect on the calculation of the mean and variance. Other statistical methods,
such as Bayesian methods, can be investigated in this circumstance. However,
this is beyond the scope of this paper. Here, the shape of the output layer
represents the sample size, e.g., how many classes the output layer has for a
classification task.

##  V Conclusion

In this work, we have introduced a one-shot testing and respective test
generation method to test the hardware accelerators for deep learning models
based on memristor crossbars with a single test vector. Our method hypotheses
that memristive non-idealities correlate to change in output distribution, and
our testing method aims at detecting this distribution shift with a single
testing vector. The proposed approach demonstrates superior performance in
fault coverage, memory storage overhead, and the number of test queries
required, highlighting its effectiveness and efficiency compared to the
existing methods. Therefore, our work allows significantly faster detection of
faults and variations at a negligible overhead before.


# Event-triggered bipartite consensus for multiagent system with general
linear dynamics: an integral-type event triggered control

Nhan-Phu Chung, Thanh-Son Trinh, and Woocheol Choi  All authors were supported
by the National Research Foundation of Korea (NRF) grants funded by the Korea
government No. NRF- 2016R1A5A1008055. N.P. Chung was supported by the National
Research Foundation of Korea (NRF) grant funded by the Korea government No.
NRF-2019R1C1C1007107. W. Choi was supported by the National Research
Foundation of Korea(NRF) grant funded by the Korea government No. NRF-
2021R1F1A1059671. N. P. Chung, T. S. Trinh, and W. Choi are with the
Department of Mathematics, Sungkyunkwan University, Suwon 16419 (e-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>choiwc@skku.edu).

###### Abstract

In this paper, we propose an integral based event-triggering controller for
bipartite consensus of the multi-agent systems whose dynamics are described by
general linear system. We prove that the system achieves the bipartite
consensus in asymptotic regime and there is a positive minimum inter-event
time (MIET) between two consecutive triggering times of each agent. The proof
of the asymptotive stability involves a novel argument used to bound the norm
of the difference between the true state and its estimated state (for each
time) by an integration of its square. Numerical results are provided
supporting the effectiveness of the proposed controller.

###### Index Terms:

bipartite consensus, chattering and genuinely Zeno, integral-based event
triggered control, multi-agent systems with linear dynamics.

##  I Introduction

The coordinated control of multi-agent system (MASs) has recieved a lot of
interest in the last decades, thanks to its wide applications in various
fields containing engineering and computer science, biology, and social
sciences. In particular, distributed controls for the coordinates of multi-
agent systems (MASs) over graphs have been studied intensively by variety of
researchers [4, 1, 2, 5, 6, 3, 8, 7]. A fundamental problem in the coordinated
control of multi-agent system is the consensus problem which requires all
agents to asymptotically achieve a common quantity during their cooperative
interactions. The main task of the consensus problem in distributed multi-
agent systems is to design the control so that all agents will obtain
agreement using only interactions of neighbors.

In certain practical problems, some agents collaborate while others are in
another competitive group. These systems are represented by signed graphs and
the weight of each edge will be positive/negative if the two agents are
cooperative/competitive. The agents are said to exhibit a bipartite consensus
if they reach agreement in modulus but not in sign [4]. The distributed
Laplacian-like control schemes were developed in [4] for the bipartite
consensus of single-integrator agents, and extended to directed signed graph
[9, 10], general linear systems [12, 13, 11]. Also, the bipartite consensus
problems have been studied for general linear system with input-saturation
[14] and communication nosies [15].

Due to limitations of sources in the multi-agent systems, we can not assume
that agents have continuous access to others’ states. Therefore, agents in the
system should have strategy to take various actions in automatically schedules
instead of doing so continuously. As an effective solution for the scheduling,
event-triggered control designs have been developed for MASs. For event-
triggered control systems, controller updates are activated only when a
sutiably designed event-triggering condition is satisfied. The event-triggered
consensus problem of MASs is first studied by Dimarogonas, Frazzoli and
Johansson [16] and has been received tremendous attention after that. Numerous
distributed event-triggered consensus protocols were introduced for MASs of
first-order [17, 18, 19, 20], of second-order [21], and of linear dynamics
[22, 23].

The distributed control with event-triggered communications have been applied
to the bipartite consensus problem for the single-integrator agents [24, 8],
the double-integrator systems [25], the general linear systems [26, 27], and
the heterogeneous systems [28]. In addition, the distributed control with
event-triggered communications were studied in the context of the bipartite
consensus for the system with input time delay [29] and the prescribed-time
bipartite consensus problem [30].

There are two common issues in designing the event-triggered controls for the
consensus problems. One is to guarantee that the controlled system actually
achieves the consensus in asymptotic regime or in a prescribed time. The other
one is to find a lower bound for the difference between two consecutive
triggering times. The larger the lower bound is, the better the system is in
saving the energy for the communications. These two issues could be in
conflict with each other, and so it is important to design a balanced
controller satisfying both the two properties. In particular, it is a non-
trivial issue to prove that the controlled system has a positive minimum
inter-event time (MIET) between two consecutive triggering times while the
system achieves the consensus. The works [32, 33, 31] designed event-triggered
controllers which guarantee a positive MIET and the consensus is achieved up
to a small error.

The idea of integral-based event-triggering condition yielding larger inter-
event intervals was proposed by Mousavi, Ghodrat and Marquez [34]. Later, this
idea is applied to multi-agent systems in [35] and it has been investigated
further in [36, 37, 23, 38, 39]. In particular, Zhang, Lunze and Wang [38]
showed that the proposed controller system for the consensus problem has a
positive MIET and the consensus is achieved asymptotically without a small
error. This kind of idea was not yet applied to bipartite consensus for
general linear system. In this article, we propose a novel integral-based
event triggering condition for our MASs with linear dynamics for both the
bipartite consensus problem which admits the asymptotic bipartite consensus
and a positive MIET.

We mention that it is more difficult to prove the consensus for controls based
on integral based event-triggering than that based on the point-wise event-
triggering, since the Lyapunov stability analysis should be performed after a
time integration (see (8)) in order to use the triggering condition. In
addition, for applying Barbalat’s lemma [40, Lemma 8.2], one needs to obtain a
uniform bound for the difference $\|\hat{z}_{i}(t)-z_{i}(t)\|$ between the
true state and the estimated state. We achieve this uniform bound by combining
a bound on integration of $\|\hat{z}_{i}(t)-z_{i}(t)\|^{2}$ on an interval and
a regularity estimate based obtained in Lemma III.3.

One more subtle issue in the event-triggered controls is the chattering Zeno
problem, which means that $t_{k+1}^{i}=t_{k}^{i}$ where $t_{k}^{i}$ is the
$k$-th event-triggering instant of agent $i$ (see (4)). To avoid this issue,
we add an exponentially decaying term and show that it does not interrupt the
system to achieve the bipartitle asymptotic consensus. Our contributions are
summarized as follows.

Statement of contributions:

  1. 1.

We design an integral based event-triggered control for the bipartite
consensus of general linear multi-agent systems, which is motivated by the
control scheme proposed in [38] for consensus of MASs. We add an exponentially
decaying term in the triggering function in order to exclude the chattering
Zeno behavior. We remark that the previous works [42, 31, 22, 43, 41, 38, 23]
implicitly assumed the systems do not have chattering Zeno behavior to
establish the Zeno-freeness or the positive MIET of the systems.

  2. 2.

We show that the bipartite consensus is achieved with our proposed event-
triggered control. One essential step in proving the consensus using integral
based event-triggered control is the application of Barbalat’s lemma. This
step requires obtaining a uniform bound for the derivative $\dot{V}$ of the a
Lyapunov function $V$ used in the proof ([36, 37, 38, 23, 39]). We give a full
detail for obtaining the uniform boundedness of the derivative (Lemma III.4).

  3. 3.

We extend the work of [8] on Zeno-free analysis on event-triggered bipartite
consensus for single-integrator multiagent systems to general linear dynamics.
In addition to prove that the Zeno behavior is excluded, we obtain a uniform
lower bound for the inter-event intervals for any agent.

Our paper is organized as follows. In section II, we review our notations,
basic definitions and properties of graphs, and present our problem
formulation of bipartite event-triggered consensus of MASs with general linear
dynamics. Our main results will be presented in section III. In section IV, we
will illustrate the efficiency and feasibility of our results by a numerical
example. And in the last section, our conclusions are given.

##  II Preliminaries

###  II-A Notations

Let $\mathbb{R}$ be the set of all real numbers and $\mathbb{N}$ be the set of
all nonnegative integer numbers. We denote $|s|$ the absolute value of a
number $s\in\mathbb{R}$. The Euclidean norm of a vector $x\in\mathbb{R}^{n}$
is denoted by $\|x\|$. We denote $M_{m\times n}(\mathbb{R})$ the set of all
matrices of $m$ rows and $n$ columns with real valued entries, and when $m=n$
we write $M_{n}(\mathbb{R})$ instead. The transpose matrix of a matrix $M\in
M_{m\times n}(\mathbb{R})$ is denoted by $M^{T}$. Given $M\in M_{m\times
n}(\mathbb{R})$, we denote by $\|M\|$ its matrix operator norm. For every
$N\in\mathbb{N}$ we denote by $1_{N}$ the vector with $N$ columns and all
entries are one. The sign function is denoted by ${\rm sgn}(\cdot)$. If $A\in
M_{m\times n}(\mathbb{R})$ and $B\in M_{p\times q}(\mathbb{R})$ then $A\otimes
B\in M_{pm\times qn}(\mathbb{R})$ is the Kronecker product.

###  II-B Graphs

Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W})$ be a signed graph with
a set of vertices $\mathcal{V}=\\{1,\dots,N\\}$, an edge set
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ and an adjacency matrix
$\mathcal{W}\in M_{N}(\mathbb{R})$ of the signed weights of $\mathcal{G}$ with
$w_{ij}\neq 0$ if $(j,i)\in\mathcal{E}$ and $w_{ij}=0$ otherwise. We always
assume that the graph has no self-loops, i.e. $w_{ii}=0$ for every
$i\in\mathcal{V}$. The Laplacian matrix $L$ of $\mathcal{G}$ is defined by
$L=C-\mathcal{W}$, where $C={\rm
diag}\bigg{(}\sum_{j=1}^{N}|w_{1j}|,\sum_{j=1}^{N}|w_{2j}|,\cdots,\sum_{j=1}^{N}|w_{Nj}|\bigg{)}$.

A connected signed graph $\mathcal{G}$ is structurally balanced if there
exists a bipartition $\mathcal{V}_{1},\mathcal{V}_{2}$ of nodes such that
$w_{ij}\geq 0$ for $i,j\in\mathcal{V}_{k}$, $k\in\\{1,2\\}$, and $w_{ij}\leq
0$ for $i\in\mathcal{V}_{k},j\in\mathcal{V}_{l}$, $l\neq k$,
$l,k\in\\{1,2\\}$.

######  Definition II.1.

([44, Definition 6]) . For a connected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W})$ with the Laplacian matrix
$L$, the general algebraic connectivity is defined by

$\alpha(L)=\min_{y^{T}\xi=0,y\neq 0}\dfrac{y^{T}Ly}{y^{T}y}.$

Furthermore $\alpha(L)=\lambda_{2}(L)$, where $\lambda_{2}(L)$ is the smallest
positive eigenvalue of the Laplacian matrix $L$.

######  Lemma II.2.

([4, Lemma 1]) Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W})$ be a
connected, structurally balanced signed graph. Then there exists a matrix
$D={\rm diag}(\sigma_{1},\sigma_{2},\dots,\sigma_{N})$ such that entries of
$D\mathcal{W}D$ are all nonnegative, where $\sigma_{i}\in\\{1,-1\\}$ for
$i\in\mathcal{V}$.

###  II-C Problem formulation

Let $A\in M_{n}(\mathbb{R})$ and $B\in M_{n\times m}(\mathbb{R})$. Consider a
group of $N$ agents with linear dynamics under the graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},W)$.

$\displaystyle\dot{x}_{i}(t)=Ax_{i}(t)+Bu_{i}(t),\mbox{
}i\in\mathcal{V}=\\{1,\dots,N\\},$ (1)

where $x_{i}(t)\in\mathbb{R}^{n}$ and $u_{i}(t)\in\mathbb{R}^{m}$ are the
state and the control input of agent i, respectively. We assume that the
signed graph $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W})$ is
structurally balanced and connected.

Every agent $i$ activates a non-decreasing triggering sequence
$0=t^{i}_{0}\leq t_{1}^{i}\leq t^{i}_{2}\leq\dots$. For any state $x_{i}(t)$
of agent $i$, we define $\hat{x}_{i}(t):=e^{(t-t_{k}^{i})A}x_{i}(t_{k}^{i})$,
where $k:={\rm argmin}\\{t-t_{\ell}:t_{\ell}\leq t,\ell\in\mathbb{N}\\}$. We
define the error measurements $e_{i}(t):=\hat{x}_{i}(t)-x_{i}(t)$. We denote
$x(t)=[x_{1}^{T}(t),\dots,x_{N}^{T}(t)]^{T}$,
$\hat{x}(t)=[\hat{x}_{1}^{T}(t),\dots,\hat{x}_{N}^{T}(t)]^{T}$,
$e_{x}(t)=[e_{1}^{T}(t),\dots,e_{N}^{T}(t)]^{T}$.

The event-triggered consensus protocol is given as

$\displaystyle u_{i}(t)$
$\displaystyle=-K\sum_{j=1}^{N}|w_{ij}|(\hat{x}_{i}(t)-{\rm
sgn}(w_{ij})\hat{x}_{j}(t)),$ (2)

where $K$ is the control matrix which is designed later.

Using Kronecker product, we can write (1) as

$\dot{x}(t)=(I_{N}\otimes A-L\otimes BK)x(t)-(L\otimes BK)e_{x}(t).$

The system of agents is said to be bipartite consensus if
$\lim_{t\to\infty}\|\sigma_{i}x_{i}(t)-\sigma_{j}x_{j}(t)\|=0$ for every
$1\leq i,j\leq N$.

######  Definition II.3.

We say that an agent $i$ has Zeno behavior if there exists
$t_{\infty}\in\mathbb{R}$ such that
$\lim_{k\to\infty}t^{i}_{k}=\sum_{k=0}^{\infty}t_{k+1}^{i}-t^{i}_{k}=t_{\infty}$.
There are two different types of Zeno behavior [45] as follows. For an agent
$i$ which has Zeno behavior, agent $i$ has

  1. 1.

Chattering Zeno if there exists $M\in\mathbb{N}$ such that
$t^{i}_{k+1}=t^{i}_{k}$ for every $k\geq M$.

  2. 2.

Genuinely Zeno if $t^{i}_{k+1}-t^{i}_{k}>0$ for every $k\in\mathbb{N}$.

The system excludes Zeno behavior if all agents do not have Zeno behavior.

We need to find a triggering condition for each agent $i$ such that the system
achieves both bipartite consensus and Zeno-freeness.

##  III Main results

In this section, we will present an event-triggered design such that the
system (1) achieves bipartite consensus. Let us introduce some intermediate
variables.

We denote $z_{i}(t):=\sigma_{i}x_{i}(t)$,
$\hat{z}_{i}(t)=\sigma_{i}\hat{x}_{i}(t)$,
$e_{z,i}(t)=\hat{z}_{i}(t)-z_{i}(t)$,
$z(t)=[z_{1}^{T}(t),\dots,z_{N}^{T}(t)]^{T}$,
$\hat{z}(t)=[\hat{z}_{1}^{T}(t),\dots,\hat{z}_{N}^{T}(t)]^{T}$,
$e_{z}(t)=[e_{z,1}^{T}(t),\dots,e_{z,N}^{T}(t)]^{T}$.

We define a new Laplacian matrix $L_{D}:=DLD$, where $D$ is the matrix given
in Lemma II.2. Then from (II-C) we get

$\dot{z}(t)=(I_{N}\otimes A-L_{D}\otimes BK)z(t)-(L_{D}\otimes BK)e_{z}(t).$

Let $h:[0,\infty)\to(0,\infty)$ be a continuous function satisfying that
$\int_{0}^{\infty}h(s)ds=1$, for example choosing $h(t)=\alpha^{-t}$ for some
$\alpha>1$. We define the triggering functions as

$\displaystyle f_{i}^{k}(t):=\int_{t_{k}^{i}}^{t}g_{i}(s)ds,$ (3)

where
$g_{i}(s)=\|e_{z,i}(s)\|^{2}-\beta_{i}\|\sum_{j=1}^{N}|w_{ij}|(\hat{z}_{i}(s)-\hat{z}_{j}(s))\|^{2}-\beta_{i}h(s)$
and $\beta_{i}$ are constants which will be determined later.

The triggering instants for agent $i$ are defined by

$\displaystyle t^{i}_{k+1}:=\inf\\{t>t^{i}_{k}:f^{k}_{i}(t)>0\\}.$ (4)

To our knowledge, the following lemma is the first result in literature of
proving the freeness of chattering Zeno for multiagent systems without adding
a minimum positive MIET for triggering instants.

######  Lemma III.1.

For every $i\in\\{1,\ldots,N\\}$ and $k\in\mathbb{N}$ we have
$t^{i}_{k+1}>t^{i}_{k}$.

###### Proof.

For $t\geq t^{i}_{k}$ we define $g(t):=\|e_{z,i}(t)\|^{2}-\beta_{i}h(t).$ Then
$g(t^{i}_{k})=-\beta_{i}h(t^{i}_{k})<0.$ As the continuity of $g$ we get that
there exists $\varepsilon>0$ such that for every
$t\in[t^{i}_{k},t^{i}_{k}+\varepsilon]$ one has
$g(t)\leq-\frac{1}{2}\beta_{i}h(t^{i}_{k}).$ Hence, for every
$t\in[t^{i}_{k},t^{i}_{k}+\varepsilon]$ we get that

$\displaystyle f^{k}_{i}(t)$ $\displaystyle=\int_{t^{i}_{k}}^{t}g_{i}(s)ds$
$\displaystyle\leq\int^{t}_{t^{i}_{k}}g(s)ds$
$\displaystyle\leq-\frac{1}{2}\beta_{i}h(t^{i}_{k})(t-t^{i}_{k}).$

This yields,
$f^{k}_{i}(t^{i}_{k}+\varepsilon)\leq-\frac{1}{2}\beta_{i}h(t^{i}_{k})\varepsilon<0.$
By the definition of $t^{i}_{k+1}$, we obtain that $t^{i}_{k+1}>t^{i}_{k}$. ∎

Now we provide some standard assumptions on the matrices $A,B$ and the signed
graph $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W})$.

######  Assumption III.1.

The pair $(A,B)$ stabilizable, i.e there exists $K_{1}\in M_{n}(\mathbb{R})$
such that all eigenvalues of $A+K_{1}B$ has strictly negative real part. We
also assume that the graph $\mathcal{G}$ is structurally balanced and
connected.

As $(A,B)$ is stabilizable, applying [46, Theorem 9.5], there exists a
positive matrix $P\in M_{n}(\mathbb{R})$ and $\kappa>0$ such that

$\displaystyle A^{T}P+PA-\alpha(L)PBB^{T}P<-\kappa I_{n}.$ (5)

We choose the control matrix $K:=B^{T}P$ in (2). We define
$\bar{z}(t):=\dfrac{1}{N}\sum_{i=1}^{N}z_{i}(t)$. Then
$\dot{\bar{z}}(t)=A\bar{z}(t)$. To show this, we observe that

$\begin{split}\dot{z}_{i}(t)&=\sigma_{i}\dot{x}_{i}(t)\\\
&=\sigma_{i}Ax_{i}(t)+\sigma_{i}Bu_{i}(t)\\\
&=Az_{i}(t)-\sigma_{i}BK\sum_{j=1}^{N}|w_{ij}|(\hat{x}_{i}(t)-\textrm{sgn}(w_{ij})\hat{x}_{j}(t))\\\
&=Az_{i}(t)-BK\sum_{j=1}^{N}|w_{ij}|(\hat{z}_{i}(t)-\hat{z}_{j}(t)).\end{split}$

Summing up this for $1\leq i\leq N$ we find $\dot{\bar{z}}(t)=A\bar{z}(t)$.

Next we note that the difference $e_{i}(t)=\hat{x}_{i}(t)-x_{i}(t)$ satisfies

$\dot{e}_{i}(t)=A(\hat{x}_{i}(t)-x_{i}(t))-Bu_{i}(t)=Ae_{i}(t)-Bu_{i}(t).$

Since $e_{z,i}(t)=\sigma_{i}e_{i}(t)$ we have

$\begin{split}\dot{e}_{z,i}(t)&=\sigma_{i}\dot{e}_{i}(t)\\\
&=\sigma_{i}(Ae_{i}(t)-Bu_{i}(t))\\\
&=Ae_{z,i}(t)-\sigma_{i}Bu_{i}(t).\end{split}$ (6)

We also note that

$\begin{split}u_{i}(t)&=-K\sum_{j=1}^{N}|w_{ij}|(\sigma_{i}\hat{z}_{i}(t)-\sigma_{i}\hat{z}_{j}(t))\\\
&=-K\sigma_{i}\sum_{j=1}^{N}|w_{ij}|(\hat{z}_{i}(t)-\hat{z}_{j}(t)).\end{split}$

Inserting this to (6) we find

$\dot{e}_{z,i}(t)=Ae_{z,i}(t)+K\sum_{j=1}^{N}|w_{ij}|(\hat{z}_{i}(t)-\hat{z}_{j}(t)).$
(7)

We set $\delta_{i}(t)=z_{i}(t)-\bar{z}(t)$ and
$\delta(t)=[\delta_{1}(t)^{T},\cdots,\delta_{N}(t)^{T}]^{T}$. Also we define
the Lyapunov function $V(t):=\delta^{T}(t)(I_{N}\otimes P)\delta(t)$.

######  Lemma III.2.

Let $c>0$ such that $\beta:=\kappa-c\|L_{D}\otimes PBB^{T}P\|^{2}>0.$ Put
$\beta_{max}:=\max\\{\beta_{1},\dots,\beta_{N}\\}$. Assume that
$\beta_{max}<\min\bigg{\\{}\dfrac{1}{2\|L_{D}\|^{2}},\dfrac{\beta
c}{2\|L_{D}\|^{2}(\beta c+1)}\bigg{\\}}$. Then for every $t\geq 0$ we get that

$\displaystyle V(t)-V(0)$
$\displaystyle\leq-\beta\int_{0}^{t}\|\delta(s)\|^{2}ds+\dfrac{1}{c}\int_{0}^{t}\|e_{z}(s)\|^{2}ds$
$\displaystyle=-c_{1}\int_{0}^{t}\|\delta(s)\|^{2}ds+c_{2},$

where
$c_{1}=\beta-\dfrac{2\beta_{max}\|L_{D}\|^{2}}{c(1-2\beta_{max}\|L_{D}\|^{2})}>0$
and $c_{2}=\dfrac{N\beta_{max}}{c(1-2\beta_{max}\|L_{D}\|^{2})}$.

###### Proof.

We have

$\displaystyle\dot{V}(t)$ $\displaystyle=$
$\displaystyle\delta^{T}(t)(I_{N}\otimes A^{T}-L_{D}\otimes
K^{T}B^{T})(I_{N}\otimes P)\delta(t)$ $\displaystyle-e^{T}(t)(L_{D}\otimes
K^{T}B^{T})(I_{N}\otimes P)\delta(t)$
$\displaystyle+\delta^{T}(t)(I_{N}\otimes P)[(I_{N}\otimes A-L\otimes
BK)\delta(t)-(L_{D}\otimes BK)e_{z}(t)]$ $\displaystyle=$
$\displaystyle\delta^{T}(t)[I_{N}\otimes(A^{T}P+PA)]\delta(t)-2\delta^{T}(t)(L_{D}\otimes
PBB^{T}P)\delta(t)$ $\displaystyle-2\delta^{T}(t)(L_{D}\otimes
PBB^{T}P)e_{z}(t).$

From Definition II.1 we get that

$\displaystyle\delta^{T}(t)(L_{D}\otimes
PBB^{T}P)\delta(t)\geq\alpha(L_{D})\delta^{T}(t)(I_{N}\otimes
PBB^{T}P)\delta(t).$

Therefore

$\displaystyle\dot{V}(t)\leq$
$\displaystyle\delta^{T}(t)[I_{N}\otimes(A^{T}P+PA-\alpha(L)PBB^{T}P)]\delta(t)$
$\displaystyle-2\delta^{T}(t)(L_{D}\otimes PBB^{T}P)e_{z}(t)$
$\displaystyle\leq$ $\displaystyle-\delta^{T}(t)(I_{N}\otimes\kappa
I_{n})\delta(t)-2\delta^{T}(t)(L_{D}\otimes PBB^{T}P)e_{z}(t)$
$\displaystyle\leq$
$\displaystyle-\kappa\delta^{T}(t)\delta(t)-2\delta^{T}(t)(L_{D}\otimes
PBB^{T}P)e_{z}(t).$

On the other hand,

$\displaystyle-2\delta^{T}(t)(L_{D}\otimes PBB^{T}P)e_{z}(t)$
$\displaystyle\leq c\delta^{T}(t)(L_{D}\otimes
PBB^{T}P)[\delta^{T}(t)(L_{D}\otimes
PBB^{T}P)]^{T}+\dfrac{\|e_{z}(t)\|^{2}}{c}$ $\displaystyle\leq c\|L_{D}\otimes
PBB^{T}P\|^{2}\delta^{T}(t)\delta(t)+\dfrac{\|e_{z}(t)\|^{2}}{c}.$

Hence

$\displaystyle\dot{V}(t)\leq-\beta\|\delta(t)\|^{2}+\dfrac{\|e_{z}(t)\|^{2}}{c}.$

Therefore

$\displaystyle V(t)-V(0)$
$\displaystyle\leq-\beta\int_{0}^{t}\|\delta(s)\|^{2}ds+\dfrac{1}{c}\int_{0}^{t}\|e_{z}(s)\|^{2}ds.$
(8)

From the event triggered conditions (3) and (4), for every $i=1,\dots,N$,
$k\in\mathbb{N}$ and $t\in[t_{k},t_{k+1})$ we get

$\displaystyle\int_{t^{i}_{k}}^{t}\|e_{z,i}(s)\|^{2}ds$ $\displaystyle\leq$
$\displaystyle\beta_{i}\int_{t^{i}_{k}}^{t}\|\sum_{j=1}^{N}w_{ij}(\hat{z}_{i}(s)-\hat{z}_{j}(s)\|^{2}ds+\beta_{i}\int_{t^{i}_{k}}^{t}h(s)ds$
$\displaystyle=$
$\displaystyle\beta_{i}\int_{t^{i}_{k}}^{t}\|\sum_{j=1}^{N}w_{ij}(z_{i}(s)-z_{j}(s)+e_{z,i}(s)-e_{z,j}(s)\|^{2}ds$
$\displaystyle+\beta_{i}\int_{t^{i}_{k}}^{t}h(s)ds.$

Hence for every $t\geq 0$ we have

$\displaystyle\int_{0}^{t}\|e_{z,i}(s)\|^{2}ds$ $\displaystyle\leq$
$\displaystyle\beta_{i}\int_{0}^{t}\|\sum_{j=1}^{N}w_{ij}(z_{i}(s)-z_{j}(s)+e_{z,i}(s)-e_{z,j}(s)\|^{2}ds$
$\displaystyle+\beta_{i}\int_{0}^{t}h(s)ds$ $\displaystyle\leq$
$\displaystyle\beta_{i}\int_{0}^{t}\|\sum_{j=1}^{N}w_{ij}(z_{i}(s)-z_{j}(s)+e_{z,i}(s)-e_{z,j}(s)\|^{2}ds+\beta_{i}.$

Let $L_{D,i}$ be the ith row of $L_{D}$ then for every $t\geq 0$ we get

$\displaystyle\int_{0}^{t}\|e_{z,i}(s)\|^{2}ds$ $\displaystyle\leq
2\beta_{i}\int_{0}^{t}(\|(L_{D,i}\otimes I_{n})z(s)\|^{2}$ $\displaystyle+$
$\displaystyle\|(L_{i}\otimes I_{n})e_{z}(s)\|^{2})ds+\beta_{i}.$

Therefore we obtain

$\displaystyle\int_{0}^{t}\|e_{z}(s)\|^{2}ds$ $\displaystyle\leq$
$\displaystyle 2\beta_{max}\int_{0}^{t}(\|(L_{D}\otimes
I_{n})z(s)\|^{2}+\|(L_{D}\otimes I_{n})e_{z}(s)\|^{2})ds$
$\displaystyle+N\beta_{max}.$

As $(L_{D}\otimes I_{n})\delta(t)=(L_{D}\otimes I_{n})z(t)$, combining with
$\beta_{max}<\dfrac{1}{2\|L_{D}\|^{2}}$ we obtain

$\displaystyle\int_{0}^{t}\|e_{z}(s)\|^{2}ds$
$\displaystyle\leq\dfrac{2\beta_{max}\|L_{D}\|^{2}}{1-2\beta_{max}\|L_{D}\|^{2}}\int_{0}^{t}\|\delta(s)\|^{2}ds$
(9) $\displaystyle+$
$\displaystyle\frac{N\beta_{max}}{1-2\beta_{max}\|L_{D}\|^{2}}.$ (10)

Combining (8) with (10) we get that

$\displaystyle V(t)-V(0)\leq$
$\displaystyle-\beta\int_{0}^{t}\|\delta(s)\|^{2}ds+\frac{N\beta_{max}}{c(1-2\beta_{max}\|L_{D}\|^{2})}$
$\displaystyle+\dfrac{2\beta_{max}\|L_{D}\|^{2}}{c(1-2\beta_{max}\|L_{D}\|^{2})}\int_{0}^{t}\|\delta(s)\|^{2}ds$
$\displaystyle=$ $\displaystyle-c_{1}\int_{0}^{t}\|\delta(s)\|^{2}ds+c_{2}.$

∎

######  Lemma III.3.

Suppose that $\dot{y}(t)=Ay(t)$ for $t\geq t_{k}^{i}$. Then we have

$\|y(T)\|_{2}^{2}\leq\|y(t_{k}^{i})\|_{2}^{2}+2\|A\|\int_{t_{k}^{i}}^{T}\|y(t)\|_{2}^{2}dt$

for all $T\geq t_{k}^{i}$, where
$\|A\|:=\max_{v\in\mathbb{R}^{n}\setminus\\{0\\}}\frac{\|Av\|}{\|v\|}$.

###### Proof.

We find

$\begin{split}\frac{d}{dt}\|y(t)\|^{2}&=2\langle
y^{\prime}(t),~{}y(t)\rangle\\\ &=2\langle Ay(t),~{}y(t)\rangle\\\ &\leq
2\|A\|\|y(t)\|^{2}.\end{split}$

Integrating this inequality over $[t_{k}^{i},T]$ we obtain

$\int_{t_{k}^{i}}^{T}\frac{d}{dt}\|y(t)\|^{2}dt\leq\int_{t_{k}^{i}}^{T}2\|A\|\|y(t)\|^{2}dt.$

This completes the proof. ∎

######  Lemma III.4.

For every $i$ the function $\|\hat{z}_{i}(t)-z_{i}(t)\|$ is uniformly bounded
for $t\geq 0$.

###### Proof.

From Lemma III.2 there exists $M>0$ such that $\|z_{i}(t)-\bar{z}(t)\|\leq M$
for every $t>0$ and every $i=1,\dots,N$. Therefore to prove
$\|\hat{z}_{i}(t)-z_{i}(t)\|$ is bounded, it suffices to show that
$\|\hat{z}_{i}(t)-\bar{z}(t)\|$ is bounded.

Since $P$ is a positive define matrix, so is $I_{N}\otimes P$. Hence,
$V(t)=\delta^{T}(t)(I_{N}\otimes P)\delta(t)\geq 0$. Therefore, from Lemma
III.2 we get that

$\displaystyle\int_{0}^{t}\|\delta(s)\|^{2}ds\leq\frac{V(0)+c_{2}}{c_{1}}.$
(11)

Since (11) and (10), for every $i\in\\{1,\ldots,N\\}$, we obtain that

$\displaystyle\int_{0}^{t}\|e_{z,i}(s)\|^{2}ds\leq\int_{0}^{t}\|e_{z}(s)\|^{2}ds\leq
c_{3},$ (12)

where
$c_{3}:=(2\beta_{\max}\|L_{D}\|^{2}(V(0)+c_{2}))/(c_{1}(1-2\beta_{\max}\|L_{D}\|^{2}))+c_{2}$.

Furthermore, for every $t\geq 0$ we have that

$\displaystyle\int_{0}^{t}\|\hat{z}_{i}(s)-\overline{z}(s)\|^{2}$
$\displaystyle\leq
2\int_{0}^{t}\|\hat{z}_{i}(s)-z_{i}(s)\|^{2}ds+2\int_{0}^{t}\|z_{i}(s)-\overline{z}(s)\|^{2}ds$
$\displaystyle=2\int_{0}^{t}\|e_{z,i}(s)\|^{2}ds+2\int_{0}^{t}\|\delta_{i}(s)\|^{2}ds.$

From (11) and (12) for every $t\geq 0$, we obtain that

$\displaystyle\int_{0}^{t}\|\hat{z}_{i}(s)-\overline{z}(s)\|^{2}\leq
2\left(c_{3}+\frac{V(0)+c_{2}}{c_{1}}\right).$ (13)

Assume that $\|\hat{z}_{i}(t)-\overline{z}(t)\|$ is not bounded. Then there
exists $M_{1}>M^{2}+4\|A\|(c_{3}+(V(0)+c_{2})/c_{1})$ such that
$\|\hat{z}_{i}(T)-\overline{z}(T)\|>M_{1}$ for some
$T\in[t^{i}_{k},t^{i}_{k+1})$. Next, we define
$y(t):=\hat{z}_{i}(t)-\overline{z}(t)$. Then $\dot{y}(t)=Ay(t)$. Therefore, by
Lemma III.3 and (13)

$\displaystyle M_{1}$ $\displaystyle<\|\hat{z}_{i}(T)-\overline{z}(T)\|^{2}$
$\displaystyle\leq\|\hat{z}_{i}(t^{i}_{k})-\overline{z}(t^{i}_{k})\|^{2}+2\|A\|\int_{t^{i}_{k}}^{T}\|\hat{z}_{i}(t)-\overline{z}(t)\|^{2}dt$
$\displaystyle=\|z_{i}(t^{i}_{k})-\overline{z}(t^{i}_{k})\|^{2}+2\|A\|\int_{t^{i}_{k}}^{T}\|\hat{z}_{i}(t)-\overline{z}(t)\|^{2}dt$
$\displaystyle\leq M^{2}+4\|A\|\left(c_{3}+\frac{V(0)+c_{2}}{c_{1}}\right)$
$\displaystyle<M_{1}.$

This is a contradiction. Hence, we get that $\|e_{z,i}(t)\|$ is bounded for
every $i=1,\ldots,N$. ∎

######  Theorem III.5.

Let a multi-agent system as (1) such that the pair $(A,B)$ is stabilizable,
and the graph $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W})$ is connected
and structurally balanced. Let $P\in M_{n}(\mathbb{R})$ be a positive matrix
being a solution of (5). We consider the event-triggered consensus protocol as
(2) with the control matrix $K:=B^{T}P$. The event triggered times are
determined by (3) and (4). Then the system achieves consensus. Furthermore,
the multi-agent system has a positive minimum inter-event time, i.e. there
exists $\tau>0$ such that $t^{i}_{k+1}-t^{i}_{k}\geq\tau$ for every
$i=1,\dots,N$, $k\in\mathbb{N}$.

###### Proof.

As $P$ is a positive matrix so is $I_{N}\otimes P$. Therefore $V(t)\geq 0$ for
every $t$. Hence from Lemma III.2 we get that
$\int_{0}^{t}\|\delta(s)\|^{2}ds\leq\dfrac{V(0)}{c_{1}}$ and therefore
$\lim_{t\to\infty}\int_{0}^{t}\|\delta(s)\|^{2}ds$ is finite. Let $\kappa_{1}$
be the smallest eigenvalue of $I_{N}\otimes P$. Then $V(0)\geq
V(t)=\delta^{T}(t)(I_{N}\otimes
P)\delta(t)\geq\kappa_{1}\delta^{T}(t)\delta(t)$. Hence $\delta(t)$ is
bounded. On the other hand, as

$\displaystyle\dot{\delta(t)}=(I_{N}\otimes A-L_{D}\otimes
BK)\delta(t)-(L_{D}\otimes BK)e_{z}(t),$

applying Lemma III.4 we get that $\dot{\delta}(t)$ is also bounded. Applying
Barbalat’s lemma [40, Lemma 8.2], we get that $\lim_{t\to\infty}\delta(t)=0$
and hence $\lim_{t\to\infty}\|z_{i}(t)-z_{j}(t)\|=0$ for every $i,j$.

Now we prove that the system has positive minimum inter-event time. We note
that

$\begin{split}\frac{d}{dt}\|e_{z,i}(t)\|^{2}=&2\langle
e_{z,i}(t),~{}\dot{e}_{z,i}(t)\rangle\\\
\leq&2\|e_{z,i}(t)\|\|\dot{e}_{z,i}(t)\|\\\
\leq&2\|BK\|\|e_{z,i}(t)\|\Big{\|}\sum_{j=1}^{N}w_{ij}(\hat{z}_{i}(t)-\hat{z}_{j}(t))\Big{\|}\\\
&+2\|A\|\|e_{z,i}(t)\|^{2}\\\
\leq&\Big{\|}\sum_{j=1}^{N}w_{ij}(\hat{z}_{i}(t)-\hat{z}_{j}(t))\Big{\|}^{2}\\\
&+(2\|A\|+\|BK\|^{2})\|e_{z,i}(t)\|^{2},\end{split}$

where we used (7) in the second inequality. We then have

$\begin{split}\|e_{z,i}(t)\|^{2}&\leq\int_{t_{k}^{i}}^{t}e^{(2\|A\|+\|BK\|^{2})(t-s)}\Big{\|}\sum_{j=1}^{N}w_{ij}(\hat{z}_{i}(s)-\hat{z}_{j}(s))\Big{\|}^{2}ds\\\
&\leq
e^{(2\|A\|+\|BK\|^{2})(t-t_{k}^{i})}\int_{t_{k}^{i}}^{t}\Big{\|}\sum_{j=1}^{N}w_{ij}(\hat{z}_{i}(s)-\hat{z}_{j}(s))\Big{\|}^{2}ds.\end{split}$

We rewrite the above inequality by

$\|e_{z,i}(s)\|^{2}\leq
e^{(2\|A\|+\|BK\|^{2})(s-t_{k}^{i})}\int_{t_{k}^{i}}^{s}\Big{\|}\sum_{j=1}^{N}w_{ij}(\hat{z}_{i}(r)-\hat{z}_{j}(r))\Big{\|}^{2}dr.$

Integrating this, we find

$\begin{split}&\int_{t_{k}^{i}}^{t}\|e_{z,i}(s)\|^{2}ds\\\
&\leq\int_{t_{k}^{i}}^{t}e^{(2\|A\|+\|BK\|^{2})(s-t_{k}^{i})}\int_{t_{k}^{i}}^{s}\Big{\|}\sum_{j=1}^{N}w_{ij}(\hat{z}_{i}(r)-\hat{z}_{j}(r))\Big{\|}^{2}drds\\\
&\leq\int_{t_{k}^{i}}^{t}e^{(2\|A\|+\|BK\|^{2})(s-t_{k}^{i})}\int_{t_{k}^{i}}^{t}\Big{\|}\sum_{j=1}^{N}w_{ij}(\hat{z}_{i}(r)-\hat{z}_{j}(r))\Big{\|}^{2}drds\\\
&=\Big{(}\int_{t_{k}^{i}}^{t}e^{(2\|A\|+\|BK\|^{2})(s-t_{k}^{i})}ds\Big{)}\int_{t_{k}^{i}}^{t}\Big{\|}\sum_{j=1}^{N}w_{ij}(\hat{z}_{i}(r)-\hat{z}_{j}(r))\Big{\|}^{2}dr.\end{split}$

From this and the triggering condition, we see that

$\int_{t_{k}^{i}}^{t_{k+1}^{i}}e^{(2\|A\|+\|BK\|^{2})(s-t_{k}^{i})}ds\geq\beta_{i}.$

The proof is done. ∎

##  IV Simulations

In this section, we present a numerical simulation of the bipartite consensus
with event-triggered communication given by (4). We consider six agents and
take the graph $L$ defined in [8] as

$L=\begin{pmatrix}3&-1&2&0&0&0\\\ -1&5&4&0&0&0\\\ 2&4&8&-2&0&0\\\
0&0&-2&6&-1&-3\\\ 0&0&0&-1&1&0\\\ 0&0&0&-3&0&3\end{pmatrix}$

We take $A$ and $B$ in [14] given as

$A=\begin{pmatrix}0&1\\\ -1&0\end{pmatrix}\quad B=\begin{pmatrix}0&1\\\
1&1\end{pmatrix}.$

The matrix $P$ satisfying (5) is computed as

$P=5\times\begin{pmatrix}0.9862&0.0143\\\ 0.0143&0.9212\end{pmatrix}.$

The initial coordinates of agent $1$ and agent $2$ are selected randomly by a
uniform distribution of interval $[0,1]$ while those of other agents are
selected randomly by a uniform distribution of interval $[-1,0]$. We set the
constant $\beta_{k}=0.008$ for $1\leq k\leq 6$.

Figure 1: First coordinates of all agents Figure 2: Second coordinates of all
agents

In Figures 1 and 2 we see that agent 1 and agent 2 converge to a same
trajectory and the other agents converge to another same trajectory. For each
$1\leq k$ we let $I_{ev}(k)$ be the minimum interval between two successive
event-triggering times of agent $k$. The values of $I_{ev}(k)$ are given in
Table I.

Figure 3: Event-triggering instants

Figure 3 indicates the event-triggering times of each agent. The interval
lengths between two successive event-triggering times of each agent are given
in Figures 4 and 5. The ranges of $y$-axis in the diagrams are fixed by
$[0,5*I_{ev}(k)]$ for each agent $1\leq k\leq 6$.

TABLE I: Minimun interval between triggering times k | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---
$I_{ev}(k)\,(s)$ | 0.031 | 0.037 | 0.022 | 0.025 | 0.031 | 0.036
Figure 4: Inter-event times of agents 1-3 Figure 5: Inter-event times of
agents 4-6

##  V Conclusion

In this work, we designed an integral based event-triggered controller for
bipartite consensus of the general linear system. We rigorously proved that
the bipartite consensus is achieved and there is a positive MIET for the
controlled system. The numerical simulation was provided supporting the
theoretical results.

## References

  * [1] Y. Cao, W. Yu, W. Ren and G. Chen, ”An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination,” in IEEE Transactions on Industrial Informatics, vol. 9, no. 1, pp. 427-438, Feb. 2013.
  * [2] S. Knorn, Z. Chen and R. H. Middleton, ”Overview: Collective Control of Multiagent Systems,” in IEEE Transactions on Control of Network Systems, vol. 3, no. 4, pp. 334-347, Dec. 2016.
  * [3] J. Qin, Q. Ma, Y. Shi and L. Wang, ”Recent Advances in Consensus of Multi-Agent Systems: A Brief Survey,” in IEEE Transactions on Industrial Electronics, vol. 64, no. 6, pp. 4972-4983, June 2017.
  * [4] Altafini, Claudio, “Consensus problems on networks with antagonistic interactions,” IEEE Transactions on Automatic Control, Vol 58, No 4, 2013.
  * [5] R. Olfati-Saber and R. M. Murray, ”Consensus problems in networks of agents with switching topology and time-delays,” in IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1520-1533, Sept. 2004.
  * [6] J. Qin, H. Gao and C. Yu, ”On Discrete-Time Convergence for General Linear Multi-Agent Systems Under Dynamic Topology,” in IEEE Transactions on Automatic Control, vol. 59, no. 4, pp. 1054-1059, April 2014.
  * [7] H. Zhang, G. Feng, H. Yan and Q. Chen, ”Observer-Based Output Feedback Event-Triggered Control for Consensus of Multi-Agent Systems,” in IEEE Transactions on Industrial Electronics, vol. 61, no. 9, pp. 4885-4894, Sept. 2014.
  * [8] H. Yu, X. Chen, T. Chen and F. Hao, “Event-triggered bipartite consensus for multiagent systems: A Zeno-free analysis”, IEEE Transactions on Automatic Control, Vol 65, No 11, 2020.
  * [9] J. Hu and W. X. Zheng, ”Bipartite consensus for multi-agent systems on directed signed networks,” 52nd IEEE Conference on Decision and Control, 2013, pp. 3451-3456.
  * [10] D. Meng, M. Du and Y. Jia, ”Interval Bipartite Consensus of Networked Agents Associated With Signed Digraphs”, in IEEE Transactions on Automatic Control, vol. 61, no. 12, pp. 3755-3770, Dec. 2016.
  * [11] M. E. Valcher and P. Misra, ”On the consensus and bipartite consensus in high-order multi-agent dynamical systems with antagonistic interactions”, Systems $\&$ Control Letters Volume 66, April 2014, Pages 94-103.
  * [12] H. Zhang and J. Chen, “Bipartite consensus of general linear multi-agent systems,” in Proc. Amer. Control Conf., Portland, OR, USA, Jun. 2014, pp. 808–-812.
  * [13] H. Zhang, “Output feedback bipartite consensus and consensus of linear multi-agent systems,” in Proc. 54th IEEE Conf. Decis. Control, Osaka, Japan, Dec. 2015, pp. 1731–-1735.
  * [14] J. Qin, W. Fu, W. X. Zheng and H. Gao, ”On the Bipartite Consensus for Generic Linear Multiagent Systems With Input Saturation,” in IEEE Transactions on Cybernetics, vol. 47, no. 8, pp. 1948-1958, Aug. 2017.
  * [15] J. Hu, Y. Wu, T. Li, and B. Ghosh, “Consensus control of general linear multi-agent systems with antagonistic interactions and communication noises,” IEEE Transactions on Automatic Control, vol. 64, no. 5, pp. 2122-2127, May 2019.
  * [16] D. V. Dimarogonas, E. Frazzoli and K. H. Johansson, ”Distributed Event-Triggered Control for Multi-Agent Systems,” in IEEE Transactions on Automatic Control, vol. 57, no. 5, pp. 1291-1297, May 2012.
  * [17] G. S. Seyboth, D. V. Dimarogonas, K. H. Johansson, ”Event-based broadcasting for multi-agent average consensus,” in Automatica Volume 49, Issue 1, January 2013, Pages 245-252.
  * [18] Z. Sun, N. Huang, B. D. O. Anderson and Z. Duan, ”Event-Based Multiagent Consensus Control: Zeno-Free Triggering via $\mathcal{L}^{p}$ Signals,” in IEEE Transactions on Cybernetics, vol. 50, no. 1, pp. 284-296, Jan. 2020.
  * [19] Y. Wu, X. Meng, L. Xie, R. Lu, H. Su, Z-G. Wu, ”An input-based triggering approach to leader-following problems”, Automatica Volume 75, January 2017, Pages 221-228.
  * [20] X. Yi, T. Yang, J. Wu and K. H. Johansson, ”Distributed event-triggered control for global consensus of multi-agent systems with input saturation”, Automatica Volume 100, February 2019, Pages 1-9.
  * [21] H. Li, X. Liao, T. Huang and W. Zhu, ”Event-Triggering Sampling Based Leader-Following Consensus in Second-Order Multi-Agent Systems,” in IEEE Transactions on Automatic Control, vol. 60, no. 7, pp. 1998-2003, July 2015.
  * [22] W. Hu, L. Liu and G. Feng, ”Consensus of Linear Multi-Agent Systems by Distributed Event-Triggered Strategy,” in IEEE Transactions on Cybernetics, vol. 46, no. 1, pp. 148-157, Jan. 2016.
  * [23] W. Zhu, Z. Jiang, G. Feng, “Event-based consensus of multi-agent systems with general linear models,” Automatica Volume 50, Issue 2, February 2014, Pages 552-558.
  * [24] J. Li, X. Chen, F. Hao, and J. Xie, “Event-triggered bipartite consensus for multi-agent systems with antagonistic interactions,” International Journal of Control, Automation and Systems, vol. 17, no. 8, pp. 2046-2058, July 2019.
  * [25] J. Ren, Q. Song, and G. Lu, “Event-triggered bipartite leader-following consensus of second-order nonlinear multi-agent systems under signed digraph,” Journal of the Franklin Institute, vol. 356, no. 12, pp. 6591-6609, August 2019\.
  * [26] Y. Cai, H. Zhang, J. Duan, and J. Zhang, “Distributed bipartite consensus of linear multiagent systems based on event-triggered output feedback control scheme,” IEEE Trans. Syst., Man, Cybern., Syst., early access, Jan. 27, 2020, doi: 10.1109/TSMC.2020.2964394.
  * [27] J. Zang, X. Chen, F. Hao, “Observer based Event-triggered Bipartite Consensus of Linear Multi-agent systems,” International Journal of Control, Automation and Systems volume 19, pages 1291–1301 (2021).
  * [28] X. Wang, K. Liu, Z. Ji, and S. Han, “Bipartite consensus of heterogeneous multiagent systems based on distributed event-triggered control,” Complexity, vol. 2020, pp. 1–14, Mar. 2020.
  * [29] Y. Cai, H. Zhang, J. Zhang, and Q. He, “Distributed bipartite leader-following consensus of linear multiagent systems with input time delay based on eventtriggered transmission mechanism,” ISA Transactions, November 2019.
  * [30] X. Chen, H. Yu, and F. Hao, “Prescribed-time event-triggered bipartite consensus of multiagent systems,” IEEE Trans. Cybern., early access, Jul. 17, 2020, doi: 10.1109/TCYB.2020.3004572.
  * [31] E. Garcia, Y. Cao, D. W. Casbeer, “Decentralized event-triggered consensus with general linear dynamics,” Automatica Volume 50, Issue 10, October 2014, Pages 2633-2640.
  * [32] Y. Cheng, V. Ugrinovskii, “Event-triggered leader-following tracking control for multivariable multi-agent systems,” Automatica, 70, 204-210 (2016).
  * [33] O. Demir, J. Lunze, “Synchronization of multi-agent systems with event-based communication,” at-Automatisierungstechnik, 62(8), 535-546 (2014).
  * [34] S. H. Mousavi, M. Ghodrat, and H. J. Marquez, “Integral-based event-triggered control scheme for a general class of non-linear systems,” Control Theory $\&$ Applications, 13(9), 1982-1988, 2015.
  * [35] M. Ghodrat and H. J. Marquez, “An integral based event triggered control scheme of distributed network systems,” 2015 European Control Conference (ECC), 2015, pp. 1724-1729.
  * [36] Y. Ma, J. Zhao, “Distributed integral-based event-triggered scheme for cooperative output regulation of switched multi-agent systems,” Information Sciences 457-458 (2018), 208-221.
  * [37] X. Wu, X. Mu, “Observer-based leaderless and leader-following consensus for multiagent systems: A modified integral-type event-triggered design,” Volume 30, Issue 9, June 2020, Pages 3753-3772.
  * [38] Z. Zhang, J. Lunze and L. Wang, “Integral-based event-triggered control for multi-agent systems with general linear dynamics,” International Journal of Control, 93:5, 1005-1014, 2020.
  * [39] Z. Zhang and L. Wang, “Distributed integral-type event-triggered synchronization of multiagent systems,” Volume 28, Issue 14,September 2018, Pages 4175-4187.
  * [40] Khalil, Nonlinear systems (3rd edition). Upper Saddle River, New Jersey, Prentice Hall, 2002.
  * [41] D. Yang, W. Ren, X. Liu, W. Chen, “Decentralized event-triggered consensus for linear multi-agent systems under general directed graphs,” Automatica Volume 69, July 2016, Pages 242-249.
  * [42] B. Cheng and Z. Li, “Fully Distributed Event-Triggered Protocols for Linear Multiagent Networks,” in IEEE Transactions on Automatic Control, vol. 64, no. 4, pp. 1655-1662, April 2019.
  * [43] Z. Li, G. Wen, Z. Duan and W. Ren, ”Designing Fully Distributed Consensus Protocols for Linear Multi-Agent Systems With Directed Graphs,” in IEEE Transactions on Automatic Control, vol. 60, no. 4, pp. 1152-1157, April 2015.
  * [44] W. Yu, G. Chen, M. Cao and J. Kurths, ”Second-Order Consensus for Multiagent Systems With Directed Topologies and Nonlinear Dynamics,” in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 40, no. 3, pp. 881-891, June 2010.
  * [45] A. D. Ames and S. Sastry, “Characterization of Zeno behavior in hybrid systems using homological methods,” Proceedings of the 2005, American Control Conference, 2005., 2005, pp. 1160-1165 vol. 2.
  * [46] J. Zabczyk,  Mathematical control theory—an introduction, 2nd edition. Birkhäuser/Springer, Cham 2020.