# ViR: the Vision Reservoir

Xian Wei ∗, Bin Wang 1, Mingsong Chen 2, Ji Yuan 3, Hai Lan 4, Jiehuang Shi 5,
Xuan Tang 6, Bo Jin 7, Guozhang Chen 8, Dongping Yang 9
<EMAIL_ADDRESS><EMAIL_ADDRESS>1<EMAIL_ADDRESS>2,
<EMAIL_ADDRESS>3,
<EMAIL_ADDRESS>4<EMAIL_ADDRESS>5<EMAIL_ADDRESS>6,
<EMAIL_ADDRESS>7<EMAIL_ADDRESS>8<EMAIL_ADDRESS>9 Corresponding
Author

###### Abstract

The most recent year has witnessed the success of applying the Vision
Transformer (ViT) for image classification. However, there are still evidences
indicating that ViT often suffers following two aspects, i) the high
computation and the memory burden from applying the multiple Transformer
layers for pre-training on a large-scale dataset, ii) the over-fitting when
training on small datasets from scratch. To address these problems, a novel
method, namely, Vision Reservoir computing (ViR), is proposed here for image
classification, as a parallel to ViT. By splitting each image into a sequence
of tokens with a fixed length, the ViR constructs a pure reservoir with a
nearly fully connected topology to replace the Transformer module in ViT. Two
kinds of deep ViR models are subsequently proposed to enhance the network
performance. Comparative experiments between the ViR and the ViT are carried
out on several image classification benchmarks. Without any pre-training
process, the ViR outperforms the ViT in terms of both model and computational
complexity. Specifically, the number of parameters of the ViR is about 15%
even 5% of the ViT, and the memory footprint is about $20\%\sim 40\%$ of the
ViT. The superiority of the ViR performance is explained by Small-World
characteristics, Lyapunov exponents, and memory capacity.

##  1 Introduction

Recently, Vision Transformer (ViT) [11] has been demonstrated remarkable
performance across various vision tasks, such as image classification [50],
instance segmentation [57], object detection and tracking [7], with the
potential to replace the convolutional neural networks (CNNs) [24].

While the convolutions in a CNN excel on extracting local features of an
image, the ViT is based on the self-attention mechanism that can directly
compute global relationships among pixels in various small sections of the
image (e.g., $15\times 16$ patches) [29, 6, 10, 24]. Furthermore, compared to
CNNs, the ViT assumes minimal prior knowledge about the task at hand, while
its performance surpasses CNNs on large-scale datasets with pre-training and
fine-tuning, and only requires substantially fewer computational resources to
train [11]. Its superiority attracts researches to further propose many
variants, e.g., DeiT, T2T ViT, PVT [50, 60, 56], to handle various downstream
tasks.

Figure 1: Comparisons of the time consumption by performing the ViR and the
ViT on the CIFAR100 dataset. The initial accuracy and the final accuracy of
the ViR are higher than the ViT without pre-training. The deep ViR is the
parallel structure. With the same depth, the time cost of the ViR is much less
than the ViT.

However, pre-training on a large-scale dataset and fine-tuning to downstream
tasks are essential for the ViT, which often lead to the exhaustive and
redundant computation, and the memory burden by extra parameters.Additionally,
the ViT with multiple Transformer encoder layers often suffers the over-
fitting especially when the training data is limited [8].

In essence, by treating the image patches as the temporal sequence, the core
innovation of the ViT is to use a kernel connection operation, e.g., a dot
product, to obtain the internal dependencies among image patches, e.g., the
spatial and temporal (sequential) coherence between different portions of an
image [9, 7, 24].

Figure 2: Model overview. We first split an input image into patches with a
proper size, and then flatten each of them into a series of sequence vectors,
as the temporal input of the ViR. To have a better performance, the ViR core
contains a residual block and could be stacked into a deep structure.

This motivates us to consider a brain-inspired network, i.e., Reservoir
Computing (RC) [32], which incorporates intrinsic spatio-temporal dynamics,
with much lower consumption on computation and memory, fewer training
parameters, and much fewer training samples [18, 34].

The main body of RC is a dynamical system, called reservoir [37], which
consists of randomly interacting non-linear neurons and fixed weights. The
non-linearity and disordered connections give rise to the complex internal
dynamics of RC. Such complex dynamics are speculated to be able to facilitate
information processing, with the most benefit at the so-called ’edge of chaos’
[28]. The intrinsic dynamics project inputs to the high-dimensional
representation space, facilitating the following regression or classification
tasks. While the recurrent connections in a reservoir are randomly generated
and fixed, readout weights are optimized according to the task at hand.
Therefore, RC is a powerful and physically efficient tool in time series
related tasks, in terms of the low training cost, fast training speed, few
parameters, suitability for hardware, and linear training schemes.

Inspired by the excellent performance of RC on time series tasks, we propose a
reservoir mechanism-based model, namely, Vision Reservoir computing (ViR), to
replace the ViT for image tasks. The ViR follows a similar basic pipeline with
the ViT and the whole network is shown in Fig. 2. Without pre-training, the
results of the ViR are close to or even better than the ViT on small-scale
datasets, but with much fewer parameters and faster training speed, when
having the same network depth. Usually, the ViR can achieve considerable
performance with layers fewer than the number of encoders of the ViT (Fig. 1).

The main contributions of this work can be summarized into three aspects: i)
As a parallel to ViT, we propose a novel model with more efficiency, namely
ViR, for image classification. ii) We design a nearly fully connected topology
of the internal reservoir, with small-world characteristics, chaotic dynamics,
and great memory capacity. Series ViR and parallel ViR are both developed,
with the latter achieving better performance. iii) ViR achieves superior
performance on small-scale benchmarks than ViT, e.g., with about 15% even 5%
the number of parameters of the ViT, and $20\%\sim 40\%$ the memory footprint
of the ViT.

##  2 Related Works

RC, mainly composed of Echo State Networks (ESNs) [18, 21] and Liquid State
Machines (LSMs) [34], has been successively applied on speech recognition
[47], time series prediction [2], MIMO-OFDM [36], smart grids [14], etc.
Physical RC [48] such as photonic RC [52] is amenable to hardware
implementation using a variety of physical systems, substrates, and devices.
However, few work have so far studied the behavior of such networks on
computer vision.

One of the related experiments has been carried out to classify digits of the
MNIST dataset using a normal ESN [43], which shows that RC can handle image
data. More applications corresponding to images with RC are detailed in [25,
22, 26]. Combining RC with other popular algorithms such as CNNs or
Reinforcement Learning (RL) is a valid approach to enhance the performance of
networks for image tasks. Tong and Tanaka [49] took full advantage of an
untrained CNN to transform raw image data into a set of small feature maps as
a preprocessing step of RC and achieved a high classification accuracy with a
much smaller number of trainable parameters compared with Schaetti’s work.
Then, a novel practical approach, called RL with a convolutional reservoir
computing (RCRC) model [5] was proposed. A fixed random-weight CNN, used for
extracting image feature maps, combined with an RC model, employed for
extracting the time series features, is adopted for the evolution strategy of
RL, which succeeded in decreasing computational cost to a large degree.
However, such studies remain restricted because they simply treat RC as an
auxiliary tool but not the core for image tasks.

Based on the above issues, we propose an RC-based model specifically for image
tasks, by exploring the internal topology of the reservoir. The proposed
topology is originated from the Simple Cycle Reservoir (SCR), shown in [40],
which performs close to the traditional ESN. Later on, the updated one-Cycle
Reservoirs with Regular Jumps (CRJ) [41] has been proposed based on SCR, which
obtains superior performances in most time-series tasks.

Recently, Verzelli et al. [55] made the best of the controllability matrix to
explain the encoding mechanism and memory capacity of the reservoir with the
topologies mentioned above, from the perspective of the mathematical
characteristics of the matrix, i.e., the rank and the nullspace of the matrix.
However, higher memory capacity usually does not correspond to higher
precision prediction [12], and the two are generally traded off in the ”edge
of chaos” state [31].

Another recent related model is the deep RC. Taking ESN as an example, the
typical architecture of deep ESN can be classified into the series ESN and the
parallel ESN, deriving other deep structures [30, 13, 61].

There exist few studies combining RC with transformer [53]. Shen et al. [44]
randomly initialized some of the layers in transformers without updates but
obtained impressive performance in natural language processing. It only draws
on the idea of initializing the parameters of the reservoir, not the ”true”
reservoir in essence.

##  3 Methodology

In the design of ViR, we first present the topology we utilized in the
reservoir and show some formulations and characteristics to expound the
working mechanism. Then, we describe the proposed ViR network and further
present the case of the deep ViR. Finally, we give some aspects to analyze the
intrinsic properties of the ViR.

###  3.1 Nearly Fully Connected Topology

Based on CRJ, we argue that for an image classification task it is necessary
to consider: 1) a simple fixed non-random reservoir topology–nearly full
connection structure with self-loop connections; 2) the weight value
$\textit{$r_{i},r_{j},r_{k}$}\in(0,1]$ for reservoir connections; 3) the signs
of the weights in 2) are deterministically generated by a rule with a certain
degree of randomness; 4) input neurons are randomly connected to the
reservoir.

Figure 3: Nearly Fully Connected Topology. Neurons in the reservoir are nearly
fully connected to others, containing three different types of weights.

Fig. 3 depicts the nearly fully connected topology. We first generate an
$N\times N$ reservoir connection matrix W matching the topology, in which all
the weights have the same original value $r_{k}$ and then we set:

$\textbf{{W}}_{1,\textit{N}}=\textbf{{W}}_{\textit{q}+1,\textit{q}}=\textit{}{r_{i}},\qquad\textit{q}=1,...,\textit{N}-1$
(1)

$r_{j}$ is the jump weight. Consider the jump size $1<\ell<\textit{N}$. The
first jump begins from neuron 1 to $1+\ell$, then from $1+\ell$ to $2\ell+1$,
until $n\ell+1>N$, where n is the number of jump. These bi-directional jump
weights are reset to:

$\displaystyle\textbf{{W}}_{1,\ell+1}=\textbf{{W}}_{\ell+1,2\ell+1}=...$ (2)
$\displaystyle=\textbf{{W}}_{\ell+1,1}=\textbf{{W}}_{2\ell+1,\ell+1}=...=\textit{$r_{j}$}$

Finally, we randomly set an element, with the symmetrical element, to 0,
indicating that the two neurons are disconnected with each other. Hence, W
mainly consists of $r_{k}$, and the amount of $r_{j},r_{c}$ is relatively
small, with two 0 elements.

For the randomness, there exists a random matrix with elements e randomly
generated in (0,1] with the same size as W. If e $<$ 0.5 (the threshold we
set), then the sign of the weight in W, corresponding to the same position as
e, will be $-$, otherwise $+$. The input weight matrix V, compared to W, is a
sparse matrix of the given shape with uniformly distributed values.

For the stability of the reservoir, W is typically scaled as
$\textbf{{W}}\leftarrow\alpha\textbf{{W}}/|\lambda_{max}|$, where
$|\lambda_{max}|$ is the spectral radius of W and $0<\alpha<1$ is a scaling
parameter [19].

