IEEE Copyright Notice

©2022 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.

Accepted to be Published in: Proceedings of the 2022 International Joint
Conference on Neural Networks (IJCNN 2022), 18-23 July, 2022, Padua, Italy.

# Acute Lymphoblastic Leukemia Detection Using Hypercomplex-Valued
Convolutional Neural Networks ††thanks: This work was supported in part by
CNPq under grant no. 315820/2021-7, FAPESP under grant no. 2019/02278-2, and
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) -
Finance Code 001.

1st Guilherme Vieira  Department of Applied Mathematics
University of Campinas
Campinas, Brazil
email<EMAIL_ADDRESS>2nd Marcos Eduardo Valle  Department of
Applied Mathematics
University of Campinas
Campinas, Brazil
email<EMAIL_ADDRESS>
###### Abstract

This paper features convolutional neural networks defined on hypercomplex
algebras applied to classify lymphocytes in blood smear digital microscopic
images. Such classification is helpful for the diagnosis of acute lymphoblast
leukemia (ALL), a type of blood cancer. We perform the classification task
using eight hypercomplex-valued convolutional neural networks (HvCNNs) along
with real-valued convolutional networks. Our results show that HvCNNs perform
better than the real-valued model, showcasing higher accuracy with a much
smaller number of parameters. Moreover, we found that HvCNNs based on Clifford
algebras processing HSV-encoded images attained the highest observed
accuracies. Precisely, our HvCNN yielded an average accuracy rate of 96.6%
using the ALL-IDB2 dataset with a 50% train-test split, a value extremely
close to the state-of-the-art models but using a much simpler architecture
with significantly fewer parameters.

###### Index Terms:

Convolutional neural network, hypercomplex algebras, Clifford algebras, Acute
Lymphoblastic Leukemia, computer assisted diagnosis.

##  I Introduction

Over the past few decades, artificial neural networks (ANN) have been employed
on various classification tasks, many of them previously performed by humans.
One popular example is the computer-assisted diagnosis (CAD), in which the
output of the ANN may assist doctors in making more accurate decisions [1].
Most applications in CAD consist of a machine learning model performing tasks
that would be handmade by specialists, reducing the financial and human costs
while also avoiding possible mistakes caused by fatigue [2, 3]. Moreover,
computers have been repeatedly appointed as outperforming unaided
professionals in these tasks [3, 4]. CAD applications have been effectively
used, for example, for leukemia identification [5].

Acute lymphoblastic leukemia (ALL) is a blood pathology that can be lethal in
only a few weeks if left unchecked. ALL is a type of blood cancer identified
by immature lymphocytes, known as lymphoblasts, in the blood and bone marrow.
The peak incidence lies in children ages 2-5 years, and one of the primary
forms of ALL detection is through microscopic blood sample inspection.
Computer-aided leukemia diagnosis has been achieved using many different
approaches in the past years, including deep learning models combined with
transfer learning and unsharpening techniques [6, 7, 8, 9]. Also, it has been
reported in the literature that a quaternion-valued convolutional neural
network exhibited better generalization capability than its corresponding
real-valued model to classify white cells as lymphoblasts [10]. Furthermore,
the quaternion-valued CNN has about 34% of the total number of parameters of
the corresponding real-valued network. This paper investigates further the
application of hypercomplex-valued convolutional neural networks (HvCNN) ALL
detection.

Like complex numbers, quaternions are hypercomplex numbers with a wide range
of applications in science and engineering. For example, quaternions provide
an efficient tool for describing 3D rotations used in computer graphics.
Furthermore, quaternion-valued neural networks have been effectively applied
for signal processing and control [11, 12], image classification [13, 14], and
many other pattern recognition tasks [15, 16]. However, besides the
quaternions, many other hypercomplex-valued algebras exist, including the
coquaternions, the tessarines, Clifford algebras, and Cayley-Dickson algebras.
The tessarines, introduced by Cockle a few years after the introduction of
quaternions, is a commutative hypercomplex algebra that has been effectively
used for signal processing and the development of neural networks [17, 18, 19,
20, 21]. The Clifford algebras comprise a broad family of associative
hypercomplex algebras with interesting geometrical properties [22, 23, 24]. A
family of hypercomplex algebras, obtained from the recursive process of
Cayley-Dickson, can be used to develop effective HvNNs [25, 26]. Furthermore,
four-dimensional hypercomplex algebras have been used for designing neural
networks for controlling a robot manipulator [12].

This paper considers the hypercomplex algebra framework proposed by Kantor and
Solodovnikov [27]. This approach furnishes a broad class of hypercomplex
algebras which comprises the tessarines, the Clifford algebras, and the
Cayley-Dickson algebras. On the downside, the general framework by Kantor and
Solodovnikov also contains many hypercomplex algebras with no attractive
features. Thus, we shall focus only on eight four-dimensional associative
hypercomplex algebras, four of which are commutative. We consider the
tessarines, the bi-complex numbers, and the Klein 4-group algebra among the
commutative algebras [12, 28]. The four non-commutative hypercomplex algebras
include quaternions and coquaternions. Also, they are isomorphic to Clifford
as well as Cayley-Dickson algebras [26, 29].

The paper is organized as follows: Next section presents the basic concepts of
hypercomplex algebras and explores notable four-dimensional algebras. Section
III addresses hypercomplex-valued CNN models and shows how to emulate them
using a real-valued convolutional network. Section IV describes the
computational experiments conducted using the ALL-IDB dataset. The paper
finishes with some concluding remarks in Section V.

##  II Hypercomplex Numbers and Some Notable Associative Four-Dimensional
Algebras

Let us present a few basic definitions regarding hypercomplex numbers.
Hypercomplex algebras can be defined in any field, but we focus on algebras
over the real numbers in this work. As pointed out in the introduction, we
consider the general framework proposed by Kantor and Solodovnikov, which
includes the most used hypercomplex algebras [27]. We finish this section by
presenting eight notable associative four-dimensional hypercomplex algebras.

###  II-A A Brief Review on Hypercomplex Number Systems

A hypercomplex algebra $\mathbb{A}$ of dimension $n+1$ over $\mathbb{R}$ is a
set

$\mathbb{A}=\\{x=x_{0}+x_{1}\boldsymbol{i}_{1}+x_{2}\boldsymbol{i}_{2}+\dots+x_{n}\boldsymbol{i}_{n}:x_{\mu}\in\mathbb{R},\forall\mu\\},$
(1)

equipped with two operations, namely addition and multiplication [27]. The
symbols $\boldsymbol{i}_{\mu}$, with $\boldsymbol{i}_{\mu}\notin\mathbb{R}$
for all $\mu=1,\ldots,n$, denote the so-called hyperimaginary units of
$\mathbb{A}$. The addition of two hypercomplex numbers
$x={x}_{0}+{x}_{1}\boldsymbol{i}_{1}+\dots+{x}_{n}\boldsymbol{i}_{n}$ and
$y={y}_{0}+{y}_{1}\boldsymbol{i}_{1}+\dots+{y}_{n}\boldsymbol{i}_{n}$ is
simply defined as

$x+y=(x_{0}+y_{0})+(x_{1}+y_{1})\boldsymbol{i}_{1}+\ldots+(x_{n}+y_{n})\boldsymbol{i}_{n}.$
(2)

The multiplication operation is carried out distributively and replacing the
product of two hypercomplex units $\boldsymbol{i}_{\mu}$ and
$\boldsymbol{i}_{\nu}$ by an hypercomplex number
$p_{\mu\nu}:=\boldsymbol{i}_{\mu}\boldsymbol{i}_{\nu}$, where

$p_{\mu\nu}={(p_{\mu\nu})}_{0}+{(p_{\mu\nu})}_{1}\boldsymbol{i}_{1}+\dots+{(p_{\mu\nu})}_{n}\boldsymbol{i}_{n}\in\mathbb{A},$
(3)

for all $\mu,\nu=1,\ldots,n$. Precisely, the multiplication of two
hypercomplex numbers is given by the equation

$\displaystyle xy$
$\displaystyle=\left(x_{0}y_{0}+\sum_{\mu,\nu=1}^{n}x_{\mu}y_{\nu}(p_{\mu\nu})_{0}\right)$
(4)
$\displaystyle+\left(x_{0}y_{1}+x_{1}y_{0}+\sum_{\mu,\nu=1}^{n}x_{\mu}y_{\nu}(p_{\mu\nu})_{1}\right)\boldsymbol{i}_{1}+\ldots$
$\displaystyle+\left(x_{0}y_{n}+x_{n}y_{0}+\sum_{\mu,\nu=1}^{n}x_{\mu}y_{\nu}(p_{\mu\nu})_{n}\right)\boldsymbol{i}_{n}.$

Note that hyperimaginary units products characterize a hypercomplex algebra
$\mathbb{A}$. In other words, the hypercomplex numbers $p_{\mu\nu}$ given by
(3) determine $\mathbb{A}$. It is common practice to arrange the hypercomplex
numbers $p_{\mu\nu}$ in a table, called the multiplication table. Examples of
multiplication tables are given in Tables I and II. Algebraic properties of an
hypercomplex algebra $\mathbb{A}$ can be inferred from its multiplication
tables. For example, symmetric multiplication tables represent commutative
hypercomplex algebras [27]. Note that the four multiplication tables in Table
II are symmetric. Thus, they represent commutative hypercomplex algebras. We
will discuss in detail the multiplication tables provided in Tables I and II
in the following subsection.

A scalar $\alpha\in\mathbb{A}$ can be identified with the hypercomplex number
$\alpha=\alpha+0\boldsymbol{i}_{1}+\dots+0\boldsymbol{i}_{n}$, and vice-versa.
Furthermore, from (4), the product by scalar in any algebra $\mathbb{A}$
satisfies

$\alpha x={\alpha x}_{0}+{\alpha x}_{1}\boldsymbol{i}_{1}+\dots+{\alpha
x}_{n}\boldsymbol{i}_{n}.$ (5)

This remark shows that a hypercomplex algebra $\mathbb{A}$ can be identified
with an $(n+1)$-dimensional vector space with the vector addition and the
product by a scalar given by (2) and (5), respectively. Moreover, the basis
elements of such $(n+1)$-dimensional vector space are
$1,\boldsymbol{i}_{1},\ldots,\boldsymbol{i}_{n}$. Besides the addition and the
product by a scalar, a hypercomplex algebra is equipped with the
multiplication of vectors given by (4).

We would like to point out that different multiplication tables do not
necessarily yield different hypercomplex algebras. Precisely, we know from
linear algebra that a vector space can be represented using different bases.
Similarly, a hypercomplex algebra can be obtained from different bases or,
equivalently, using different hypercomplex units. Since the multiplication
table determines the outcome of the product of any two hypercomplex units, a
change of basis results in a different multiplication table. Because of this
remark, we say two hypercomplex algebras $\mathbb{A}$ and
$\mathbb{A}^{\prime}$ are isomorphic if they differ by a change of basis. In
other words, $\mathbb{A}$ and $\mathbb{A}^{\prime}$ are isomorphic
hypercomplex algebras if the multiplication table of $\mathbb{A}^{\prime}$ can
be obtained from the multiplication table of $\mathbb{A}$ through a change of
basis.

###  II-B Four-dimensional Hypercomplex Algebras

Let us now focus on four-dimensional hypercomplex algebras, i.e., hypercomplex
algebras of the form

$\mathbb{A}=\\{x={x}_{0}+{x}_{1}\boldsymbol{i}+{x}_{2}\boldsymbol{j}+{x}_{3}\boldsymbol{k}:x_{0},\ldots,x_{3}\in\mathbb{R}\\},$
(6)

where $\boldsymbol{i}\equiv\boldsymbol{i}_{1}$,
$\boldsymbol{j}\equiv\boldsymbol{i}_{2}$, and
$\boldsymbol{k}\equiv\boldsymbol{i}_{3}$ are the three hypercomplex units.
Four-dimensional hypercomplex algebras are particularly useful for image
processing because a color can be represented using a single hypercomplex
number. In other words, four-dimensional hypercomplex algebras allows
representing a color by a single entity.

Note that the hypercomplex numbers
$p_{\mu\nu}={(p_{\mu\nu})}_{0}+{(p_{\mu\nu})}_{1}\boldsymbol{i}+{(p_{\mu\nu})}_{2}\boldsymbol{j}+{(p_{\mu\nu})}_{3}\boldsymbol{k}$
in the multiplication table results in a large number of algebras. Some of
these algebras are isomorphic, and many of them have no attractive features.
Therefore, we present a construction rule that yields eight associative four-
dimensional hypercomplex algebras in the following.

