#  Moderate Deviation Principles for Unbounded Additive Functionals of
Distribution Dependent SDEs

Panpan Ren 2,a), Shen Wang 1,b)
1)Center for Applied Mathematics, Tianjin University, Tianjin 300072, China
2)Mathematic Department, City University of Hong Kong, Hong Kong, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

By comparing the original equations with the corresponding stationary ones,
the moderate deviation principle (MDP) is established for unbounded additive
functionals of several different models of distribution dependent SDEs, with
non-degenerate and degenerate noises.

AMS subject Classification: 60H10, 60H15.
Keywords: Moderate deviation principle, exponential equivalence, distribution
dependent SDEs.

##  1 Introduction

To characterise long time behaviours of stochastic systems, various limit
theorems, including LLN(law of large numbers), CLT(central limit theorems),
and LDP(large deviation principle) have been intensively investigated in the
literature of Markov processes and random sequences, see for instance [1, 2,
3, 4, 5, 6, 9, 11, 19, 20, 21]. On the other hand, less is known for limit
theorems on nonlinear systems, where a typical model is the distribution
dependent SDE (also called McKean-Vlasov or Mean-filed SDE), which arises from
characterizations on nonlinear Fokker-Planck equations and mean-filed particle
systems, see [10] and references within. Recently, the Donsker-Varadhan LDP
for path-distribution dependent SDEs was investigated in [13] for empirical
measures of distribution dependent SDEs, which in particular implies LDP for
bounded continuous additive functionals. In this paper, we investigate the
MDP(moderate deviation principle) for unbounded additive functionals.

Below, we first briefly recall the notion of LDP and MDP, then introduce the
model studied in the present paper.

Let $E$ be a polish space, and let $(X_{t})_{t\geq 0}$ be a right continuous
Markov process on $E$ with infinitesimal generator $L$. For a measurable space
$(E,\mathscr{B})$, let $\mathscr{P}(E)$ denote the set of all probability
measures on $E$ with weak topology. Consider the empirical measures of
$(X_{t})_{t\geq 0}$:

$L_{t}:=\frac{1}{t}\int_{0}^{t}\delta_{X_{s}}\text{\rm{d}}s,\,\,\,t>0.$

The following Donsker-Varadhan type long time LDP for $L_{t}$ has been studied
in [7]:

(1.1) $\displaystyle\mathbb{P}_{x}(L_{t}\in M)\approx\exp\\{-t\inf_{\nu\in
M}J(\nu)\\},\quad M\subset\mathscr{P}(E),$

where
$J(\nu)=\sup_{\inf_{x}U(x)>0,U\in\mathcal{D}(L)}\int\frac{-LU}{U}\text{\rm{d}}\nu$,
$\mathbb{P}_{x}$ denotes the probability of Markov process starting from $x$,
and $\mathscr{P}(E)$ is the class of all probability measures on $E$, equipped
with the weak topology.

In general, when the Markov process $(X_{t})_{t\geq 0}$ is ergodic, in order
to describe the convergence of the empirical distribution $L_{t}$ to the
unique invariant probability measure $\bar{\mu}$ as $t\rightarrow\infty$, a
standard way is to look at the convergence rate of

$L_{t}^{A}:=\int_{E}A\text{\rm{d}}L_{t}=\frac{1}{t}\int_{0}^{t}A(X_{s})\text{\rm{d}}s\rightarrow\bar{\mu}(A)\,\,\,\textrm{as}\,\,\,t\rightarrow\infty$

for $A$ in a class of reference functions. This leads to the study of the LDP
(MDP) for the additive functional $L_{t}^{A}$. When $A$ is bounded and
continuous, (1.1) and the Contraction Principle imply the LDP of $L_{t}^{A}$,
that is, for $M\in\mathscr{B}(\mathbb{B})$,

$\mathbb{P}_{x}(L_{t}^{A}\in M)\approx\exp\\{-t\inf_{z\in M}J^{A}(z)\\},\quad
A\subset\mathbb{R},$

where $J^{A}(z)=\inf\\{J(\nu);\,\,\,\int A\text{\rm{d}}\nu=z\\}$. But this
approach does not apply when $A$ is unbounded. So, we consider the MDP
(moderate deviation principle) for $L_{t}^{A}$ with unbounded $A$, which is
equivalent to LDP for the modified additive functional

$l_{t}^{A}:=\frac{t}{a(t)}\Big{(}L_{t}^{A}-\bar{\mu}(A)\Big{)}=\frac{1}{a(t)}\int_{0}^{t}\big{(}A(X_{s})-\bar{\mu}(A)\big{)}\text{\rm{d}}s,$

where $a(t)$ is a positive function satisfying

(1.2)
$\displaystyle\lim_{t\rightarrow\infty}\frac{\sqrt{t}}{a(t)}=0,\,\,\,\,\lim_{t\rightarrow\infty}\frac{a(t)}{t}=0.$

######  Definition 1.1.

  1. (1)

$L_{t}^{A}$ is said to satisfy the upper bound uniform MDP with a rate
function $I$, denoted by $L_{t}^{A}\in MDP_{u}(I)$, if for any $a$ satisfying
(1.2),

$\limsup_{t\rightarrow\infty}\frac{t}{a^{2}(t)}\log\mathbb{P}(l_{t}^{A}\in
F)\leq-\inf_{F}I,\quad
F\subset\mathbb{R}\,\,\,\textrm{is}\,\,\,\textrm{closed}.$

  2. (2)

$L_{t}^{A}$ is said to satisfy the lower bound uniform MDP with a rate
function $I$, denoted by $L_{t}^{A}\in MDP_{l}(I)$, if for any $a$ satisfying
(1.2),

$\liminf_{t\rightarrow\infty}\frac{t}{a^{2}(t)}\log\mathbb{P}(l_{t}^{A}\in
G)\geq-\inf_{G}I,\quad
G\subset\mathbb{R}\,\,\,\textrm{is}\,\,\,\textrm{open}.$

  3. (3)

$L_{t}^{A}$ is said to satisfy the uniform MDP with a rate function $I$,
denoted by $L_{t}^{A}\in MDP(I)$, if $L_{t}^{A}\in MDP_{u}(I)$ and
$L_{t}^{A}\in MDP_{l}(I)$.

The MDP has been established in [9] for non-degenerate SDEs by using Wang’s
Harnack inequality [16]:

$\text{\rm{d}}X_{t}=b(X_{t})\text{\rm{d}}t+\sigma(X_{t})\text{\rm{d}}B_{t},\,\,\,X_{0}=x\in\mathbb{R}^{d}.$

The assumptions in [9] was further simplified and improved in [19], so that
degenerate situations are also included.

In this paper, we investigate MDP for unbounded additive functionals of the
following distribution dependent SDE (DDSDE for short) on $\mathbb{R}^{d}$:

(1.3)
$\begin{split}&\text{\rm{d}}X_{t}=b(X_{t},\mathscr{L}_{X_{t}})\text{\rm{d}}t+\sigma(X_{t},\mathscr{L}_{X_{t}})\text{\rm{d}}B_{t},\end{split}$

where
$b:\mathbb{R}^{d}\times\mathscr{P}_{2}(\mathbb{R}^{d})\rightarrow\mathbb{R}^{d}$,
$\sigma:\mathbb{R}^{d}\times\mathscr{P}_{2}(\mathbb{R}^{d})\rightarrow\mathbb{R}^{d\times
d}$, $B_{t}$ is a $d$-dimensional Brownian motion, $\mathscr{L}_{X_{t}}$ is
the law of $X_{t}$ under the reference probability space.

Let $\mathscr{P}_{2}$ be the space of all probability measures $\mu$ on
$\mathbb{R}^{d}$ such that

$\|\mu\|_{2}:=\bigg{(}\int_{\mathbb{R}^{d}}|x|^{2}\mu(\text{\rm{d}}x)\bigg{)}^{\frac{1}{2}}<\infty.$

It is well known that $\mathscr{P}_{2}$ is a Polish space under the
Wasserstein distance

$W_{2}(\mu,\nu):=\inf_{\pi\in\mathscr{C}(\mu,\nu)}\Bigg{(}\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}|x-y|^{2}\pi(\text{\rm{d}}x,\text{\rm{d}}y)\Bigg{)}^{\frac{1}{2}},$

where $\mathscr{C}(\mu,\nu)$ is the set of all couplings for $\mu$ and $\nu$.

As in [13], to establish MDP for DDSDE (1.3), we choose a reference SDE whose
solution is Markovian so that existing results on the MDP apply. By comparing
the original equation with the reference one in the sense of MDP, we establish
the MDP for the DDSDE. We will state the main results in Section 2, and
present complete proofs in Section 3.

##  2 Main results

We consider several different situations.

###  2.1 Lipschitz Continuous $A$.

We consider DDSDE (1.3) and make the following assumptions:

  1. (H1)

$b$ is continuous, and $\sigma$ is Lipschitz continuous on
$\mathbb{R}^{d}\times\mathscr{P}_{2}(\mathbb{R}^{d})$ such that

$\displaystyle 2\langle
b(x,\mu)-b(y,\nu),x-y\rangle+\|\sigma(x,\mu)-\sigma(y,\nu)\|_{HS}^{2}$
$\displaystyle\leq\lambda_{2}W_{2}(\mu,\nu)^{2}-\lambda_{1}|x-y|^{2},\,\,\quad\,\,x,y\in\mathbb{R}^{d};\,\,\,\mu,\nu\in\mathscr{P}_{2}(\mathbb{R}^{d})$

holds for some constants $\lambda_{1}>\lambda_{2}\geq 0$.

  2. (H2)

There exist constants $0<\kappa_{1}\leq\kappa_{2}<\infty$ such that

$\kappa_{1}^{2}I\leq\sigma(x,\mu)\sigma(x,\mu)^{*}\leq\kappa_{2}^{2}I,\quad
x\in\mathbb{R}^{d},~{}\mu\in\mathscr{P}_{2}(\mathbb{R}^{d}),$

where $\sigma^{*}$ denotes the transpose of the matrix $\sigma$, $I$ denotes
the identity matrix.

According to [18, Theorem 2.1], assumption (H1) implies that for any $X_{0}\in
L^{2}(\Omega\rightarrow\mathbb{R}^{d},\mathcal{F}_{0},\mathbb{P})$, the
equation (1.3) has a unique solution. We write
$P_{t}^{*}\nu=\mathscr{L}_{X_{t}}$ if $\mathscr{L}_{X_{0}}=\nu$. By [18,
Theorem 3.1(2)], $P_{t}^{*}$ has a unique invariant probability measure
$\bar{\mu}\in\mathscr{P}_{2}(\mathbb{R}^{d})$ such that

(2.1) $W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2}\leq
W_{2}(\nu,\bar{\mu})^{2}e^{-(\lambda_{1}-\lambda_{2})t},\,\,\,~{}t\geq
0,~{}\,\nu\in\mathscr{P}_{2}(\mathbb{R}^{d}).$

Consider the stationary reference SDE:

(2.2)
$\begin{split}&\text{\rm{d}}\bar{X}_{t}=b(\bar{X}_{t},\bar{\mu})\text{\rm{d}}t+\sigma(\bar{X}_{t},\bar{\mu})\text{\rm{d}}B_{t},\quad\mathscr{L}_{X_{0}}=\bar{\mu}.\end{split}$

Under (H1), the equation (2.2) has a unique solution $\bar{X}^{x}_{t}$ for any
starting point $x\in\mathbb{R}^{d}$, and $\bar{\mu}$ is the unique invariant
probability measure of the associated Markov semigroup

$\bar{P}_{t}f(x):=\mathbb{E}[f(\bar{X}^{x}_{t})],\,\,\,t\geq
0,\,\,x\in\mathbb{R}^{d},\,\,\,f\in\mathscr{B}_{b}(\mathbb{R}^{d}),$

where $\bar{P}_{t}$ is generated by

$\bar{\mathscr{A}}:=\frac{1}{2}\sum_{i,j=1}^{d}\\{\sigma\sigma^{*}\\}_{ij}(x,\bar{\mu})\partial_{i}\partial_{j}+\sum_{i=1}^{d}b_{i}(x,\bar{\mu})\partial_{i}.$

According to [9] and [19], under assumptions (H1) and (H2), $\bar{P}_{t}$ is
$\bar{\mu}$-hypercontractive and strong Feller, i.e.,
$\|\bar{P}_{t}\|_{L^{2}(\bar{\mu})\rightarrow L^{4}(\bar{\mu})}=1$ for large
$t>0$ and $\bar{P}_{t}\mathscr{B}_{b}(\mathbb{R}^{d})\subset
C_{b}(\mathbb{R}^{d})$ for $t>0$. In particular, the hypercontractivity
implies that there exists $\lambda>0$ such that

$\bar{\mu}(|\bar{P}_{t}f-\bar{\mu}(f)|^{2})\leq e^{-\lambda
t}\bar{\mu}(|f-\bar{\mu}(f)|^{2}),\quad t\geq 0,\quad f\in L^{2}(\bar{\mu}),$

so, for any $f\in L^{2}(\bar{\mu})$,

(2.3)
$\bar{V}(f):=\int_{0}^{\infty}\bar{\mu}(|\bar{P}_{t}f-\bar{\mu}(f)|^{2})\text{\rm{d}}t<\infty.$

We have the following result:

######  Theorem 2.1.

Assume (H1) and (H2). If $\mathbb{E}[e^{\delta|X_{0}|^{2}}]<\infty$ for some
constant $\delta>0$, then for any Lipschitz continuous function $A$ on
$\mathbb{R}^{d}$, $L_{t}^{A}\in\textrm{MDP}(I)$ for
$I(y)={y^{2}}/({8\bar{V}(A)})$, $y\in\mathbb{R}$.

###  2.2 Hölder continuous $A$.

When $A$ is Hölder continuous, we need to assume that
$\sigma(x,\mu)=\sigma(\mu)$ does not depend on $x$. In this case, the DDSDE
becomes

(2.4)
$\begin{split}&\text{\rm{d}}X_{t}=b(X_{t},\mathscr{L}_{X_{t}})\text{\rm{d}}t+\sigma(\mathscr{L}_{X_{t}})\text{\rm{d}}B_{t},\end{split}$

and the reference SDE reduces to

(2.5)
$\begin{split}&\text{\rm{d}}\bar{X}_{t}=b(\bar{X}_{t},\bar{\mu})\text{\rm{d}}t+\sigma(\bar{\mu})\text{\rm{d}}B_{t}.\end{split}$

Below we give the main result of this subsection.

######  Theorem 2.2.