For the training process, assuming that
$\textit{{u}(t)}=(u_{1}(t),...,u_{K}(t))$ means the activation of $K$ input
units at time step $t$ from flattened patches, and
$\textit{{x}(t)}=(x_{1}(t),...,x_{M}(t))$ represents the $M$ internal units in
the reservoir with the output $\textit{{y}(t)}=(y_{1}(t),...,y_{Q}(t))$
containing $Q$ output units. The $M\times K$ matrix V stores input weights.
The $M\times(K+M+Q)$ matrix $\textbf{{W}}_{out}$ shows the connections from a
reservoir to output units. Additionally, all the values mentioned above are
real-valued. Apart from $\textbf{W}_{out}$, all the matrices are not trainable
and their entries are initialized with a suitable distribution and then fixed.
Fig. 2 shows the described structure.

The internal units are updated according to:

$\textbf{{x}}(\textit{t}+1)=\textit{f
}(\textbf{{Vu}}(\textit{t}+1)+\textbf{{Wx}}(\textit{t})+\textbf{{b}}(\textit{t}+1))$
(3)

where f is the activation function (typically sigmoidal); b(t+1) is an
optional uniform i.i.d. noise. The readout is computed by:

$\displaystyle\textbf{{y}}(\textit{t}+1)=\textbf{{W}}_{out}$
$\displaystyle[\textbf{{u}}(\textit{t}+1);\textbf{{x}}(\textit{t}+1);\textbf{{y}}(\textit{t});$
(4)
$\displaystyle\textbf{{u}}(\textit{t}+1)^{2};\textbf{{x}}(\textit{t}+1)^{2};\textbf{{y}}(\textit{t})^{2}]$

where ’;’ is a concatenation operation.

As shown in Eq. 4, the essence of network is to approximate output weights
$\textit{{W}}_{out}$ through training samples, to obtain the predictive
ability of certain tasks. Hence, while training, it is essential to collect
and store the state of the reservoir x(t) and the corresponding outputs y(t)
in a matrix X and Y after warm-up [19]. The classic calculation method is the
Least Square Method (LSM) [33]:

$\textit{{W}}_{out}=(\textit{{X}}^{T}\textit{{X}})^{-1}\textit{{X}}^{T}\textit{{Y}}$
(5)

where $(\ast)^{T}$ and $(\ast)^{-1}$ mean the transpose and the inverse of
matrix operator, respectively. Usually, in case X is ill-posed and
irreversible, the ridge regression method [45] is utilized (Eq. 6) instead of
LSM. For other optimizing algorithms refer to [35, 39].

$\textit{{W}}_{out}=(\textit{k}\textit{{I}}+\textit{{X}}^{T}\textit{{X}})^{-1}\textit{{X}}^{T}\textit{{Y}}$
(6)

where k is a relatively small positive number called regular coefficient, and
I is an identity matrix. In our work, we use a trainable linear layer (LL) to
approximate $\textit{{W}}_{out}$ and Eq. 4 can be rewritten as:

$\displaystyle\textbf{{y}}(\textit{t}+1)=\textbf{{LL}}$
$\displaystyle[\textbf{{u}}(\textit{t}+1);\textbf{{x}}(\textit{t}+1);\textbf{{y}}(\textit{t});$
(7)
$\displaystyle\textbf{{u}}(\textit{t}+1)^{2};\textbf{{x}}(\textit{t}+1)^{2};\textbf{{y}}(\textit{t})^{2}]$

###  3.2 The Vision Reservoir (ViR)

Fig. 2 depicts the proposed model for image classification, and the key
component is the ViR core which is composed of a reservoir with the internal
topology mentioned above and a residual block.

The typical reservoir receives a time-series sequence as input. Similar to the
treatment in ViT, some pretreatments are used to convert raw images to patches
as the time series input. We reshape the original image
$\textbf{x}\in\mathbb{R}^{\textit{H}\times\textit{W}\times\textit{C}}$ into a
series of patches
$\textbf{x}_{\textit{p}}\in\mathbb{R}^{\textit{N}\times(\textit{P}^{2}\cdot\textit{C})}$,
where $(\textit{H, W})$ and $(\textit{P, P})$ respectively represent the
resolution of x and $\textbf{x}_{\textit{p}}$, and
$\textit{N}=\textit{H}\textit{W}/\textit{P}^{2}$ is the number of patches,
also serving as the input time steps. With a trainable linear projection E
(Eq. 8), we flatten the patches and map to D dimensions to make the inputs
suitable for the reservoir. We refer to the output of this projection as the
patch coding. Therefore, the input at time step t+n can be written as:

$\textbf{{u}}(\textit{t+n})=\textbf{x}^{n}_{\textit{p}}\textbf{{E}},\quad\textbf{{E}}\in\mathbb{R}^{(\textit{P}^{2}\cdot\textit{C})\times\textit{D}},\textit{n}=0,1,...,\textit{N}-1$
(8)

Then the ViR core receives the data. It consists of the nearly fully connected
reservoir (Fig. 3) and a residual block including a layer-norm (LN) operation
and a feed-forward (FF) layer. The non-linear function in FF is a Gaussian
Error Linear Unit (GELU) [16]. The processing of the reservoir has been shown
in Eq. 3 and Eq. 4, and LN is applied to $\textbf{y}_{\textit{r}}$ (the output
of the reservoir) with the feed-forward layer with a residual connection
between them, shown as:

$\textbf{{y}}_{\textit{c}}=\textbf{{FF}}(\textbf{{LN}}(\textbf{{y}}_{\textit{r}}))+\textbf{y}_{\textit{r}}$
(9)

A classification operation is attached to $\textbf{{y}}_{\textit{c}}$ (the
output of the ViR core ), which is implemented by a MLP, and we can obtain the
image representation and the final classification results y by Eq. 10:

$\textbf{{y}}=\textbf{{LN}}(\textbf{{y}}_{\textit{c}})$ (10)

###  3.3 The Deep ViR

We further stack reservoirs to get the deep ViR to enhance the network
performance.

The first one is the series reservoir consisting of L reservoirs depicted in
Fig. 4. Similarly, the input matrices $\textbf{{{V}}}^{(l)}$ and reservoir
connection matrices $\textbf{{W}}^{(l)}$ are constant and generated as
mentioned above, l $\in$ $\\{$1,2,…,L$\\}$, with similar training process
described in subsection 3.1.

Figure 4: The structure of the deep ViR. The upper one is the series
reservoir, and the lower one refers to the parallel reservoir.

$\textbf{{U}}^{(l)}$ is the output matrix. Units in reservoir l updating and
the output of reservoir l are given by:

$\textit{$\textbf{x}^{(l)}$}(\textit{t}+1)=\textit{f
}(\textit{$\textbf{V}^{(l)}$}\textit{$\textbf{y}^{(l-1)}$}(\textit{t}+1)+\textit{$\textbf{W}^{(l)}\textbf{x}^{(l)}$}(\textit{t}))$
(11)
$\textit{$\textbf{y}^{(l)}$}(\textit{t}+1)=\textit{$\textbf{U}^{(l)}$}[\textit{$\textbf{y}^{(l)}$}(\textit{t});\textit{$\textbf{x}^{(l)}$}(\textit{t}+1);\textit{$\textbf{y}^{(l)}$}(\textit{t})^{2};\textit{$\textbf{x}^{(l)}$}(\textit{t}+1)^{2}]$
(12)

where l $\in$ $\\{$1,2,…,L$\\}$ and
$\textbf{{y}}^{(0)}(\textit{t})=\textbf{{u}}(\textit{t})$,
$\textbf{{y}}^{(L)}(\textit{t})=\textbf{{y}}(\textit{t})$.

The other one is a parallel reservoir, depicted in Fig. 4.

L reservoirs simultaneously receive the same input sequence u(t) and all L
reservoirs can be trained simultaneously referring to the above process. The
units in L reservoirs and the output units are updated as follows:

$\textit{$\textbf{x}^{(l)}$}(\textit{t}+1)=\textit{f
}(\textit{$\textbf{V}^{(l)}$}\textbf{{u}}(\textit{t}+1)+\textit{$\textbf{W}^{(l)}\textbf{x}^{(l)}$}(\textit{t}))$
(13)
$\textit{$\textbf{y}^{(l)}$}(\textit{t}+1)=\textit{$\textbf{U}^{(l)}$}[\textit{$\textbf{y}^{(l)}$}(\textit{t});\textit{$\textbf{x}^{(l)}$}(\textit{t}+1);\textit{$\textbf{y}^{(l)}$}(\textit{t})^{2};\textit{$\textbf{x}^{(l)}$}(\textit{t}+1)^{2}]$
(14)

The final output of a parallel reservoir is the arithmetic mean of L reservoir
outputs, given by:

$\textit{{y}}(\textit{t})=\sum_{l=1}^{L}\textit{$\textbf{y}^{(l)}$}(\textit{t})/\textit{L}$
(15)

###  3.4 Theoretical Analyses

Usually, we evaluate the quality of a reservoir through three indicators: the
Small-World (SW) characteristics, the Largest Lyapunov Exponent (LLE), and the
Memory Capacity (MC) [37]. The reservoir with SW characteristics has a
stronger information processing ability and faster information dissemination
speed than the common reservoir [21, 1]. LLE of a reservoir represents the
dynamics and stability, and usually the value of LLE should be approximately
equal to 0 for great performance. MC is the property of a reservoir to keep
the previous input information, related to the data processing capability.

Small-World Characteristics: RC is a brain-inspired neural network, which
mimics the connections of cerebral neurons, cortical neural connectivity has
been shown to exhibit a small-world (SW) network topology [58], which has a
shorter average path length and larger clustering coefficient than regular
networks. In a reservoir, a small clustering degree means that dynamic
information flow through the reservoir nodes is not ‘too cluttered’. Also, a
small average path length can allow for the representation of a variety of
dynamic time scales.

Due to the bi-directional connections, we can view the interconnection
topology as an undirected graph G=(J, E), J and E representing neurons and the
connections in the reservoir, respectively. This is similar to the kernel
connections in the ViT. Define $\textbf{{l}}_{\textbf{{G}}}$ to be the average
path length between vertex pairs in J, which is calculated by [38]:

$\textbf{{l}}_{\textbf{{G}}}=\frac{2}{M(M+1)}\sum_{\begin{subarray}{c}i\geq
j\end{subarray}}d_{ij}$ (16)

where $d_{ij}$ is the geodesic distance from vertex i to vertex j, and M is
the number of nodes (equal to the number of neurons in the reservoir). If
$i=j$, the distance is 0 [38]. Moreover, if there are no self-loop
connections, Eq. 16 should be rewritten as:

$\textbf{{l}}_{\textbf{{G}}}=\frac{2}{M(M-1)}\sum_{\begin{subarray}{c}i>j\end{subarray}}d_{ij}$
(17)

Assuming that the neighborhood $|\textit{M}_{i}|$ of the node $\textit{v}_{i}$
is the nodes next to $\textit{v}_{i}$, $\textit{M}_{i}$ is the number of nodes
in $|\textit{M}_{i}|$. The local clustering coefficient
$\textbf{{C}}_{\textbf{{i}}}$ of $\textit{v}_{i}$ is given by a ratio, i.e.,
the connecting edges between nodes in the neighborhood divided by the number
of possible connecting edges between them, shown in Eq. 19 [58]:

$\textbf{{M}}_{\textbf{{i}}}={\textit{v}_{j}:\textit{e}_{ij}\in\textbf{{E}}\vee\textit{e}}_{ji}\in\textbf{{E}}$
(18)
$\textbf{{C}}_{\textbf{{i}}}=\frac{2|{\textit{e}_{jk}:\textit{v}_{j},\textit{v}_{k}\in\textbf{{M}}_{i},\textit{e}}_{jk}\in\textbf{{E}}|}{M(M-1)}$
(19)