Like in the construction of Clifford algebras [30], we assume the product of
hypercomplex units is associative. Furthermore, we let the identity

$\boldsymbol{k}=\boldsymbol{i}\boldsymbol{j},$ (7)

hold true. Finally, we assume the four-dimensional hypercomplex algebra is
either commutative or anti-commutative.

####  II-B1 Anticommutative Algebras

We obtain an anticommutative four-dimensional hypercomplex algebra by imposing
$\boldsymbol{i}\boldsymbol{j}=-\boldsymbol{j}\boldsymbol{i}$. From the
associativity and (7), we obtain

$\displaystyle\boldsymbol{k}^{2}$
$\displaystyle=(\boldsymbol{i}\boldsymbol{j})(\boldsymbol{i}\boldsymbol{j})=\boldsymbol{i}(\boldsymbol{j}\boldsymbol{i})\boldsymbol{j}=\boldsymbol{i}(-\boldsymbol{i}\boldsymbol{j})\boldsymbol{j}=-\boldsymbol{i}^{2}\boldsymbol{j}^{2},$
(8) $\displaystyle\boldsymbol{i}\boldsymbol{k}$
$\displaystyle=\boldsymbol{i}(\boldsymbol{i}\boldsymbol{j})=\boldsymbol{i}^{2}\boldsymbol{j},$
(9) $\displaystyle\boldsymbol{j}\boldsymbol{k}$
$\displaystyle=\boldsymbol{j}(\boldsymbol{i}\boldsymbol{j})=\boldsymbol{j}(-\boldsymbol{j}\boldsymbol{i})=-\boldsymbol{j}^{2}\boldsymbol{i}.$
(10)

To simplify the exposition, let $\boldsymbol{i}^{2}=\gamma_{1}$ and
$\boldsymbol{j}^{2}=\gamma_{2}$. From (7)-(10), we obtain an associative and
anticommutative four-dimensional algebra denoted by
$A[\gamma_{1},\gamma_{2}]$, whose multiplication table is then

$A[\gamma_{1},\gamma_{2}]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $\gamma_{1}$ | $\boldsymbol{k}$ | $\gamma_{1}\boldsymbol{j}$
$\boldsymbol{j}$ | $-\boldsymbol{k}$ | $\gamma_{2}$ | $-\gamma_{2}\boldsymbol{i}$
$\boldsymbol{k}$ | $-\gamma_{1}\boldsymbol{j}$ | $\gamma_{2}\boldsymbol{i}$ | $-\gamma_{1}\gamma_{2}$
(11)

By considering $\gamma_{1},\gamma_{2}\in\\{-1,+1\\}$, we obtain the four-
dimensional hypercomplex algebras $A[-1,-1]$, $A[-1,+1]$, $A[+1,-1]$, and
$A[+1,+1]$ whose multiplication tables are depicted in Table I.

TABLE I: Multiplication tables of the anticommutative algebras. Quaternions | $C\ell_{2,0}$ | Coquaternions | $C\ell_{1,1}$
---|---|---|---
| $A[-1,-1]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $-1$ | $\boldsymbol{k}$ | $-\boldsymbol{j}$
$\boldsymbol{j}$ | $-\boldsymbol{k}$ | $-1$ | $\boldsymbol{i}$
$\boldsymbol{k}$ | $\boldsymbol{j}$ | $-\boldsymbol{i}$ | $-1$
| $A\left[+1,+1\right]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $1$ | $\boldsymbol{k}$ | $\boldsymbol{j}$
$\boldsymbol{j}$ | $-\boldsymbol{k}$ | $1$ | $-\boldsymbol{i}$
$\boldsymbol{k}$ | $-\boldsymbol{j}$ | $\boldsymbol{i}$ | $-1$
| $A\left[-1,+1\right]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $-1$ | $\boldsymbol{k}$ | $-\boldsymbol{j}$
$\boldsymbol{j}$ | $-\boldsymbol{k}$ | $1$ | $-\boldsymbol{i}$
$\boldsymbol{k}$ | $\boldsymbol{j}$ | $\boldsymbol{i}$ | $1$
| $A\left[+1,-1\right]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $1$ | $\boldsymbol{k}$ | $\boldsymbol{j}$
$\boldsymbol{j}$ | $-\boldsymbol{k}$ | $-1$ | $\boldsymbol{i}$
$\boldsymbol{k}$ | $-\boldsymbol{j}$ | $-\boldsymbol{i}$ | $1$
TABLE II: Multiplication tables of commutative algebras. Bicomplex numbers |  | Tessarines | Klein 4-group
---|---|---|---
| $B[-1,-1]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $-1$ | $\boldsymbol{k}$ | $-\boldsymbol{j}$
$\boldsymbol{j}$ | $\boldsymbol{k}$ | $-1$ | $-\boldsymbol{i}$
$\boldsymbol{k}$ | $-\boldsymbol{j}$ | $-\boldsymbol{i}$ | $1$
| $B[+1,-1]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $1$ | $\boldsymbol{k}$ | $\boldsymbol{j}$
$\boldsymbol{j}$ | $\boldsymbol{k}$ | $-1$ | $-\boldsymbol{i}$
$\boldsymbol{k}$ | $\boldsymbol{j}$ | $-\boldsymbol{i}$ | $-1$
| $B[-1,+1]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $-1$ | $\boldsymbol{k}$ | $-\boldsymbol{j}$
$\boldsymbol{j}$ | $\boldsymbol{k}$ | $1$ | $\boldsymbol{i}$
$\boldsymbol{k}$ | $-\boldsymbol{j}$ | $\boldsymbol{i}$ | $-1$
| $B[+1,+1]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $1$ | $\boldsymbol{k}$ | $\boldsymbol{j}$
$\boldsymbol{j}$ | $\boldsymbol{k}$ | $1$ | $\boldsymbol{i}$
$\boldsymbol{k}$ | $\boldsymbol{j}$ | $\boldsymbol{i}$ | $1$

######  Remark 1.

The hypercomplex algebra $A[-1,-1]$ coincides with the quaternions because
they have the same multiplication table. The algebra $A[-1,+1]$ corresponds to
the co-quaternions, also known as split-quaternions [12]. Similarly,
$A[+1,+1]$ and $A[+1,-1]$ can be identified with the Clifford algebras
$C\ell_{2,0}$ and $C\ell_{1,1}$, respectively. Furthermore, the algebras
$A[-1,+1]$, $A[+1,-1]$, and $A[+1,+1]$ are all isomorphic. Finally, we would
like to remark that the algebras $A[-1,-1]$, $A[-1,+1]$, $A[+1,-1]$, and
$A[+1,+1]$ can be derived using the generalized Cayley-Dickson process [25,
26].

####  II-B2 Commutative Algebras

In a similar fashion, we impose the condition
$\boldsymbol{i}\boldsymbol{j}=\boldsymbol{j}\boldsymbol{i}$ to obtain the
commutative four-dimensional hypercomplex algebras. Again, using associativity
and (7), we are able to write the identities

$\displaystyle\boldsymbol{k}^{2}$
$\displaystyle=(\boldsymbol{i}\boldsymbol{j})(\boldsymbol{i}\boldsymbol{j})=\boldsymbol{i}(\boldsymbol{j}\boldsymbol{i})\boldsymbol{j}=\boldsymbol{i}(\boldsymbol{i}\boldsymbol{j})\boldsymbol{j}=\boldsymbol{i}^{2}\boldsymbol{j}^{2},$
(12) $\displaystyle\boldsymbol{i}\boldsymbol{k}$
$\displaystyle=\boldsymbol{i}(\boldsymbol{i}\boldsymbol{j})=\boldsymbol{i}^{2}\boldsymbol{j},$
(13) $\displaystyle\boldsymbol{j}\boldsymbol{k}$
$\displaystyle=\boldsymbol{j}(\boldsymbol{i}\boldsymbol{j})=\boldsymbol{j}(\boldsymbol{j}\boldsymbol{i})=\boldsymbol{j}^{2}\boldsymbol{i}.$
(14)

By expressing $\boldsymbol{i}^{2}=\gamma_{1}$ and
$\boldsymbol{j}^{2}=\gamma_{2}$, we obtain a commutative hypercomplex algebra
$B[\gamma_{1},\gamma_{2}]$ whose multiplication table is

$B[\gamma_{1},\gamma_{2}]$ | $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $\gamma_{1}$ | $\boldsymbol{k}$ | $\gamma_{1}\boldsymbol{j}$
$\boldsymbol{j}$ | $\boldsymbol{k}$ | $\gamma_{2}$ | $\gamma_{2}\boldsymbol{i}$
$\boldsymbol{k}$ | $\gamma_{1}\boldsymbol{j}$ | $\gamma_{2}\boldsymbol{i}$ | $\gamma_{1}\gamma_{2}$
(15)

Analogously, we end up with the four-dimensional algebras
$B[-1,-1],B[-1,+1],B[+1,-1],B[+1,+1]$ by taking
$\gamma_{1},\gamma_{2}\in\\{-1,+1\\}$. Table II contains the multiplication
table of these four algebras.

######  Remark 2.

Because they have the same multiplication table, the hypercomplex algebra
$B[-1,+1]$ corresponds to the tessarines, also known as commutative
quaternions [19, 17]. Similarly, the algebra $B[-1,-1]$ corresponds to the bi-
complex numbers [12] while $B[+1,+1]$ is equivalent to the Klein 4-group, a
commutative algebra of great interest in symmetric group theory [28]. Finally,
we would like to point out that the algebras $B[-1,-1]$ and $B[+1,-1]$ can be
both obtained from $B[-1,+1]$ by a change of bases. Therefore, the three
algebras $B[-1,-1]$, $B[+1,-1]$ and $B[-1,+1]$ are all isomorphic.

Concluding, we have a total of eight four-dimensional hypercomplex algebras.
All of them are associative, four are anticommutative and the remaining are
commutative. Furthermore, the hypercomplex units are well structured in their
multiplication table. Precisely, their multiplication table can be written as
follows

| $\boldsymbol{i}$ | $\boldsymbol{j}$ | $\boldsymbol{k}$
---|---|---|---
$\boldsymbol{i}$ | $s_{11}$ | $s_{12}\boldsymbol{k}$ | $s_{13}\boldsymbol{j}$
$\boldsymbol{j}$ | $s_{21}\boldsymbol{k}$ | $s_{22}$ | $s_{23}\boldsymbol{i}$
$\boldsymbol{k}$ | $s_{31}\boldsymbol{j}$ | $s_{32}\boldsymbol{i}$ | $s_{33}$
(16)

where $s_{ij}\in\\{-1,+1\\}$, for all $i,j=1,\ldots,3$, depends on the
parameters $\gamma_{1}$ and $\gamma_{2}$ as well as on the commutativity or
anticommutativity of the multiplication. The multiplication table (16) helped
us to efficiently implement convolutional neural networks based on the eight
hypercomplex algebras presented in this section. We detail this remark in the
following section.

##  III Hypercomplex-valued Convolutional Neural Networks (HvCNN)

Convolutional layers are crucial building blocks of convolutional neural
networks. The main strength of convolutional layers is their ability to
process data locally and, thus, learn local patterns. Convolutional neural
networks have been widely applied to image processing tasks [31]. Let us
briefly describe a real-valued convolutional layer.

###  III-A Real-valued Convolutional Layers

Suppose a convolutional layer is fed by a real-valued image $\mathbf{I}$ with
$C$ feature channels. Let $\mathbf{I}(p,c)\in\mathbb{R}$ denote the intensity
of the $c$th channel of the image $\mathbf{I}$ at pixel $p$. The neurons of a
convolutional layer are parameterized structures called filters. The filters
have the same number $C$ of channels as the image $\mathbf{I}$. Let $D$,
commonly a rectangular grid, denote the domain of the filters. Also, let the
weights of a convolutional layer with $K$ real-valued filters be arranged in
an array $\mathbf{F}$ such that $\mathbf{F}(q,c,k)$ denotes the value of the
$c$th channel of the $k$th filter at the point $q\in D$, for $c=1,\ldots,C$
and $k=1,\ldots,K$. A convolutional layer with $K$ filters yields a real-
valued image $\mathbf{J}$ with $K$ feature channels obtained by evaluating an
activation function on the addition of a bias term and the convolution of the
image $\mathbf{I}$ by each of the $K$ filters. Precisely, let
$(\mathbf{I}\ast\mathbf{F})(p,k)$ denote the convolution of the image
$\mathbf{I}$ by the $k$th filter at pixel $p$. Intuitively,
$(\mathbf{I}\ast\mathbf{F})(p,k)$ is the sum of the multiplication of the
weights of the $k$th filter and the intensities of the pixels of the image in
a window characterized by the translation of $p$ by $S(q)$, for $q\in D$. The
term $S(q)$, for $q$ in the domain $D$ of the filter, represents a translation
that can take vertical and horizontal strides into account. In mathematical
terms, the convolution of the image $\mathbf{I}$ by the $k$th filter at pixel
$p$ is given by