Assume (H1),(H2), and let $\sigma(x,\mu)=\sigma(\mu)$ do not depend on $x$. If
there exists a constant $\delta>0$ such that
$\mathbb{E}[e^{\delta|X_{0}|^{2}}]<\infty$, then for any function $A$ such
that

$\sup_{x\neq
y}{\frac{|A(x)-A(y)|}{|x-y|^{\alpha}\big{(}1+|x|+|y|\big{)}^{2-\alpha}}}<\infty,\quad
x,y\in\mathbb{R}^{d}$

holds for some $\alpha\in(0,1)$, $L_{t}^{A}\in\textrm{MDP}(I)$ for
$I(y)={y^{2}}/({8\bar{V}(A)})$, $y\in\mathbb{R}$.

###  2.3 Non-Hölder continuous $A$.

In this part, we consider non-Hölder continuous $A$ for which we need to
further strengthen the assumption that $\sigma$ is constant matrix. So, the
DDSDE and the reference SDE reduce to

(2.6)
$\begin{split}&\text{\rm{d}}X_{t}=b(X_{t},\mathscr{L}_{X_{t}})\text{\rm{d}}t+\sigma\text{\rm{d}}B_{t},\end{split}$

and

(2.7)
$\begin{split}&\text{\rm{d}}\bar{X}_{t}=b(\bar{X}_{t},\bar{\mu})\text{\rm{d}}t+\sigma\text{\rm{d}}B_{t}.\end{split}$

######  Theorem 2.3.

Assume (H1),(H2) and let $\sigma$ be constant. If
$\mathbb{E}[e^{\delta|X_{0}|^{2}}]<\infty$ for some $\delta>0$, then for any
function $A$ such that

$\sup_{x\neq
y}{\frac{|A(x)-A(y)|\cdot{\log(e+|x|^{2}+|y|^{2})\cdot[\log(e+|x-y|^{-1})]^{p}}}{\big{(}1+|x|^{2}+|y|^{2}\big{)}}}<\infty,\quad
x,y\in\mathbb{R}^{d}$

holds for some $p>1$, $L_{t}^{A}\in\textrm{MDP}(I)$ for
$I(y)={y^{2}}/({8\bar{V}(A)})$, $y\in\mathbb{R}$.

###  2.4 The degenerate case

In this section, we consider the distribution dependent stochastic Hamiltonian
system for $X_{t}=(X_{t}^{(1)},X_{t}^{(2)})$ on $\mathbb{R}^{m+d}$:

(2.8) $\displaystyle\left\\{\begin{aligned}
\text{\rm{d}}X_{t}^{(1)}&=(AX_{t}^{(1)}+BX_{t}^{(2)})\text{\rm{d}}t,\\\
\text{\rm{d}}X_{t}^{(2)}&=Z(X_{t},\mathscr{L}_{X_{t}})\text{\rm{d}}t+M\text{\rm{d}}B_{t},\end{aligned}\right.$

where $A,B$ and $M$ are $m\times m$, $m\times d$ and $d\times d$ matrixes
respectively, $B_{t}$ is $d$ dimensional Brownian motion. Define

$W_{2}(\nu_{1},\nu_{2}):=\inf_{\pi\in\mathscr{C}(\nu_{1},\nu_{2})}\Bigg{(}\int_{\mathbb{R}^{m+d}\times\mathbb{R}^{m+d}}\big{(}|\xi_{1}^{(1)}-\xi_{2}^{(1)}|^{2}+|\xi_{1}^{(2)}-\xi_{2}^{(2)}|^{2}\big{)}\pi\big{(}\text{\rm{d}}\xi_{1},\text{\rm{d}}\xi_{2}\big{)}\Bigg{)}^{\frac{1}{2}}.$

We assume

  1. (D1)

$M$ is invertible and $Rank[B,AB,\ldots,A^{m-1}B]=m$.

  2. (D2)

$Z:\mathbb{R}^{m+d}\times\mathscr{P}_{2}(\mathbb{R}^{m+d})\rightarrow\mathbb{R}^{d}$
is Lipschitz continuous.

  3. (D3)

There exist constants $r>0$, $\theta_{1}>\theta_{2}>0$ and
$r_{0}\in(-\|B\|^{-1},\|B\|^{-1})$ such that

$\displaystyle\langle
r^{2}(x^{(1)}-y^{(1)})+rr_{0}B(x^{(2)}-y^{(2)}),A(x^{(1)}-y^{(1)})+B(x^{(2)}-y^{(2)})\rangle$
$\displaystyle+\langle
Z(x,\mu)-Z(y,\nu),x^{(2)}-y^{(2)}+rr_{0}B^{*}(x^{(1)}-y^{(1)})\rangle$
$\displaystyle\leq-\theta_{1}(|x^{(1)}-y^{(1)}|^{2}+|x^{(2)}-y^{(2)}|^{2})+\theta_{2}W_{2}(\mu,\nu)^{2},$
$\displaystyle\,\quad\,x=(x^{(1)},x^{(2)}),~{}y=(y^{(1)},y^{(2)})\in\mathbb{R}^{m+d},~{}\mu,\nu\in\mathscr{P}_{2}(\mathbb{R}^{m+d}).$

######  Theorem 2.4.

Assume (D1)-(D3), and let $A$ be a Lipschitz continuous function on
$\mathbb{R}^{m+d}$. Then

  1. (1)

For any $\mu_{0},\nu_{0}\in\mathscr{P}_{2}(\mathbb{R}^{m+d})$, there exists a
constant $C$ such that

$W_{2}(P_{t}^{*}\mu_{0},P_{t}^{*}\nu_{0})^{2}\leq
Ce^{-\frac{\theta_{1}-\theta_{2}}{2C}t}W_{2}(\mu_{0},\nu_{0})^{2},\quad\quad
t\geq 0.$

  2. (2)

$P_{t}^{*}$ has an invariant probability measure
$\bar{\mu}\in\mathscr{P}_{2}(\mathbb{R}^{m+d})$ such that

(2.9) $\displaystyle W_{2}(P_{t}^{*}\mu_{0},\bar{\mu})^{2}\leq
Ce^{-\frac{\theta_{1}-\theta_{2}}{2C}t}W_{2}(\mu_{0},\bar{\mu})^{2},\quad\quad
t\geq 0,~{}\mu_{0}\in\mathscr{P}_{2}(\mathbb{R}^{m+d}).$

  3. (3)

If there exists a constant $\delta>0$ such that
$\mathbb{E}[e^{\delta|X_{0}|^{2}}]<\infty$, then $L_{t}^{A}\in\textrm{MDP}(I)$
for $I(y)={y^{2}}/({8\bar{V}(A)})$, $y\in\mathbb{R}^{m+d}$.

##  3 Proofs of main results

###  3.1 Proof of Theorem 2.1

To prove the Theorem 2.1, we will compare $l_{t}^{A}$ with the additive
functional for $\bar{X}_{t}$. Let

$\bar{L}_{t}^{A}:=\frac{1}{t}\int_{0}^{t}A(\bar{X}_{s})\text{\rm{d}}s,$

and

$\bar{l}_{t}^{A}:=\frac{t}{a(t)}(\bar{L}_{t}^{A}-\bar{\mu}(A))=\frac{1}{a(t)}\int_{0}^{t}\big{(}A(\bar{X}_{s})-\bar{\mu}(A)\big{)}\text{\rm{d}}s,$

where $a(t)$ is a positive function satisfying (1.2).

Define the Cramér functional of $\bar{l}_{t}^{A}$:

(3.1) $\displaystyle\Lambda(z)$
$\displaystyle:=\lim_{t\rightarrow+\infty}\frac{t}{a^{2}(t)}\log\mathbb{E}_{x}\bigg{[}\exp\Big{\\{}\frac{a^{2}(t)}{t}z\bar{l}_{t}^{A}\Big{\\}}\bigg{]}$
$\displaystyle=\lim_{t\rightarrow+\infty}\frac{t}{a^{2}(t)}\log\mathbb{E}_{x}\bigg{[}\exp\Big{\\{}\frac{a(t)}{t}z\int_{0}^{t}\big{(}A(\bar{X}_{s})-\bar{\mu}(A)\big{)}\text{\rm{d}}s\Big{\\}}\bigg{]},$

where $\mathbb{E}_{x}$ is the expectation conditioned to $Y_{0}=x$, $z$ is a
constant. The Legendre transformation of $\Lambda(z)$ is defined by

$\Lambda^{*}(y):=\sup_{z\in\mathbb{R}^{d}}\\{zy-\Lambda(z)\\},$

which is related to the rate function. According to the Gärtner-Ellis Theorem
and [9, Theorem 1.3], $\bar{L}_{t}^{A}\in\textrm{MDP}(I)$ for
$I(y)={y^{2}}/({8\bar{V}(A)})$, $y\in\mathbb{R}$.

Below we introduce the following exponential approximation lemma which is
useful in applications, see for instance [8, Theorem 4.2.16] and [14, Theorem
3.2].

######  Lemma 3.1.

(Exponential approximations) If
$\bar{L}_{t}^{A}\in\textrm{MDP}_{u}(I)$(respectively $\textrm{MDP}_{l}(I)$)
and for any $a$ satisfying (1.2),

$\lim_{t\rightarrow\infty}\frac{t}{a^{2}(t)}\log\mathbb{P}(|l_{t}^{A}-\bar{l}_{t}^{A}|>\varepsilon)=-\infty,\,\,\forall\varepsilon>0,$

then $L_{t}^{A}\in\textrm{MDP}_{u}(I)$(respectively $\textrm{MDP}_{l}(I)$).

Using this Lemma, we prove the following result, which is crucial in the
present study.

######  Theorem 3.2.

If $\bar{L}_{t}^{A}\in\textrm{MDP}_{u}(I)$(respectively $\textrm{MDP}_{l}(I)$)
and there exists a constant $\delta>0$ such that

(3.2)
$\displaystyle\mathbb{E}\Big{[}\exp\Big{\\{}\delta\int_{0}^{\infty}|X_{s}-\bar{X}_{s}|\text{\rm{d}}s\Big{\\}}\Big{]}<\infty,$

then $L_{t}^{A}\in\textrm{MDP}_{u}(I)$(respectively $\textrm{MDP}_{l}(I)$).

###### Proof.

Due to that $\lim_{t\rightarrow\infty}\frac{a(t)}{t}=0$, there exists
$t_{0}>0$ such that $\sqrt{\frac{a(t)}{t}}\leq\delta$ when $t\geq t_{0}$.
Below, we assume that $t\geq t_{0}$ and we have

$\mathbb{P}(|l_{t}^{A}-\bar{l}_{t}^{A}|>\varepsilon)\leq\mathbb{P}\Big{(}\sqrt{\frac{a(t)}{t}}\int_{0}^{t}|X_{s}-\bar{X}_{s}|\text{\rm{d}}s>\sqrt{\frac{a(t)}{t}}\frac{a(t)\varepsilon}{K}\Big{)},$

by Chebyshev’s inequality, we obtain

$\displaystyle\mathbb{P}(|l_{t}^{A}-\bar{l}_{t}^{A}|>\varepsilon)$
$\displaystyle\leq\frac{\mathbb{E}\Big{[}\exp\Big{\\{}\sqrt{\frac{a(t)}{t}}\int_{0}^{t}|X_{s}-\bar{X}_{s}|\text{\rm{d}}s\Big{\\}}\Big{]}}{\exp\\{\sqrt{\frac{a(t)}{t}}\frac{a(t)\varepsilon}{K}\\}},$

then (1.2) and (3.2) imply that $\forall\varepsilon>0$,

$\displaystyle\lim_{t\rightarrow\infty}\frac{t}{a^{2}(t)}\log\mathbb{P}(|l_{t}^{A}-\bar{l}_{t}^{A}|>\varepsilon)$
$\displaystyle\leq\lim_{t\rightarrow\infty}\frac{t}{a^{2}(t)}\Big{(}\log\mathbb{E}\Big{[}\exp\Big{\\{}\sqrt{\frac{a(t)}{t}}\int_{0}^{t}|X_{s}-\bar{X}_{s}|\text{\rm{d}}s\Big{\\}}\Big{]}-\sqrt{\frac{a(t)}{t}}\frac{a(t)\varepsilon}{K}\Big{)}$
$\displaystyle\leq\lim_{t\rightarrow\infty}\frac{t}{a^{2}(t)}\log\mathbb{E}\Big{[}\exp\Big{\\{}\delta\int_{0}^{t}|X_{s}-\bar{X}_{s}|\text{\rm{d}}s\Big{\\}}\Big{]}-\lim_{t\rightarrow\infty}\sqrt{\frac{t}{a(t)}}\frac{\varepsilon}{K}$
$\displaystyle=-\infty.$

Then the desired assertion follows from Lemma 3.1. ∎

###### Proof of Theorem 2.1.

Let $\mathscr{L}_{X_{0}}=\nu$ and $\mathscr{L}_{\bar{X}_{0}}=\bar{\mu}$.
According to [9, Theorem 1.1-1.3], $\bar{L}_{t}^{A}\in\textrm{MDP}(I)$. So, it
suffices to show (3.2) for some $\delta>0$.

Condition (H1) implies that the reference SDE (2.2) is well-posed and the
solution is a Markov process, $\bar{\mu}$ is the unique invariant probability
measure of $P_{t}^{*}$. Simply denote
$X_{t}=X_{t}^{\nu},\bar{X}_{t}=\bar{X}_{t}^{x}$ and
$P_{t}^{*}\nu=\mathscr{L}_{X_{t}^{\nu}}$ for
$\nu\in\mathscr{P}_{2}(\mathbb{R}^{d})$. By Itô’s formula and (H1),

$\displaystyle\text{\rm{d}}|X_{t}-\bar{X}_{t}|^{2}$
$\displaystyle\leq\big{\\{}\lambda_{2}W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2}-\lambda_{1}|X_{t}-\bar{X}_{t}|^{2}\big{\\}}\text{\rm{d}}t$
$\displaystyle\quad+2\big{\langle}X_{t}-\bar{X}_{t},\big{(}\sigma(X_{t},P_{t}^{*}\nu)-\sigma(\bar{X}_{t},\bar{\mu})\big{)}\text{\rm{d}}B_{t}\big{\rangle}.$

Let $\xi_{t}=\big{(}e^{-\lambda
t}+|X_{t}-\bar{X}_{t}|^{2}\big{)}^{\frac{1}{2}}$, where
$\lambda:=\lambda_{1}-\lambda_{2}$. By (2.1), we find a constant $C>0$ such
that