The overall clustering level $\bar{\textit{C}}$ is
$\bar{\textbf{{C}}}=\frac{1}{M}\sum_{\begin{subarray}{c}i=1\end{subarray}}^{\begin{subarray}{c}M\end{subarray}}C_{i}$.

The degree of SW, named small-worldness, is given as:

$\delta=\frac{C}{C_{0}}/\frac{l_{G}}{l_{0}}$ (20)

where $\textit{C}_{0}$ and $\textit{l}_{0}$ represent the average path length
and clustering level of a regular network with similar size. If $\delta>1$,
the network is a SW network [17].

Lyapunov Exponent: The Largest Lyapunov Exponent (LLE) [59] represents the
stability of reservoir dynamics, expounding the sensitivity of initial
conditions of a system to small perturbations, defined as [51]:

$\textbf{$\lambda$}=\lim_{k\to\infty}\frac{1}{k}ln(\frac{\gamma_{k}}{\gamma_{0}})$
(21)

where $\gamma_{0}$ is the initial distance between the perturbed and the
unperturbed trajectory, $\gamma_{k}$ is the distance at time k. For ordered
dynamic systems, $\lambda<0$ and for chaotic systems $\lambda>0$. At
$\lambda\approx 0$, a phase transition occurs (called the critical point, or
edge of chaos) with the best computational capability [3, 4].

Memory Capacity: Memory Capacity (MC) [20] is another metric to measure the
learning performance of our model. With receiving a random input u(t) at a
time t, the reservoir is trained to generate the desired output
$\textbf{y}_{d}(\textit{t})=u(t-\tau)$. The output y is learned from u(t)
which was $\tau$ steps earlier. Then the MC is given as:

$\textbf{MC}_{\tau}=\frac{cov^{2}(\textbf{u}_{\tau},\textbf{y})}{v^{2}(\textbf{u}_{\tau})v^{2}(\textbf{y})},\qquad\textbf{MC}=\sum_{\tau=1}^{T}\textbf{MC}_{\tau}$
(22)

where $cov^{2}(\textbf{u}_{\tau},\textbf{y})$ indicates the covariance between
the true value $\textbf{u}_{\tau}$ and the predicted value y. $v^{2}(\ast)$
means the variance of a series $\ast$. T is the maximal time delay we set.

We have experimentally demonstrated the SW characteristics, largest Lyapunov
exponents, and memory capacities of our model, in Section 4.1.

##  4 Experiment Results

The comparative study between the proposed ViR and the common ViT model is
carried out on three classical datasets, i.e. MNIST, CIFAR10, and
CIFAR100[27]. We also compare the number of parameters in the ViR with the ViT
and analyze the convergence speed as well as the memory footprint of our
models. Further, the robustness is tested on CIFAR10-C [15].

In this section, original ViT is named ViT-Base [11] with several changes, as
shown in Table 1.

Table 1: The system parameters of the ViR and the ViT. N is the number of neurons in a reservoir, and $\alpha$ is a scaling parameter of the spectral radius of W; SD is the sparse degree of input matrix V. And $r_{i},r_{j},r_{k}$ and jump size are detailed in subsection 3.1. In the ViT row, patch size is the same for all tested datasets. | parameters | values
---|---|---
ViR | (N, $\alpha$, SD) | (1000, 0.9, 0.05)
($r_{i},r_{j},r_{k}$, jump size) | (0.05, 0.5, 0.08, 137)
ViT | Hidden size | 512
MLP size | 2048
Heads | 12
Patch size | $4\times 4$

###  4.1 Small-Worldness, Lyapunov Exponent and Memory Capacity

Table 2 shows the normalized average path length $\frac{l_{G}}{l_{0}}$,
clustering coefficient $\frac{C}{C_{0}}$, and small-worldness $\delta$,
$\frac{C}{C_{0}}/\frac{l_{G}}{l_{0}}$. The baseline is the classic regular
network and random network detailed in [23].

Table 2: Small-worldness of the reservoirs with 1000 neurons. $l_{0}$ and $C_{0}$ are the average path length and clustering level of the regular network, correspondingly. Both are usually equal to 1. | $l_{G}/l_{0}$ | $C/C_{0}$ | $\delta$
---|---|---|---
Regular Network | 1.00 | 1.00 | 1.00
Ours | 0.98 | 0.99 | 1.02
Random Network | 0.09 | 0.02 | 0.20

Our model has a lower clustering level and a smaller average path than the
regular one. It still exhibits the SW property, referring to the fact that our
topology has great potential for information calculation and processing.
Similar to the brain [42], a small average path indicates low wiring cost for
physical implementations. By applying a standard algorithm given in [46],
inputs are sampled from Gaussian distribution [54] for the memory capacity and
the largest Lyapunov exponents.

Fig. 5(a) shows we get the peak Memory Capacity (MC) when the spectral radius
$\rho$(W) is around 1. Also, Fig. 5(b) shows that the largest Lyapunov
Exponent (LLE, defined in subsection 3.4) is close to 0 when $\rho$(W) is
around 1$\sim$1.5. Meanwhile, the influences of the input scaling (IS) to MC
and LLE are also shown in Fig. 5. And the results indicate that we should
constrain the $\rho$(W) and the IS to about 1 for image tasks.

(a). Lyapunov exponents versus spectral radius.

(b). Memory capacities versus spectral radius.

Figure 5: Lyapunov exponents and memory capacities. The horizontal axe denotes
the spectral radius of W. The vertical axe denotes the Lyapunov exponents and
memory capacities in (a) and (b), respectively. IS is a scaling factor to the
input weight matrix $\textbf{W}_{in}$.

###  4.2 Main Results with Training from Scratch

Table 3: Comparisons between ViR and the ViT models without pre-training on prevalent image classification datasets. The digital suffix means the number of the ViR layers or encoders of the ViT. ”M” is expressed as a unit symbol of one million.  | MNIST | CIFAR10 | CIFAR100
---|---|---|---
| accuracy[%] | parameters[M] | accuracy[%] | parameters[M] | accuracy[%] | parameters[M]
ViT-1 | 98.31 | 3.48 | 64.81 | 3.49 | 35.21 | 3.53
ViR-1 | 98.92 | 0.60 | 78.03 | 0.61 | 51.41 | 0.62
ViT-3 | 98.49 | 10.42 | 74.78 | 10.44 | 43.63 | 10.47
Series-ViR-3 | 98.27 | 1.79 | 73.39 | 1.80 | 46.91 | 1.81
Parallel-ViR-3 | 98.95 | 1.59 | 78.51 | 1.60 | 52.25 | 1.61
ViT-6 | 98.54 | 20.84 | 77.68 | 20.85 | 44.14 | 20.88
Series-ViR-6 | 98.45 | 3.59 | 74.3 | 3.60 | 46.87 | 3.61
Parallel-ViR-6 | 99.05 | 3.19 | 79.13 | 3.20 | 51.73 | 3.21
ViT-12 | 98.72 | 41.66 | 79.72 | 41.67 | 45.61 | 41.71
Series-ViR-12 | 98.68 | 7.17 | 75.63 | 7.18 | 47.02 | 7.19
Parallel-ViR-12 | 99.17 | 6.24 | 80.02 | 6.25 | 51.98 | 6.26

Without any pre-training, we compare our models ViR-1, ViR-3, ViR-6, and
ViR-12 with ViT-1, ViT-3, ViT-6, and ViT-12 by performing image classification
tasks on MNIST, CIFAR10, and CIFAR100. Table 3 shows the classification
accuracy and the number of parameters. It can be seen that ViR-1 has more
competitive results than ViT-12 and therefore ViR models have a promising
advantage in saving parameters. According to the aforementioned analysis, the
reservoir with a nearly fully connected topology has great information
processing capability and rich dynamics. Hence, our model is suitable for
handling image tasks.

Accuracy: All the ViR models except Series-ViR perform better than ViT models
with the same depths. Depths are the layers of the ViR or the encoders of the
ViT. Interestingly, the shallow model ViR-1 usually rivals ViT-1, ViT-3, and
ViT-12. This indicates that shallow ViR models have a competitive performance
compared with the deep ViT models, but with lower time costs and fewer
parameters. The great MC of the reservoir donates the high accuracy to some
degree.

Convergence Speed: As depicted in Fig. 1, the initial test accuracy of the ViR
is already close to the best results of the ViT. Meanwhile, the ViT-12 suffers
over-fitting. The convergence speed of most ViR models is much faster than
ViT. This reflects the SW characteristics and rich dynamics from LLE.

The Number of Parameters: Due to the fact that training a reservoir is limited
to the output layer, $\textbf{{W}}_{out}$, much fewer parameters are trained
compared to other models. This is one of the attractive characteristics of RC.
In this aspect, the ViR has the promising advantage compared with ViT.

Table 3 shows the trainable parameters of the ViR and the ViT on different
datasets with different layers. The number of parameters of the ViR is about
15% of the ViT with the same depth. But the comparison between shallow ViR
models and deep ViT models shows that the number of parameters of the ViR
could be about 5% of the ViT while guaranteeing an acceptable accuracy.

Table 3 also indicates that, with the same depth, the series reservoir usually
performs worse than the parallel one. One possible explanation is that: the
series one always randomizes the input to the next reservoir, having no
substantial help for tasks. However, the parallel one randomizes the inputs
only once and then gets the arithmetic mean results. As a result, the
enhancement of accuracy is predictable. With the increase of reservoir layers,
the gains from deep structures can’t offset the influence of time and
computational costs compared to shallow ones. This reveals that it is not
necessary to stack too many reservoirs.

###  4.3 Memory Footprint

Considering the potential crash risk from memory overloading, it is necessary
to evaluate and reduce its usage in a single task while ensuring acceptable
results. The memory footprint of the ViR, compared with ViT models, on MNIST
and CIFAR100 datasets, is shown in Fig. 6.

Figure 6: Comparisons of memory footprint on MNIST and CIFAR100 datasets with
the patch sizes of $4\times 4,14\times 14$, and $16\times 16$.

For small patch size, we observed that the memory footprint of the ViT models
is about 2.5 to 5 times to ours, with the same depth. Although the large patch
size of the ViT could reduce the memory footprint, our models (with small
patch size) still have a slight superiority in such cases. It is worth
noticing that, for both the series ViR and the parallel ViR the memory
footprints within the optimal number of layers are nearly equal.