$(\mathbf{I}\ast\mathbf{F})(p,k)=\sum_{c=1}^{C}\sum_{q\in
D}\mathbf{I}\big{(}p+S(q),c\big{)}\mathbf{F}(q,c,k).$ (17)

Moreover, the intensity of the $k$th feature channel of the output of a
convolutional layer at pixel $p$ is defined by

$\mathbf{J}(p,k)=\varphi\left(b(k)+(\mathbf{I}\ast\mathbf{F})(p,k)\right),$
(18)

where $\varphi:\mathbb{R}\to\mathbb{R}$ denotes the activation function.

###  III-B Hypercomplex-valued Convolutional Layers

The hypercomplex-valued convolutional layer is defined analogously to the
real-valued convolutional layer by replacing the real numbers and operations
with their corresponding hypercomplex versions in (17) and (18) [32, 33].
Precisely, the “intensity” of the $k$th channel of the hypercomplex-valued
output image $\mathbf{J}^{(h)}$ at pixel $p$ is given by

$\mathbf{J}^{(h)}(p,k)=\varphi_{\mathbb{A}}\left(b^{(h)}(k)+(\mathbf{I}^{(h)}\ast\mathbf{F}^{(h)})(p,k)\right),$
(19)

where $\varphi_{\mathbb{A}}:\mathbb{A}\to\mathbb{A}$ is a hypercomplex-valued
activation function, $b_{k}^{(h)}\in\mathbb{A}$ is the bias term, and

$(\mathbf{I}^{(h)}\ast\mathbf{F}^{(h)})(p,k)=\sum_{c=1}^{C}\sum_{q\in
D}\mathbf{I}^{(h)}(p+S(q),c)\mathbf{F}^{(h)}(q,c,k),$ (20)

is the convolution of $\mathbf{I}^{(h)}$ by the $k$th hypercomplex-valued
filter at pixel $p$. In this paper, we only consider split-functions defined
using a real-valued function $\varphi:\mathbb{R}\to\mathbb{R}$ as follows for
all
$x\in{x}_{0}+{x}_{1}\boldsymbol{i}_{1}+\dots+{x}_{n}\boldsymbol{i}_{n}\in\mathbb{A}$:

$\varphi_{\mathbb{A}}(x)=\varphi(x_{0})+\varphi(x_{1})\boldsymbol{i}_{1}+\ldots+\varphi(x_{n})\boldsymbol{i}_{n}.$
(21)

###  III-C Emulating Hypercomplex-valued Convolutional Layers

Since most deep neural network libraries are designed for real-valued inputs,
we show how to emulate a four-dimensional hypercomplex-valued convolutional
layer using a real-valued convolutional layer. The reasoning is quite similar
to the approaches reported in the literature for complex- and quaternion-
valued deep networks [32, 33].

First, an image $\mathbf{I}^{(h)}$ with $C$ channels defined on a four-
dimensional hypercomplex algebra can be represented by

$\mathbf{I}^{(h)}={\mathbf{I}}_{0}+{\mathbf{I}}_{1}\boldsymbol{i}+{\mathbf{I}}_{2}\boldsymbol{j}+{\mathbf{I}}_{3}\boldsymbol{k},$
(22)

where $\mathbf{I}_{0}$, $\mathbf{I}_{1}$, $\mathbf{I}_{2}$, and
$\mathbf{I}_{3}$ are real-valued images with $C$ channels. Similarly, a bank
of $K$ hypercomplex-valued filters can be represented by

$\mathbf{F}^{(h)}=\mathbf{F}_{0}+\mathbf{F}_{1}\boldsymbol{i}+\mathbf{F}_{2}\boldsymbol{j}+\mathbf{F}_{3}\boldsymbol{k},$
(23)

where $\mathbf{F}_{0}$, $\mathbf{F}_{1}$, $\mathbf{F}_{2}$, and
$\mathbf{F}_{3}$ are real-valued arrays representing each a bank of $K$
filters with domain $D$ and $C$ feature channels. From the multiplication
table (16) and omitting the arguments $(p+S(q),c)$ and $(q,c,k)$ to simplify
the notation, we obtain

$\displaystyle\mathbf{I}^{(h)}(p+S(q),c)\mathbf{F}^{(h)}(q,c,k)$
$\displaystyle=({\mathbf{I}}_{0}+{\mathbf{I}}_{1}\boldsymbol{i}+{\mathbf{I}}_{2}\boldsymbol{j}+{\mathbf{I}}_{3}\boldsymbol{k})(\mathbf{F}_{0}+\mathbf{F}_{1}\boldsymbol{i}+\mathbf{F}_{2}\boldsymbol{j}+\mathbf{F}_{3}\boldsymbol{k})$
$\displaystyle=\mathbf{I}_{0}\mathbf{F}_{0}+s_{11}\mathbf{I}_{1}\mathbf{F}_{1}+s_{22}\mathbf{I}_{2}\mathbf{F}_{2}+s_{33}\mathbf{I}_{3}\mathbf{F}_{3}$
$\displaystyle\;+(\mathbf{I}_{0}\mathbf{F}_{1}+\mathbf{I}_{1}\mathbf{F}_{0}+s_{23}\mathbf{I}_{2}\mathbf{F}_{3}+s_{32}\mathbf{I}_{3}\mathbf{F}_{2})\boldsymbol{i}$
$\displaystyle\;+(\mathbf{I}_{0}\mathbf{F}_{2}+s_{13}\mathbf{I}_{1}\mathbf{F}_{3}+\mathbf{I}_{2}\mathbf{F}_{0}+s_{31}\mathbf{I}_{3}\mathbf{F}_{1})\boldsymbol{j}$
$\displaystyle\;+(\mathbf{I}_{0}\mathbf{F}_{3}+s_{12}\mathbf{I}_{1}\mathbf{F}_{2}+s_{21}\mathbf{I}_{2}\mathbf{F}_{1}+\mathbf{I}_{3}\mathbf{F}_{0})\boldsymbol{k}$

Therefore, the real-part of the convolution given by (20) satisfies the
equation

$\displaystyle\big{(}\mathbf{I}^{(h)}\ast\mathbf{F}^{(h)}\big{)}_{0}(p,k)$
$\displaystyle=\sum_{c=1}^{C}\sum_{q\in
D}\Big{[}\mathbf{I}_{0}(p+S(q),c)\mathbf{F}_{0}(q,c,k)$
$\displaystyle\;+s_{11}\mathbf{I}_{1}(p+S(q),c)\mathbf{F}_{1}(q,c,k)$ (24)
$\displaystyle\;+s_{22}\mathbf{I}_{2}(p+S(q),c)\mathbf{F}_{2}(q,c,k)$
$\displaystyle\;+s_{33}\mathbf{I}_{3}(p+S(q),c)\mathbf{F}_{3}(q,c,k)\Big{]},$

Equivalently, the real-part of the convolution of the image $\mathbf{I}^{(h)}$
by the $k$th hypercomplex-valued filter at pixel $p$ can be computed using the
real-valued convolution

$\big{(}\mathbf{I}^{(h)}\ast\mathbf{F}^{(h)}\big{)}_{0}(p,k)=\big{(}\mathbf{I}^{(r)}\ast\mathbf{F}_{0}^{(r)}\big{)}(p,k),$
(25)

where $\mathbf{I}^{(r)}$ is the real-valued image with $4C$ features channels
obtained by concatenating the real and imaginary parts of $\mathbf{I}^{(h)}$
as follows

$\mathbf{I}^{(r)}(p,:)=[\mathbf{I}_{0}(p,:),\mathbf{I}_{1}(p,:),\mathbf{I}_{2}(p,:),\mathbf{I}_{3}(p,:)],$
(26)

for all pixels $p$, and $\mathbf{F}_{0}^{(r)}$ is the real-valued filter
defined by

$\displaystyle\mathbf{F}^{(r)}_{0}(q,1:C,k)=\mathbf{F}_{0}(q,1:C,k),$ (27)
$\displaystyle\mathbf{F}^{(r)}_{0}(q,C+1:2C,k)=s_{11}\mathbf{F}_{1}(q,1:C,k),$
(28)
$\displaystyle\mathbf{F}^{(r)}_{0}(q,2C+1:3C,k)=s_{22}\mathbf{F}_{2}(q,1:C,k),$
(29)
$\displaystyle\mathbf{F}^{(r)}_{0}(q,3C+1:4C,k)=s_{33}\mathbf{F}_{3}(q,1:C,k),$
(30)

for all $q\in D$ and $k=1,\ldots,K$. For short, the notation

$\mathbf{F}^{(r)}_{0}=[\mathbf{F}_{0},s_{11}\mathbf{F}_{1},s_{22}\mathbf{F}_{2},s_{33}\mathbf{F}_{3}],$
(31)

means that $\mathbf{F}^{(r)}_{0}$ is obtained by concatenating
$\mathbf{F}_{0}$, $s_{11}\mathbf{F}_{1}$, $s_{22}\mathbf{F}_{2}$, and
$s_{33}\mathbf{F}_{3}$ as prescribed above. Note from (17) that

$\displaystyle\big{(}\mathbf{I}^{(r)}\ast\mathbf{F}_{0}^{(r)}\big{)}(p,k)=\sum_{c=1}^{4C}\sum_{q\in
D}\mathbf{I}^{(r)}\big{(}p+S(q),c\big{)}\mathbf{F}_{0}^{(r)}(q,c,k)$
$\displaystyle\quad=\sum_{q\in
D}\Bigg{[}\sum_{c=1}^{C}\mathbf{I}^{(r)}\big{(}p+S(q),c\big{)}\mathbf{F}_{0}^{(r)}(q,c,k)+\ldots$
$\displaystyle\qquad+\sum_{c=3C+1}^{4C}\mathbf{I}^{(r)}\big{(}p+S(q),c\big{)}\mathbf{F}_{0}^{(r)}(q,c,k)\Bigg{]}$
$\displaystyle\quad=\sum_{q\in
D}\Bigg{[}\sum_{c=1}^{C}\mathbf{I}_{0}\big{(}p+S(q),c\big{)}\mathbf{F}_{0}(q,c,k)+\ldots$
$\displaystyle\qquad+\sum_{c^{\prime}=1}^{C}s_{33}\mathbf{I}_{3}\big{(}p+S(q),c^{\prime}\big{)}\mathbf{F}_{3}(q,c^{\prime},k)\Bigg{]},$

which coincides with
$\big{(}\mathbf{I}^{(h)}\ast\mathbf{F}^{(h)}\big{)}_{0}(p,k)$ given by (24).
Therefore, using a split-function, the real-part $\mathbf{J}_{0}(p,k)$ of the
output $\mathbf{J}^{(h)}(p,k)$ of the hypercomplex-valued convolutional layer
given by (20) can be computed using a real-valued convolutional layer as
follows

$\mathbf{J}_{0}(p,k)=\varphi\Big{(}b_{0}(k)+\big{(}\mathbf{I}^{(r)}\ast\mathbf{F}_{0}^{(r)}\big{)}(p,k)\big{)},$
(32)

where the bias term $b_{0}(k)$ corresponds to the real-part of $b(k)$ while
$\mathbf{I}^{(r)}$ and $\mathbf{F}_{0}^{(r)}$ are given by (26) and (31),
respectively. In a similar vein, the three imaginary parts
$\mathbf{J}_{1}(p,k)$, $\mathbf{J}_{2}(p,k)$, and $\mathbf{J}_{3}(p,k)$ of the
$k$th channel of the hypercomplex-valued image $\mathbf{J}^{(h)}$ at pixel $p$
can be computed using real-valued convolutional layers with bias terms
$b_{1}(k)$, $b_{2}(k)$, and $b_{3}(k)$ and real-valued filters

$\displaystyle\mathbf{F}^{(r)}_{1}=[\mathbf{F}_{1},\mathbf{F}_{0},s_{23}\mathbf{F}_{3},s_{32}\mathbf{F}_{2}],$
(33)
$\displaystyle\mathbf{F}^{(r)}_{2}=[\mathbf{F}_{2},s_{13}\mathbf{F}_{3},\mathbf{F}_{0},s_{31}\mathbf{F}_{1}],$
(34)
$\displaystyle\mathbf{F}^{(r)}_{3}=[\mathbf{F}_{3},s_{12}\mathbf{F}_{2},s_{21}\mathbf{F}_{1},\mathbf{F}_{0}],$
(35)