$\displaystyle\text{\rm{d}}\xi_{t}\leq-\frac{\lambda_{1}}{2}\xi_{t}\text{\rm{d}}t+Ce^{-\frac{\lambda}{2}t}\text{\rm{d}}t+\text{\rm{d}}M_{t},$

where
$\text{\rm{d}}M_{t}=\frac{1}{\xi_{t}}\big{\langle}X_{t}-\bar{X}_{t},\big{(}\sigma(X_{t},P_{t}^{*}\nu)-\sigma(\bar{X}_{t},\bar{\mu})\big{)}\text{\rm{d}}B_{t}\big{\rangle}$.
Therefore, for some $\delta>0$, we obtain that

$\displaystyle\mathbb{E}\big{[}e^{\delta\int_{0}^{t}\xi_{s}\text{\rm{d}}s}\big{]}$
$\displaystyle\leq e^{\frac{4\delta
C}{\lambda_{1}\lambda}}\mathbb{E}\Big{[}e^{\frac{2\delta\xi_{0}}{\lambda_{1}}}e^{\frac{2\delta}{\lambda_{1}}\int_{0}^{t}\text{\rm{d}}M_{s}}\Big{]}$
$\displaystyle=e^{\frac{4\delta
C}{\lambda_{1}\lambda}}\mathbb{E}\Big{[}\mathbb{E}\big{[}e^{\frac{2\delta\xi_{0}}{\lambda_{1}}}e^{\frac{2\delta}{\lambda_{1}}\int_{0}^{t}\text{\rm{d}}M_{s}}|\mathcal{F}_{0}\big{]}\Big{]}$
$\displaystyle\leq
C(\delta)\Big{(}\mathbb{E}\Big{[}e^{\frac{4\delta\xi_{0}}{\lambda_{1}}}\Big{]}\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{E}\Big{[}e^{\frac{64\delta^{3}\kappa_{2}\sqrt{d}}{\lambda_{1}^{2}}\int_{0}^{t}|X_{s}-\bar{X}_{s}|\text{\rm{d}}s}\Big{]}\Big{)}^{\frac{1}{4}},\,\,\,t>0$

holds for some constant $C(\delta)>0$. Therefore, we obtain that

$\mathbb{E}e^{\delta\int_{0}^{\infty}|X_{s}-\bar{X}_{s}|\text{\rm{d}}s}\leq\mathbb{E}e^{\delta\int_{0}^{\infty}\xi_{s}\text{\rm{d}}s}<\infty$

for $\delta>0$ small enough. Therefore, there exists some constant $\delta>0$
such that (3.2) holds. ∎

###  3.2 Proof of Theorem 2.2

In order to prove Theorem 2.2, we need the following result.

######  Theorem 3.3.

If $\bar{L}_{t}^{A}\in\textrm{MDP}_{u}(I)$(respectively $\textrm{MDP}_{l}(I)$)
and there exists a constant $\delta>0$ such that

(3.3)
$\displaystyle\mathbb{E}\Big{[}\exp\Big{\\{}\delta\int_{0}^{\infty}|X_{s}-\bar{X}_{s}|^{\alpha}\big{(}1+|X_{s}|+|\bar{X}_{s}|\big{)}^{2-\alpha}\text{\rm{d}}s\Big{\\}}\Big{]}<\infty,$

then $L_{t}^{A}\in\textrm{MDP}_{u}(I)$(respectively $\textrm{MDP}_{l}(I)$).

The proof is similar to that of Theorem 3.2, so we omit to save space.

###### Proof of Theorem 2.2.

Let $\mathscr{L}_{X_{0}}=\nu$ and $\mathscr{L}_{\bar{X}_{0}}=\bar{\mu}$.
According to [19, Theorem 2.1], $\bar{L}_{t}^{A}\in\textrm{MDP}(I)$ for
$I(y)={y^{2}}/({8\bar{V}(A)})$, $y\in\mathbb{R}$. Therefore, it suffices to
show (3.3) for some $\delta>0$.

The assumption (H1) and (2.1) yield

$\|\sigma(P_{t}^{*}\nu)-\sigma(\bar{\mu})\|_{HS}^{2}\leq\lambda_{2}W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2}\leq\lambda_{2}e^{-(\lambda_{2}-\lambda_{1})t}W_{2}(\nu,\bar{\mu})^{2}.$

By Young’s inequality and $C_{r}$ inequality, for any $\lambda>0$,

$\displaystyle|X_{t}-\bar{X}_{t}|^{\alpha}\big{(}1+|X_{t}|+|\bar{X}_{t}|\big{)}^{2-\alpha}$
$\displaystyle=|X_{t}-\bar{X}_{t}|^{\alpha}e^{\lambda t}e^{-\lambda
t}\big{(}1+|X_{t}|+|\bar{X}_{t}|\big{)}^{2-\alpha}$
$\displaystyle\leq\frac{\alpha}{2}e^{\frac{2\lambda
t}{\alpha}}|X_{t}-\bar{X}_{t}|^{2}+\frac{2-\alpha}{2}e^{-\frac{2\lambda
t}{2-\alpha}}3\big{(}1+|X_{t}|^{2}+|\bar{X}_{t}|^{2}\big{)}.$

Below, for simplicity, we take
$\lambda<\frac{\alpha(\lambda_{1}-\lambda_{2})}{2}$. By Hölder’s inequality,
we have

$\displaystyle\mathbb{E}\Big{[}e^{\delta\int_{0}^{\infty}|X_{s}-\bar{X}_{s}|^{\alpha}(1+|X_{s}|+|\bar{X}_{s}|)^{2-\alpha}\text{\rm{d}}s}\Big{]}$
$\displaystyle\leq\Big{(}\mathbb{E}\Big{[}e^{\alpha\delta\int_{0}^{\infty}e^{\frac{2\lambda
s}{\alpha}}|X_{s}-\bar{X}_{s}|^{2}\text{\rm{d}}s}\Big{]}\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{E}\Big{[}e^{3(2-\alpha)\delta\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}(1+|X_{s}|^{2}+|\bar{X}_{s}|^{2})\text{\rm{d}}s}\Big{]}\Big{)}^{\frac{1}{2}}.$

Below search for a constant $\delta>0$ such that

$I_{1}:=\mathbb{E}\Big{[}e^{\alpha\delta\int_{0}^{\infty}e^{\frac{2\lambda
s}{\alpha}}|X_{s}-\bar{X}_{s}|^{2}\text{\rm{d}}s}\Big{]}<\infty,$

and

$I_{2}:=\mathbb{E}\Big{[}e^{3(2-\alpha)\delta\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}(1+|X_{s}|^{2}+|\bar{X}_{s}|^{2})\text{\rm{d}}s}\Big{]}<\infty.$

By Itô’s formula and (H1), we have

$\text{\rm{d}}|X_{t}-\bar{X}_{t}|^{2}\leq\big{(}\lambda_{2}W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2}-\lambda_{1}|X_{t}-\bar{X}_{t}|^{2}\big{)}\text{\rm{d}}t+2\langle
X_{t}-\bar{X}_{t},\big{(}\sigma(P_{t}^{*}\nu)-\sigma(\bar{\mu})\big{)}\text{\rm{d}}B_{t}\rangle.$

By the chain rule, we obtain

$\displaystyle\text{\rm{d}}\\{e^{\frac{2\lambda
t}{\alpha}}|X_{t}-\bar{X}_{t}|^{2}\\}$ $\displaystyle\leq e^{\frac{2\lambda
t}{\alpha}}\Big{\\{}\frac{2\lambda}{\alpha}|X_{t}-\bar{X}_{t}|^{2}+\lambda_{2}W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2}-\lambda_{1}|X_{t}-\bar{X}_{t}|^{2}\Big{\\}}\text{\rm{d}}t$
$\displaystyle\,\,\,\,\,+2e^{\frac{2\lambda t}{\alpha}}\langle
X_{t}-\bar{X}_{t},\big{(}\sigma(P_{t}^{*}\nu)-\sigma(\bar{\mu})\big{)}\text{\rm{d}}B_{t}\rangle.$

Therefore, we obtain that

$\displaystyle\mathbb{E}\Big{[}e^{\alpha\delta\int_{0}^{t}e^{\frac{2\lambda
s}{\alpha}}|X_{s}-\bar{X}_{s}|^{2}\text{\rm{d}}s}\Big{]}$ $\displaystyle\leq
C_{1}(\delta)\mathbb{E}\Big{[}e^{\frac{\alpha\delta|X_{0}-\bar{X}_{0}|^{2}}{\lambda_{1}-2\lambda/{\alpha}}+\frac{2\alpha\delta}{\lambda_{1}-2\lambda/{\alpha}}\int_{0}^{t}e^{\frac{2\lambda
s}{\alpha}}\langle
X_{s}-\bar{X}_{s},(\sigma(P_{s}^{*}\nu)-\sigma(\bar{\mu}))\text{\rm{d}}B_{s}\rangle}\Big{]}$
$\displaystyle=C_{1}(\delta)\mathbb{E}\Big{[}\mathbb{E}\big{[}e^{\frac{\alpha\delta|X_{0}-\bar{X}_{0}|^{2}}{\lambda_{1}-2\lambda/{\alpha}}+\frac{2\alpha\delta}{\lambda_{1}-2\lambda/{\alpha}}\int_{0}^{t}e^{\frac{2\lambda
s}{\alpha}}\langle
X_{s}-\bar{X}_{s},(\sigma(P_{s}^{*}\nu)-\sigma(\bar{\mu}))\text{\rm{d}}B_{s}\rangle}|\mathcal{F}_{0}\big{]}\Big{]}$
$\displaystyle\leq
C_{1}(\delta)\Big{(}\mathbb{E}\Big{[}e^{\frac{\alpha\delta|X_{0}-\bar{X}_{0}|^{2}}{\lambda_{1}-2\lambda/{\alpha}}}\Big{]}\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{E}\Big{[}e^{\frac{32\alpha^{2}\delta^{2}\lambda_{2}W_{2}(\nu,\bar{\mu})^{2}}{(\lambda_{1}-2\lambda/{\alpha})^{2}}\int_{0}^{t}e^{\frac{2\lambda
s}{\alpha}}|X_{s}-\bar{X}_{s}|^{2}\text{\rm{d}}s}\Big{]}\Big{)}^{\frac{1}{4}},$

where
$C_{1}(\delta):=e^{\frac{\alpha\delta\lambda_{2}W_{2}(\nu,\bar{\mu})^{2}}{(\lambda_{1}-2\lambda/{\alpha})(\lambda_{1}-\lambda_{2}-2\lambda/{\alpha})}}$.
We choose $\delta$ such that
$\delta\leq\frac{(\lambda_{1}-2\lambda/{\alpha})^{2}}{32\alpha\lambda_{2}W_{2}(\nu,\bar{\mu})^{2}}$,
which leads to $I_{1}<\infty$.

Next we need to prove that $I_{2}<\infty$. By (B1), there exist constants
$c_{1},c_{2}>0$ such that

(3.4)
$\displaystyle\text{\rm{d}}|X_{t}|^{2}\leq\big{(}c_{2}-c_{1}|X_{t}|^{2}+c_{2}W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2}\big{)}\text{\rm{d}}t+2\langle
X_{t},\sigma(P_{t}^{*}\nu)\text{\rm{d}}B_{t}\rangle,$ (3.5)
$\displaystyle\text{\rm{d}}|\bar{X}_{t}|^{2}\leq\big{(}c_{2}-c_{1}|\bar{X}_{t}|^{2}+c_{2}\|\bar{\mu}\|_{2}^{2}\big{)}\text{\rm{d}}t+2\langle\bar{X}_{t},\sigma(\bar{\mu})\text{\rm{d}}B_{t}\rangle,$

and

$\|\sigma(P_{t}^{*}\nu)\|_{HS}^{2}\leq
c_{2}\big{(}1+W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2}\big{)}.$

Recall that

$\displaystyle I_{2}$
$\displaystyle:=\mathbb{E}\Big{[}e^{3(2-\alpha)\delta\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}(1+|X_{s}|^{2}+|\bar{X}_{s}|^{2})\text{\rm{d}}s}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}e^{3(2-\alpha)\delta\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}\text{\rm{d}}s+3(2-\alpha)\delta\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}|X_{s}|^{2}\text{\rm{d}}s+3(2-\alpha)\delta\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}|\bar{X}_{s}|^{2}\text{\rm{d}}s}\Big{]}$ $\displaystyle\leq
e^{\frac{3\delta(2-\alpha)^{2}}{2\lambda}}\Big{(}\mathbb{E}\Big{[}e^{6\delta{(2-\alpha)}\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}|X_{s}|^{2}\text{\rm{d}}s}\Big{]}\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{E}\Big{[}e^{6\delta{(2-\alpha)}\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}|\bar{X}_{s}|^{2}\text{\rm{d}}s}\Big{]}\Big{)}^{\frac{1}{2}}.$

Thus, for $I_{2}<\infty$, it suffices to show

$I_{2}^{\prime}:=\mathbb{E}\Big{[}e^{6\delta{(2-\alpha)}\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}|X_{s}|^{2}\text{\rm{d}}s}\Big{]}<\infty,$

and

$I_{2}^{\prime\prime}:=\mathbb{E}\Big{[}e^{6\delta{(2-\alpha)}\int_{0}^{\infty}e^{-\frac{2\lambda
s}{2-\alpha}}|\bar{X}_{s}|^{2}\text{\rm{d}}s}\Big{]}<\infty.$

By the chain rule and (3.4), we have

$\displaystyle\text{\rm{d}}\\{e^{-\frac{2\lambda t}{2-\alpha}}|X_{t}|^{2}\\}$
$\displaystyle\leq e^{-\frac{2\lambda
t}{2-\alpha}}\big{\\{}\big{(}-\frac{2\lambda}{2-\alpha}-c_{1}\big{)}|X_{t}|^{2}+c_{2}+c_{2}W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2}\big{\\}}\text{\rm{d}}t+2e^{-\frac{2\lambda
t}{2-\alpha}}\langle X_{t},\sigma(P_{t}^{*}\nu)\text{\rm{d}}B_{t}\rangle.$

Then