Table 4: Robustness for evaluating the influence of corruptions of input images. The $\textbf{CE}_{c}$ value for a certain type of corruption is shown from column $2$ to $9$, correspondingly. The CE value is the arithmetic mean corruption error of the corruptions in Noise, Blur, Weather, and Digital columns. In these cases, models are trained only on clean CIFAR10 images and tested on CIFAR10-C. | Noise | Blur | Weather | Digital | CE
---|---|---|---|---|---
| Gaussian | Shot | Defocus | Motion | Snow | Frost | Contrast | JPEG
ViT-1 | 1.8471 | 1.9345 | 1.8551 | 1.8546 | 1.9271 | 1.9468 | 1.9635 | 1.9736 | 1.9128
ViT-3 | 1.7218 | 1.7263 | 1.6837 | 1.7728 | 1.7978 | 1.7761 | 1.7726 | 1.7379 | 1.7486
ViT-6 | 1.6662 | 1.7562 | 1.6608 | 1.6907 | 1.6845 | 1.6973 | 1.7612 | 1.7261 | 1.7054
ViT-12 | 1.5557 | 1.7023 | 1.5234 | 1.5343 | 1.5310 | 1.6287 | 1.6215 | 1.6779 | 1.5969
ViR-1 | 1.6441 | 1.8079 | 1.6573 | 1.7385 | 1.7294 | 1.8717 | 1.7629 | 1.7506 | 1.7447
Series-ViR-3 | 1.8835 | 1.9225 | 1.7164 | 1.8763 | 2.0488 | 2.2069 | 2.1572 | 1.8542 | 1.9582
Series-ViR-6 | 1.9820 | 2.2625 | 2.0411 | 2.1119 | 2.4030 | 2.4629 | 2.3488 | 2.3164 | 2.2411
Series-ViR-12 | 1.8219 | 2.4180 | 2.3383 | 2.3281 | 2.8341 | 2.8164 | 2.8712 | 2.4978 | 2.4907
Parallel-ViR-3 | 1.6365 | 1.7849 | 1.6159 | 1.7034 | 1.7152 | 1.8102 | 1.7603 | 1.8061 | 1.7291
Parallel-ViR-6 | 1.5035 | 1.8193 | 1.6361 | 1.6801 | 1.7296 | 1.8739 | 1.7829 | 1.6950 | 1.7151
Parallel-ViR-12 | 1.4911 | 1.8188 | 1.6006 | 1.6858 | 1.7239 | 1.8758 | 1.7242 | 1.6739 | 1.6993

###  4.4 Robustness

We evaluate the robustness of the ViR from two aspects: i.e. corruptions of
input images and perturbations of system hyperparameters.

Corruptions of input images. The input images are selected from the CIFAR10-C
dataset, which consists of imposed corruptions from noise, blur, weather and
digital categories on the original CIFAR10 dataset [15].

To achieve the comprehensive evaluation of the robustness to a given type of
corruption, we score the classification performance across five corruption
severity levels, denoted by s ($1\leq s\leq 5$), and aggregate these scores
according to:

$\textbf{CE}_{c}=\sum_{s=1}^{5}\textbf{E}_{s,c}-\textbf{E}_{clean},\textbf{CE}=\frac{\textbf{CE}_{c}}{n}$
(23)

where $\textbf{E}_{clean}$ is the top-1 error rate on clean CIFAR10 dataset;
$\textbf{E}_{s,c}$ is the top-1 error rate on CIFAR10-C, c is the type of
corruptions. CE is arithmetic mean of all types of $\textbf{CE}_{c}$, and n
represents the number of corruption types. It should be pointed out that, the
smaller value of $\textbf{CE}_{c}$ or CE represents the stronger robustness.

Table 4 compares the robustness performance by means of $\textbf{CE}_{c}$ and
CE. The results show that the number of layers within parallel-ViR has little
influence on robustness. With the increasing encoding numbers of the ViT, it
has increasingly robustness, which is contrary to in the cases of the series
ViR model.

(a).MC

(b).LLE

Figure 7: The influence of Input Scaling (IS). Considering the Memory Capacity
(MC) (a) and the Largest Lyapunov Exponent (LLE) (b), the value of the
spectral radius and IS should be close to 1 when training.

Perturbations of system hyperparameters. From Fig. 1, we can see that the
number of layers has a smaller impact on our models, compared with the ViT,
perhaps because the spectral radius of W in the ViR is constrained to be
around 1 when training [37]. Moreover, the influence of IS is also reduced
because of the constrained spectral radius, shown in Fig. 7. It has the same
conclusion for other hyperparameters of the ViR, such as the influence of the
number of neurons N, $r_{i},r_{j},r_{k}$ and the jump size. SW characteristics
support our experimental results, which make RC have strong robustness.
However, the hyperparameters in ViT, such as the number of heads, patch size,
and MLP size etc., will significantly impact the classification accuracy. This
indicates that our model has a certain degree of robustness to the
perturbations of system hyperparameters.

##  5 Conclusion

In this paper, we proposed a novel model, namely ViR, for image
classification. Similar to the ViT, the ViR treats the image as a sequence of
pixel patches. The sequences are then processed by using a reservoir with a
nearly fully connected topology. This simple and low-cost network model
performs well, compared with the ViT models, on MNIST, CIFAR10, and CIFAR100.
The ViR has small-world characteristics, chaos dynamics, and great memory
capacities. The ViR exceeds the ViT models, with the learning from scratch, on
image classification, with a lower memory footprint, a smaller number of
parameters, and faster training speed. Encouraging by these experimental
results, further study will be focused on the following three aspects, i)
theoretical explanations for the working mechanism of the reservoir, ii) pre-
training on large-scale datasets, iii) applying the ViR to more computer
vision tasks.

## References

  * [1] Réka Albert and Albert-László Barabási.  Statistical mechanics of complex networks.  Rev. Mod. Phys., 74(1):47, 2002.
  * [2] Witali Aswolinskiy, René Felix Reinhart, and Jochen Steil.  Time series classification in reservoir-and model-space.  Neural Process. Lett., 48(2):789–809, 2018.
  * [3] Nils Bertschinger and Thomas Natschläger.  Real-time computation at the edge of chaos in recurrent neural networks.  Neural Comput., 16(7):1413–1436, 2004.
  * [4] Joschka Boedecker, Oliver Obst, Joseph T Lizier, N Michael Mayer, and Minoru Asada.  Information processing in echo state networks at the edge of chaos.  Theor. Biosci., 131(3):205–213, 2012.
  * [5] Hanten Chang and Katsuya Futagami.  Reinforcement learning with convolutional reservoir computing.  Appl. Intell., 50(8):2400–2410, 2020.
  * [6] Sneha Chaudhari, Varun Mithal, Gungor Polatkan, and Rohan Ramanath.  An attentive survey of attention models.  ACM TIST, 12(5):1–32, 2021.
  * [7] Xin Chen, Bin Yan, Jiawen Zhu, Dong Wang, Xiaoyun Yang, and Huchuan Lu.  Transformer tracking.  In CVPR, pages 8126–8135, 2021.
  * [8] Zhengsu Chen, Lingxi Xie, Jianwei Niu, Xuefeng Liu, Longhui Wei, and Qi Tian.  Visformer: The vision-friendly transformer.  In ICCV, 2021.
  * [9] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, et al.  Rethinking attention with performers.  In ICLR, 2020.
  * [10] Alana de Santana Correia and Esther Luna Colombini.  Attention, please! a survey of neural attention models in deep learning.  CoRR, abs/2103.16775, 2021.
  * [11] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In ICLR, 2021.
  * [12] Igor Farkaš, Radomír Bosák, and Peter Gergel’.  Computational analysis of memory capacity in echo state networks.  Neural Netw., 83:109–120, 2016.
  * [13] Claudio Gallicchio, Alessio Micheli, and Luca Pedrelli.  Deep reservoir computing: A critical experimental analysis.  Neurocomputing, 268:87–99, 2017.
  * [14] Kian Hamedani, Lingjia Liu, Rachad Atat, Jinsong Wu, and Yang Yi.  Reservoir computing meets smart grids: Attack detection using delayed feedback networks.  IEEE Trans. Industr. Inform., 14(2):734–743, 2017.
  * [15] Dan Hendrycks and Thomas G. Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  In ICLR. OpenReview.net, 2019.
  * [16] Dan Hendrycks and Kevin Gimpel.  Bridging nonlinearities and stochastic regularizers with gaussian error linear units.  CoRR, abs/1606.08415, 2016.
  * [17] Mark D Humphries, Kevin Gurney, and Tony J Prescott.  The brainstem reticular formation is a small-world, not scale-free, network.  Proc. Royal Soc. B: Biol. Sci., 273(1585):503–511, 2006.
  * [18] Herbert Jaeger.  The “echo state” approach to analysing and training recurrent neural networks-with an erratum note.  Bonn, Germany: German National Research Center for Information Technology GMD Technical Report, 148(34):13, 2001.
  * [19] Herbert Jaeger.  Tutorial on training recurrent neural networks, covering BPPT, RTRL, EKF and the “echo state network” approach, volume 5.  GMD-Forschungszentrum Informationstechnik Bonn, 2002.
  * [20] Herbert Jaeger et al.  Short term memory in echo state networks, volume 5.  GMD-Forschungszentrum Informationstechnik, 2001.
  * [21] Herbert Jaeger and Harald Haas.  Harnessing nonlinearity: Predicting chaotic systems and saving energy in wireless communication.  Science, 304(5667):78–80, 2004.
  * [22] Azarakhsh Jalalvand, Kris Demuynck, Wesley De Neve, and Jean-Pierre Martens.  On the application of reservoir computing networks for noisy image recognition.  Neurocomputing, 277:237–248, 2018.
  * [23] Yuji Kawai, Jihoon Park, and Minoru Asada.  A small-world topology enhances the echo state property and signal propagation in reservoir computing.  Neural Netw., 112:15–23, 2019.
  * [24] Salman H. Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah.  Transformers in vision: A survey.  CoRR, abs/2101.01169, 2021.
  * [25] Denis Kleyko, Sumeer Khan, Evgeny Osipov, and Suet-Peng Yong.  Modality classification of medical images with distributed representations based on cellular automata reservoir computing.  In ISBI, pages 1053–1056. IEEE, 2017.
  * [26] Petia D. Koprinkova-Hristova.  Reservoir computing approach for gray images segmentation.  CoRR, abs/2107.11077, 2021.
  * [27] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  2012\.
  * [28] Robert Legenstein and Wolfgang Maass.  Edge of chaos and prediction of computational performance for neural circuit models.  Neural Netw., 20(3):323–334, 2007.
  * [29] Yawei Li, Kai Zhang, Jiezhang Cao, Radu Timofte, and Luc Van Gool.  Localvit: Bringing locality to vision transformers.  CoRR, abs/2104.05707, 2021.
  * [30] Xuanlin Liu, Mingzhe Chen, Changchuan Yin, and Walid Saad.  Analysis of memory capacity for deep echo state networks.  In ICMLA, pages 443–448. IEEE, 2018.
  * [31] Lorenzo Livi, Filippo Maria Bianchi, and Cesare Alippi.  Determination of the edge of criticality in echo state networks through fisher information maximization.  IEEE Trans. Neural Netw. Learn. Syst., 29(3):706–717, 2017.
  * [32] Mantas Lukoševičius and Herbert Jaeger.  Reservoir computing approaches to recurrent neural network training.  Computer Science Review, 3(3):127–149, 2009.
  * [33] Mantas Lukoševičius, Herbert Jaeger, and Benjamin Schrauwen.  Reservoir computing trends.  KI-Künstliche Intelligenz, 26(4):365–371, 2012.
  * [34] Wolfgang Maass, Thomas Natschläger, and Henry Markram.  Real-time computing without stable states: A new framework for neural comput based on perturbations.  Neural Comput., 14(11):2531–2560, 2002.
  * [35] Han Min and Wang Ya-Nan.  Multivariate time series online predictor with kalman filter trained reservoir.  Acta Pharm. Sin., 36(1):169–173, 2010.
  * [36] Somayeh Susanna Mosleh, Lingjia Liu, Cenk Sahin, Yahong Rosa Zheng, and Yang Yi.  Brain-inspired wireless communications: Where reservoir computing meets mimo-ofdm.  IEEE Trans. Neural Netw. Learn. Syst., 29(10):4694–4708, 2017.
  * [37] Kohei Nakajima and Ingo Fischer.  Reservoir Computing.  Springer, 2021.
  * [38] Mark EJ Newman.  The structure and function of complex networks.  SIAM REV., 45(2):167–256, 2003.
  * [39] Mustafa C Ozturk and Jose C Principe.  Computing with transiently stable states.  In IJCNN, volume 3, pages 1467–1472. IEEE, 2005.
  * [40] Ali Rodan and Peter Tino.  Minimum complexity echo state network.  IEEE Trans. Neural Netw., 22(1):131–144, 2010.
  * [41] Ali Rodan and Peter Tiňo.  Simple deterministically constructed cycle reservoirs with regular jumps.  Neural Comput., 24(7):1822–1852, 2012.
  * [42] Mikail Rubinov, Rolf JF Ypma, Charles Watson, and Edward T Bullmore.  Wiring cost and topological participation of the mouse brain connectome.  PNAS, 112(32):10032–10037, 2015.
  * [43] Nils Schaetti, Michel Salomon, and Raphaël Couturier.  Echo state networks-based reservoir computing for mnist handwritten digits recognition.  In CSE and EUC and DCABES, pages 484–491. IEEE, 2016.
  * [44] Sheng Shen, Alexei Baevski, Ari S. Morcos, Kurt Keutzer, Michael Auli, and Douwe Kiela.  Reservoir transformer.  CoRR, abs/2012.15045, 2020.
  * [45] Zhiwei Shi and Min Han.  Support vector echo-state machine for chaotic time-series prediction.  IEEE Trans. Neural Netw., 18(2):359–372, 2007.
  * [46] Ippei Shimada and Tomomasa Nagashima.  A numerical approach to ergodic problem of dissipative dynamical systems.  Progress of Theoretical Physics, 61(6):1605–1616, 1979.
  * [47] Mark D Skowronski and John G Harris.  Minimum mean squared error time series classification using an echo state network prediction model.  In ISCAS, pages 4 pp.–3156. IEEE, 2006.
  * [48] Gouhei Tanaka, Toshiyuki Yamane, Jean Benoit Héroux, Ryosho Nakane, Naoki Kanazawa, Seiji Takeda, Hidetoshi Numata, Daiju Nakano, and Akira Hirose.  Recent advances in physical reservoir computing: A review.  Neural Netw., 115:100–123, 2019.
  * [49] Zhiqiang Tong and Gouhei Tanaka.  Reservoir computing with untrained convolutional neural networks for image recognition.  In ICPR, pages 1289–1294. IEEE, 2018.
  * [50] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In ICML, pages 10347–10357. PMLR, 2021.
  * [51] Kazuya Tsuruta, Zonghuang Yang, Yoshifumi Nishio, and Akio Ushida.  Small-world cellular neural networks for image processing applications.  In ECCTD, volume 1, pages 225–228. Citeseer, 2003.
  * [52] Guy Van der Sande, Daniel Brunner, and Miguel C Soriano.  Advances in photonic reservoir computing.  Nanophotonics, 6(3):561–576, 2017.
  * [53] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In NIPS, pages 5998–6008, 2017.
  * [54] David Verstraeten, Joni Dambre, Xavier Dutoit, and Benjamin Schrauwen.  Memory versus non-linearity in reservoirs.  In IJCNN, pages 1–8. IEEE, 2010.
  * [55] Pietro Verzelli, Cesare Alippi, Lorenzo Livi, and Peter Tiňo.  Input-to-state representation in linear reservoirs dynamics.  IEEE Trans. Neural Netw. Learn. Syst., 2021.
  * [56] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.  Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.  CoRR, abs/2102.12122, 2021.
  * [57] Yuqing Wang, Zhaoliang Xu, Xinlong Wang, Chunhua Shen, Baoshan Cheng, Hao Shen, and Huaxia Xia.  End-to-end video instance segmentation with transformers.  In CVPR, pages 8741–8750, 2021.
  * [58] Duncan J Watts and Steven H Strogatz.  Collective dynamics of ‘small-world’networks.  Nature, 393(6684):440–442, 1998.
  * [59] Alan Wolf, Jack B Swift, Harry L Swinney, and John A Vastano.  Determining lyapunov exponents from a time series.  Physica D: nonlinear phenomena, 16(3):285–317, 1985.
  * [60] Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Francis E. H. Tay, Jiashi Feng, and Shuicheng Yan.  Tokens-to-token vit: Training vision transformers from scratch on imagenet.  CoRR, abs/2101.11986, 2021.
  * [61] Zhou Zhou, Lingjia Liu, Vikram Chandrasekhar, Jianzhong Zhang, and Yang Yi.  Deep reservoir computing meets 5g mimo-ofdm systems in symbol detection.  In AAAI, volume 34, pages 1266–1273, 2020.