respectively.

We would like to finish this section with few remarks: First, emulating a
hypercomplex-valued convolutional layer allow us to take advantage of open-
source deep libraries such as Tensorflow and PyTorch for python and Flux for
Julia Language. Consequently, hypercomplex-valued versions of well-known deep
neural networks can be implemented in current deep learning libraries. On top
of that, although not properly designed for hypercomplex-valued models,
pooling layers, sophisticated optimizers, and speed-up training techniques
such as batch normalization and weight initialization can be incorporated as
the first attempt into hypercomplex-valued deep networks. In the following
section, we consider a hypercomplex-valued deep neural network for the
classification of lymphocytes from smear blood images that resembles the LeNet
architecture [34].

##  IV Lymphoblast Image Classification Task

One of the primary forms of diagnosis of acute lymphoblastic leukemia (ALL) is
through microscopic blood smear image inspection [6, 7, 8, 9]. Precisely,
physicians diagnose ALL by the presence of many lymphoblasts in a blood smear
image in which white cells are stained with bluish-purple coloration. A
candidate cell image is selected, cut from the blood smear image, and fed into
a machine learning classifier for a computer-aided leukemia diagnosis. For
illustrative purposes, Fig. 1 shows two candidate cell images used in such a
classification task.

a) Probable lymphoblast | b) Healthy cell
---|---
|
Figure 1: Examples of candidate cells for the classification task. Images from
the ALL-IDB dataset [35].

The classifier predicts if the candidate image is a lymphoblast in the
simplest binary case.

In our model, the candidate images have $100\times 100$ pixels and have been
saved using either the RGB (red-green-blue) or the HSV (hue-saturation-value)
color encodings. Using the RGB encoding, an image is characterized by the
intensities of red (R), green (G), and blue (B), respectively. An RGB encoded
image has been mapped into a hypercomplex-valued image
$\mathbf{I}^{(h)}_{RGB}$ by means of the equation

$\mathbf{I}^{(h)}_{RGB}=R\boldsymbol{i}+G\boldsymbol{j}+B\boldsymbol{k}.$ (36)

Similarly, a HSV-encoded image is characterized by the hue $H\in[0,2\pi)$, the
value $V\in[0,1]$, and the saturation $S\in[0,1]$. A hypercomplex-valued image
$\mathbf{I}^{(h)}_{HSV}$ is derived from an HSV-encoded image as follows [10]:

$\mathbf{I}^{(h)}_{HSV}=\big{(}\cos(H)+\sin(H)\boldsymbol{i}\big{)}(S+V\boldsymbol{j}).$
(37)

Note that, because $\boldsymbol{i}\boldsymbol{j}=\boldsymbol{k}$ in all the
considered hypercomplex algebras, (37) is equivalent to

$\mathbf{I}^{(h)}_{HSV}=S\cos(H)+S\sin(H)\boldsymbol{i}+V\cos(H)\boldsymbol{j}+V\sin(H)\boldsymbol{k}.$
(38)

We performed the lymphocyte classification task using real-valued CNNs
(RvCNNs) and the proposed HvCNNs. Similar architectures are adopted for both
real- and hypercomplex-valued models, as suggested in [10]. The RvCNN features
three convolutional layers with $3\times 3$ filters followed by a max-pooling
layer with $2\times 2$ kernels. A dense layer with 1 unit yields the output.
The hypercomplex-valued models have the same layer layout but a much smaller
number of filters per convolution layer because each hypercomplex-valued
channel is equivalent to four real-valued feature channels. The activation
function adopted for all convolutional layers is the rectified linear unit
(ReLU). The dense layer for both architectures is a single neuron that outputs
the label $0$ for a healthy white cell and $1$ for a lymphoblast image. Table
III shows a breakdown of total parameters per layer for each architecture. All
deep network models in this work were implemented using the python libraries
Keras and Tensorflow. The source codes are available at
https://github.com/mevalle/Hypercomplex-valued-Convolutional-Neural-Networks.

TABLE III: Parameter distribution per layer for each architecture. |  | RvCNN | HvCNN
---|---|---|---
Conv Layer 1 | (3,3) filters | 32 | 8
Parameters | 896 | 320
Conv Layer 2 | (3,3) filters | 64 | 16
Parameters | 18,496 | 4,672
Conv Layer 3 | (3,3) filters | 128 | 32
Parameters | 73,856 | 18,560
Dense Layer | Units | 1 | 1
Parameters | 12,801 | 12,801
Total |  | 106,049 | 36,353

###  IV-A Computational Experiments

Let us now describe the outcome of the computational experiments performed
using the acute lymphoblastic leukemia image database (ALL-IDB), a popular
public dataset for segmentation and classification tasks directed at ALL
detection [35]. The ALL-image database (ALL-IDB) consists of two sets of
images. The ALL-IDB1 contains 108 blood smear images for segmentation and
classification tasks. The ALL-IDB2 contains 260 segmented images, each
containing a single blood element like the images depicted in Fig. 1, and is
aimed exclusively for the classification task [35].

We used all the 260 images from the ALL-IDB2 dataset in our computational
experiments. Like Genovese et al. [7, 8], we randomly split the dataset into
the training and test sets containing each 50% of the total number of images.
The training set is enlarged using horizontal and vertical flips. We conducted
100 simulations per experiment. Each simulation consists of splitting training
and test set, augmenting the training set, initializing the network
parameters, training for 100 epochs using ADAM optimizer and the binary cross-
entropy loss function, and predicting test images. We evaluate the
performances using the accuracy score in the test set.

We derive a total of 18 network configurations using the real numbers and the
eight hypercomplex algebras detailed in Section II. Namely, each of the nine
models (1 RvCNN and 8 HvCNNs) is used in the classification tasks of both RGB
and HSV encoded image sets. The box plots depicted in Fig. 2 summarize the
outcome of the computational experiment.

a) RGB-encoded images | b) HSV-encoded images
---|---
|
Figure 2: Boxplot of test set accuracies produced by real-valued and
hypercomplex-valued neural networks.

Note that all models performed well for the RGB encoded images, with medians
close to $95\%$ accuracy except for the HvCNN based on the algebra $B[-1,+1]$
that yields a median accuracy rate of $93.8\%$. In the HSV case, however,
performances vary more drastically. The real-valued model exhibits poor
performance compared to all the hypercomplex-valued ones, with a median
accuracy rate of $91.5\%$. The HvCNNs based on the algebras $A[-1,-1]$,
$B[-1,-1]$, and $B[-1,+1]$ yielded all a median accuracy score of $96.2\%$
while the HvCNN based on the algebra $B[+1,-1]$ achieved a median accuracy
score of $96.5\%$. Moreover, the HvCNNs based on the isomorphic algebras
$A[-1,+1]$, $A[+1,-1]$, and $A[+1,+1]$ as well as the HvCNN based on
$B[+1,+1]$ yielded all a median accuracy score of $96.9\%$. The significant
improvement in the accuracy scores of the HvCNN models indicates they can take
advantage of the locally cohesive structure of the HSV encoding.

Figure 3: Hasse diagram of representative experiment configurations.

To better depict the outcome of this computational experiment, we summarize
the performance of the network classifiers in the Hasse diagram shown in Fig.
3. This figure depicts a single HvCNN model of each isomorphic hypercomplex
algebra group to simplify the exposition. Precisely, Fig. 3 compares the
performance of the HvCNNs based on the hypercomplex algebras $A[-1,-1]$
(quaternions), $A[-1,+1]$ (coquaternions), $B[-1,+1]$ (tessarines), $B[+1,+1]$
(Klein 4-group), along with the real-valued models. In this diagram, a solid
line connecting two models indicates that the one above achieved better
performance than the one below, with a confidence level of 0.99 according to a
Student’s t-test. In other words, models higher up in the diagram perform
significantly better than those on the lower end. Furthermore, the solid lines
indicate a transitive relation. Thus, if model A is better than B and B is
better than C, then A is better than C. First off, Fig. 3 confirms that the
HvCNN models performed better using the HSV than the RGB encoding, and HvCNNs
on HSV encoded images outperform the real-valued models on both encodings. In
addition, it shows the real-valued model on HSV encoded images as the poorest
performer. Moreover, coquaternion- and tessarine-based HvCNNs outperformed the
HvCNN based on quaternions, the four-dimensional algebra most widely used in
applications. At this point, we would like to recall that superior performance
of neural networks based on non-usual hypercomplex algebras has been
previously reported in the literature [26, 29], despite quaternion-based
neural network yielding better performance in applications like controlling a
robot manipulator [12].

Finally, we would like to recall that Genovese et al. obtained average
accuracy rates of $97.92\%$ using a ResNet18 combined with histopathological
transfer learning [7]. The top-performing HvCNNs achieved average accuracy
scores of $96.51\%$ and $96.39\%$. However, in contrast to the ResNet18
network with approximately 11.4M parameters, the HvCNNs have only 36K
trainable parameters. In particular, the coquaternion-valued HvCNN with HSV
encoding achieved $98\%$ of the average accuracy score of the ResNet18 with
transfer learning but with only $0.3\%$ of its total number of trainable
parameters.

##  V Concluding Remarks

In this work, we extended the concept of a quaternion-valued CNN to general
hypercomplex algebras. We constructed eight such algebras with desirable
properties according to Kantor and Solodovnikov framework. These algebras are
isomorphic to well-known four-dimensional algebras: quaternions,
coquaternions, tessarines, Klein 4-group, Cayley-Dickson algebras, and
Clifford algebras. The hypercomplex-valued neural networks have been applied
for lymphoblast image classification.

Using the public dataset ALL-IDB2, we conducted experiments featuring real-
valued and hypercomplex-valued models. We observed that the HvCNNs performed
similarly to the real-valued models in the RGB-encoded images while
outperforming the RvCNNs with HSV-encoded images. The superior performance of
the HvCNN indicates that they take better advantage of the HSV color system,
which is more akin to human vision and more widely used in computer vision
applications [36]. Consequently, HvCNN models seem more efficient at
comprising information in its filters and four-dimensional entities than the
real-valued models. Moreover, coquaternion- and tessarine-valued models
outperformed the quaternion-valued CNNs. Lastly, the performance attained by
the top-performing HvCNN models is significant and comparable to notable
results in the literature. Indeed, Genovese et al. observed an average
accuracy score of $97.92\%$ with the ResNet18, a deep network containing
around 11 million parameters [7]. The coquaternion-valued CNN yielded an
average accuracy of $96.51\%$ with approximately $0.3\%$ of the total of
trainable parameters of the real-valued ResNet18.