$\displaystyle\mathbb{E}\Big{[}e^{6\delta{(2-\alpha)}\int_{0}^{t}e^{-\frac{2\lambda
s}{2-\alpha}}|X_{s}|^{2}\text{\rm{d}}s}\Big{]}$ $\displaystyle\leq
C_{2}(\delta)\mathbb{E}\Big{[}e^{\frac{6\delta{(2-\alpha)}|X_{0}|^{2}}{2\lambda/(2-\alpha)+c_{1}}}e^{\frac{12\delta{(2-\alpha)}}{2\lambda/(2-\alpha)+c_{1}}\int_{0}^{t}e^{-\frac{2\lambda
s}{2-\alpha}}\langle
X_{s},\sigma(P_{s}^{*}\nu)\text{\rm{d}}B_{s}\rangle}\Big{]}$
$\displaystyle\leq
C_{2}(\delta)\Big{(}\mathbb{E}\Big{[}e^{\frac{12\delta{(2-\alpha)}|X_{0}|^{2}}{2\lambda/(2-\alpha)+c_{1}}}\Big{]}\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{E}\Big{[}e^{\frac{288\delta^{2}(2-\alpha)^{4}c_{2}(1+W_{2}(\nu,\bar{\mu})^{2})}{(2\lambda+c_{1}(2-\alpha))^{2}}\int_{0}^{t}e^{-\frac{2\lambda
s}{2-\alpha}}|X_{s}|^{2}\text{\rm{d}}s}\Big{]}\Big{)}^{\frac{1}{4}},$

where
$C_{2}(\delta)=\exp\big{\\{}6c_{2}\delta(2-\alpha)^{3}\big{(}\frac{1}{4\lambda^{2}+2\lambda
c_{1}(2-\alpha)}+\frac{1}{(2\lambda+c_{1}(2-\alpha))(2\lambda+(\lambda_{1}-\lambda_{2})(2-\alpha))}\big{)}\big{\\}}$.
Then for
$\delta\leq\frac{(2\lambda+c_{1}(2-\alpha))^{2}}{48\delta(2-\alpha)^{3}c_{2}(1+W_{2}(\nu,\bar{\mu})^{2})}$,
we have $I_{2}^{\prime}<\infty$.

On the other hand, the same argument gives

$\displaystyle\mathbb{E}\Big{[}e^{6\delta{(2-\alpha)}\int_{0}^{t}e^{-\frac{2\lambda
s}{2-\alpha}}|\bar{X}_{s}|^{2}\text{\rm{d}}s}\Big{]}\leq
C_{3}(\delta)\Big{(}\mathbb{E}\Big{[}e^{\frac{12\delta{(2-\alpha)}|\bar{X}_{0}|^{2}}{2\lambda/(2-\alpha)+c_{1}}}\Big{]}\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{E}\Big{[}e^{\frac{288\delta^{2}(2-\alpha)^{4}\|\sigma(\bar{\mu})\|_{HS}^{2}}{(2\lambda+c_{1}(2-\alpha))^{2}}\int_{0}^{t}e^{-\frac{2\lambda
s}{2-\alpha}}|\bar{X}_{s}|^{2}\text{\rm{d}}s}\Big{]}\Big{)}^{\frac{1}{4}}$

where
$C_{3}(\delta)=\exp\\{\frac{6\delta(2-\alpha)^{3}c_{2}(1+\|\bar{\mu}\|_{2}^{2})}{4\lambda^{2}+2\lambda
c_{1}(2-\alpha)}\\}$. So, when
$\delta\leq\frac{(2\lambda+c_{1}(2-\alpha))^{2}}{48\delta(2-\alpha)^{3}\|\sigma(\bar{\mu})\|_{HS}^{2}}$
we have $I_{2}^{\prime\prime}<\infty$.

Finally, we take
$\delta\leq\min\Big{\\{}\frac{(\lambda_{1}-2\lambda/{\alpha})^{2}}{32\alpha\lambda_{2}W_{2}(\nu,\bar{\mu})^{2}},\frac{(2\lambda+c_{1}(2-\alpha))^{2}}{48\delta(2-\alpha)^{3}c_{2}(1+W_{2}(\nu,\bar{\mu})^{2})},\frac{(2\lambda+c_{1}(2-\alpha))^{2}}{48\delta(2-\alpha)^{3}\|\sigma(\bar{\mu})\|_{HS}^{2}}\Big{\\}}$.
We conclude, there exists $\delta>0$ such that $I_{2}<\infty$, which together
with $I_{1}<\infty$ finishes the proof. ∎

###  3.3 Proof of Theorem 2.3

Let $\mathscr{L}_{X_{0}}=\nu$ and $\mathscr{L}_{\bar{X}_{0}}=\bar{\mu}$.
According to [19, Theorem 2.1], $\bar{L}_{t}^{A}\in\textrm{MDP}(I)$ for
$I(y)={y^{2}}/({8\bar{V}(A)})$, $y\in\mathbb{R}$. Therefore, by the Lemma 3.1
(see also [8, Theorem 4.2.16] or [14, Theorem 3.2]), it suffices to prove

(3.6)
$\displaystyle\mathbb{E}\Big{[}\exp\Big{\\{}\delta\int_{0}^{\infty}\frac{\big{(}1+|X_{s}|^{2}+|\bar{X}_{s}|^{2}\big{)}}{\log(e+|X_{s}|^{2}+|\bar{X}_{s}|^{2})[\log(e+|X_{s}-\bar{X}_{s}|^{-1})]^{p}}\text{\rm{d}}s\Big{\\}}\Big{]}<\infty$

for some constant $\delta>0$.

By the chain rule and (H1), we have

$\displaystyle\text{\rm{d}}\big{(}e^{\lambda_{1}t}|X_{t}-\bar{X}_{t}|^{2}\big{)}$
$\displaystyle=e^{\lambda_{1}t}\big{\\{}\lambda_{1}|X_{t}-\bar{X}_{t}|^{2}\text{\rm{d}}t+\text{\rm{d}}|X_{t}-\bar{X}_{t}|^{2}\big{\\}}$
$\displaystyle\leq\lambda_{2}e^{\lambda_{1}t}W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2}\text{\rm{d}}t.$

Then we obtain

$\displaystyle|X_{t}-\bar{X}_{t}|^{2}\leq
e^{-(\lambda_{1}-\lambda_{2})t}W_{2}(\nu,\bar{\mu})^{2},$

this implies that

$\displaystyle|X_{t}-\bar{X}_{t}|^{-1}\geq
e^{\frac{\lambda_{1}-\lambda_{2}}{2}t}W_{2}(\nu,\bar{\mu})^{-1}.$

Let $\alpha=\sup_{t\geq 0}\big{(}|X_{t}|^{2}+|\bar{X}_{t}|^{2}\big{)}$,
$\beta=W_{2}(\nu,\bar{\mu})$, $\lambda=\frac{\lambda_{1}-\lambda_{2}}{2}$,
then we have

$\displaystyle\int_{0}^{\infty}|A(X_{t})-A(\bar{X}_{t})|\text{\rm{d}}t\leq\frac{e+\alpha}{\log(e+\alpha)}\int_{0}^{\infty}\frac{\text{\rm{d}}t}{[\log(e+\beta^{-1}e^{\lambda
t})]^{p}}.$

Let $\beta^{-1}e^{\lambda t}=s$, then we have
$\text{\rm{d}}t=\frac{\text{\rm{d}}s}{\lambda s}$, so that

$\displaystyle\int_{0}^{\infty}\frac{\text{\rm{d}}t}{[\log(e+\beta^{-1}e^{\lambda
t})]^{p}}$
$\displaystyle=\frac{1}{\lambda}\int_{\beta^{-1}}^{\infty}\frac{\text{\rm{d}}s}{s[\log(e+s)]^{p}}$
$\displaystyle\leq\frac{1}{\lambda}\int_{\beta^{-1}}^{\beta^{-1}+1}\frac{\text{\rm{d}}s}{s}+\frac{1}{\lambda}\int_{\beta^{-1}+1}^{\infty}\big{(}1+\frac{e}{1+\beta^{-1}}\big{)}\big{(}\log(e+s)\big{)}^{-p}\text{\rm{d}}{\log(e+s)}$
$\displaystyle\leq\frac{\log(1+\beta)}{\lambda}+\frac{1+e}{\lambda(p-1)}.$

Thus,

(3.7)
$\displaystyle\int_{0}^{\infty}|A(X_{t})-A(\bar{X}_{t})|\text{\rm{d}}t\leq\frac{1}{\lambda}\Big{\\{}\frac{(e+\alpha)(1+e)}{p-1}+J\Big{\\}},$

where $J:=\frac{e+\alpha}{\log(e+\alpha)}\cdot\log(e+\beta)$. Let

$h(\alpha)=\frac{e+\alpha}{\log(e+\alpha)}\cdot\log(e+\beta)-\alpha.$

When $\alpha\geq\beta$, we have $h^{\prime}(\alpha)\leq 0$, which implies that
$h$ decreases with respect to $\alpha$, and we obtain that $J\leq\alpha+e$.

When $0<\alpha<\beta$, let $g(\alpha)=\frac{e+\alpha}{\log(e+\alpha)}$, we
have $g^{\prime}(\alpha)\geq 0$, which implies that $g$ increases in $\alpha$,
so that
$\sup_{\alpha\in(0,\beta)}h(\alpha)\leq\frac{e+\beta}{\log(e+\beta)}\cdot\log(e+\beta)=e+\beta$.

Combining this with (3.7), we find a constant $C_{0}>0$ such that

$\displaystyle\int_{0}^{\infty}|A(X_{t})-A(\bar{X}_{t})|\text{\rm{d}}t$
$\displaystyle\leq C_{0}(e+\alpha+\beta)$
$\displaystyle=C_{0}\Big{\\{}\sup_{t>0}\\{|X_{t}|^{2}+|\bar{X}_{t}|^{2}\\}+W_{2}(\nu,\bar{\mu})+e\Big{\\}}.$

Since
$\mathbb{E}[e^{\delta|X_{0}|^{2}}]+\bar{\mu}(e^{\delta|\cdot|^{2}})<\infty$
for some $\delta>0$ and $\mathscr{L}_{\bar{X}_{t}}=\bar{\mu}$, (3.6) follows
if

(3.8)
$\displaystyle\mathbb{E}\Big{[}\sup_{t>0}e^{\delta|X_{t}|^{2}}\Big{]}<\infty$

holds for some $\delta>0$.

Indeed, (3.8) holds also for $\bar{X}_{t}$ replacing $X_{t}$, since when
$\mathscr{L}_{\bar{X}_{0}}=\bar{\mu}$, we have $\mathscr{L}_{(X_{t})_{t\geq
0}}=\mathscr{L}_{(\bar{X}_{t})_{t\geq 0}}$.

By (H1), there exists a constant $C_{1}>0$ such that

$\displaystyle\text{\rm{d}}\left(e^{(\lambda_{1}-\lambda_{2})t}|X_{t}|^{2}\right)\leq
C_{1}e^{(\lambda_{1}-\lambda_{2})t}\text{\rm{d}}t+2e^{(\lambda_{1}-\lambda_{2})t}\langle
X_{t},\sigma\text{\rm{d}}B_{t}\rangle.$

So,

$\displaystyle\delta|X_{t}|^{2}\leq\frac{\delta C_{1}}{\tilde{\lambda}}+\delta
e^{-\tilde{\lambda}t}|X_{0}|^{2}+2\delta
e^{-\tilde{\lambda}t}\int_{0}^{t}e^{\tilde{\lambda}s}\langle
X_{s},\sigma\text{\rm{d}}B_{s}\rangle,$

where $\tilde{\lambda}:=\lambda_{1}-\lambda_{2}$. Therefore, we obtain

$\displaystyle\mathbb{E}\Big{[}\sup_{0\leq s\leq
t}e^{\delta|X_{s}|^{2}}\Big{]}$ $\displaystyle\leq e^{\delta
C_{1}/{\tilde{\lambda}}}\mathbb{E}\Big{[}\mathbb{E}\Big{[}\sup_{0\leq s\leq
t}e^{\delta|X_{0}|^{2}}\cdot e^{2\delta
e^{-\tilde{\lambda}s}\int_{0}^{s}e^{\tilde{\lambda}u}\langle
X_{u},\sigma\text{\rm{d}}B_{u}\rangle}|\mathcal{F}_{0}\Big{]}\Big{]}$ (3.9)
$\displaystyle\leq e^{\delta
C_{1}/{\tilde{\lambda}}}\Big{(}\mathbb{E}\Big{[}e^{2\delta|X_{0}|^{2}}\Big{]}\Big{)}^{\frac{1}{2}}\cdot\Big{(}\mathbb{E}\Big{[}\sup_{0\leq
s\leq t}e^{4\delta
e^{-\tilde{\lambda}s}\int_{0}^{s}e^{\tilde{\lambda}u}\langle
X_{u},\sigma\text{\rm{d}}B_{u}\rangle}\Big{]}\Big{)}^{\frac{1}{2}}.$

By the BDG inequality, there exists a constant $C_{2}>0$, such that

$\displaystyle\tilde{J}:=\mathbb{E}\Big{[}\sup_{0\leq s\leq t}e^{4\delta
e^{-\tilde{\lambda}s}\int_{0}^{s}e^{\tilde{\lambda}u}\langle
X_{u},\sigma\text{\rm{d}}B_{u}\rangle}\Big{]}$ $\displaystyle\leq
C_{2}\Big{(}\mathbb{E}\Big{[}e^{16\delta^{2}e^{-2\tilde{\lambda}t}\int_{0}^{t}e^{2\tilde{\lambda}u}|\sigma^{*}X_{u}|^{2}\text{\rm{d}}u}\Big{]}\Big{)}^{\frac{1}{2}}$
$\displaystyle=C_{2}\Big{(}\mathbb{E}\Big{[}e^{16\delta^{2}\int_{0}^{t}\|\sigma\|^{2}|X_{s}|^{2}\frac{1-e^{-2\tilde{\lambda}t}}{2\tilde{\lambda}}\frac{2\tilde{\lambda}}{1-e^{-2\tilde{\lambda}t}}e^{-2\tilde{\lambda}(t-s)}\text{\rm{d}}s}\Big{]}\Big{)}^{\frac{1}{2}}.$

Since
$\lambda_{t}(\text{\rm{d}}s):=\frac{2\tilde{\lambda}}{1-e^{-2\tilde{\lambda}t}}e^{-2\tilde{\lambda}(t-s)}\text{\rm{d}}s$
is a probability measure on $[0,t]$, therefore by the Jensen’s inequality, we
obtain