# Performance Comparisons of Self-stabilizing Algorithms for Maximal
Independent Sets

Barton F. Cone1, Stephen T. Hedetniemi2, Lance C. Ingle3, Ken Kennedy1
1Fulfilld.io
{bart<EMAIL_ADDRESS>2School of Computing, Clemson University
<EMAIL_ADDRESS>3GTRI, Georgia Tech
<EMAIL_ADDRESS>
###### Abstract

Sensor networks, such as ultra-wideband sensors for the smart warehouse, may
need to run distributed algorithms for automatically determining a topological
layout. In this paper, we present 5 different self-stabilizing algorithms
(their central and distributed counterparts) for determining maximal
independent sets. The performance of the algorithms, in terms of time
complexity, simulation analysis, and size of maximal independent sets found
are then compared.

—————–

##  I Introduction

Maximal independent sets (MIS) have several uses, one of which is in wireless
networks [1, 13]. Wireless and sensor networks are ideal testbeds for self-
stabilizing algorithms, and this corresponds with work that Fulfilld.io is
doing with ultra-wideband (UWB) sensors for the smart warehouse. The UWB
sensors are positioned such that objects can be tracked with near realtime
precision allowing a variety of algorithms to be performed (path planning,
route optimization, bin optimization, …).

In this paper, we compare a variety of self-stabilizing algorithms that have
been designed to find independent sets, or maximal independent sets, of nodes
in distributed systems. The topology of a distributed system is modeled by an
undirected graph $G=(V,E)$ of order $n=|V|$ of nodes, and size $m=|E|$ of
edges, where nodes represent processes and edges represent communication links
between processes.

The open neighborhood of a node $i\in V$ is the set $N(i)=\\{j|ij\in E\\}$ of
nodes that are adjacent to $i$; these nodes are called the neighbors of node
$i$. The closed neighborhood of a node $i$ is the set $N[i]=N(i)\cup\\{i\\}$.
The degree of a node is $deg(i)=|N(i)|$, and the maximum degree of a node is
denoted $\Delta(G)$.

The processes of a self-stabilizing algorithm consist of a set of variables
associated with a node and a set of rules, each of which consists of a guard
and a statement. In the distance-$1$ model, a guard is a Boolean expression
over the variables in the closed neighborhood $N[i]$ of a node $i$. If the
Boolean expression evaluates to true at a node $i$, then node $i$ is said to
be eligible to make a move, which consists of changing the values of the
node’s variables as specified by the associated statement.

The values of a node’s variables at any point define its local state. The
local states of the $n$ nodes define the global state or configuration of the
system. An algorithm is called self-stabilizing if regardless of a current,
initial configuration, the system is guaranteed to reach a legitimate or
desired global state in a finite amount of time without any external
intervention, and to remain in a legitimate state [12].

A set $S\subseteq V$ of nodes is called independent if no two nodes in $S$ are
adjacent. In the graph theory literature, $i(G)$ denotes the minimum
cardinality of a maximal independent set, and $\beta_{0}(G)$ denotes the
maximum cardinality of an independent set in $G$.

A set $S$ of nodes is called a dominating set if every node in $V\setminus S$
is adjacent to at least one node in $S$. The domination number of a graph $G$
equals the minimum cardinality of a dominating set in $G$, while the upper
domination number equals the maximum cardinality of a minimal dominating set
in $G$. The following inequality chain is well-known in domination theory [5].

${\gamma\leq i\leq\beta_{0}\leq\Gamma}$ (1)

We focus on comparing the performance of several self-stabilizing graph
algorithms that have been published for finding maximal independent sets. In
particular, we will simulate each algorithm in order to see which algorithms
find either smaller or larger maximal independent sets. We are also interested
in the general question of whether it is possible to modify these algorithms
so that they find maximal independent sets whose cardinalities are better
approximations to either $i(G)$ or $\beta_{0}(G)$. It should also be pointed
out that maximal independent sets are also minimal dominating sets. Therefore,
these algorithms can be used to find minimal dominating sets whose
cardinalities may approximate either $\gamma(G)$ or $\Gamma(G)$.

##  II Central Algorithms

In this section, we present five self-stabilizing algorithms for finding
independent sets that utilize the distance-1 model with an unfair central
scheduler, whereby only one eligible node ${x}$ is permuted to move at a time.
All of the algorithms are silent, in that after stabilization, no node will
make another move. Since Algorithm C2 is a modification of Algorithm C1, and
Algorithms C3 and C4 are further modifications of Algorithm C2, proofs of
correctness and complexity are provided where relevant. Complexity results are
stated for the other algorithms; the reader is referred to the original papers
for their proofs.

###  II-A Central Scheduler Algorithm 1

Algorithm C1, due to Shukla, Rosenkrantz and Ravi [11], was the first self-
stabilizing algorithm for finding a maximal independent set. Each node $i$
maintains only one Boolean variable $x(i)$. When the algorithm stabilizes, the
set of nodes $X=\\{i$ $|x(i)=1\\}$ defines a maximal independent set.

RIn: if x(i) = 0 ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1)

then x(i) = 1

ROut: if x(i) = 1 ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1)

then x(i) = 0

Algorithm 1 C1

###### Theorem 1

Algorithm C1 finds a maximal independent set in at most 2n moves.

Proof: See proof of Algorithm 3.1 in [6].

###  II-B Central Scheduler Algorithm 2

Algorithm C2 is a modification of Algorithm C1 in which the degrees of the
nodes are taken into account. In an attempt to find a larger maximal
independent set, the comparison ${deg}(i)$ ${\geq}$ ${deg}(j)$ is used. We
will refer to this version of the algorithm as ${{C2_{\beta}}_{0}}$. In order
to find a smaller maximal independent set, this can be changed to ${deg}(i)$
${\leq}$ ${deg}(j)$, which will be referred to as ${C2_{i}}$. The algorithm
and proof of correctness are given below.

RIn: if x(i) = 0 ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1)

then x(i) = 1

ROut: if x(i) = 1 ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1 ${\wedge}$
${deg}$(i) ${\geq}$ ${deg}$(j))

then x(i) = 0

Algorithm 2 C2

###### Lemma 1

When the system is stable, the set $X$ of nodes $i$ for which ${x(i)=1}$ forms
an independent set.

Proof: Assume that Algorithm C2 has stabilized, and suppose that the set $X$
is not independent. Then there are two adjacent nodes ${i}$ and $j$ for which
$x(i)=x(j)=1$. If the degree of ${i}$ is greater than or equal to the degree
of ${j}$, then node $i$ is eligible to execute ROut. Otherwise, the degree of
${j}$ is greater than the degree of ${i}$, in which case node $j$ is eligible
to execute rule ROut. This contradicts the assumption that the system is
stable. Therefore, ${X}$ is an independent set.

###### Lemma 2

When the system is stable, the set $X$ forms a maximal independent set.