## References

  * [1] L. H. Eadie, P. Taylor, and A. P. Gibson, “A systematic review of computer-assisted diagnosis in diagnostic cancer imaging,” _European journal of radiology_ , vol. 81, no. 1, pp. e70–e76, 2012.
  * [2] C. R. Pereira, D. R. Pereira, S. A. Weber, C. Hook, V. H. C. de Albuquerque, and J. P. Papa, “A survey on computer-assisted parkinson’s disease diagnosis,” _Artificial intelligence in medicine_ , vol. 95, pp. 48–63, 2019\.
  * [3] W. Qian, L. P. Clarke, B. Zheng, M. Kallergi, and R. Clark, “Computer assisted diagnosis for digital mammography,” _IEEE Engineering in Medicine and Biology Magazine_ , vol. 14, no. 5, pp. 561–569, 1995.
  * [4] D. Leaper, J. C. Horrocks, J. Staniland, and F. De Dombal, “Computer-assisted diagnosis of abdominal pain using “estimates” provided by clinicians,” _Br Med J_ , vol. 4, no. 5836, pp. 350–354, 1972.
  * [5] H. T. Salah, I. N. Muhsen, M. E. Salama, T. Owaidah, and S. K. Hashmi, “Machine learning applications in the diagnosis of leukemia: Current trends and future directions,” _International Journal of Laboratory Hematology_ , vol. 41, no. 6, pp. 717–725, 12 2019.
  * [6] N. Bibi, M. Sikandar, I. U. Din, A. Almogren, and S. Ali, “Iomt-based automated detection and classification of leukemia using deep learning,” _Journal of Healthcare Engineering_ , 2020.
  * [7] A. Genovese, M. S. Hosseini, V. Piuri, K. N. Plataniotis, and F. Scotti, “Histopathological transfer learning for acute lymphoblastic leukemia detection,” _CIVEMSA 2021 - IEEE International Conference on Computational Intelligence and Virtual Environments for Measurement Systems and Applications, Proceedings_ , 6 2021.
  * [8] ——, “Acute lymphoblastic leukemia detection based on adaptive unsharpening and deep learning,” _ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings_ , vol. 2021-June, pp. 1205–1209, 2021.
  * [9] M. Zolfaghari and H. Sajedi, “A survey on automated detection and classification of acute leukemia and WBCs in microscopic blood cells,” _Multimedia Tools and Applications_ , pp. 1–31, 1 2022. [Online]. Available: https://link.springer.com/article/10.1007/s11042-022-12108-7
  * [10] M. A. Granero, C. X. Hernández, and M. E. Valle, “Quaternion-valued convolutional neural network applied for acute lymphoblastic leukemia diagnosis,” in _Intelligent Systems_ , A. Britto and K. Valdivia Delgado, Eds. Cham: Springer International Publishing, 2021, pp. 280–293.
  * [11] S. P. Talebi, S. Werner, and D. P. Mandic, “Quaternion-Valued Distributed Filtering and Control,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 10, pp. 4246–4257, 10 2020.
  * [12] K. Takahashi, “Comparison of high-dimensional neural networks using hypercomplex numbers in a robot manipulator control,” _Artificial Life and Robotics_ , vol. 26, no. 3, pp. 367–377, 8 2021. [Online]. Available: https://link.springer.com/article/10.1007/s10015-021-00687-x
  * [13] F. Shang and A. Hirose, “Quaternion Neural-Network-Based PolSAR Land Classification in Poincare-Sphere-Parameter Space,” _IEEE Transactions on Geoscience and Remote Sensing_ , vol. 52, pp. 5693–5703, 2014.
  * [14] M. E. Valle and R. A. Lobo, “Quaternion-valued recurrent projection neural networks on unit quaternions,” _Theoretical Computer Science_ , vol. 843, pp. 136–152, 12 2020.
  * [15] T. Parcollet, M. Morchid, and G. Linarès, “A survey of quaternion neural networks,” _Artificial Intelligence Review_ , vol. 53, no. 4, pp. 2957–2982, 4 2020. [Online]. Available: https://doi.org/10.1007/s10462-019-09752-1
  * [16] E. Bayro-Corrochano, S. Solis-Gamboa, G. Altamirano-Escobedo, L. Lechuga-Gutierres, and J. Lisarraga-Rodriguez, “Quaternion Spiking and Quaternion Quantum Neural Networks: Theory and Applications,” _https://doi.org/10.1142/S0129065720500598_ , vol. 31, no. 2, 9 2020.
  * [17] J. Navarro-Moreno, R. M. Fernández-Alcalá, J. D. Jiménez-López, and J. C. Ruiz-Molina, “Tessarine Signal Processing under the T-Properness Condition,” _Journal of the Franklin Institute_ , 8 2020. [Online]. Available: https://linkinghub.elsevier.com/retrieve/pii/S0016003220305391
  * [18] J. Navarro-Moreno and J. C. Ruiz-Molina, “Wide-sense Markov signals on the tessarine domain. A study under properness conditions,” _Signal Processing_ , vol. 183, p. 108022, 6 2021.
  * [19] F. Ortolani, D. Comminiello, M. Scarpiniti, A. Uncini, F. Ortolani, D. Comminiello, M. Scarpiniti, A. Uncini, D. Comminiello, M. Scarpiniti, and A. Uncini, “On 4-Dimensional Hypercomplex Algebras in Adaptive Signal Processing,” _Smart Innovation, Systems and Technologies_ , vol. 102, pp. 131–140, 6 2017. [Online]. Available: https://link.springer.com/chapter/10.1007/978-3-319-95098-3_12
  * [20] R. Carniello, W. Vital, and M. Valle, “Universal approximation theorem for tessarine-valued neural networks,” in _Anais do XVIII Encontro Nacional de Inteligência Artificial e Computacional_. Porto Alegre, RS, Brasil: SBC, 2021, pp. 233–243. [Online]. Available: https://sol.sbc.org.br/index.php/eniac/article/view/18256
  * [21] F. Senna and M. Valle, “Tessarine and quaternion-valued deep neural networks for image classification,” in _Anais do XVIII Encontro Nacional de Inteligência Artificial e Computacional_. Porto Alegre, RS, Brasil: SBC, 2021, pp. 350–361. [Online]. Available: https://sol.sbc.org.br/index.php/eniac/article/view/18266
  * [22] D. Hestenes and G. Sobczyk, _Clifford algebra to geometric calculus: a unified language for mathematics and physics_. Springer Science & Business Media, 2012, vol. 5.
  * [23] E. Hitzer, T. Nitta, and Y. Kuroe, “Applications of Clifford’s Geometric Algebra,” _Advances in Applied Clifford Algebras_ , vol. 23, no. 2, pp. 377–404, 6 2013.
  * [24] J. Vaz and R. da Rocha, _An Introduction to Clifford Algebras and Spinors_. Oxford University Press, 2016\.
  * [25] R. B. Brown, “On generalized Cayley-Dickson algebras.” _Pacific Journal of Mathematics_ , vol. 20, no. 3, pp. 415–422, 1967. [Online]. Available: https://projecteuclid.org/euclid.pjm/1102992693
  * [26] G. Vieira and M. Eduardo Valle, “Extreme Learning Machines on Cayley-Dickson Algebra Applied for Color Image Auto-Encoding,” in _2020 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 7 2020, pp. 1–8. [Online]. Available: https://ieeexplore.ieee.org/document/9207495/
  * [27] I. L. Kantor and A. S. Solodovnikov, _Hypercomplex Numbers: An Elementary Introduction to Algebras_. Springer New York, 1989.
  * [28] M. Kobayashi, “Hopfield neural networks using Klein four-group,” _Neurocomputing_ , vol. 387, pp. 123–128, 4 2020.
  * [29] G. Vieira and M. E. Valle, “A general framework for hypercomplex-valued extreme learning machines,” _Journal of Computational Mathematics and Data Science_ , vol. 3, p. 100032, 6 2022. [Online]. Available: https://linkinghub.elsevier.com/retrieve/pii/S2772415822000062
  * [30] P. Renaud and P. R. Clifford, “CLIFFORD ALGEBRAS LECTURE NOTES ON APPLICATIONS IN PHYSICS,” _ALGEBRAS LECTURE NOTES ON APPLICATIONS IN PHYSICS_ , 11 2020. [Online]. Available: https://hal.archives-ouvertes.fr/hal-03015551https://hal.archives-ouvertes.fr/hal-03015551/document
  * [31] Aurelien Géron, _Hands–On Machine Learning with Scikit–Learn and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems_ , 2nd ed. Sebastopol, California, USA.: O Reilly, 10 2019.
  * [32] C. Trabelsi, O. Bilaniuk, Y. Zhang, D. Serdyuk, S. Subramanian, J. F. Santos, S. Mehri, N. Rostamzadeh, Y. Bengio, and C. J. Pal, “Deep complex networks,” 5 2017. [Online]. Available: http://github.com/ChihebTrabelsi/deep_complex_
  * [33] C. Gaudet and A. Maida, “Deep Quaternion Networks,” _arXiv_ , 12 2017. [Online]. Available: http://arxiv.org/abs/1712.04604
  * [34] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2323, 1998.
  * [35] R. D. Labati, V. Piuri, and F. Scotti, “All-IDB: The acute lymphoblastic leukemia image database for image processing,” in _Proceedings - International Conference on Image Processing, ICIP_ , 2011, pp. 2045–2048.
  * [36] H.-D. Cheng, X. H. Jiang, Y. Sun, and J. Wang, “Color image segmentation: advances and prospects,” _Pattern recognition_ , vol. 34, no. 12, pp. 2259–2281, 2001.


before the following crash event. If the non-volatile memory already contains
a valid and unmarked copy of this node, then the operation’s linearization
point (according to Definition B.23) indeed removes this node from the set,
according to Definition B.16. Otherwise, the mentioned flush is the first
flush of the victim node, and according to Definition B.16, it removes it from
the set in this case as well.

∎

###### Claim B.25.

A non-surviving remove operation takes no effect.

###### Proof.

By Definition B.23, during a none-surviving remove operation, if a victim node
is found, and even if it is made valid and marked, it is not flushed. By
Definition B.16, whether it is originally a set member or not, it is not
removed from the set. ∎

####  B.1.3. Contains

We do not use the term of success for describing a contains execution, and,
therefore, the terms for its survival are straight forward.

###### Definition B.26 (A Surviving Contains Operation).

A contains operation is considered as a surviving operation if it terminates
before the first crash event that follows its invocation. For defining
linearization points per contains execution, let $n_{1}$ and $n_{2}$ be the
last nodes assigned into the curr variable.

  1. (1)

When the operation returns true, its linearization point is set to be a point
during the execution in which $n_{2}$ is a set member (chosen arbitrarily).

  2. (2)

When the operation returns false in line
LABEL:code.lf_key_not_found_return_false, its linearization point is set to be
the point guaranteed by Claim B.15 for $n_{1}$ and $n_{2}$.

  3. (3)

When the operation returns false in line
LABEL:code.contains_flush_marked_return_false, its linearization point is set
to be a point during the execution in which $n_{2}$ is reachable but not a set
member (chosen arbitrarily).

###### Claim B.27.

A surviving contains operation takes effect instantaneously at its
linearization point.

###### Proof.

Let $n_{1}$ and $n_{2}$ be the last nodes assigned into the curr variable. We
are going to prove the claim for each of the three surviving contains types.

  1. (1)

Suppose that the operation returns true. We are going to show that there
indeed exists a point during the execution in which $n_{2}$ is a set member.
Since the operation does not return in line
LABEL:code.contains_flush_marked_return_false, from Claim B.4, $n_{2}$ is not
marked during the traversal. In addition, since $n_{2}$ is made valid at the
latest when executing line LABEL:code.lf_node_exists, from Claim B.4, it is
also valid when executing line LABEL:code.lf_contains_line_after_makevalid.
There are several possible scenarios:

    1. (a)

$n_{2}$ is not marked during the execution. In this case, $n_{2}$ becomes a
set member at the latest when executing line
LABEL:code.lf_contains_line_after_makevalid. In this case, there obviously
exists a point during the execution at which $n_{2}$ is a set member.

    2. (b)

$n_{2}$ is marked during the execution, and is flushed at some point after
becoming valid and before becoming marked (by Claim B.4, $n_{2}$ becomes valid
before it is marked). There exists a suitable point in this case as well.

    3. (c)

The remaining case is when $n_{2}$ is not flushed after becoming valid and
before being marked. In this case, it is flushed at the latest in line
LABEL:code.lf_contains_line_after_makevalid, and therefore, by Definition
B.16, it is a set member at some point, before being marked.

There exists a suitable linearization point in every case.

  2. (2)

Suppose that the operation returns false in line
LABEL:code.lf_key_not_found_return_false. Claim B.15 guarantees that both
$n_{1}$ and $n_{2}$ are reachable at this point. Since $n_{1}$’s key must be
smaller then the key received as input, and $n_{2}$ must be bigger, by Claim
B.8, there does not exist a reachable node with the given key at this point.
By Claim B.11, there does not exist a set member with the given key at this
point.

  3. (3)

Suppose that the operation returns false in line
LABEL:code.contains_flush_marked_return_false. If it still reachable when
executing line LABEL:code.contains_flush_marked, then a marked copy of $n_{2}$
resides in the non-volatile memory (i.e., it is not a set member by Definition
B.16), while $n_{2}$ is still reachable, and the guaranteed point exists.
Otherwise, before it becomes unreachable (which happens during the contains
execution, according to Claim B.15), at the latest, it is flushed as a marked
node in line LABEL:code.trim_flush of Listing 2. Therefore, the guaranteed
point exists in this case as well. By Claim B.8 and B.11, there does not exist
a set member with the given key at this point.

∎

Since a contains operation does not effect the list (it executes flushes, that
can also be executed implicitly), there is no need to prove that non-surviving
contains executions do not take effect.

###### Theorem B.28.

The link-free list is durable linearizable.

###### Proof.

By Definition B.19, B.23 and B.26, all the operations that are fully executed
between two crashes (and some of the operations that are halted due to crash
events), have a linearization point. By Claim B.20, B.24 and B.27, each
operation takes effect instantaneously at its linearization point. By Claim
B.21 and B.25, operations for which we did not define linearization points
(non-surviving operations), do not take effect at all. In summary, the link-
free list is durable linearizable by definition (Izraelevitz et al., 2016). ∎