$\displaystyle\tilde{J}$ $\displaystyle\leq
C_{2}\Big{(}\mathbb{E}\Big{[}e^{\frac{16\delta^{2}(1-e^{-2\tilde{\lambda}t})}{2\tilde{\lambda}}\int_{0}^{t}\|\sigma\|^{2}|X_{s}|^{2}\lambda_{t}(\text{\rm{d}}s)}\Big{]}\Big{)}^{\frac{1}{2}}$
$\displaystyle\leq
C_{2}\Big{(}\mathbb{E}\Big{[}\int_{0}^{t}e^{\frac{8\delta^{2}\|\sigma\|^{2}|X_{s}|^{2}}{\tilde{\lambda}}}\lambda_{t}(\text{\rm{d}}s)\Big{]}\Big{)}^{\frac{1}{2}}.$

When $t\geq 1$, we have

$\displaystyle\tilde{J}\leq\frac{C_{2}^{2}}{4\tilde{\lambda}}+\tilde{\lambda}\int_{0}^{t}\mathbb{E}\Big{[}e^{\delta|X_{s}|^{2}-2\tilde{\lambda}(t-s)}\Big{]}\text{\rm{d}}s.$

Substituting into (3.3) and applying the Gronwall’s lemma, we obtain

(3.10) $\displaystyle\mathbb{E}\Big{[}\sup_{0\leq s\leq
t}e^{\delta|X_{s}|^{2}}\Big{]}$ $\displaystyle\leq
C_{3}\Big{(}1+\mathbb{E}\Big{[}\sup_{0\leq s\leq
1}e^{\delta|X_{s}|^{2}}\Big{]}\Big{)}$

for some constant $C_{3}>0$. Finally,

$\displaystyle\mathbb{E}\Big{[}\sup_{0\leq t\leq
1}e^{\delta|X_{t}|^{2}}\Big{]}\leq\Big{(}\mathbb{E}\Big{[}e^{2\delta|X_{0}|^{2}}\Big{]}\Big{)}^{\frac{1}{2}}\cdot
e^{c\delta\int_{0}^{1}(1+W_{2}(P_{t}^{*}\nu,\bar{\mu})^{2})\text{\rm{d}}t}\cdot\Big{(}\mathbb{E}\Big{[}\sup_{0\leq
t\leq 1}e^{4\delta\int_{0}^{t}\langle
X_{s},\sigma\text{\rm{d}}B_{s}\rangle}\Big{]}\Big{)}^{\frac{1}{2}}.$

By the exponential martingale inequality and the Jensen’s inequality, we
obtain that there exists a constant $C_{\delta}$ such that

$\displaystyle\mathbb{E}\Big{[}\sup_{0\leq t\leq
1}e^{\delta|X_{t}|^{2}}\Big{]}$ $\displaystyle\leq
C_{\delta}\sqrt{e}\Big{(}\int_{0}^{1}\mathbb{E}\big{[}e^{16\delta^{2}\|\sigma\|^{2}|X_{s}|^{2}}\big{]}\text{\rm{d}}s\Big{)}^{\frac{1}{4}}.$

Taking $\delta\leq{1}/({16\|\sigma\|^{2}})$ and we obtain that
$\mathbb{E}\Big{[}\sup_{0\leq t\leq 1}e^{\delta|X_{t}|^{2}}\Big{]}<\infty$.
This together with (3.10) imply that $\mathbb{E}\Big{[}\sup_{0\leq s\leq
t}e^{\delta|X_{s}|^{2}}\Big{]}<\infty$.

###  3.4 Proof of Theorem 2.4

Let

$\rho(\xi_{1},\xi_{2}):=\left(|\xi_{1}^{(1)}-\xi_{2}^{(1)}|^{2}+|\xi_{1}^{(2)}-\xi_{2}^{(2)}|^{2}\right)^{1/2}.$

We take $X_{0},Y_{0}\in
L^{2}(\Omega\rightarrow\mathbb{R}^{m+d},\mathcal{F}_{0},\mathbb{P})$ such that
$\mathscr{L}_{X_{0}}=\mu_{0},\mathscr{L}_{Y_{0}}=\nu_{0}$ and

$W_{2}(\mu_{0},\nu_{0})^{2}=\mathbb{E}\rho(X_{0},Y_{0})^{2}.$

Let $X_{t}=(X_{t}^{(1)},X_{t}^{(2)})$ and $Y_{t}=(Y_{t}^{(1)},Y_{t}^{(2)})$
solve (2.4) with initial values $X_{0}$ and $Y_{0}$ respectively. Obviously,
$X_{t}^{(1)}-Y_{t}^{(1)}$ and $X_{t}^{(2)}-Y_{t}^{(2)}$ solve the ODE