Proof: From Lemma 1, we know that when the system is stable, $X$ is an
independent set. Suppose that $X$ is not a maximal independent set. In that
case, there must be a node $i$ not in $X$, none of whose neighbors are in $X$.
In this case, node ${i}$ is eligible to execute rule RIn. This contradicts the
assumption that the system is stable. Thus, when the system is stable, the set
$X$ is a maximal independent set.

###### Lemma 3

A node ${i}$ that executes RIn will never make another move.

Proof: Suppose there is a node ${i}$ that executes RIn. By definition, this
means that after node $i$ executes RIn, every node $j$ adjacent to $i$ has
$x(j)=0$. But since $x(i)=1$, no node adjacent to $i$ can ever execute RIn.
This, in turn, implies that node $i$ can never become eligible to execute
ROut. Thus, node $i$ will never make another move.

###### Lemma 4

A node ${i}$ that executes ROut can make at most one other move.

Proof: Suppose a node ${i}$ executes ROut. Having executed this rule, the only
rule that $i$ can execute is RIn. But from Lemma 3, it follows that if $i$
executes this rule, it will never make another move..

###### Theorem 2

Algorithm C2 finds a maximal independent set in at most 2n moves.

Proof: See Lemma 2 for correctness and Lemma 4 for complexity.

###  II-C Central Scheduler Algorithm 3

Algorithm C3 is a modification of Algorithm C2. As with Algorithm C2,
${{C3_{\beta}}_{0}}$ and ${C3_{i}}$ have the comparison signs reversed in
order to find a larger and smaller maximal independent set. The idea of
Algorithm C3 is that a very weak vertex, one with a smaller degree than all of
its neighbors, can always enter, or be excluded from, the maximal independent
set. This is handled by a new rule RInVW. The performance comparison data in
§IV shows that this does produce larger and smaller sets. The algorithm and
proof of correctness are given below.

RIn: if x(i) = 0 ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1)

then x(i) = 1

RInVW: if x(i) = 0 ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(${deg}$(i) ${\geq}$
${deg}$(j))

then x(i) = 1

ROut: if x(i) = 1 ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1 ${\wedge}$
${deg}$(i) ${\geq}$ ${deg}$(j))

then x(i) = 0

Algorithm 3 C3

###### Lemma 5

When the system is stable, the set $X$ forms a maximal independent set.

Proof: With a slight modification, this can be seen from Lemma 2.

###### Lemma 6

A node ${i}$ that executes RInVW will never make another move.

Proof: Suppose a node ${i}$ does make another move after executing RInVW. In
this case, the next move must be ROut and ${i}$ must have a neighbor ${j\in
X}$. However, for ${i}$ to have executed RInVW, it must have a smaller degree
than all of its neighbors. This violates the condition of ROut that a neighbor
in ${X}$ has a degree equal to, or smaller, than ${i}$. Therefore, a node
${i}$ will not make another move after executing RInVW.

###### Lemma 7

A node ${i}$ that executes RIn will make at most one more move.

Proof: For ${i}$ to make another move, it must next execute ROut.
Additionally, for ${i}$ to have executed RIn, none of its neighbors could have
been in $X$ at the time. Therefore, a neighbor of ${i}$ must be a very weak
node and have executed RInVW. As seen from Lemma 6, this node will never make
another move, so after ${i}$ executes ROut, it will be next to a very weak
node in $X$ and cannot execute any further rules.

###### Lemma 8

A node ${i}$ that executes ROut will make at most two more moves.

Proof: Assume a node ${i\in X}$ is next to a neighbor ${j\in X}$ from the
initial configuration. Node ${i}$ can then execute ROut. From Lemma 7, node
${i}$ can execute at most two more moves.

###### Theorem 3

Algorithm C3 finds a maximal independent set in at most 3n moves.

Proof: See Lemma 5 for correctness and Lemmas 6 and 7, and 8 for complexity.

###  II-D Central Scheduler Algorithm 4

Algorithm C4 is a further modification of Algorithm C3. As with Algorithm C2
and C3, ${{C4_{\beta}}_{0}}$ and ${C4_{i}}$ have the comparison signs reversed
in order to find a larger and smaller maximal independent set. Algorithm C3
was concerned with very weak vertices. Algorithm C4 relaxes this to examine
relatively very weak vertices. A vertex is relatively very weak if it has a
smaller degree than all of its neighbors that are in the set ${X}$.

RIn: if x(i) = 0 ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1 ${\wedge}$
${deg}$(i) ${\geq}$ ${deg}$(j))

then x(i) = 1

ROut: if x(i) = 1 ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1 ${\wedge}$
${deg}$(i) ${\geq}$ ${deg}$(j))

then x(i) = 0

Algorithm 4 C4

A solution was developed independently by Yen, Huang, and Turau in [14] for a
similar algorithm named $\mathcal{A}_{deg}$, which provides an approximation
ratio that was bounded by $(\Delta+2)/3$. Their solution utilizes game theory
and provides several measurements for its performance compared to other
algorithms. Their findings also correspond with ours in Section IV that this
approach, considering the degree of the node, provides the best solution for
maximal independent sets.

###  II-E Central Scheduler Algorithm 5

Algorithm C5 is modeled after the Grundy coloring algorithm of Hedetniemi,
Jacobs and Srimani [9], and is found in [8] by Hedetniemi, Jacobs and Kennedy
as an example of a self-stabilizing algorithm that can find two disjoint
independent sets. In Algorithm C5, every node is assigned a color
${x(i)\in\\{1,2,3\\}}$ where:

${R=\\{i{\mid}x(i)=1\\}}$ (2) ${B=\\{i{\mid}x(i)=2\\}}$ (3)

and the following function is defined:

Color(i) = min({1, 2, 3} - ({x(j) $\mid$ j $\in$ N(i)} $\cap$ {1, 2}))

When the algorithm stabilizes, as shown in [8], $R$ is a maximal independent
set in $G=(V,E)$, and $B$ is a maximal independent set in the induced subgraph
$G[V-R]=(V-R,(V-R\times V-R)\cap E)$.

Re-color: if x(i) $\neq$ Color(i)

then x(i) = Color(i)

Algorithm 5 C5

###### Theorem 4

Algorithm C5 finds a maximal independent set $R$ in $G$ and $B$ in $G[V-R]$ in
at most 3n moves.

Proof: See proof of Algorithm 3 in [8].

##  III Distributed Algorithms

In this section, we present five self-stabilizing algorithms for finding
maximal independent sets running under the distance-1 model with an unfair
distributed scheduler, whereby any number of eligible nodes may move at the
same time. The algorithms are all silent. Four algorithms are new and proofs
are given for their correctness and complexity. As before, results are given
for the other algorithm with the reader being referred to the original paper
for its proof. For each of the algorithms, we assume that the nodes $i$ have
unique identifiers $id(i)$.

###  III-A Distributed Scheduler Algorithm 1

Algorithm D1 was designed by Turau (see [12]) as a generalization of Algorithm
C1. The algorithm includes ${wait}$ and ${back}$ states to take into account
cases in which two adjacent nodes are eligible to move at the same time. In
case two adjacent nodes want to enter the independent set $X$ at once by
executing rule RIn, ids are used to determine which node will be allowed to
enter the set.

RWait: if x(i) = 0 ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1)

then x(i) = ${w}$

RBack: if x(i) = ${w}$ ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1)

then x(i) = 0

RIn: if x(i) = ${w}$ ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1)
${\wedge}$ (${\forall}$k ${\in}$ N(i))(x(k) ${\neq}$ ${w}$ ${\vee}$ id(k)
${>}$ id(i))

then x(i) = 1

ROut: if x(i) = 1 ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1)

then x(i) = 0

Algorithm 6 D1

###### Theorem 5

Algorithm D1 finds a maximal independent set in at most ${max(3n-5,2n)}$
moves.

Proof: See proof of Algorithm ${\mathcal{A}_{\text{MIS}}}$ in [12].

###  III-B Distributed Scheduler Algorithm 2

Algorithm D2 is the distributed version of Algorithm C2, the new algorithm
presented earlier for finding a maximal independent set. As with Algorithm C2,
the comparison ${deg}(i)$ ${\geq}$ ${deg}(j)$ can be changed to ${deg}(i)$
${\leq}$ ${deg}(j)$ to find a smaller maximal independent set. This change
will be referred to as Algorithm D2-1.

RWait: if x(i) = 0 ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1)

then x(i) = ${w}$

RBack: if x(i) = ${w}$ ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1)

then x(i) = 0

RIn: if x(i) = ${w}$ ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1)
${\wedge}$ (${\forall}$k ${\in}$ N(i))(x(k) ${\neq}$ ${w}$ ${\vee}$ id(k)
${\geq}$ id(i))

then x(i) = 1

ROut: if x(i) = 1 ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1 ${\wedge}$
${deg}$(i) ${\geq}$ ${deg}$(j))

then x(i) = 0

Algorithm 7 D2

###### Lemma 9

When the system is stable, the set $X$ of nodes with $x(i)=1$ forms an
independent set.

Proof: See proof of Lemma 1 with slight modification for wait state and ids.

###### Lemma 10

When the system is stable, no node $i$ has $x(i)=w$.

Proof: Assume that the system is stable and there exists a node $i$ with
$x(i)=w$. Assume furthermore, that node $i$ has the smallest $id$ of all nodes
$j$ with $x(j)=w$. Since the system is stable, node $i$ is not eligible to
execute rule RBack. This implies that no neighbor $j\in N(i)$ has $x(j)=1$.
Thus, every neighbor $j\in N(i)$ has $x(j)\in\\{0,w\\}$. But since the system
is stable, and node $i$ is not eligible to execute rule RIn, node $i$ must
have at least one neighbor, say $k\in N(i)$, with $x(k)=w$ and $id(k)<id(i)$.
But this contradicts our assumption that node (i) has the smallest $id$ among
all nodes with $x(j)=w$. Thus, when the system is stable, no node $i$ has
$x(i)=w$.

###### Lemma 11

When the system is stable, the set $X$ forms a maximal independent set.

Proof: Assume that the system is stable and the set $X$ does not form a
maximal independent set. From Lemma 9, we know that when the system is stable
$X$ is an independent set. Therefore, $X$ is not a maximal independent set.
This implies that there exists a node $i$ with $x(i)\in\\{0,w\\}$ and no
neighbor $j\in N(i)$ has $x(j)=1$. But from Lemma 6, we know that if the
system is stable, then no node $i$ has $x(i)=w$. Therefore, there must exist a
node $i$ with $x(i)=0$ and all neighbors $j\in N(i)$ have $x(j)=0$. Therefore,
node (i) is eligible to execute rule RWait, and the system is not stable.

###### Lemma 12

If a node i executes rule RIn, it will never make another move.

Proof: Assume that a node $i$ executes rule RIn. The only rule it could be
eligible to execute after this is rule ROut. By contradiction, suppose that
node ${i}$ executes ROut sometime after executing RIn. Therefore, a neighbor
$j$ of ${i}$ must have entered the independent set after, or at the same time,
as ${i}$. From Lemma 3, we know that a neighbor ${j}$ of ${i}$ could not have
executed RIn while ${i}$ is in the independent set. Therefore, ${j}$ must have
executed RIn at the same time as ${i}$. However, the guard of RIn requires
that a node either have no neighbors in the wait state or any neighbor in the
wait state must have a larger id. As the ids are unique and ${i}$ executed
RIn, node ${j}$ must have a larger id than ${i}$ and could not enter the
independent set. Thus a node ${i}$ will never make another move after
executing RIn.