###  B.2. Lock-Freedom

####  B.2.1. A Preliminary Discussion

Lock-freedom is impossible to show in the presence of crashes. To see that
this is the case, imagine an adversarial schedule of crashes that repeatedly
creates a crash one step before the completion of an operation. Such crashes
can also occur during the recovery process itself. As far as we know, lock-
freedom has not been previously discussed in the presence of crashes.

One way to deal with this problem is to admit that in the presence of crashes
lock-freedom cannot be guaranteed, but as crashes are expected to occur
infrequently, this still leaves the question of lock-freedom during crash-free
executions. Such lock-freedom is of high value in practice, when crashes are
indeed rare. A more theoretical approach is to consider crashes as progress,
as if a crash itself is one of the operations on the data structure.
Interestingly, this yields the same challenge. While executions with crashes
always make progress, crash-free executions need a proof of progress. So in
what follows we prove that the link-free list is lock-free in the absence of
crashes.

We are going to prove that in crash-free executions, at least one of the
operations terminates. To derive a contradiction, assume there is some
execution for which no executing operation terminates after a certain point.
Notice that we can assume that no operation is invoked after this point, and
that the set of running operations is finite (since there is a finite number
of system threads). The rest of the proof relates to the suffix $\alpha$ of
the execution, starting from this point.

###### Claim B.29.

There is a finite number of state changes of reachable nodes during $\alpha$.

###### Proof.

A contains execution must terminate after executing line
LABEL:code.lf_node_exists, an insert execution must terminate after executing
line LABEL:code.lf_insert_node_exists or LABEL:code.insert_make_valid, and a
remove execution must terminate after a successful CAS execution in line
LABEL:code.logically_remove. In addition, the state change in line
LABEL:code.make_node_invalid, during an insert execution, is of an unreachable
node. Consequently, we can assume that after a certain point, state changes
are made only in line LABEL:code.remove_make_valid, of Listing 5. Since a
finite number of new nodes is created and made reachable during $\alpha$ (at
most one node per pending insert operation), and since every such node
eventually becomes valid in line LABEL:code.insert_make_valid of Listing 4, we
can assume that the number of state changes in line
LABEL:code.remove_make_valid of Listing 5 is finite as well. ∎

###### Claim B.30.

There is a finite number of pointer changes of reachable nodes during
$\alpha$.

###### Proof.

The pointers of reachable nodes change either in line
LABEL:code.trim_unlink_cas of Listing 2 or line LABEL:code.insert_cas of
Listing 4. A state change in line LABEL:code.insert_cas of Listing 4 would
cause the termination of an insert execution and thus, the only pointer
changes are physical removals of marked nodes, executed in line
LABEL:code.trim_unlink_cas of Listing 2. Since there is a finite number of
state changes of reachable nodes during $\alpha$ (by Claim B.29), the number
of marked nodes is bounded and thus, there is a finite number of pointer
changes of reachable nodes during $\alpha$. ∎

###### Theorem B.31.

The link-free list is lock-free.

###### Proof.

From Claims B.29 and B.30, after a certain point, there are no state or
pointer changes in the list. Therefore, we consider the suffix
$\alpha^{\prime}$ of the execution that contains no state or pointer changes
of reachable nodes. Obviously, starting from this point, the list becomes
stable, and does not change anymore.

Since the list is finite, from Claim B.8, every find and contains execution
eventually ends. In addition, every insert and remove operation must be
unsuccessful, and also terminate (since calls to the find method always
terminate). We get a contradiction and therefore, the implementation is lock-
free. ∎

##  Appendix C SOFT Correctness

In this section we prove the correctness (i.e., durable linearizability) and
progress guarantee (lock-freedom) of the soft list. We start by proving some
volatile list invariants. In Section C.1 we prove the linearizability of our
implementation when there are no crash events, followed by a durable
linearizability proof in Section C.2. Finally, we show our implementation is
lock-free in Section C.3.

###### Claim C.1 (State Transitions).

The state of a volatile node can only go through the following transitions:

  1. (1)

From “intend to insert” to “inserted”

  2. (2)

From “inserted” to “inserted with intention to delete”

  3. (3)

From “inserted with intention to delete” to “deleted”

###### Proof.

A node’s state can change either in line LABEL:code.soft_complete_insert of
Listing 11, or in line LABEL:code.soft_mark_node or
LABEL:code.soft_complete_remove of Listing 12. In all three cases, the state
changes according to one of the options mentioned above, and the claim follows
immediately. Notice that in the rest of the assignments into a node’s _next_
pointer (line LABEL:code.soft_trim_cas of Listing 9 and line
LABEL:code.soft_link_node of Listing 11), the state stays unchanged. ∎

###### Claim C.2 (Deleted States).

Once the state of a node becomes “deleted”, its _next_ pointer does not change
anymore.

###### Proof.

A node’s _next_ pointer changes either in line LABEL:code.soft_trim_cas of
Listing 9 or in line LABEL:code.soft_link_node of Listing 11. In both cases,
the state of the node whose _next_ pointer is to be updated, is checked before
the update (guaranteeing that its state is not “deleted”), and the CAS
execution ensures that it does not change until the pointer changes (from
Claim C.1, its state cannot become “deleted” and change again afterwards).
Notice that we deal with state changes in Claim C.1. In this claim we refer
only to reference changes. ∎

###### Claim C.3 (The States of the Sentinel Nodes).

The states of the head and tail sentinel nodes are always “inserted”.

###### Proof.

As mentioned in the proof of Claim C.1, a node’s state can change either in
line LABEL:code.soft_complete_insert of Listing 11, or in line
LABEL:code.soft_mark_node or LABEL:code.soft_complete_remove of Listing 12. In
all three cases, the node’s key is sent as an input parameter to the insert or
remove operation, respectively. Assuming the neither $-\infty$ nor $\infty$
are sent as input parameters to the insert and remove operations, the states
of the head and tail sentinel nodes always remain “inserted”. ∎

###### Definition C.4 (Reachability).

We say that a volatile node $n$ is _reachable_ from a volatile node
$n^{\prime}$ if there exists nodes $n_{0},n_{1},\ldots,n_{k}$ such that
$n_{0}=n^{\prime}$, $n_{k}=n$ and for every $0\leq i<k$, $n_{i}$ is the
predecessor of $n_{i+1}$ in the list. We say that a node $n$ is _reachable_ if
it is reachable from the head sentinel node.

###### Definition C.5 (Logically in the List).

We say that a volatile node $n$ is logically in the list if $n$ is reachable
and its state is either “inserted” or “inserted with intention to delete”.

###### Definition C.6 (Infant Nodes).

We say that a volatile node $n$ is an _infant_ if $n$ is neither head nor
tail, and there does not exist an earlier successful execution of the CAS
operation in line LABEL:code.soft_link_node in Listing 11, satisfying
$newNode=n$.

###### Claim C.7 (Volatile Nodes Invariants).

Let $n_{1}$ and $n_{2}$ be two different volatile nodes. Then:

  1. (1)

If $n_{2}$ is the successor of $n_{1}$ then $n_{2}$ is not an infant.

  2. (2)

Right before executing line LABEL:code.soft_link_node in Listing 11, having
$newNode=n_{2}$, it holds that: (1) $n_{2}$ is an infant, and (2) $n_{2}$’s
state is “intend to insert”.

  3. (3)

If $n_{2}$ is not an infant and its state is not “deleted”, then $n_{2}$ is
reachable.

  4. (4)

If $n_{1}$’s key is smaller than or equal to $n_{2}$’s key, then $n_{1}$ is
not reachable from $n_{2}$.

  5. (5)

If $n_{2}$ is reachable from $n_{1}$ at a certain point, then as long as
$n_{2}$’s state is not “deleted”, $n_{2}$ is still reachable from $n_{1}$.

  6. (6)

If $n_{1}$ is not an infant then the tail sentinel node is reachable from
$n_{1}$.

###### Proof.

In the initial stage, the head and tail sentinels are the only volatile nodes
in the list, both with an “inserted” state, and tail is head’s successor.
Invariant 1 holds since tail is not an infant, Invariant 2 holds vacuously,
Invariants 3, 5 and 6 hold since both head and tail are reachable, and
Invariant 4 holds since head is not reachable from tail.

Now, assume all invariants hold until a certain point during the execution. We
are going to prove that they also hold after executing the next step by one of
the system threads.

  1. (1)

If $n_{2}$ was also $n_{1}$’s successor before the current step, then by
assumption, it is not an infant. Otherwise, $n_{1}$’s _next_ pointer was
updated to point to $n_{2}$ in the current step, either in line
LABEL:code.soft_trim_cas of Listing 9, in line LABEL:code.soft_init_state of
Listing 11, or in line LABEL:code.soft_link_node of Listing 11. In the first
two cases, there exists an earlier point during the execution, in which
$n_{2}$ is the successor of a certain node (during the execution of the find
method). By assumption, $n_{2}$ is not an infant in these cases. In the third
case, after executing the current step, $n_{2}$ is not an infant by Definition
C.6.

  2. (2)

Assume that the next step will execute line LABEL:code.soft_link_node of
Listing 11, having $newNode=n_{2}$. Assume by contradiction that $n_{2}$ is
not an infant. Since the CAS in line LABEL:code.soft_link_node can only be
executed on nodes created in line LABEL:code.allocate_new_node, by the
creating thread, $n_{2}$ is an infant and (1) holds. Now, assume by
contradiction that $n_{2}$’s state is not “intend to insert”. Then it had been
changed in line LABEL:code.soft_complete_insert of Listing 11, during another
insert execution, implying that, by Invariant 1 and the choice of the
resultNode variable, $n_{2}$ is the successor of some node and thus, is not an
infant – a contradiction. Therefore, $n_{2}$’s state is “intend to insert” and
(2) holds as well.

  3. (3)

If $n_{2}$ was an infant before the current step, then the current step is the
execution of line LABEL:code.soft_link_node in Listing 11, making $n_{2}$ the
successor of some node which is reachable by assumption. $n_{2}$ is reachable
in this case. Otherwise, by assumption and Claim C.1, it was reachable during
the former step. Assume by contradiction that it is no longer reachable after
executing the current step. Then $n_{2}$ is reachable from a node $n_{1}$ that
was reachable after the previous step, and is no longer reachable (may be
$n_{2}$ itself). Assume w.l.o.g that $n_{1}$ is such a node for which the path
of nodes from Definition C.4 is the longest. The node $n_{1}$ can only become
unreachable if the current step is the execution of line
LABEL:code.soft_trim_cas in Listing 9, and if $n_{1}$’s state is “deleted”.
This means that $n_{1}\neq n_{2}$. Since $n_{1}$’s successor stays reachable
in this case, we get a contradiction. Therefore, $n_{2}$ is reachable in this
case as well.

  4. (4)

By assumption, $n_{1}$ is not reachable from $n_{2}$ after the previous step.
Since all changes of nodes’ successors (line LABEL:code.soft_trim_cas in
Listing 9 and lines LABEL:code.soft_init_state and LABEL:code.soft_link_node
in Listing 11) preserve keys order (notice the halting condition in line
LABEL:code.soft_find_check_key of Listing 9), the Invariant still holds.

  5. (5)

If $n_{2}$ is not reachable from $n_{1}$ after the previous step then the
invariant holds vacuously. Otherwise, assume by contradiction that $n_{2}$ was
reachable from $n_{1}$ after the previous step, and is no longer reachable
from $n_{1}$ after the current step. Let $n_{3}$ be the first node reachable
from $n_{1}$ after the previous step, that is not reachable from it after
executing the current step ($n_{3}$ must exist). The node $n_{3}$ can only
become unreachable from $n_{1}$ if the current step is the execution of line
LABEL:code.soft_trim_cas in Listing 9, and if $n_{3}$’s state is “deleted”.
This means that $n_{3}\neq n_{2}$. Since $n_{3}$’s successor stays reachable
from $n_{1}$ in this case, we get a contradiction. Therefore, $n_{2}$ is still
reachable from $n_{1}$.

  6. (6)