(3.11) $\displaystyle\left\\{\begin{aligned}
\text{\rm{d}}(X_{t}^{(1)}-Y_{t}^{(1)})&=\Big{(}A(X_{t}^{(1)}-Y_{t}^{(1)})+B(X_{t}^{(2)}-Y_{t}^{(2)})\Big{)}\text{\rm{d}}t,\\\
\text{\rm{d}}(X_{t}^{(2)}-Y_{t}^{(2)})&=\Big{(}Z(X_{t},\mathscr{L}_{X_{t}})-Z(Y_{t},\mathscr{L}_{Y_{t}})\Big{)}\text{\rm{d}}t.\end{aligned}\right.$

Since $r_{0}\in(-\|B\|^{-1},\|B\|^{-1})$, for any $r>0$ there exists a
constant $C>1$ such that

$\displaystyle\frac{1}{C}\big{(}|X_{t}^{(1)}-Y_{t}^{(1)}|^{2}+|X_{t}^{(2)}-Y_{t}^{(2)}|^{2}\big{)}$
$\displaystyle\leq\Psi_{t}:=\frac{r^{2}}{2}|X_{t}^{(1)}-Y_{t}^{(1)}|^{2}+\frac{1}{2}|X_{t}^{(2)}-Y_{t}^{(2)}|^{2}+rr_{0}\langle
X_{t}^{(1)}-Y_{t}^{(1)},B(X_{t}^{(2)}-Y_{t}^{(2)})\rangle$ $\displaystyle\leq
C\big{(}|X_{t}^{(1)}-Y_{t}^{(1)}|^{2}+|X_{t}^{(2)}-Y_{t}^{(2)}|^{2}\big{)}.$

Combining this with (3.11) and (D3), we obtain

$\displaystyle\text{\rm{d}}\Psi_{t}$
$\displaystyle\leq-\theta_{1}\big{(}|X_{t}^{(1)}-Y_{t}^{(1)}|^{2}+|X_{t}^{(2)}-Y_{t}^{(2)}|^{2}\big{)}+\theta_{2}W_{2}(P_{t}^{*}\mu_{0},P_{t}^{*}\nu_{0})^{2},$

by the chain rule, we have

$\displaystyle\text{\rm{d}}(e^{\lambda t}\Psi_{t})$ $\displaystyle\leq
e^{\lambda
t}\big{\\{}\lambda\Psi_{t}-\theta_{1}\big{(}|X_{t}^{(1)}-Y_{t}^{(1)}|^{2}+|X_{t}^{(2)}-Y_{t}^{(2)}|^{2}\big{)}+\theta_{2}W_{2}(P_{t}^{*}\mu_{0},P_{t}^{*}\nu_{0})^{2}\big{\\}}\text{\rm{d}}t,$

thus we obtain

$\displaystyle\mathbb{E}\Psi_{t}$ $\displaystyle\leq e^{-\lambda
t}\mathbb{E}\Psi_{0}-e^{-\lambda t}\int_{0}^{t}e^{\lambda
s}(\theta_{1}-\theta_{2}-\lambda
C)\mathbb{E}\big{[}|X_{s}^{(1)}-Y_{s}^{(1)}|^{2}+|X_{s}^{(2)}-Y_{s}^{(2)}|^{2}\big{]}\text{\rm{d}}s,$

we take $\lambda=\frac{\theta_{1}-\theta_{2}}{2C}$ and we obtain

$\displaystyle\mathbb{E}\Psi_{t}$ $\displaystyle\leq
e^{-\frac{\theta_{1}-\theta_{2}}{2C}t}\mathbb{E}\Psi_{0},$

and we deduce that

$\displaystyle W_{2}(P_{t}^{*}\mu_{0},P_{t}^{*}\nu_{0})^{2}$
$\displaystyle\leq\mathbb{E}[\rho(X_{t},Y_{t})^{2}]$ $\displaystyle\leq
Ce^{-\frac{\theta_{1}-\theta_{2}}{2C}t}W_{2}(\mu_{0},\nu_{0})^{2},$

Consequently, $P_{t}^{*}$ has a unique invariant probability measure
$\bar{\mu}$ such that (2.9) holds.

Next, let $\mathscr{L}_{\bar{X}_{0}}=\bar{\mu}$, consider the reference
Stochastic Hamiltonian System for
$\bar{X}_{t}=(\bar{X}_{t}^{(1)},\bar{X}_{t}^{(2)})$ on $\mathbb{R}^{m+d}$:

(3.12) $\displaystyle\left\\{\begin{aligned}
\text{\rm{d}}\bar{X}_{t}^{(1)}&=(A\bar{X}_{t}^{(1)}+B\bar{X}_{t}^{(2)})\text{\rm{d}}t,\\\
\text{\rm{d}}\bar{X}_{t}^{(2)}&=Z(\bar{X}_{t},\bar{\mu})dt+M\text{\rm{d}}B_{t}.\end{aligned}\right.$

According to [19, Theorem 3.1], $\bar{L}_{t}^{A}\in\textrm{MDP}(I)$ for
$I(y)={y^{2}}/({8\bar{V}(A)})$. Since $A$ is Lipschitz continuous, by (2.9),
we can find some small $\delta>0$ such that (3.2) holds. Therefore, the proof
is finished by Theorem 3.2.

#### Acknowledgement.

The authors would like to thank Professor Feng-Yu Wang for supervision.

## References

  * [1] P. A. Baldi, _Large deviations and stochastic homogenisation_ , Ann. Mat. Pura Appl. 151(1988), 161–177.
  * [2] A. A. Borovkov, A. A. Mogulskii, _Probabilities of large deviations in topological vector space I_ , Siberian Math. J. 19(1978), 697–709.
  * [3] A. A. Borovkov, A. A. Mogulskii, _Probabilities of large deviations in topological vector space II_ , Siberian Math. J. 21(1980), 12–26.
  * [4] J. Bao, F.-Y. Wang, C. Yuan, _Limit theorems for additive functionals of path-depedent SDEs_ , Discrete Contin. Dyn. Syst. 40(2020), 5173–5188.
  * [5] X. Chen, _The moderate deviations of independent random vectors in a Banach space_ , Chinese J. Appl. Probab. Statist. 7(1991), 24–32.
  * [6] P. Cattiaux, P. Dai Pra, S. Roelly, _A constructive approach to a class of ergodic HJB equatons with unbounded and nonsmooth cost_ , SIAM J. Control Optim. 47(2008), 2598–2615.
  * [7] M. D. Donsker, S. R. S. Varadhan, _Asymptotic evaluation of certain Markov process expectations for large time, I-IV_ , Comm. Pure Appl. Math. 28(1975), 1–47, 279–301; 29(1976), 389–461; 36(1983), 183–212.
  * [8] A. Dembo, O. Zeitouni, _Large Deviations Techniques and Applications_ , Second Edition, Springer, New York. 1998.
  * [9] F. Gao, _Long time asymptotics of unbounded additive functionals of Markov processes_ , Electron. J. Probab. 22(2017), 1–21.
  * [10] X. Huang, P. Ren, F.-Y. Wang, _Distribution Dependent Stochastic Differential Equation_ , arXiv:2012.13656.
  * [11] K. Itô, M. Nisio, _On stationary solutions of a stochastic differential equation_ , J. Math.Kyoto Univ. 4(1964), 1–75.
  * [12] I. Kontoyiannis, S. P. Meyn, _Spectral theory and limit theorems for geometrically ergodic Markov processes_ , Ann. Appl. Probab. 13(2003), 304–362.
  * [13] P. Ren, F.-Y. Wang, _Donsker-Varadhan Large Deviations for Path-Distribution Dependent SPDEs_ , arXiv:2002.08652.
  * [14] M. Röckner, F.-Y. Wang, L. Wu, _Large deviations for stochastic generalized porous media equations_ , Stoch. Proc. Appl. 116(2006), 1677–1689.
  * [15] D. W. Stroock, S. R. S. Varadhan, _Multidimensional Diffusion Processes_ , Springer, New York. 1979.
  * [16] F.-Y. Wang, _Harnack inequality for SDE with multiplicative noise and extension to Neumann semigroup on nonconvex mainfolds_ , Ann. Probab. 39(2011), 1449–1467.
  * [17] F.-Y. Wang, _Hypercontractivity and applications for stochastic Hamiltonian systems_ , J. Funct. Anal. 272(2017), 5360–5383.
  * [18] F.-Y. Wang, _Distribution dependent SDEs for Landau type equations._ Stoch. Proc. Appl. 128(2018), 595–621.
  * [19] F.-Y. Wang, Y. Zhang, _Application of Harnack inequality to long time asymptotics of Markov processes(in Chinese)_ , Sci. Sin. Math. 49(2019), 505–516.
  * [20] L. Wu, _Moderate deviations of dependent random variables related to CLT_ , Ann. Probab. 23(1995), 420–445.
  * [21] L. Wu, _Uniformly integrable operators and large deviations for Markov processes_ , J. Funct. Anal. 172(2000), 301–376.


lemtheorem lem coroltheorem corol observationtheorem observation
observationSubclm observationSub

# On Strong Linearizability and Write Strong Linearizability in Message-
Passing

David Yu Cheng Chan<EMAIL_ADDRESS>University of
CalgaryCalgaryAlbertaCanada ,  Vassos Hadzilacos<EMAIL_ADDRESS>University of TorontoTorontoOntarioCanada ,  Xing Hu<EMAIL_ADDRESS>University of TorontoTorontoOntarioCanada and  Sam Toueg<EMAIL_ADDRESS>University of TorontoTorontoOntarioCanada

(2021)

###### Abstract.

We prove that in asynchronous message-passing systems where at most one
process may crash, there is no lock-free strongly linearizable implementation
of a weak object that we call Test-_or_ -Set (ToS). This object allows a
single distinguished process to apply the set operation once, and a
_different_ distinguished process to apply the test operation also once. Since
this weak object can be directly implemented by a single-writer single-reader
(SWSR) register (and other common objects such as max-register, snapshot and
counter), this result implies that there is no $1$-resilient lock-free
strongly linearizable implementation of a SWSR register (and of these other
objects) in message-passing systems.

We also prove that there is no $1$-resilient lock-free _write_ strongly-
linearizable implementation of a 2-writer 1-reader (2W1R) register in
asynchronous message-passing systems.

††journalyear: 2021††copyright: acmlicensed††conference: Proceedings of the
2021 ACM Symposium on Principles of Distributed Computing; July 26–30, 2021;
Virtual Event, Italy††booktitle: Proceedings of the 2021 ACM Symposium on
Principles of Distributed Computing (PODC ’21), July 26–30, 2021, Virtual
Event, Italy††price: 15.00††doi: 10.1145/3465084.3467938††isbn:
978-1-4503-8548-0/21/07

##  1\. Introduction

In seminal work, Golab, Higham, and Woelfel showed that linearizability has
the following limitation: a _randomized_ algorithm that works with atomic
objects against a strong adversary may lose some of its properties if we
replace the atomic objects that it uses with objects that are only
linearizable (sl11, ). To address this, they proposed a stronger version of
linearizability, called _strong linearizability_ : intuitively, while in
linearizability the order of all operations can be determined “off-line” given
the entire execution, in strong linearizability the order of all operations
has to be fixed irrevocably “on-line” without knowing the rest of the
execution. Golab _et al._ proved that strongly linearizable (implementations
of) objects are “as good” as atomic objects for randomized algorithms against
a strong adversary: they can replace atomic objects while preserving the
algorithm’s correctness properties.

There are many cases, however, where strong linearizability is impossible to
achieve. In particular, for shared-memory systems, Helmi _et al._ proved that
a large class of so-called _non-trivial_ objects including multi-writer
registers, max-registers, snapshots, and counters, do not have strongly
linearizable non-blocking implementations from single-writer multi-reader
(SWMR) registers (sl12, ),

In this paper, we consider asynchronous message-passing systems where at most
one process may crash, and show that in such systems there is no lock-free
strongly linearizable implementation of a weak object that we call _Test-or-
Set (ToS)_ :111Henceforth, we say that an object implementation is _$1$
-resilient lock-free_ if it is lock-free under the assumption that at most one
process may crash. This progress condition is defined more precisely in
Section 2.1. with ToS, one distinguished process can apply the set operation
once, and another distinguished process can apply the test operation also only
once: the test operation returns $1$ if set has previously been applied, and
it returns $0$ otherwise.

Since a single-writer single-reader (SWSR) register directly implements a ToS
object, the above result immediately implies that there is no $1$-resilient
lock-free strongly linearizable implementation of a SWSR register in message-
passing systems. This result strengthens a recent result by Attiya, Enea, and
Welch which shows that _multi_ -writer registers do not have strongly
linearizable _nonblocking_ implementations in message-passing systems (AEW21,
), 222Appendix A shows that the nonblocking progress condition defined in
(AEW21, ) implies $1$-resilient lock-freedom. and it also answers an open
question asked in that paper, namely, whether there is a (fault-tolerant)
strongly linearizable implementation of a _single_ -writer register in
message-passing systems. Attiya _et al._ also prove that max-registers,
snapshot, and counters objects do not have nonblocking strongly linearizable
implementations in message-passing systems. Since max-registers, snapshot, and
counters also directly implement a ToS object, our result implies that there
is no $1$-resilient lock-free strongly linearizable implementation of these
objects in message-passing systems.

Since there is no nonblocking strongly linearizable implementation of MWMR
registers from SWMR registers in shared-memory systems (sl12, ), Hadzilacos,
Xing, and Toueg proposed an _intermediate_ notion of linearizability, called
_write strong-linearizability_ (HHT211, ), and proved that there _is_ a wait-
free write strongly-linearizable implementation of MWMR registers from SWMR
registers. This is useful because some randomized algorithms that do _not_
terminate with linearizable MWMR registers, terminate with write strongly-
linearizable MWMR registers (HHT211, ).

The above results raise the following question: is there a _write_ strongly-
linearizable implementation of MWMR registers in message-passing systems? We
prove here that the answer is negative. More precisely, we prove that there is
no $1$-resilient lock-free write strongly-linearizable implementation of even
a 2-Writer 1-Reader (2W1R) register in message-passing systems.

##  2\. Model sketch

We consider a standard asynchronous message-passing distributed system where
processes communicate via messages and may fail by crashing. The proof of our
result is based on a bivalency argument, and we assume that the reader is
familiar with the model and terminology introduced by Fischer, Lynch, and
Paterson in (FischerEtal1985, ) to prove their famous impossibility result.
Recall that in this model, processes take _steps_ , and in each step a process
does the following: it attempts to receive a message $m$ previously sent to it
($m=\bot$ if does not receive any message), it changes state according to the
message received, and it sends a finite set of messages to other processes. A
step taken by a process $p$ in which it receives message $m$ is denoted
$e=(p,m)$. A configuration consists of the state of all the processes and of
the message buffer (which consists of all the messages sent but not yet
received). A history is a sequence of steps. A process is _correct_ if it
takes infinitely many steps, we say that it _crashes_ otherwise. We consider
systems with reliable communication links, i.e., where every message sent to a
correct process is eventually received. Henceforth we consider only such
executions.

###  2.1. Objects

We consider implementations of ToS and 2W1R objects in message-passing
systems. In an object implementation, each operation spans an interval that
starts with an _invocation_ and terminates with a _response_. For any two
operations $o$ and $o^{\prime}$, $o$ _precedes_ $o^{\prime}$ if the response
of $o$ occurs before the invocation of $o^{\prime}$, and $o$ _is concurrent
with_ $o^{\prime}$ if neither precedes the other.

Roughly speaking, an object implementation is _linearizable_ (HerlihyWing1990,
) if operations (which may be concurrent) behave as if they occur in some
sequential order (called “linearization order”) that is consistent with the
order in which operations actually occur: if an operation $o$ precedes an
operation $o^{\prime}$, then $o$ is before $o^{\prime}$ in the linearization
order.

In the message-passing model, the occurrence of an invocation or response to
an operation is encoded by a change in the state of the process that invoked
the operation (and by a corresponding change in the configuration). Let
$\mathcal{H}$ be the set of all histories of an object implementation (note
that this set is prefix-closed). A history $H\in\mathcal{H}$ is _sequential_
if no two operations are concurrent in $H$.333Strictly-speaking, what we mean
here is that “no operations are concurrent” in the configurations reached when
applying $H$ to the initial configuration of this object implementation. For
convenience, when clear, we sometimes use $H$ to denote the sequence of
configurations obtained by applying $H$ to the initial configuration of an
object. An operation $o$ is _complete_ in a history $H\in\mathcal{H}$ if $H$
contains both the invocation and response of $o$, otherwise $o$ is _pending_.
A _completion_ of a history $H$ is a history $H^{\prime}$ obtained from $H$ by
removing a subset of the pending operations and completing the remaining ones
with responses.

Let $\mathcal{H}$ be the set of all histories of an implementation of an
object of type $T$.444Intuitively, an object type is specified by how this
object behaves when it is accessed sequentially (HerlihyWing1990, ).

###### Definition 1.

A function $f$ is _a linearization function for $\mathcal{H}$_ (with respect
to type $T$) if it maps each history $H\in\mathcal{H}$ to a sequential history
$f(H)$ such that:

  1. (1)

$f(H)$ has exactly the same operations as some completion $H^{\prime}$ of $H$.

  2. (2)

If operation $o$ precedes $o^{\prime}$ in $H^{\prime}$, then $o$ occurs before
$o^{\prime}$ in $f(H)$.

  3. (3)

The sequence of operations in $f(H)$ conforms to the type $T$.

###### Definition 2.

An algorithm $I$ that implements an object of type $T$ is _linearizable_ if
there is a linearization function (with respect to type $T$) for the set of
histories $\mathcal{H}$ of $I$.

We now define a weak progress condition for object implementations in message-
passing systems. Intuitively, a $1$-resilient lock-free implementation
guarantees that if at most one process crashes, then the implementation is
lock-free: whenever a correct process has a pending operation, some operation
will complete. More precisely:

###### Definition 3 (1-resilient lock-free).

An implementation is $1$-resilient lock-free if it satisfies the following
property. Let $C$ be any reachable configuration that has a pending operation
by some process $p$. For every infinite history $H$ that is applicable to $C$
such that at most one process crashes and $p$ is correct, there is a finite
prefix $H^{\prime}$ of $H$ such that more operations have completed in
$H^{\prime}(C)$ than in $C$.

###  2.2. Test-or-Set

We define a simple object called _Test-or-Set (ToS)_ as follows. The state of
a ToS object is a single bit $b$, initially $0$. A single distinguished
process is allowed to apply a single operation test that returns the value of
$b$; it can apply this operation only once. A different distinguished process
is allowed to apply a single operation set that sets $b$ to $1$ (and returns
done); it can apply this operation only once. The sequential specification of
the ToS object is the obvious one: the test operation returns $1$ if a set
operation has previously been applied, and $0$ if not.

###  2.3. Strongly Linearizable Implementations of Test-or-Set

In this section, $\mathcal{H}$ is the set of all histories of a ToS
implementation.

###### Definition 4.

A function $f$ is _a linearization function for $\mathcal{H}$_ (with respect
to the type ToS) if it maps each history $H\in\mathcal{H}$ to a sequential
history $f(H)$ such that:

  1. (1)

$f(H)$ has exactly the same operations as some completion $H^{\prime}$ of $H$.

  2. (2)

If operation $o$ precedes $o^{\prime}$ in $H^{\prime}$, then $o$ occurs before
$o^{\prime}$ in $f(H)$.

  3. (3)

For any test operation $t$ in $f(H)$, if no set operation occurs before $t$ in
$f(H)$, then $t$ reads 0; otherwise, $t$ reads 1.

###### Definition 5.

(sl11, ) A function $f$ is _a strong linearization function for $\mathcal{H}$_
if:

(L) $f$ is a linearization function for $\mathcal{H}$, and

(P) for any histories $G,H\in\mathcal{H}$, if $G$ is a prefix of $H$, then
$f(G)$ is a prefix of $f(H)$.

###### Definition 6.

An algorithm $I$ that implements a _ToS_ object is _strongly linearizable_ if
there is a strong linearization function (with respect to the type ToS) for
the set of histories $\mathcal{H}$ of $I$.

###  2.4. Write Strongly-Linearizable Implementations of Registers

In this section, $\mathcal{H}$ is the set of all histories of a register
implementation.

###### Definition 7.

A function $f$ is _a linearization function for $\mathcal{H}$_ (with respect
to the type register) if it maps each history $H\in\mathcal{H}$ to a
sequential history $f(H)$ such that:

  1. (1)

$f(H)$ has exactly the same operations as some completion $H^{\prime}$ of $H$.

  2. (2)

If operation $o$ precedes $o^{\prime}$ in $H^{\prime}$, then $o$ occurs before
$o^{\prime}$ in $f(H)$.

  3. (3)

For any read operation $r$ in $f(H)$, if no write operation occurs before $r$
in $f(H)$, then $r$ reads the initial value of the register; otherwise, $r$
reads the value written by the last write operation that occurs before $r$ in
$f(H)$.

###### Definition 8.

(HHT211, ) A function $f$ is _a write strong-linearization function for
$\mathcal{H}$_ if:

(L) $f$ is a linearization function for $\mathcal{H}$, and

(P) for any histories $G,H\in\mathcal{H}$, if $G$ is a prefix of $H$, then the
sequence of write operations in $f(G)$ is a prefix of the sequence of write
operations in $f(H)$.

An algorithm $I$ that implements a _ToS_ object is _strongly linearizable_ if
there is a strong linearization function (with respect to the type ToS) for
the set of histories $\mathcal{H}$ of $I$.

###### Definition 9.

An algorithm $I$ that implements a _register_ is _write strongly-linearizable_
if there is a write strong-linearization function (with respect to the type
register) for the set of histories $\mathcal{H}$ of $I$.

##  3\. Impossibility Results

###  3.1. Test-or-Set

###### Theorem 1.

For all $n\geq 2$, there is no $1$-resilient lock-free strongly linearizable
implementation of the Test-or-Set object in an asynchronous message-passing
system of $n$ processes.

###### Proof.

Suppose, for contradiction, that there is a $1$-resilient lock-free strongly
linearizable implementation $I$ of the Test-or-Set object in a message-passing
system of $n$ processes. Without loss of generality, suppose that this
implementation only allows process $0$ to invoke the test operation and only
allows process $1$ to invoke the set operation. The other $n-2$ processes may
take steps to help complete operations, but do not invoke any operations
themselves.

Let $A$ be the message-passing algorithm that uses the implementation $I$ as
shown in Figure 1.

Figure 1 Algorithm $A$ that uses the implementation $I$ of a test-or-set
object

1:Code for process $0$:

2:$I.\textsc{test}$

3:

4:Code for process $1$:

5:$I.\textsc{set}$

Henceforth, we consider the set of runs (i.e., histories) of algorithm $A$ in
a message-passing system with $n\geq 2$ processes in which at most one process
crashes and every message sent to a correct process is eventually received.

Let $C_{{\textit{init}}}$ be the initial configuration of algorithm $A$. A
configuration $C$ is _reachable_ if there is a history $H$ such that
$C=H(C_{{\textit{init}}})$. For any reachable configuration $C$:

  * •

$C$ is _$v$ -valent_ for $v\in\\{0,1\\}$ if there is no finite history $H$
applicable to $C$ such that the test operation has returned $1-v$ in $H(C)$.

  * •

$C$ is _bivalent_ if it is neither $0$-valent nor $1$-valent.

  * •

$C$ is _univalent_ if it is _$v$ -valent_ for exactly one $v\in\\{0,1\\}$.

###### Observation 1.0.

If the test operation has returned some value $v\in\\{0,1\\}$ in some
reachable configuration $C$, then $C$ is $v$-valent.

###### Proof.

This holds because algorithm $A$ invokes at most one test operation. ∎

###### Observation 1.0.

A reachable configuration $C$ cannot be both $0$-valent and $1$-valent.

###### Proof.

Consider the following history: starting from $C$, every process takes steps
in a round-robin order, and in each step a process receives the earliest
pending message for it. So all processes take infinitely many steps and every
message is eventually received. Since the implementation $I$ is $1$-resilient
lock-free and no process crashes, it is clear that eventually both processes
$0$ and $1$ complete their execution of algorithm $A$; in particular, process
$0$ completes its test operation on the test-or-set object implemented by $I$.
So there exists a finite history $H$ applicable to $C$ such that the test
operation by process $0$ has completed in $H(C)$. Clearly, this test operation
returns some value $v\in\\{0,1\\}$. Thus $C$ is not $(1-v)$-valent. ∎

###### Observation 1.0.

If $C$ is a reachable bivalent configuration, then for each $v\in\\{0,1\\}$,
there exists a finite history $H_{v}$ such that $H_{v}(C)$ is $v$-valent.

###### Proof.

Let $C$ be a reachable bivalent configuration. Thus $C$ is neither $0$-valent
nor $1$-valent. Thus for each $v\in\\{0,1\\}$, there exists a finite history
$H_{v}$ applicable to $C$ such that the test operation has returned $v$ in
$H_{v}(C)$. By Section 3.1, $H_{v}(C)$ is $v$-valent. ∎

###### Claim 1.1.

The initial configuration $C_{{\textit{init}}}$ (before any operation is
invoked) is bivalent.

###### Proof.

Consider the following run of $A$: (a) process $1$ completes its set
operation; then (b) process $0$ invokes its test operation and completes it.
Clearly, the test operation returns $1$. So $C_{{\textit{init}}}$ is not
$0$-valent.

Consider the following run of $A$: (a) process $0$ completes its test
operation; then (b) process $1$ invokes its set operation, and completes it.
Clearly, the test operation returns $0$. So $C_{{\textit{init}}}$ is not
$1$-valent.

Since $C_{{\textit{init}}}$ is neither $0$-valent nor $1$-valent, it is
bivalent. ∎

###### Claim 1.2.

If $C$ is a reachable bivalent configuration, then no operation has completed
in $C$.

###### Proof.

Suppose, for contradiction, that there is a history $H$ applicable to
$C_{{\textit{init}}}$ such that $C=H(C_{{\textit{init}}})$ is bivalent, yet
some operation has completed in $H(C_{{\textit{init}}})$. Suppose the test
operation has completed in $H(C_{{\textit{init}}})$, and let $v\in\\{0,1\\}$
be the value returned. Then, by Section 3.1, $H(C_{{\textit{init}}})$ is
$v$-valent — contradicting that $H(C_{{\textit{init}}})$ is bivalent. So a set
operation has completed in $H(C_{{\textit{init}}})$.

Since $H(C_{{\textit{init}}})$ is bivalent, it is neither $0$-valent nor
$1$-valent. Thus for each $v\in\\{0,1\\}$, there exists a finite history
$H_{v}$ applicable to $H(C_{{\textit{init}}})$ such that the test operation
has returned $v$ in $HH_{v}(C_{{\textit{init}}})$. For each $v\in\\{0,1\\}$,
let $H^{\prime}_{v}=HH_{v}$.

Let $f$ be any strong-linearization function for the set of all histories of
the implementation $I$ of the test-or-set object. Then:

  * •

In $f(H^{\prime}_{0})$, the test operation occurs before the set operation
because otherwise the test operation could not return $0$.

  * •

In $f(H^{\prime}_{1})$, the test operation occurs after the set operation
because otherwise the test operation could not return $1$.

Since $H$ is a prefix of both $H^{\prime}_{0}$ and $H^{\prime}_{1}$, by
Definition 5, $f(H)$ is a prefix of both $f(H^{\prime}_{0})$ and
$f(H^{\prime}_{1})$. So $f(H)$ does not contain any operations. However, since
a set operation has completed in $H(C_{{\textit{init}}})$, by Definition 4 and
5 $f(H)$ must contain this operation — a contradiction. ∎

###### Claim 1.3.

Let $C$ be any reachable bivalent configuration, $e=(p,m)$ be any step that is
applicable to $C$, $\mathcal{C}_{-e}$ be the set of configurations reachable
from $C$ without applying $e$, and
$\mathcal{D}=e(\mathcal{C}_{-e})=\\{e(E)|E\in\mathcal{C}_{-e}\textrm{ and
}e\textrm{ is applicable to }E\\}$. Then $\mathcal{D}$ contains a bivalent
configuration.

###### Proof.

Note that since $e$ is applicable to $C$, $e$ is also applicable to every
configuration in $\mathcal{C}_{-e}$.

Suppose, for contradiction, that $\mathcal{D}$ does not contain a bivalent
configuration. Then by Section 3.1, $\mathcal{D}$ contains only univalent
configurations. Since $C$ is bivalent, by Section 3.1, for each
$v\in\\{0,1\\}$ there is a configuration $E_{v}$ reachable from $C$ such that
$E_{v}$ is $v$-valent. For each $v\in\\{0,1\\}$, if $E_{v}$ is in
$\mathcal{C}_{-e}$, then let $E^{\prime}_{v}=e(E_{v})\in\mathcal{D}$;
otherwise $e$ was applied to reach $E_{v}$, so let $E^{\prime}_{v}$ be a
configuration in $\mathcal{D}$ from which $E_{v}$ is reachable. Thus for each
$v\in\\{0,1\\}$, $E^{\prime}_{v}$ is in $\mathcal{D}$ and is $v$-valent. So
$\mathcal{D}$ contains both $0$-valent and $1$-valent configurations.

Consequently, there exists a configuration $C_{\textit{deli}}$ in
$\mathcal{C}_{-e}$ and a step $e^{\prime}\neq e$ applicable to
$C_{\textit{deli}}$ such that $e(C_{\textit{deli}})$ and
$e^{\prime}e(C_{\textit{deli}})$ are univalent configurations in $\mathcal{D}$
that have opposite valence. There are two cases: either $e$ and $e^{\prime}$
are steps of different processes, or $e$ and $e^{\prime}$ are steps of the
same process $p$.

Case 1::

$e$ and $e^{\prime}$ are steps of different processes.

Then $ee^{\prime}(C_{\textit{deli}})=e^{\prime}e(C_{\textit{deli}})$. Thus,
$e^{\prime}e(C_{\textit{deli}})$ is both $0$-valent and $1$-valent —
contradicting Section 3.1.

Case 2::

$e$ and $e^{\prime}$ are steps of the same process $p$. Consider the following
history: starting from $C_{\textit{deli}}$, every process except $p$ takes
steps in a round-robin order, and in each step a process receives the earliest
pending message for it. So all processes except $p$ take infinitely many steps
and every message is eventually received. Since the implementation $I$ is
$1$-resilient lock-free, it is clear that eventually a configuration is
reached where some operation has completed. Thus, there is a finite $p$-free
history $H_{-p}$ applicable to $C_{\textit{deli}}$ such that an operation has
completed in $H_{-p}(C_{\textit{deli}})$. Since $H_{-p}$ is $p$-free, $H_{-p}$
is applicable to both $e(C_{\textit{deli}})$ and
$e^{\prime}e(C_{\textit{deli}})$, and both $e$ and $e^{\prime}e$ are
applicable to $H_{-p}(C_{\textit{deli}})$. Furthermore, it is clear that
$eH_{-p}(C_{\textit{deli}})=H_{-p}e(C_{\textit{deli}})$ and
$e^{\prime}eH_{-p}(C_{\textit{deli}})=H_{-p}e^{\prime}e(C_{\textit{deli}})$
are univalent configurations with opposite valence. So
$H_{-p}(C_{\textit{deli}})$ is bivalent — contradicting Claim 1.2 since an
operation has completed in $H_{-p}(C_{\textit{deli}})$.

∎

We now construct an infinite history $H_{\textit{bi}}$ applicable to
$C_{{\textit{init}}}$ such that every configuration in
$H_{\textit{bi}}(C_{{\textit{init}}})$ is bivalent as follows:

  1. (1)

Let $C=C_{{\textit{init}}}$ ($C$ is bivalent by Claim 1.1) and let $S$ be an
arbitrary sequence of all $n$ processes.

  2. (2)

Let $p$ be the first process in $S$, $m$ be the earliest message in the
message buffer of $p$ in $C$ (or $\bot$ if no such message exists), and
$e=(p,m)$.

  3. (3)

By Claim 1.3, there is a bivalent configuration $C^{\prime}$ reachable from
$C$ where $e$ has been applied.

  4. (4)

Move $p$ to the end of $S$, and let $C=C^{\prime}$.

  5. (5)

Repeat from Step 2.

Note that all the configurations “traversed” by the application of
$H_{\textit{bi}}$ to $C_{{\textit{init}}}$ are bivalent. By Claim 1.2, no
operation has completed in any of them. However, in the infinite history
$H_{\textit{bi}}$, every process takes infinitely many steps and every message
is eventually received. Thus, since the implementation $I$ of the test-or-set
object (used by algorithm $A$) is $1$-resilient lock-free, at least one
operation by process $0$ or $1$ on this test-or-set object must have completed
— a contradiction. ∎

Since $ToS$ can be _directly_ implemented by a SWSR register (and also by
other objects such as max-registers, snapshot, and counters) Theorem 1
implies:

###### Corollary 2.

For all $n\geq 2$, there is no $1$-resilient lock-free strongly linearizable
implementation of SWSR registers in an asynchronous message-passing system of
$n$ processes. Moreover, there is no such an implementation of max-registers,
snapshot, and counters.

The above corollary is stronger than a result in (AEW21, ) which states that,
if three or more processes are allowed to invoke operations,555These processes
are called _clients_ in (AEW21, ). there is no strongly linearizable
nonblocking message-passing implementation of multi-writer registers, max-
registers, counters, or snapshot objects. Note that relating the two results
is not immediate, because Corollary 2 is about $1$-resilient lock-free
implementations, while the result in (AEW21, ) is about nonblocking
implementation as defined in (AEW21, ). In Appendix A, we show that
nonblocking implies $1$-resilient lock-freedom.

###  3.2. 2W1R 1-bit Registers

###### Theorem 3.

For all $n\geq 2$, there is no $1$-resilient lock-free write strongly-
linearizable implementation of a $1$-bit 2W1R register in an asynchronous
message-passing system of $n$ processes.

###### Proof.

Suppose, for contradiction, that there is a $1$-resilient lock-free write
strongly-linearizable implementation $I$ of a $1$-bit 2W1R register in a
message-passing system of $n$ processes. Without loss of generality, suppose
that this implementation has initial value $0$, and only allows process $0$ to
invoke read operations and processes $0$ and $1$ to invoke write operations.
The other $n-2$ processes may take steps to help complete operations, but do
not invoke any operations themselves.

Let $A$ be the message-passing algorithm that uses the implementation $I$ as
shown in Figure 2. Note that in algorithm $A$, process $0$ does not invoke its
read operation before process $1$ completes its write.

Figure 2 Algorithm $A$ that uses the implementation $I$ of a 2W1R register

1:Code for process $0$:

2:$I.\textsc{write}(0)$

3:repeat

4:until receive “OK” from process $1$

5:$I.\textsc{read}$

6:

7:Code for process $1$:

8:$I.\textsc{write}(1)$

9:send “OK” to process $0$

Henceforth, we consider the set of runs (i.e., histories) of algorithm $A$ in
a message-passing system with $n\geq 2$ processes in which at most one process
crashes and every message sent to a correct process is eventually received.

Let $C_{{\textit{init}}}$ be the initial configuration of algorithm $A$. A
configuration $C$ is _reachable_ if there is a history $H$ such that
$C=H(C_{{\textit{init}}})$. For any reachable configuration $C$:

  * •

$C$ is _$v$ -valent_ for $v\in\\{0,1\\}$ if there is no finite history $H$
applicable to $C$ such that the read operation has returned $1-v$ in $H(C)$.

  * •

$C$ is _bivalent_ if it is neither $0$-valent nor $1$-valent.

  * •

$C$ is _univalent_ if it is _$v$ -valent_ for exactly one $v\in\\{0,1\\}$.

###### Observation 3.0.

If the read operation has returned some value $v\in\\{0,1\\}$ in some
reachable configuration $C$, then $C$ is $v$-valent.

###### Proof.

This holds because algorithm $A$ invokes at most one read operation. ∎

###### Observation 3.0.

A reachable configuration $C$ cannot be both $0$-valent and $1$-valent.

###### Proof.

Consider the following history: starting from $C$, every process takes steps
in a round-robin order, and in each step a process receives the earliest
pending message for it. So all processes take infinitely many steps and every
message is eventually received. Since the implementation $I$ is $1$-resilient
lock-free and no process is correct, it is clear that both processes $0$ and
$1$ complete their execution of algorithm $A$; in particular, process $0$
completes its read of the register implemented by $I$. So there exists a
finite history $H$ applicable to $C$ such that the read operation by process
$0$ has completed in $H(C)$. Clearly, this read operation returns some value
$v\in\\{0,1\\}$. Thus $C$ is not $(1-v)$-valent. ∎

###### Observation 3.0.

If $C$ is a reachable bivalent configuration, then for each $v\in\\{0,1\\}$,
there exists a finite history $H_{v}$ such that $H_{v}(C)$ is $v$-valent.

###### Proof.

Let $C$ be a reachable bivalent configuration. Thus $C$ is neither $0$-valent
nor $1$-valent. Thus for each $v\in\\{0,1\\}$, there exists a finite history
$H_{v}$ applicable to $C$ such that the read operation has returned $v$ in
$H_{v}(C)$. By Section 3.2, $H_{v}(C)$ is $v$-valent. ∎

###### Claim 3.1.

The initial configuration $C_{{\textit{init}}}$ (before any operation is
invoked) is bivalent.

###### Proof.

Consider the following run of $A$: (a) process $0$ completes its
$\textsc{write}(0)$ operation; then (b) process $1$ invokes its
$\textsc{write}(1)$ operation, completes it, and sends “OK”; then (c) process
$0$ receives “OK”, and completes its read operation. Clearly, this read
returns 1. So $C_{{\textit{init}}}$ is not $0$-valent.

Consider the following run of $A$: (a) process $1$ completes its
$\textsc{write}(1)$ operation and sends “OK”; then (b) process $0$ invokes its
$\textsc{write}(0)$ operation, and completes it; then (c) process $0$ receives
“OK”, and completes its read operation. Clearly, this read returns 0. So
$C_{{\textit{init}}}$ is not $1$-valent.

Since $C_{{\textit{init}}}$ is neither $0$-valent nor $1$-valent, it is
bivalent. ∎

###### Claim 3.2.

If $C$ is a reachable bivalent configuration, then no operation has completed
in $C$.

###### Proof.

Suppose, for contradiction, that there is a history $H$ applicable to
$C_{{\textit{init}}}$ such that $H(C_{{\textit{init}}})$ is bivalent, yet some
operation has completed in $H(C_{{\textit{init}}})$. Suppose the read
operation has completed in $H(C_{{\textit{init}}})$, and let $v\in\\{0,1\\}$
be the value returned. Then, by Section 3.2, $H(C_{{\textit{init}}})$ is
$v$-valent — contradicting that $H(C_{{\textit{init}}})$ is bivalent. So a
write operation has completed in $H(C_{{\textit{init}}})$.

Since $H(C_{{\textit{init}}})$ is bivalent, it is neither $0$-valent nor
$1$-valent. Thus for each $v\in\\{0,1\\}$, there exists a finite history
$H_{v}$ applicable to $H(C_{{\textit{init}}})$ such that the read operation
has returned $v$ in $HH_{v}(C_{{\textit{init}}})$. For each $v\in\\{0,1\\}$,
let $H^{\prime}_{v}=HH_{v}$.

Let $f$ be any write strong-linearization function for the set of all
histories of the implementation $I$ of the 2W1R register.

###### Subclaim 3.2.1.

For each $v\in\\{0,1\\}$, in $f(H^{\prime}_{v})$, the $\textsc{write}(1-v)$
operation occurs before the $\textsc{write}(v)$ operation.666In an abuse of
notation, by $f(H^{\prime}_{v})$ we mean $f(H^{\prime I}_{v})$ where
$H^{\prime I}_{v}$ are the steps of the implementation $I$ in
$H^{\prime}_{v}$.

###### Proof.

Recall that in algorithm $A$, process $0$ does not invoke its read operation
before process $1$ completes its write. So, since the read operation has
completed in $H^{\prime}_{v}(C_{{\textit{init}}})$, all three operations have
completed in $H^{\prime}_{v}(C_{{\textit{init}}})$. Thus in
$f(H^{\prime}_{v})$, the read operation, which returns $v$, must occur after
the two $\textsc{write}(-)$ operations. Therefore, in $f(H^{\prime}_{v})$, the
$\textsc{write}(1-v)$ operation occurs before the $\textsc{write}(v)$
operation. ∎

Since $H$ is a prefix of both $H^{\prime}_{0}$ and $H^{\prime}_{1}$, by
Definition 5, $f(H)$ is a prefix of both $f(H^{\prime}_{0})$ and
$f(H^{\prime}_{1})$. So $f(H)$ does not contain any operations. However, since
a set operation has completed in $H(C_{{\textit{init}}})$, by Definition 4 and
5 $f(H)$ must contain this operation — a contradiction.

By Subclaim 3.2.1, in $f(H^{\prime}_{0})$, the $\textsc{write}(1)$ occurs
before the $\textsc{write}(0)$, and in $f(H^{\prime}_{1})$, the
$\textsc{write}(0)$ occurs before the $\textsc{write}(1)$. Since $H$ is a
prefix of both $H^{\prime}_{0}$ and $H^{\prime}_{1}$, by Definition 8, the
sequence of $\textsc{write}(-)$ operations in $f(H)$ is a prefix of the
sequence of the $\textsc{write}(-)$ operations in both $f(H^{\prime}_{0})$ and
$f(H^{\prime}_{1})$. So $f(H)$ does not contain any $\textsc{write}(-)$
operation. However, since a $\textsc{write}(-)$ operation has completed in
$H(C_{{\textit{init}}})$, by Definition 7 and 8 $f(H)$ must contain this
operation — a contradiction. ∎

The rest of the proof is almost the same as in the proof of Theorem 1.

###### Claim 3.3.

Let $C$ be any reachable bivalent configuration, $e=(p,m)$ be any step that is
applicable to $C$, $\mathcal{C}_{-e}$ be the set of configurations reachable
from $C$ without applying $e$, and
$\mathcal{D}=e(\mathcal{C}_{-e})=\\{e(E)|E\in\mathcal{C}_{-e}\textrm{ and
}e\textrm{ is applicable to }E\\}$. Then $\mathcal{D}$ contains a bivalent
configuration.

###### Proof.

Note that since $e$ is applicable to $C$, $e$ is also applicable to every
configuration in $\mathcal{C}_{-e}$.

Suppose, for contradiction, that $\mathcal{D}$ does not contain a bivalent
configuration. Then by Section 3.2, $\mathcal{D}$ contains only univalent
configurations. Since $C$ is bivalent, by Section 3.2, for each
$v\in\\{0,1\\}$ there is a configuration $E_{v}$ reachable from $C$ such that
$E_{v}$ is $v$-valent. For each $v\in\\{0,1\\}$, if $E_{v}$ is in
$\mathcal{C}_{-e}$, then let $E^{\prime}_{v}=e(E_{v})\in\mathcal{D}$;
otherwise $e$ was applied to reach $E_{v}$, so let $E^{\prime}_{v}$ be a
configuration in $\mathcal{D}$ from which $E_{v}$ is reachable. Thus for each
$v\in\\{0,1\\}$, $E^{\prime}_{v}$ is in $\mathcal{D}$ and is $v$-valent. So
$\mathcal{D}$ contains both $0$-valent and $1$-valent configurations.

Consequently, there exists a configuration $C_{\textit{deli}}$ in
$\mathcal{C}_{-e}$ and a step $e^{\prime}\neq e$ applicable to
$C_{\textit{deli}}$ such that $e(C_{\textit{deli}})$ and
$e^{\prime}e(C_{\textit{deli}})$ are univalent configurations in $\mathcal{D}$
that have opposite valence. There are two cases: either $e$ and $e^{\prime}$
are steps of different processes, or $e$ and $e^{\prime}$ are steps of the
same process $p$.

Case 1::

$e$ and $e^{\prime}$ are steps of different processes.

Then $ee^{\prime}(C_{\textit{deli}})=e^{\prime}e(C_{\textit{deli}})$. Thus,
$e^{\prime}e(C_{\textit{deli}})$ is both $0$-valent and $1$-valent —
contradicting Section 3.2.

Case 2::

$e$ and $e^{\prime}$ are steps of the same process $p$. Consider the following
history: starting from $C_{\textit{deli}}$, every process except $p$ takes
steps in a round-robin order, and in each step a process receives the earliest
pending message for it. So all processes except $p$ take infinitely many steps
and every message is eventually received. Since the implementation $I$ is
$1$-resilient lock-free, it is clear that eventually a configuration is
reached where some operation has completed. Thus, there is a finite $p$-free
history $H_{-p}$ applicable to $C_{\textit{deli}}$ such that an operation has
completed in $H_{-p}(C_{\textit{deli}})$. Since $H_{-p}$ is $p$-free, $H_{-p}$
is applicable to both $e(C_{\textit{deli}})$ and
$e^{\prime}e(C_{\textit{deli}})$, and both $e$ and $e^{\prime}e$ are
applicable to $H_{-p}(C_{\textit{deli}})$. Furthermore, it is clear that
$eH_{-p}(C_{\textit{deli}})=H_{-p}e(C_{\textit{deli}})$ and
$e^{\prime}eH_{-p}(C_{\textit{deli}})=H_{-p}e^{\prime}e(C_{\textit{deli}})$
are univalent configurations with opposite valence. So
$H_{-p}(C_{\textit{deli}})$ is bivalent — contradicting Claim 3.2 since an
operation has completed in $H_{-p}(C_{\textit{deli}})$.

∎

We now construct an infinite history $H_{\textit{bi}}$ applicable to
$C_{{\textit{init}}}$ such that every configuration in
$H_{\textit{bi}}(C_{{\textit{init}}})$ is bivalent as follows:

  1. (1)

Let $C=C_{{\textit{init}}}$ ($C$ is bivalent by Claim 3.1) and let $S$ be an
arbitrary sequence of all $n$ processes.

  2. (2)

Let $p$ be the first process in $S$, $m$ be the earliest message in the
message buffer of $p$ in $C$ (or $\bot$ if no such message exists), and
$e=(p,m)$.

  3. (3)

By Claim 3.3, there is a bivalent configuration $C^{\prime}$ reachable from
$C$ where $e$ has been applied.

  4. (4)

Move $p$ to the end of $S$, and let $C=C^{\prime}$.

  5. (5)

Repeat from Step 2.

Note that all the configurations “traversed” by the application of
$H_{\textit{bi}}$ to $C_{{\textit{init}}}$ are bivalent. By Claim 3.2, no
operation has completed in any of them. However, in the infinite history
$H_{\textit{bi}}$, every process takes infinitely many steps and every message
is eventually received. Thus, since the implementation $I$ of the 2W1R
register (used by algorithm $A$) is $1$-resilient lock-free, at least one
operation by process $0$ or $1$ on this register must have completed — a
contradiction. ∎

##  4\. Conclusion

We proved that there is no $1$-resilient lock-free strongly linearizable
implementation of the ToS object in asynchronous message-passing systems. This
impossibility result is strong in two dimentions: the progress condition is
weak and the ToS object itself is also weak. In particular, it implies that
there is no $1$-resilient lock-free strongly linearizable implementation of a
SWSR register in message-passing systems.

We also proved that there is no $1$-resilient lock-free _write_ strongly-
linearizable implementation of a 2W1R register in asynchronous message-passing
systems. This is in contrast to shared-memory systems, since there is a wait-
free write strongly-linearizable implementation of MWMR registers from SWMR
registers (HHT211, ).

## References

  * (1) Attiya, H., Enea, C., Welch, J.L.: Impossibility of strongly-linearizable message-passing objects via simulation by single-writer registers.  CoRR abs/2105.06614 (2021).  URL https://arxiv.org/abs/2105.06614
  * (2) Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process.  J. ACM 32(2), 374–382 (1985).  DOI 10.1145/3149.214121.  URL http://doi.acm.org/10.1145/3149.214121
  * (3) Golab, W., Higham, L., Woelfel, P.: Linearizable implementations do not suffice for randomized distributed computation.  In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, p. 373–382 (2011)
  * (4) Hadzilacos, V., Hu, X., Toueg, S.: On register linearizability and termination.  In: Proceedings of the 40th annual ACM Symposium on Principles of Distributed Computing, PODC, pp. 521–531 (2021)
  * (5) Helmi, M., Higham, L., Woelfel, P.: Strongly linearizable implementations: Possibilities and impossibilities.  In: Proceedings of the 31st annual ACM Symposium on Principles of distributed computing, PODC ’12, p. 385–394 (2012)
  * (6) Herlihy, M.P., Wing, J.M.: Linearizability: A correctness condition for concurrent objects.  ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990).  DOI 10.1145/78969.78972.  URL http://doi.acm.org/10.1145/78969.78972

##  Appendix A Appendix: Comparing two progress properties

We now compare the progress property that we considered in this paper, namely,
$1$-resilient lock-freedom, and the nonblocking property defined in (AEW21, ).
Recall that:

###### Definition 0 (1-resilient lock-free).

An implementation is 1-resilient lock-free if it satisfies the following
property. Let $C$ be any reachable configuration that has a pending operation
by some process $p$. For every infinite history $H$ that is applicable to $C$
such that at most one process crashes and $p$ is correct, there is a finite
prefix $H^{\prime}$ of $H$ such that more operations have completed in
$H^{\prime}(C)$ than in $C$.

In (AEW21, ), Attiya _et al._ consider object implementations, denoted
$I(c,s)$, for a set of $c$ _clients_ and a disjoint set of $s$ _servers_ :
intuitively, only clients are allowed to invoke object operations, while
servers can only help clients perform their operations. They define the
following progress guarantee for such implementations ($g_{i}$ denotes a
configuration):

###### Definition 1 (nonblocking).

(AEW21, ) An implementation $I(c,s)$ is nonblocking iff for every infinite
execution $e=g_{0}\rightarrow...\rightarrow g_{k}\rightarrow...$ and $k>0$, if
at least one client and $s-(c-1)$ servers execute a step infinitely often in
$e$, then some invocation completes after $g_{k}$ (i.e., the sequence of
transitions in $e$ after $g_{k}$ includes a return transition).

We first note that nonblocking implementations are 1-resilient lock-free. More
precisely:

###### Observation .

For all $c\geq 2$, every nonblocking implementation $I(c,s)$ of an object $O$
is 1-resilient lock-free.

###### Proof.

Let $I(c,s)$ be a nonblocking implementation of an object $O$ for some $c\geq
2$. We claim that it is $1$-resilient lock-free. Let $C$ be any reachable
configuration that has a pending operation by some process $p$ (note that $p$
is a client). So $C=H_{0}(C_{{\textit{init}}})$ for some non-empty finite
history $H_{0}$. Consider any infinite history $H$ that is applicable to $C$
such that at most one process crashes and $p$ is correct. Let $e$ be the
infinite execution that corresponds to the history $H_{0}H$ (applied to
$C_{{\textit{init}}}$). Thus, $e=g_{0}\rightarrow...\rightarrow
g_{k}\rightarrow...$, where $g_{0}=C_{{\textit{init}}}$ and $g_{k}=C$ for some
$k>0$. Since (1) $I(c,s)$ is nonblocking, (2) a client (namely, $p$) is
correct, and (3) $s-1\geq s-(c-1)$ servers are also correct, some invocation
completes after $g_{k}$. Thus, there is a finite prefix $H^{\prime}$ of $H$
such that more operations have completed in $H^{\prime}(C)$ than in $C$. ∎

In contrast to the above, 1-resilient lock-free implementations are not
necessarily nonblocking. To see this, consider a system with $c\geq 2$ clients
and $s\geq c$ servers: in executions where exactly one client and one server
crashes (i.e., there are _two_ crashes), nonblocking still guarantees some
progress, while $1$-resilient lock-freedom does not make any progress
guarantees. In fact:

###### Observation .

There is a $1$-resilient lock-free implementation $I$ of an object $O$ for a
system with $n$ processes (consisting of $c=2$ clients and $s\geq c$ servers)
such that $I$ is _not_ nonblocking.

###### Proof.

Let $O$ be the trivial object that returns $0$ to all operations. Let $I$ be
the following implementation of $O$ in a system with $n$ processes ($c=2$
clients and $s\geq c$ servers). To invoke an operation on $O$, a client
process $p$ sends a message to the other $n-1$ processes. When a process
receives this message, it sends an acknowledgement back to $p$. Process $p$
waits until it receives $n-2$ acknowledgements and then it returns $0$. Note
that:

  * •

$I$ is $1$-resilient lock-free because if at most $1$ process crashes, every
operation invoked by a correct process eventually completes.

  * •

$I$ is _not_ nonblocking. To see this, consider an execution $e$ in which one
of the two clients and one server crash and take no steps (every other process
is correct). In $e$ at least one client and $s-1=s-(c-1)$ servers take
infinitely many steps. By Definition 1, nonblocking requires that at least one
invocation must complete in execution $e$. But implementation $I$ does not
satisfy this: since two processes are crashed from the start in $e$, the
correct client cannot complete any operation (it will never receive $n-2$
acknowledgements) so no invocation ever completes in $e$.

∎

Observations A and A imply that the nonblocking progress property (Definition
1) is strictly stronger than the $1$-resilient lock-free progress property
defined here (Definition 3).