###### Lemma 13

A node i that executes rule RWait can make at most one more move.

Proof: Suppose there is a node ${i}$ that executes RWait. Node ${i}$ is now in
the wait state and can only execute RBack or RIn.

Case 1: node ${i}$ executes RIn. From lemma 12, we see that node ${i}$ will
never make another move.

Case 2: node ${i}$ executes RBack. For node ${i}$ to have executed RBack, a
node $j\in N(i)$ must have executed RIn in which case node ${i}$ will not be
able to execute another move.

###### Lemma 14

A node ${i}$ that executes ROut will make at most two more moves.

Proof: Suppose there is a node ${i}$ that executes ROut from its initial
state. For node ${i}$ to have executed ROut, there had to have been a neighbor
${j}$ such that ${x(j)=1}$ and ${deg(i)\geq deg(j)}$. It is possible that node
${j}$ executes ROut at the same time as ${i}$. Thus, node ${i}$ could execute
RWait, and from Lemma 13, we see that ${i}$ will make at most one more move.

###### Lemma 15

A node ${i}$ that executes RBack will make at most two more moves.

Proof: Suppose there is a node ${i}$ that executes RBack from its initial
state. For node ${i}$ to have executed RBack, there had to have been a
neighbor ${j}$ such that ${x(j)=1}$. If node ${j}$ then executes ROut (only
from the initial state), the next move that ${i}$ can make is RWait, and from
Lemma 13, we see that ${i}$ could make at most one more move.

###### Theorem 6

Algorithm D2 finds a maximal independent set in at most 3n moves.

Proof: This follows immediately from Lemmas 11, 14 and 15.

###  III-C Distributed Scheduler Algorithm 3

RWait: if x(i) = 0 ${\wedge}$ ((${\nexists}$j ${\in}$ N(i))(x(j) = 1) ${\vee}$
(${\nexists}$k ${\in}$ N(i))(${deg}$(i) ${\geq}$ ${deg}$(k)))

then x(i) = ${w}$

RBack: if x(i) = ${w}$ ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1)
${\wedge}$ (${\exists}$k ${\in}$ N(i))(${deg}$(i) ${\geq}$ ${deg}$(k))

then x(i) = 0

RIn: if x(i) = ${w}$ ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1)
${\wedge}$ (${\forall}$k ${\in}$ N(i))(x(k) ${\neq}$ ${w}$ ${\vee}$ id(k)
${\geq}$ id(i))

then x(i) = 1

RInVW: if x(i) = ${w}$ ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(${deg}$(i)
${\geq}$ ${deg}$(j))

then x(i) = 1

ROut: if x(i) = 1 ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1 ${\wedge}$
${deg}$(i) ${\geq}$ ${deg}$(j))

then x(i) = 0

Algorithm 8 D3

###### Lemma 16

When the system is stable, the set $X$ forms a maximal independent set.

Proof: This can be seen with a slight modification of Lemma 11.

###### Lemma 17

A node ${i}$ that executes RInVW will never make another move.

Proof: See proof of Lemma 6.

###### Lemma 18

A node ${i}$ that executes RIn will make at most one other move.

Proof: From Lemmas 12 and 17, if node ${i}$ executes RIn, the only possible
move for node ${i}$ to make will be to execute ROut. This can only occur if a
neighbor ${j\in N(i)}$ executes RInVW. At that point, node ${i}$ will not make
another move as RWait will not be enabled.

###### Lemma 19

A node i that executes rule RWait can make at most 2 * deg(i) - 1 more moves.

Proof: Suppose there is a node ${i}$ that executes RWait. Node ${i}$ is now in
the wait state and can execute RBack, RIn, or RInVW.

Case 1: node ${i}$ executes RInVW. From lemma 17, we see that node ${i}$ will
never make another move.

Case 2: node ${i}$ executes RIn. From lemma 18, we see that node ${i}$ will
make at most one more move.

Case 3: node ${i}$ executes RBack. For node ${i}$ to have executed RBack, a
neighbor $j\in N(i)$ must have executed RIn or RInVW. From Lemma 17, if node
${j}$ executes RInVW, ${j}$ will not make another move nor will node ${i}$.
However from Lemma 18, if node ${j}$ executed RIn, a neighbor ${k\in N(j)}$
where ${k\neq i}$ may execute RInVW. After such a move, node ${j}$ must
execute ROut allowing ${i}$ to once again execute RWait. This set of moves can
occur up to $deg(i)$ times allowing for a maximum of $2*deg(i)-1$ moves at
node ${i}$ after $i$ has executed the initial RWait.

###### Lemma 20

A node i that executes rule RBack can make at most 2 * deg(i) more moves.

Proof: A node ${i}$ may initially be in the wait state with a neighbor ${j\in
N(i)}$ initially in the set X. Node $i$ can then execute RBack. The next move
node $i$ could make is to execute RWait, at which point from Lemma 19, node
$i$ can make at most $2*deg(i)-1$ more moves.

###### Lemma 21

A node i may execute at most 2 ROut moves.

Proof: Nodes $i$ and $j$ where${j\in N(i)}$ may be initially in the set X. At
this point, $i$ can execute ROut. From Lemma 17, if a node executes RInVW, it
will never make another move, and from Lemma 18, if a node executes RIn, it
will execute ROut at most one more time.

###### Theorem 7

Algorithm D3 finds a maximal independent set in at most O(${\Delta}$n) moves.

Proof: See Lemma 16 for correctness and Lemmas 17, 18, 19, 20, and 21 for
complexity.

###  III-D Distributed Scheduler Algorithm 4

RWait: if x(i) = 0 ${\wedge}$ ((${\nexists}$j ${\in}$ N(i))(x(j) = 1) ${\vee}$
(${\nexists}$k ${\in}$ N(i))(x(k) = 1 ${\wedge}$ ${deg}$(i) ${\geq}$
${deg}$(k)))

then x(i) = ${w}$

RBack: if x(i) = ${w}$ ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1)
${\wedge}$ (${\exists}$k ${\in}$ N(i))(x(k) = 1 ${\wedge}$ ${deg}$(i) ${\geq}$
${deg}$(k))

then x(i) = 0

RIn: if x(i) = ${w}$ ${\wedge}$ (${\nexists}$j ${\in}$ N(i))(x(j) = 1
${\wedge}$ ${deg}$(i) ${\geq}$ ${deg}$(j))

then x(i) = 1

ROut: if x(i) = 1 ${\wedge}$ (${\exists}$j ${\in}$ N(i))(x(j) = 1 ${\wedge}$
${deg}$(i) ${\geq}$ ${deg}$(j))

then x(i) = 0

Algorithm 9 D4

The maximum number of moves for this algorithm remains an open problem. As
stated for Algorithm C4, an approximation ratio was developed by Yen, Huang,
and Turau in [14] showing that the central solution was bounded by
$(\Delta+2)/3$.

###  III-E Distributed Scheduler Algorithm 5

Algorithm D5, a distributed version of Algorithm C5, is given below. In [8],
no distributed version of Algorithm C5 was given. We have included one below
along with a proof of its correctness and complexity. $R$, $B$, and $Color$
are defined in §II-E. Additionally, we define the following function:

swn($i$) $\equiv$ $\exists$j $\in$ N(i)(id(j) $<$ id(i) $\wedge$ x(j) = w)

RWait: if x(i) ${=}$ 3 ${\wedge}$ x(i) ${\neq}$ Color(i)

then x(i) = ${w}$

RBack: if x(i) = ${w}$ ${\wedge}$ Color(i) = 3

then x(i) = 3

RIn: if x(i) = ${w}$ ${\wedge}$ Color(i) ${\neq}$ 3 ${\wedge}$ ${\neg}$swn(i)

then x(i) = Color(i)

ROut: if x(i) ${\in}$ {1, 2} ${\wedge}$ x(i) ${\neq}$ Color(i)

then x(i) = 3

Algorithm 10 D5

###### Lemma 22

When the system is stable, no node is in the wait state.

Proof: By contradiction, let us assume that the system is stable and there is
a node ${i}$ in the wait state that has the smallest ID of all nodes in the
wait state. In this case, node $i$ is eligible to execute RBack or RIn, and
therefore, the system is not stable.

###### Lemma 23

When the system is stable, ${R}$ is maximal independent in ${G}$, and ${B}$ is
maximal independent in $G[V-R]$.

Proof: By Lemma 22, when the system is stable, no node is in the wait state.
The set ${R}$ must be an independent set; otherwise, two nodes $i,j\in R$
would be adjacent having $x(i)=x(j)=1$ and both would be eligible to execute
ROut. A similar argument shows that ${B}$ must be an independent set.
Additionally, ${R}$ must be maximal independent in ${G}$. If a node ${j}$ is
not adjacent to a node in ${R}$, it can execute either RWait or RIn. Likewise,
${B}$ must be maximal independent in $G[V-R]$.

###### Lemma 24

If a node i executes RIn and x(i) = 1, then it will never make another move.

Proof: Due to the $swn$ function, we know that all neighbors of ${i}$ in the
wait state must have larger $id$s than ${i}$. Additionally, from the $Color$
function, no neighbor of ${i}$ can have the color 1. Therefore, after ${i}$
executes RIn, no neighbor of ${i}$ will be able to set its color to 1, and
${i}$ will never move again.

###### Lemma 25

If a node i executes RIn and x(i) = 2, then node i will make at most 2 *
deg(i) - 1 more moves.

Proof: Suppose node ${i}$ has the largest id of all of its neighbors and
executes rule RIn and x(i) = 2. As in Lemma 24, no neighbor of ${i}$ will set
its color to 2 while ${i}$ has color 2. Therefore, for ${i}$ to move again, a
neighbor ${j}$ with $x(j)=1$ must execute ROut. This is possible in the
initial state if ${j}$ is adjacent to a neighbor also colored 1. At this
point, ${i}$ can execute ROut and then RWait as it has no neighbors colored 1.

Case 1: If ${i}$ next executes RIn and sets $x(i)=1$, from Lemma 24, we know
that ${i}$ will never make another move.

Case 2: A neighbor ${k}$ of ${i}$ sets $x(k)=2$. Node ${i}$ can now execute
RBack. Assume ${k}$ is also adjacent to a neighbor ${l}$ with $x(l)=1$ from
the initial state. As with ${j}$, ${l}$ may execute ROut allowing ${k}$ to set
its color to 1. At this point, node ${i}$ can again execute RWait to attempt
to set $x(i)=2$. This process can repeat for $deg(i)$ \- 1 times. At the end,
${i}$ will either execute RBack or RIn.

###### Lemma 26

A node i may execute at most deg(i) RWait moves.

Proof: This follows from Lemma 25.

###### Lemma 27

A node i may execute at most deg(i) + 1 RBack moves.

Proof: A node ${i}$ may initially be in the wait state when it has neighbors
colored 1 and 2. At this point, ${i}$ may execute RBack. From Lemma 26, we see
that there may be $deg(i)$ RWait moves, each of which may be followed by an
RBack move.

###### Lemma 28

A node i may execute at most 2 ROut moves.

Proof: A node in the initial state with color 1 or 2 may execute ROut if it is
adjacent to a neighbor with the same color. From Lemma 24, we know that after
a node executes RIn and sets $x(i)=1$, it will never move again. However, if
it sets ${x(i)=2}$, it may execute one more ROut rule if a neighbor ${j}$
where $x(j)=1$ from the initial configuration executes ROut.