If $n_{1}$ was an infant after the previous step then the current step
(executing a successful CAS in line LABEL:code.soft_link_node of Listing 11)
makes $n_{1}$ the predecessor of a node whose tail is reachable from, by
assumption. Therefore, tail is reachable from $n_{1}$ in this case. Otherwise,
assume by contradiction that tail was reachable from $n_{1}$ after the
previous step (must hold by assumption), but is no longer reachable from it
after the current step. Let $n_{2}$ be the last node reachable from $n_{1}$,
for whom tail is not reachable from after executing the current step ($n_{2}$
must exist). Then the current step must change $n_{2}$’s _next_ pointer. Since
$n_{2}$ cannot be an infant (by Invariant 1), this step is a successful CAS,
either in line LABEL:code.soft_trim_cas of Listing 9 or in line
LABEL:code.soft_link_node of Listing 11. In both cases, $n_{2}$’s successor is
set to be a node that tail is reachable from, by assumption. Since we get a
contradiction to Definition C.4, tail is reachable from $n_{1}$ in this case
as well.

∎

###### Claim C.8 (The Volatile List Invariant).

The volatile list is always sorted by the nodes’ keys, no key ever appears
twice, and the head and tail sentinel nodes are always the first and last
members of the list, respectively.

###### Proof.

From Invariant 4 of Claim C.7, the volatile list is always sorted by the
nodes’ keys and no key ever appears twice. By Claim C.3 and Invariant 3 of
Claim C.7, the head and tail sentinel nodes are always members of the list,
and by Invariant 4 of Claim C.7, they are the first and last members,
respectively. ∎

###### Claim C.9 (Being Logically in the Volatile List).

A volatile node $n$ is logically in the list if and only if its state is
either “inserted” or “inserted with intention to delete”.

###### Proof.

By Definition C.5, if $n$ is logically in the list then its state is either
“inserted” or “inserted with intention to delete”. It remains to show that if
its state is either “inserted” or “inserted with intention to delete” then it
is reachable and, thus, logically in the list by Definition C.5. When $n$’s
state was changed from “intend to insert” to “inserted” in line
LABEL:code.soft_complete_insert of Listing 11, it must have had a predecessor.
From Invariant 1 of Claim C.7, it is not an infant. From Invariant 3 of Claim
C.7, it is reachable. ∎

###  C.1. Linearizability

We define linearization points for the insert, remove and contains operations,
as well as for the find auxiliary method. We explicitly specify the
linearization points of the linked-list when no crashes occur.

####  C.1.1. Find

We define the linearization point of the find method to be the point
guaranteed from Claim C.10 below.

###### Claim C.10.

Let $n_{1}$ and $n_{2}$ be the two volatile nodes returned as output from the
find method. Then during the method execution, there exist a point in which
(1) $n_{1}$ is reachable, (2) $n_{2}$ is $n_{1}$’s successor, and (3)
$n_{2}$’s state is not “deleted”.

###### Proof.

When $n_{1}$’s state is read for the first time during the execution, it is
not “deleted” (otherwise, it would have been trimmed and not returned). In
addition, since it must have had a predecessor at an earlier point (otherwise,
it would not have been traversed), from Invariant 1 of Claim C.7, it is not an
infant, and from Invariant 3 of Claim C.7, it is reachable at this point. If
$n_{2}$ is $n_{1}$ successor at this point, then the claim holds for this
point. Notice that $n_{2}$’s state cannot be “deleted” at this point, since
otherwise, it would have been trimmed at a later point and not returned as
output. If $n_{2}$ is not $n_{1}$’s successor at this point, then there exists
a point between the first read of $n_{1}$ and the first read of $n_{2}$ in
which $n_{2}$ becomes $n_{1}$’s successor. From Claim C.2, $n_{1}$’s state is
not “deleted” at this point and thus, from Invariant 3 of Claim C.7, it is
reachable at this point. In addition, $n_{2}$’s state is not “deleted” at this
point as well, and the claim holds in this case. ∎

####  C.1.2. Insert

Let $n$ be the volatile node created during a successful execution of the
insert operation (line LABEL:code.allocate_new_node in Listing 11). Since the
operation returns true, it is guaranteed that $n$’s state changes from “intend
to insert” to “inserted” in line LABEL:code.soft_complete_insert. We define
the linearization point of a successful insert operation at this point. From
Claim C.1 and C.9, this is indeed the first point during the execution in
which $n$ is logically in the list.

Now, let there be an unsuccessful execution of the insert operation, and let
$m$ be the volatile node returned as the second output parameter from the find
call in line LABEL:code.soft_insert_find. Since the condition checked in line
LABEL:code.soft_node_exists must hold, its key is equal to the key received as
input. Claim C.11 below guarantees that during the execution there exists a
point in which $m$ is logically in the list. We set this point as the
operation’s linearization point in this case.

###### Claim C.11.

There exists a point between the linearization point of the mentioned find
execution and the return of the operation in which $m$’s state is either
“inserted” or “inserted with intention to delete”.

###### Proof.

If $m$’s state, read in line LABEL:code.soft_fail_insert, is not “intend to
insert”, then From Claim C.10 it is guaranteed that at the linearization point
of the find execution, $m$’s state is not “deleted”. If it is either
“inserted” or “inserted with intention to delete”, then from Definition C.5,
we are done. Otherwise, it is “intend to insert”. However, when checking its
state in line LABEL:code.soft_fail_insert, it is not “intend to insert” (since
the operation is unsuccessful, and the condition checked in line
LABEL:code.soft_fail_insert must hold). From Claim C.1, it is guaranteed that
before checking this condition, there exists a point in which $m$’s state
became “inserted”, and the claim holds.

The remaining case is when the state read in line LABEL:code.soft_fail_insert
is “intend to insert”. In this case, the executing thread does not return
before $m$’s state changes (the condition checked in line
LABEL:code.soft_insert_check_state holds). From Claim C.1, it is guaranteed
that there exists a point in which $m$’s state is “inserted”, and the claim
holds in the case as well. ∎

####  C.1.3. Remove

Let $n$ be the volatile node returned from the find method call in line
LABEL:code.soft_remove_find of Listing 12.

If the operation returned in line LABEL:code.soft_fail_remove_1_return then
its linearization point is defined at the linearization point of the find call
from line LABEL:code.soft_remove_find. The find call returned two nodes that,
from Claim C.10, are guaranteed to be reachable and successive at its
linearization point. From Claim C.8 it is guaranteed that there does not exist
a reachable node with the given key, and in particular, there does not exist a
node with the given key which is logically in the list at this point.

If the operation returned in line LABEL:code.soft_fail_remove_2_return, then
the linearization point is the read of currState during the find execution.
Since it was returned from the find call, from Invariant 1 of Claim C.7, it is
not an infant. In addition, since its state is “intend to insert”, from
Invariant 3 of Claim C.7, it is reachable. By Definition C.5, it is not
logically in the list, and by Claim C.8, there does not exist another node
with the given key, which is reachable and in particular, logically in the
list at this point.

Otherwise, the operation returned in line LABEL:code.soft_return_result. It is
guaranteed from Claim C.10 that at the linearization point of the find call,
$n$’s state was not “deleted”. Since the loops in lines
LABEL:code.soft_while1–LABEL:code.soft_mark_node and
LABEL:code.soft_while2–LABEL:code.soft_complete_remove terminated before the
return from the operation in line LABEL:code.soft_return_result, from Claim
C.1, $n$’s state was changed from “inserted with intention to delete” to
“deleted” at some point between the linearization point of the find method and
the return from the operation. This is the operation’s linearization point in
this case. From Claim C.9, it is guaranteed that the node stopped being
logically in the list exactly at this step.

####  C.1.4. Contains

Let $n$ be the last volatile node assigned into the curr variable in line
LABEL:code.soft_contains_loop_end of Listing 10.

###### Claim C.12.

Let $m$ be the last node assigned into the curr variable before $n$. Then
there exists a point during the traversal in which both nodes are reachable
and $n$ is $m$’s successor.

###### Proof.

Assume by contradiction that the claim does not hold. Let $n_{1}$ and $n_{2}$
be the first two nodes for which (1) $n_{1}$ and $n_{2}$ are assigned into the
curr variable sequentially, and (2) the guaranteed point does not exist for
them. Since this point does exist for $n_{1}$ and the former node assigned
into curr, $n_{1}$ is reachable at some point during the execution. From
Invariant 5 of Claim C.7, $n_{1}$ is reachable as long as its state is not
“deleted”. Since $n_{2}$ is its successor when assigned into the curr
variable, from Claim C.2 it was its successor at the last step in which
$n_{1}$ was reachable before this assignment (might be the assignment itself).
Therefore, there exists such a point for $n_{1}$ and $n_{2}$ – a
contradiction, and the claim holds. ∎

If $n$’s key is not equal to the key received as input, then the linearization
point is set to be the point guaranteed from Claim C.12. From Claim C.8, it is
guaranteed that there does not exist a reachable node with the given key at
this point.

Otherwise, $n$’s key is equal to the key received as input. If its state, when
executing line LABEL:code.read_state, is either “inserted” or “inserted with
intention to delete”, then the operation’s linearization point is the read of
its state in line LABEL:code.read_state. From Claim C.9, $n$ is logically in
the list at this point.

If its state is “intend to insert” when executing line LABEL:code.read_state,
then the linearization point is set to be the one guaranteed from Claim C.12,
in which $n$ is reachable. From Claim C.1, $n$’s state at this point is
“intend to insert” as well and, thus, it is not logically in the list. From
Claim C.8, since $n$ is reachable, there does not exist another reachable (and
in particular, which is logically in the list) node with the given key at this
point.

If $n$’s state is “deleted” when executing line LABEL:code.read_state and its
state at the point guaranteed from Claim C.12 is also “deleted”, then this
point is the operation’s linearization point. From the above reasons, there
does not exist a node with the given key which is logically in the list at
this point.

The remaining case is when $n$’s state is not “deleted” at the point
guaranteed from Claim C.12, but it is “deleted” when executing line
LABEL:code.read_state. Since its state is eventually “deleted”, there exists a
point between the guaranteed point and the execution of line
LABEL:code.read_state in which $n$ state was changed to “deleted” and this is
the operation’s linearization point in this case. From Invariant 5 of Claim
C.7, $n$ is reachable at this point and therefore, from the above reasons,
there does not exist a node with the given key which is logically in the list
at this point in this case as well.

###  C.2. Durable Linearizability

As in Section B.1, we use the notion of _durable linearizability_ (Izraelevitz
et al., 2016) for correctness. The recovery procedure, executed after a crash
(and described in Section 4.6), is assumed to terminate before new threads
start executing their code. Given an operation for which a crash event occurs
after its invocation and before its response, we consider its response point
as the end of the respective recovery procedure. Notice that in the following
definitions, we do not consider recoveries that are interrupted by crash
events. We do so for clarity and brevity. The definitions can be easily
extended to include such cases.

Before diving into the durable linearizability proof, we prove some basic
claims regarding the persistent nodes, used during recovery.

###### Claim C.13 (State Transitions of Persistent Nodes).

The state of a persistent node can only go through the following transitions:

  1. (1)

From valid and removed to invalid

  2. (2)

From invalid to valid and not removed

  3. (3)

From valid and not removed to valid and removed

###### Proof.

Let $p$ be a persistent node, allocated in line LABEL:code.allocate_new_node
of Listing 11, and let $v$ be the negation of its validStart bit, when
allocated (i.e., $v$ is assigned into the pValidity field of the respective
volatile node). When $p$ is allocated, its state is valid and removed. The
state of $p$ can only change when creating or destroying it (Listing 7). The
create method can only be called from line LABEL:code.soft_init_pnode of
Listing 11, and the destroy method can only be called from line
LABEL:code.flush_delete of Listing 12, both with $v$ as their pValidity input
parameter. Notice that the first create execution terminates before the first
destroy invocation, since the state of the respective volatile node is set to
“inserted” in line LABEL:code.soft_complete_insert of Listing 11, only after
the termination of the first create call, and is set to “inserted with
intention to delete” in line LABEL:code.soft_mark_node of Listing 12, before
the first invocation of the destroy method (and by Claim C.1, a volatile
node’s state can be “inserted” only before it becomes “inserted with intention
to delete”).

The first create execution changes $p$’s state to invalid and then valid and
not removed. Any further create calls do not change its state at all (since
the value of the validStart and validEnd bits is already $v$). Therefore, any
destroy call can only change it from valid and not removed to valid and
removed (since it only changes the deleted bit), and the claim follows. ∎

###### Claim C.14 (Non-Removed Persistent Nodes).

Let $n$ be a volatile node, and assume its representing persistent node has
already been created in line LABEL:code.soft_init_pnode of Listing 11. If
$n$’s state is either “intention to insert” or “inserted”, then the state of
its representing persistent node is valid and not removed.

###### Proof.