###### Theorem 8

Algorithm D5 finds a maximal independent set ${R}$ in ${G}$ and a maximal
independent set ${B}$ in $G[V-R]$ in $O({\Delta}n)$ moves.

Proof: See Lemma 23 for correctness and Lemmas 24, 25, 26, 27, and 28 for
complexity.

##  IV Performance Comparisons

In the previous two sections, we have presented several self-stabilizing
algorithms for finding maximal independent sets, using both central and
distributed schedulers. We implemented each algorithm and run simulations on
four classes of graphs: trees (connected and acyclic graphs), bipartite graphs
(connected graphs having no cycles of odd length), unit disk graphs (the
intersection graphs of unit disks randomly placed in the plane) and arbitrary
connected graphs. In each case we randomly generated 5,000 graphs of order
$n=500$, for each of these four types. For algorithms using the central
scheduler, we selected at random any of the currently eligible nodes to move,
and for algorithms using the distributed scheduler, we randomly selected a
subset of the set of currently eligible nodes to move. In each case we
recorded the number of moves made before the algorithm stabilized, and the
size of the independent set found by the algorithm.

Algorithm | Tree | % Diff. | Bipartite | % Diff. | Unit Disk | % Diff. | Connected | % Diff.
---|---|---|---|---|---|---|---|---
${C1}$ | 267.5 | - | 167.6 | - | 61.1 | - | 95.1 | -
${{C2_{\beta}}_{0}}$ | 282.5 | 5.5% | 178.5 | 6.3% | 65.9 | 7.6% | 102.8 | 7.8%
${C2_{i}}$ | 247.3 | -7.8% | 154.4 | -8.2% | 58.1 | -5.0% | 86.5 | -9.5%
${{C3_{\beta}}_{0}}$ | 296.9 | 10.4% | 185.7 | 10.2% | 68.0 | 10.7% | 106.4 | 11.2%
${C3_{i}}$ | 232.5 | -14.0% | 149.9 | -11.1% | 57.6 | -5.9% | 85.0 | -11.2%
${{C4_{\beta}}_{0}}$ | 297.2 | 10.5% | 186.5 | 10.7% | 71.3 | 15.4% | 107.6 | 12.3%
${C4_{i}}$ | 221.1 | -19.0% | 148.1 | -12.4% | 57.2 | -6.6% | 80.4 | -16.8%
${C5}$ | 267.2 | -0.1% | 167.3 | -0.2% | 61.1 | 0.0% | 95.0 | -0.1%
${D1}$ | 264.2 | - | 166.7 | - | 60.9 | - | 94.4 | -
${{D2_{\beta}}_{0}}$ | 272.8 | 3.2% | 174.3 | 4.5% | 64.5 | 5.7% | 100.6 | 6.4%
${D2_{i}}$ | 253.2 | -4.3% | 157.7 | -5.5% | 58.4 | -4.2% | 87.9 | -7.1%
${{D3_{\beta}}_{0}}$ | 296.7 | 11.6% | 185.8 | 10.8% | 67.5 | 10.3% | 106.3 | 11.9%
${D3_{i}}$ | 233.3 | -12.4% | 150.8 | -10.0% | 57.8 | -5.2% | 85.6 | -9.8%
${{D4_{\beta}}_{0}}$ | 297.1 | 11.7% | 186.4 | 11.2% | 71.3 | 15.7% | 107.6 | 13.1%
${D4_{i}}$ | 221.1 | -17.8% | 147.5 | -12.2% | 57.2 | -6.3% | 80.4 | -16.0%
${D5}$ | 263.3 | -0.3% | 166.3 | -0.2% | 60.9 | 0.0% | 94.2 | -0.2%
TABLE I: Average size of maximal independent sets found Algorithm | Complexity | Tree | % Diff. | Bipartite | % Diff. | Unit Disk | % Diff. | Connected | % Diff.
---|---|---|---|---|---|---|---|---|---
${C1}$ | $2n$ | 205.4 | - | 253.5 | - | 239.1 | - | 275.9 | -
${{C2_{\beta}}_{0}}$ | $2n$ | 182.0 | -12.1% | 200.8 | -23.2% | 215.4 | -10.4% | 225.7 | -20.0%
${C2_{i}}$ | $2n$ | 199.7 | -2.8% | 240.0 | -5.5% | 237.5 | -0.7% | 259.3 | -6.2%
${{C3_{\beta}}_{0}}$ | $3n$ | 274.0 | 28.6% | 259.6 | 2.4% | 237.9 | -0.5% | 261.1 | -5.5%
${C3_{i}}$ | $3n$ | 253.3 | 20.9% | 274.3 | 7.9% | 246.9 | 3.2% | 276.2 | 0.1%
${{C4_{\beta}}_{0}}$ | ? | 285.8 | 32.7% | 288.2 | 12.8% | 300.0 | 22.6% | 302.8 | 9.3%
${C4_{i}}$ | ? | 389.7 | 61.9% | 396.6 | 44.0% | 344.9 | 36.2% | 382.5 | 32.4%
${C5}$ | $3n$ | 302.4 | 38.2% | 331.8 | 26.8% | 307.5 | 25.0% | 372.0 | 29.7%
${D1}$ |  ${max}$(3${n}$-5,2${n}$) | 388.1 | - | 422.2 | - | 393.8 | - | 474.6 | -
${{D2_{\beta}}_{0}}$ | $3n$ | 383.4 | -1.2% | 381.8 | -10.0% | 351.8 | -11.3% | 389.5 | -19.7%
${D2_{i}}$ | $3n$ | 376.9 | -2.9% | 394.5 | -6.8% | 369.3 | -6.4% | 416.7 | -13.0%
${{D3_{\beta}}_{0}}$ | $O({\Delta}n)$ | 490.1 | 23.2% | 449.8 | 6.3% | 387.1 | -1.7% | 429.2 | -10.0%
${D3_{i}}$ | $O({\Delta}n)$ | 444.7 | 13.6% | 452.8 | 7.0% | 388.9 | -1.3% | 450.4 | -5.2%
${{D4_{\beta}}_{0}}$ | ? | 511.8 | 27.5% | 487.7 | 14.4% | 481.1 | 20.0% | 484.6 | 2.1%
${D4_{i}}$ | ? | 659.6 | 51.8% | 655.8 | 43.3% | 550.9 | 33.3% | 624.8 | 27.3%
${D5}$ | $O({\Delta}n)$ | 646.1 | 49.9% | 628.6 | 39.3% | 513.4 | 26.4% | 688.6 | 36.8%
TABLE II: Worst-case complexity and average number of moves
$500$$1{,}000$$1{,}500$$2{,}000$$0$$1{,}000$$2{,}000$Order $n$Number of
Moves${{C4_{\beta}}_{0}}$${C4_{i}}$${{D4_{\beta}}_{0}}$${D4_{i}}$ Figure 1:
Comparison of the average number of moves for the C4/D4 algorithms on random
trees of various orders. $500$$1{,}000$$1{,}500$$2{,}000$$30$$40$$50$$60$Order
$n$% Difference${{C4_{\beta}}_{0}}$ vs ${C1}$${C4_{i}}$ vs
${C1}$${{D4_{\beta}}_{0}}$ vs ${D1}$${D4_{i}}$ vs ${D1}$ Figure 2: Comparison
of the % differences for the average number of moves of the C4/D4 algorithms
with C1/D1 on random trees of various orders.

Our simulation results indicate that the central scheduler algorithms usually
find larger independent sets than the distributed scheduler algorithms, see
Table I, and generally require fewer moves, see Table II, to reach a stable
state. The second result was expected, as distributed algorithms often include
wait states. However, we were not expecting the first result. Of the
algorithms studied, Algorithm C2, and its distributed version D2, are faster
than the previously published algorithms C1 and D1. In terms of set size, the
following inequality was observed for finding large maximal independent sets:

$C4,D4>C3,D3>C2,D2>C1=C5,D1=D5$ (4)

and the following inequality for small maximal independent sets:

$C4,D4<C3,D3<C2,D2<C1=C5,D1=D5$ (5)

Algorithm C4, and the distributed D4, consistently produced the largest and
smallest maximal independent sets. This is also consistent with findings in
[14]. Algorithm C5, and its distributed version D5, produced sets of the same
size as C1 and the D1 but made far more moves.

##  V Conclusions

With the introduction of distributed sensors in environments such as the smart
warehouse, the need for algorithms that can be run on these sensors in order
to create topological layouts, such as maximal independent sets, will only
increase. This paper has presented a variety of algorithms and approaches for
determining fast methods for finding a MIS set as well as methods for
determining the smallest/largest MIS set.

The complexity of Algorithm D4, as well as a fixed bound for Algorithm C4, are
still open problems and of interest to the authors.

## References

  * [1] K. Alzoubi, P.J. Wan, O. Frieder, Maximal independent set, weakly-connected dominating set, and induced spanners in wireless ad hoc networks, International Journal of Foundations of Computer Science 14 (2)(2003)287-303.
  * [2] W. Goddard, S. T. Hedetniemi, D. P. Jacobs and P. K. Srimani, Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks. Proc. Fifth IPDPS Workshop on Advances in Parallel and Distributed Computational Models, Nice, France, pp. 162, 2003.
  * [3] W. Goddard, S. T. Hedetniemi, D. P. Jacobs, P. K. Srimani and Z. Xu, Self-stabilizing graph protocols. Parallel Process. Lett. 18:189-199, 2005.
  * [4] N. Guellati and H. Kheddouci, A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs. J. Parallel Distrib. Comput., 70(4)  (2010) 406–415.
  * [5] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, Marcel-Dekker, New York, 1998.
  * [6] S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs and P. K. Srimani, Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Comput. Math. Appl. 46 (2003) 803–811.
  * [7] S. M. Hedetniemi, S. T. Hedetniemi, K. E. Kennedy, and A. A. McRae, Self-stabilizing Algorithms for Unfriendly Partitions into two Disjoint Dominating Sets. Parallel Processing Letters (March 2013).
  * [8] S. T. Hedetniemi, D. P. Jacobs and K. E. Kennedy, Linear-time self-stabilizing algorithms for disjoint independent sets. The Computer Journal (10 September 2012).
  * [9] S. T. Hedetniemi, D. P. Jacobs and P. K. Srimani, Linear time self-stabilizing colorings. Inform. Process. Lett. 87:251-255, 2003.
  * [10] M. Ikeda, S. Kamei and H. Kakugawa, A space-optimal self-stabilizing algorithm for the maximal independent set problem. Proc 3rd Int. Conf. on Parallel and Distributed Computing, Applications and Technologies, 70-74, 2002.
  * [11] S. Shukla, D. Rosenkrantz and S. Ravi, Obsevations on self-stabilizing graph algorithms for anonymous networks. proc. 2nd Workshop on Self-Stabilizing Systems, 7.1-7.5, 1995.
  * [12] V. Turau. Linear self-stabilizing algorithms for the independent and dominating set problems. Inform. Process. Lett. 103 (2007) 88–93.
  * [13] Peng Wang, Stephan Bohacek, On the practical complexity of solving the maximum weighted independent set problem for optimal scheduling in wireless networks. WICON’ 08 (17-19 November 2008).
  * [14] Li-Hsing Yen, Jean-Yao Huang and Volker Turau, Designing Self-Stabilizing Systems Using Game Theory. ACM Transactions on Autonomous and Adaptive Systems, Volume 11, Issue 3, Article 18, 2016.