As shown in the proof of Claim C.13, the state of $n$’s representing
persistent node becomes valid and not removed when it is created in line
LABEL:code.soft_init_pnode of Listing 11. In addition, from Claim C.13, it can
only become valid and removed, after $n$’s state becomes “inserted with
intention to delete”. Since $n$’s state is either “intention to insert” or
“inserted”, the state of its representing persistent node remains valid and
not removed. ∎

###### Claim C.15 (Removed Persistent Nodes).

Let $n$ be a volatile node, and assume its representing persistent node has
already been marked as removed in line LABEL:code.flush_delete of Listing 12.
Then the state of its representing persistent node does not become valid and
not removed anymore.

###### Proof.

As shown in Claim C.13, any further create or destroy calls would not effect
the persistent node’s state. ∎

We are going to prove that, given an execution, removing all crash events
would leave us with a linearizable history, including all the operations that
were fully executed between two crashes, and some of the operations that were
halted due to crashes (and then recovered during recovery). We are going to
define, per operation execution, whether it is a surviving operation. A
surviving operation is an operation that is linearized in the final crash-free
history of the execution (by removing all crash events). Obviously, operations
that were fully executed between two crash events are always considered as
surviving operations. Additionally, we are going to define the linearization
points of all surviving operations in the crash-free history.

####  C.2.1. Insert

Before defining the conditions for the survival of an insert operation, we
need to re-define the success of an insertion in the presence of crash events.

###### Definition C.16 (A Successful Insert Operation).

Given an execution of an insert operation, we say that this operation is
successful if one of the following holds:

  1. (1)

The operation returns true.

  2. (2)

A volatile node $n$ is allocated in line LABEL:code.allocate_new_node, the
result variable is assigned with true in line
LABEL:code.soft_insert_result_true, and the respective persistent node of $n$
is created in line LABEL:code.soft_init_pnode by some thread before any crash
event.

The operation is unsuccessful if it returns false.

###### Definition C.17 (A Surviving Insert Operation).

An insert operation is considered as a surviving operation if, before the
first crash event that follows its invocation, one of the following holds:

  1. (1)

The operation is unsuccessful according to Definition C.16. In this case, its
linearization point is set to be its original linearization point, presented
in Section C.1.2.

  2. (2)

The operation is successful according to Definition C.16, and some thread (not
necessarily the one that executes the successful insertion) changes the state
of the node allocated in line LABEL:code.allocate_new_node, in line
LABEL:code.soft_complete_insert. In this case, the linearization point is set
to be its original linearization point as well.

  3. (3)

The operation is successful according to Definition C.16, and no thread
changes the state of the node allocated in line LABEL:code.allocate_new_node,
in line LABEL:code.soft_complete_insert. In this case, the linearization point
is set to be the insertion of a new respective volatile node to the list
during recovery.

###### Claim C.18.

A surviving insert operation takes effect instantaneously at its linearization
point.

###### Proof.

First, let $n$ be the last volatile node allocated during a successful insert
operation (according to Definition C.16). We are going to show that $n$ is
logically inserted into the volatile list at the operation’s linearization
point (presented in Definition C.17).

If some thread (not necessarily the one that executes the successful
insertion) changes the state of $n$ in line LABEL:code.soft_complete_insert,
then by Definition C.17, the operation’s linearization point is this change.
As proved in Section C.1.2, $n$ is indeed logically inserted into the list at
this point. Notice that in this case, we do not consider the insertion of a
new representing node during recovery, as a logical insertion of $n$ into the
list. By Invariant 5 of Claim C.7, $n$ is still reachable when the crash
occurs. In addition, notice that as long as this node is not removed from the
list, its state remains “inserted” and by Claim C.14, the state of its
representing persistent node is indeed valid and not removed during recovery.

Otherwise, no thread changes $n$’s state from “intention to insert” to
“inserted” before the crash event. By Definition C.16, a respective persistent
node of $n$ is created in line LABEL:code.soft_init_pnode. From Claim C.1,
$n$’s state does not change at all before the first crash and therefore, by
Definition C.5, it is not logically in the list. As described in Section 4.6,
during recovery, a new volatile node, representing $n$, is logically inserted
into the list, and by Definition C.17, this is the linearization point of the
operation in this case. Notice that by Claim C.14, the state of its
representing persistent node is indeed valid and not removed during recovery,
in this case as well.

When an insert operation is unsuccessful by Definition C.16, it is also
unsuccessful by the original definition. From Section C.1.2, there exists a
point during its execution for which a node with the given key is already
logically in the list and thus, the unsuccessful operation indeed returns a
correct answer. Additionally, notice that even if a representing persistent
node is allocated, its state remains valid and removed, since the create
method is only called after the volatile node is successfully inserted into
the list, and the destroy method is only called when the state of the volatile
node is either “inserted with intention to delete” or “deleted” (by Claim
C.14). ∎

###### Claim C.19.

A non-surviving insert operation takes no effect.

###### Proof.

By Definition C.17, during a none-surviving insert operation, if a volatile
node is allocated, and even if it is inserted into the list, its state remains
“intention to insert” and, thus, it is not logically in the list by Definition
C.5. In addition, by Definition C.17, during a non-surviving insert operation,
a persistent node may be allocated, but not created (or partially created, and
thus, in an invalid state). Therefore, during recovery, even if the persistent
node is allocated, its state is either valid and removed, or invalid, and
therefore, the represented volatile node is not inserted into the new list. ∎

####  C.2.2. Remove

We also re-define the success of a removal in the presence of crash events.

###### Definition C.20 (A Successful Remove Operation).

Given an execution of an remove operation, we say that this operation is
successful if one of the following holds:

  1. (1)

The operation returns true.

  2. (2)

The result variable is assigned with true in line LABEL:code.soft_mark_node,
and the respective persistent node is marked as deleted in line
LABEL:code.flush_delete by some thread before any crash event.

The operation is unsuccessful if it returns false.

###### Definition C.21 (A Surviving Remove Operation).

A remove operation is considered as a surviving operation if, before the first
crash event that follows its invocation, one of the following holds:

  1. (1)

The operation is unsuccessful according to Definition C.20. In this case, its
linearization point is set to be its original linearization point, presented
in Section C.1.3.

  2. (2)

The operation is successful according to Definition C.20, and some thread (not
necessarily the one that executes the successful removal) changes the state of
the victim node in line LABEL:code.soft_complete_remove. In this case, the
linearization point is set to be its original linearization point as well.

  3. (3)

The operation is successful according to Definition C.20, and no thread
changes the state of the victim node in line LABEL:code.soft_complete_remove.
In this case, the linearization point is set to be immediately after the crash
event (if there is more than one such removal, they are linearized in an
arbitrary order).

###### Claim C.22.

A surviving remove operation takes effect instantaneously at its linearization
point.

###### Proof.

First, assume a successful remove operation (according to Definition C.20),
and let $n$ be the node whose state is updated from “inserted” to “inserted
with intention to delete” in line LABEL:code.soft_mark_node. We are going to
show that $n$ is logically removed from the volatile list at the operation’s
linearization point (presented in Definition C.21).

If some thread (not necessarily the one that executes the successful removal)
changes the state of $n$ from “inserted with intention to delete” to “deleted”
in line LABEL:code.soft_complete_remove, then by Definition C.21, the
operation’s linearization point is this change. As proved in Section C.1.3,
$n$ is indeed logically removed from the list at this point. Notice that in
this case, it is guaranteed that $n$ will not be re-added into the volatile
list during recovery, since by Claim C.15, it has a persistent representative,
marked as deleted.

Otherwise, no thread changes $n$’s state from “inserted with intention to
delete” to “deleted” before the crash event. By Definition C.20, the
respective persistent node of $n$ is marked as removed in line
LABEL:code.flush_delete. From Claim C.1, $n$’s state remains “inserted with
intention to delete” until the first crash event. By Claim C.9, it is
logically in the list until this crash event. As described in Section 4.6,
during recovery, a node representing $n$ will not be inserted into the list
(since its representative is marked as deleted, by Claim C.15), and in
particular, will not be reachable. By Definition C.5, it will no longer be
logically in the list. Therefore, it is indeed logically removed from the list
at the crash event, right before its linearization point, as presented in
Definition C.21.

When a remove operation is unsuccessful by Definition C.20, it is also
unsuccessful by the original definition. From Section C.1.3, there exists a
point during its execution for which there is no node with the given key which
is logically in the list (and from Claim C.15, any persistent representative
would have a valid and removed state) and thus, the unsuccessful operation
indeed returns a correct answer. ∎

###### Claim C.23.

A non-surviving remove operation takes no effect.

###### Proof.

By Definition C.21, during a none-surviving remove operation, even if the
state of the victim node becomes “inserted with intention to delete”, by
Definition C.21, it does not become “deleted”, and no thread executes the
destruction of its respective persistent node (i.e., by Claim C.14, it is
still valid and not removed).

Therefore, by Definition C.5, it is still logically in the list until the
crash event occurs, and during recovery, it is re-added to the new list. ∎

####  C.2.3. Contains

As opposed to the insert and remove operations, a contains operation is
considered as a surviving operation only when it terminates:

###### Definition C.24 (A Surviving Contains Operation).

A contains operation is considered as a surviving operation if and only if it
terminates before the first crash event occurring after its invocation. If it
survives, its linearization point is set to be its original linearization
point, presented in Section C.1.4.

###### Claim C.25.

A surviving contains operation takes effect instantaneously at its
linearization point.

###### Proof.

Since we only consider contains operations that terminate without being
interrupted by crash events, the claim follows directly from Section C.1.4 ∎

###### Claim C.26.

A non-surviving contains operation takes no effect.

###### Proof.

The claim follows directly from the fact that a contains operation (and in
particular, an operation with no response), does not change the list. ∎

###### Theorem C.27.

The soft list is durable linearizable.

###### Proof.

By Definition C.17, C.21 and C.24, all the operations that are fully executed
between two crashes (and some of the operations that are halted due to crash
events), have a linearization point. By Claim C.18, C.22 and C.25, each
operation takes effect instantaneously at its linearization point. By Claim
C.19, C.23 and C.26, operations for which we did not define linearization
points (non-surviving operations), do not take effect at all. In summary, the
soft list is durable linearizable by definition (Izraelevitz et al., 2016). ∎

###  C.3. Lock-Freedom

Similarly to (and following the discussion in) Section B.2, in this section we
prove that in crash-free executions, at least one of the operations
terminates. To derive a contradiction, assume there is some execution for
which no executing operation terminates after a certain point. Notice that we
can assume that no operation is invoked after this point, and that the set of
running operations is finite (since there is a finite number of system
threads). The rest of the proof relates to the suffix $\alpha$ of the
execution, starting from this point.

###### Claim C.28.

There is a finite number of state changes during $\alpha$.

###### Proof.

An insert operation must terminate after executing line
LABEL:code.soft_complete_insert in Listing 11. Likewise, a remove operation
must terminate after executing line LABEL:code.soft_complete_remove in Listing
12). In addition, any remove operation includes at most two successful state
changes (in lines LABEL:code.soft_mark_node and
LABEL:code.soft_complete_remove of Listing 12). Since the number of running
operations is finite by assumption, the number of state changes is finite as
well. ∎

###### Claim C.29.

There is a finite number of pointer changes during $\alpha$.

###### Proof.

The loop in lines
LABEL:code.soft_insert_start_link_loop–LABEL:code.soft_insert_end_link_loop of
Listing 11 must eventually terminate after a successful CAS execution in line
LABEL:code.soft_link_node and therefore, there are no pointer updates in lines
LABEL:code.soft_init_state and LABEL:code.soft_link_node of Listing 11. Thus,
pointer updates can only occur in line LABEL:code.soft_trim_cas of Listing 9.
When executing this update, the pred node is reachable from Claim C.2 and
Invariants 1 and 3 of Claim C.7. Since curr is pred’s successor and succ is
curr’s successor right before this change, succ is also reachable before this
step. Therefore, no node becomes reachable when executing this CAS. Since this
is the only possible pointer change, the list can only shrink, and the number
of such pointer changes is finite. ∎

###### Theorem C.30.

The soft list is lock-free.

###### Proof.

From Claims C.28 and C.29, after a certain point, there are no state or
pointer changes. Therefore, we consider the suffix $\alpha^{\prime}$ of the
execution that contains no state or pointer changes. Obviously, starting from
this point, the list becomes stable, and does not change anymore.

Since the list is finite, from Claim C.8, every find and contains execution
eventually ends. In addition, every insert and remove operation must be
unsuccessful, and also terminate (since calls to the find method always
terminate). We get a contradiction and therefore, the implementation is lock-
free. ∎