# On singularly perturbed systems that are monotone with respect to a matrix
cone of rank $k$††thanks: This work was partially supported by a research
grant from the ISF.

Ron Ofir, Pietro Lorenzetti, and Michael Margaliot RO and PL contributed
equally to this work. PL and MM are with the School of Electrical Engineering,
Tel Aviv University, Ramat Aviv, Israel 69978. RO is with the Andrew and Erna
Viterbi Faculty of Electrical and Computer Engineering, Technion–Israel
Institute of Technology, Haifa 3200003, Israel. Correspondence
<EMAIL_ADDRESS>
###### Abstract

We derive a sufficient condition guaranteeing that a singularly perturbed
linear time-varying system is strongly monotone with respect to a matrix cone
$C$ of rank $k$. This implies that the singularly perturbed system inherits
the asymptotic properties of systems that are strongly monotone with respect
to $C$, which include convergence to the set of equilibria when $k=1$, and a
Poincaré-Bendixson property when $k=2$. We extend this result to singularly
perturbed nonlinear systems with a compact and convex state-space. We
demonstrate our theoretical results using a simple numerical example.

##  I Introduction

Dynamical systems whose flow preserves the ordering induced by a proper111A
cone is called proper if it is closed, convex, and pointed. cone $K$ are
called monotone systems. Such systems play an important role in systems and
control theory. We begin by reviewing the classic example that is based on the
proper cone $K={\mathbb{R}}^{n}_{+}:=\\{x\in{\mathbb{R}}^{n}:x_{i}\geq
0,\;i=1,\dots,n\\}$, that is, the non-negative orthant in ${\mathbb{R}}^{n}$.
This cone induces a (partial) ordering $\leq$ between vectors
$a,b\in{\mathbb{R}}^{n}$ defined by

$a\leq b\iff b-a\in K\iff a_{i}\leq b_{i},\;i=1,\dots,n.$

Systems whose flow preserves this ordering are called positive systems [1] or
cooperative systems [2] and have a rich theory. In particular, the seminal
work of Hirsch [3, 4, 5, 6] (see also the work of Matano in [7, 8]) has led to
what is now known as Hirsch’s generic convergence theorem, asserting that the
generic precompact orbit of a strongly monotone system approaches the set of
equilibria (see Poláčik [9, 10] and Smith-Thieme [11] for an improved version
of this result). Angeli and Sontag [12] have extended the notion of a monotone
system to a system with inputs and outputs, and showed how monotonicity can be
applied to analyze the feedback connection of such systems.

A generalization of monotone systems are systems whose flow preserves the
ordering induced by a cone of rank $k$ (abbreviated $k$-cone). A set
$C\subset\mathbb{R}^{n}$ is called a $k$-cone if:

  1. 1.

$C$ is closed,

  2. 2.

$x\in C\implies\alpha x\in C$ for all $\alpha\in{\mathbb{R}}$,

  3. 3.

$C$ contains a linear $k$-dimensional subspace, and no linear subspace of a
higher dimension.

The notion of a $k$-cone was introduced by Fusco and Oliva [13, 14] in the
finite-dimensional case, and by Krasnoselśkii et al. [15] in Banach spaces. To
avoid degenerate cases, we will assume also that $C$ has a non-empty interior.

For example, if $P\in{\mathbb{R}}^{n\times n}$ is symmetric with $k$ negative
eigenvalues and $n-k$ positive eigenvalues then the set

$C_{P}^{-}:=\\{x\in{\mathbb{R}}^{n}:x^{\mathsf{T}}Px\leq 0\\}$ (1)

is a $k$-cone. Since $C_{P}^{-}$ is defined by the matrix $P$, we refer to it
as a _matrix $k$-cone_. Similarly,

$C_{P}^{+}:=\\{x\in{\mathbb{R}}^{n}:x^{\mathsf{T}}Px\geq 0\\}$

is a matrix $(n-k)$-cone.

In general, a $k$-cone is quite different from a proper cone, as it includes a
linear subspace and it is typically not convex. Given a $k$-cone $C$, it is
possible to define the relations:

$a\leq^{\scriptstyle C}b\iff b-a\in C,$

and

$a\ll^{\scriptstyle C}b\iff b-a\in\operatorname{{\mathrm{i}nt}}(C),$

but these are not (partial) orderings. In fact, they are neither antisymmetric
nor transitive. A dynamical system is called monotone with respect to (w.r.t.)
$C$ if its flow $\Phi$ satisfies

$a\leq^{\scriptstyle C}b\implies\Phi_{t}(a)\leq^{\scriptstyle
C}\Phi_{t}(b)\text{ for all }t\geq 0,$

and strongly monotone w.r.t. $C$ if, in addition,

$a\leq^{\scriptstyle C}b,\;a\not=b\implies\Phi_{t}(a)\ll^{\scriptstyle
C}\Phi_{t}(b)\text{ for all }t>0.$

For example, consider the LTI system $\dot{x}=Ax$, with
$A\in{\mathbb{R}}^{n\times n}$, and the matrix $k$-cone in (1). Fix
$a,b\in{\mathbb{R}}^{n}$ such that $a\leq^{\scriptstyle C_{P}^{-}}b$, that is,
$(b-a)^{\mathsf{T}}P(b-a)\leq 0$. Then

$\displaystyle(\Phi_{t}(b)-\Phi_{t}(a))^{\mathsf{T}}P(\Phi_{t}(b)-\Phi_{t}(a))$
$\displaystyle=(\exp(At)(b-a))^{\mathsf{T}}P(\exp(At)(b-a))$
$\displaystyle=(b-a)^{\mathsf{T}}\left(P+(PA+A^{\mathsf{T}}P)t+o(t)\right)(b-a),$

implying that a sufficient condition for the flow to be strongly monotone
w.r.t. $C_{P}^{-}$ is that

$PA+A^{\mathsf{T}}P\preceq-2sP-\sigma I_{n},\text{ for some }s\geq
0,\sigma>0.$ (2)

This linear matrix inequality (LMI) resembles the Lyapunov equation, but here
$P$ is not necessarily positive-definite.

Moreover, Eq. (2) implies that the function
$V:{\mathbb{R}}^{n}\to{\mathbb{R}}$ defined by $V(z):=z^{\mathsf{T}}Pz$
satisfies

$\dot{V}(x(t))\leq-2sV(x(t))-\sigma x^{\mathsf{T}}(t)x(t)$

along a solution of $\dot{x}=Ax$.

An important observation is that if $K$ is a proper cone then $C:=K\cup(-K)$
is a $1$-cone [14]. Since cooperative systems admit
${\mathbb{R}}^{n}_{+}\cup(-{\mathbb{R}}^{n}_{+})$ as an invariant set, the
class of systems that are monotone w.r.t. a $k$-cone naturally includes the
classical cooperative (and, more generally, monotone) dynamical systems.
However, as noted above there is an essential difference between a $k$-cone,
with $k\geq 2$, and a proper cone, and this requires substantially new ideas
for exploring the implications of monotonicity w.r.t. a $k$-cone.

As noted by Sanchez [16], there are many important examples of flows that are
monotone with respect to a $k$-cone, with $k\geq 2$, including: high-
dimensional competitive systems (see, e.g., [17, 18, 19, 20, 21, 22, 23, 24,
25]); systems with quadratic cones like in (1) and associated Lyapunov-like
functions (see, for example, [26, 27, 28, 29]); and monotone cyclic feedback
systems with negative feedback [30, 31, 32, 33], arising from a wide range of
neural and physiological control systems. A recent example of an important
system that is monotone with respect to a 2-cone is the antithetic integral
feedback system [34].

To the best of our knowledge, condition (2) appeared for the first time in the
work of R. A. Smith [35, 36]. He showed that strong monotonicity w.r.t. to a
matrix 2-cone implies a Poincaré-Bendixson property: the $\omega$-limit set of
a bounded orbit containing no equilibria is a closed orbit. Such a result can
be useful in establishing that a dynamical system admits a closed orbit, which
is in general not trivial.

Consider a system that is strongly monotone with respect to a (not necessarily
matrix) $k$-cone $C$, with $k\geq 2$. A nontrivial orbit
$O(a):=\\{\Phi_{t}(a):t\geq 0\\}$ is called _pseudo-ordered_ if there exist
times $\tau_{1}\not=\tau_{2}$ such that $\Phi_{\tau_{1}}(a)\leq^{\scriptstyle
C}\Phi_{\tau_{2}}(a)$. Otherwise, it is called _unordered_. The structure of
an $\omega$-limit set of a pseudo-ordered orbit is much more complicated than
in the case of a system that is monotone w.r.t. a proper cone, due to the lack
of convexity of $C$. Sanchez [16, 37] showed that the closure of any orbit in
the $\omega$-limit set of a pseudo-ordered orbit is ordered with respect to
$C$, and proved a Poincaré-Bendixson property for pseudo-ordered orbits when
$k=2$. Sanchez considered smooth finite dimensional flows, and used the
$C^{1}$-Closing Lemma to prove his results. Feng, Wang and Wu [38] considered
the more general case of a semiflow on a Banach space, without the smoothness
requirement, and proved that the $\omega$-limit set $\omega(x)$ of a pseudo-
ordered semiorbit admits a trichotomy: $\omega(x)$ is either ordered; or
$\omega(x)$ is contained in the set of equilibria; or $\omega(x)$ possesses a
certain ordered homoclinic property.

Recently, Feng, Wang, and Wu [39] proved that a system that is strongly
monotone w.r.t. a $k$-cone admits an open and dense subset $D$ of the phase
space such that orbits with initial point in $D$ are either pseudo-ordered or
convergent to equilibria. This covers the celebrated Hirsch’s Generic
Convergence Theorem for $k=1$, and yields a generic Poincaré-Bendixson
property for $k=2$. Their approach uses ergodic arguments based on
$k$-exponential separation.

Wang, Yao and Zhang [40] also analyzed systems that are strongly monotone
w.r.t. a $k$-cone from a measure-theoretic perspective. They showed that
prevalent (or, equivalently, almost all) orbits will be pseudo-ordered or
convergent to equilibria. This reduces to Hirsch’s prevalent convergence
Theorem for $k=1$; and implies an almost-sure Poincaré–Bendixson Theorem in
the case $k=2$.

Weiss and Margaliot [41] introduced $k$-cooperative systems, i.e., ODE systems
that are strongly monotone with respect to the $k$-cone of vectors in
${\mathbb{R}}^{n}$ with up to $k-1$ sign variations. They showed that
$1$-cooperative systems are just cooperative systems, cyclic feedback systems
with negative feedback are $2$-cooperative systems, and competitive systems
are (up to a coordinate transformation) $(n-1)$-cooperative systems. They also
established a strong Poincaré-Bendixson property for strongly $2$-cooperative
nonlinear systems, namely, if the ${\omega}$-limit set of a precompact
solution does not include an equilibrium point then it is a closed orbit. As
noted above, Sanchez [16] proved a Poincaré-Bendixson property for _certain_
trajectories of a system that is strongly monotone with respect to a $2$-cone.
The results for 2-cooperative systems are stronger: they apply to every
precompact trajectory. See [34] for an application of these results to a
closed-loop model from systems biology.

Forni, Sepulchre and their colleagues [42, 43] considered monotone systems
w.r.t. a matrix $k$-cone (see (1)) in a systems and control perspective,
calling them $k$-dominant systems, and used (2) as the definition of
$k$-dominance with rate $s$. Importantly, using the fact that (2) is an LMI,
they extended the notion of a system that is monotone w.r.t. a matrix $k$-cone
to systems with inputs and outputs, and studied the interconnections of such
systems.

Singularly perturbed systems [44], [45, Ch. 11] appear naturally in many
control applications. For instance, see [46, 47] for an application to low-
gain integral control, and [48] for an application to power systems stability.

Wang and Sontag [49] showed that a singularly perturbed strongly monotone
system inherits the generic convergence properties of strongly monotone
systems, and demonstrated an application in systems biology. Niu and Xie [50]
showed that singularly perturbed systems that are strongly monotone w.r.t. a
2-cone inherit the generic Poincaré-Bendixon property. The results in [49, 50]
are based on geometric singular perturbations theory [51, 52].

Here, we consider $k$-dominance for singularly perturbed systems. We derive a
new sufficient condition for a singularly perturbed system to be $k$-dominant.
Our proof uses standard tools from linear algebra and dynamical systems
theory, and does not require the heavy machinery of geometric singular
perturbations theory. Another advantage of our approach is that it provides an
_explicit_ matrix cone $C_{\mathcal{P}}^{-}$ such that the perturbed system is
strongly monotone w.r.t. this cone for all ${\varepsilon}>0$ sufficiently
small.

The paper is organized as follows. Section II describes some preliminary
results that are used later on. Section III describes our main results, and
the final section concludes.

We use standard notation. Vectors [Matrices] are denoted by small [capital]
letters. Denote ${\mathbb{R}}_{+}:=\\{x\in{\mathbb{R}}\ |\ x\geq 0\\}$. A
matrix $A\in{\mathbb{R}}^{n\times n}$ is called positive-definite (denoted
$A\succ 0)$ if $A$ is symmetric and $x^{\mathsf{T}}Ax>0$ for all
$x\in{\mathbb{R}}^{n}\setminus\\{0\\}$. The inertia of a symmetric matrix
$A\in{\mathbb{R}}^{n\times n}$ is the triple

$\operatorname{{\mathrm{I}n}}(A):=(\nu(A),\zeta(A),\pi(A)),$

in which $\nu(A)$, $\zeta(A)$ and $\pi(A)$ stand for the number of negative,
zero, and positive eigenvalues of $A$, respectively. For example,
$\operatorname{{\mathrm{I}n}}(A)=(0,0,n)$
[$\operatorname{{\mathrm{I}n}}(A)=(n,0,0)$] iff $A$ is positive-definite
[negative-definite].

##  II Preliminaries

For the reader’s convenience, we recall some background on singular
perturbation theory from [44, Chap. 5].

###  II-A Singular Perturbation Theory for LTV Systems

Consider the LTV singularly perturbed system

$\displaystyle\dot{x}(t)$ $\displaystyle=A(t)x(t)+B(t)z(t),$
$\displaystyle{\varepsilon}\dot{z}(t)$ $\displaystyle=C(t)x(t)+D(t)z(t),$ (3)

where
$x:{\mathbb{R}}_{+}\to{\mathbb{R}}^{n_{r}},z:{\mathbb{R}}_{+}\to{\mathbb{R}}^{n_{f}}$,
and ${\varepsilon}>0$ small.

######  Assumption 1.

There exists $c_{1}>0$ such that

$\mathrm{Re}(\lambda(D(t)))\leq-c_{1}<0\text{ for all }t\geq 0.$

######  Assumption 2.

The matrices $A(t),B(t),C(t),D(t)$ are continuously differentiable, bounded,
and with bounded derivatives for all $t\geq 0$.

######  Theorem 3.

[44, Theorem 3.1 (Ch. 5)] Assume that the matrices $A,B,C,D$ satisfy
Assumptions 1 and 2. Then, there exists an ${\varepsilon}^{*}>0$ such that for
all ${\varepsilon}\in(0,{\varepsilon}^{*})$ there exist continuously
differentiable matrices $L_{\varepsilon}(t)$ and $H_{\varepsilon}(t)$, bounded
for all $t\geq 0$, satisfying

$\displaystyle{\varepsilon}\dot{L}_{\varepsilon}$
$\displaystyle=DL_{\varepsilon}-C-{\varepsilon}L_{\varepsilon}(A-BL_{\varepsilon}),$
(4) $\displaystyle-{\varepsilon}\dot{H}_{\varepsilon}$
$\displaystyle=H_{\varepsilon}D-B+{\varepsilon}H_{\varepsilon}L_{\varepsilon}B-{\varepsilon}(A-BL_{\varepsilon})H_{\varepsilon}.$
(5)

Moreover,

$\displaystyle L_{\varepsilon}=L_{0}+O({\varepsilon}),\quad
H_{\varepsilon}=H_{0}+O({\varepsilon}),$ (6)

with $L_{0}:=D^{-1}C$, $H_{0}:=BD^{-1}$.

Under the assumptions of Theorem 3, the matrix

$T_{\varepsilon}(t):=\left[\begin{matrix}I_{n_{r}}&{\varepsilon}H_{\varepsilon}(t)\\\
-L_{\varepsilon}(t)&I_{n_{f}}-{\varepsilon}L_{\varepsilon}(t)H_{\varepsilon}(t)\end{matrix}\right],$
(7)

is well-defined and non-singular for all $t\geq 0$. Introducing the state-
variables $\left[\begin{smallmatrix}\xi\\\
\eta\end{smallmatrix}\right]:=(T_{\varepsilon})^{-1}\left[\begin{smallmatrix}x\\\
z\end{smallmatrix}\right]$ transforms the singularly perturbed LTV system
(II-A) to the decoupled system:

$\displaystyle\begin{bmatrix}\dot{\xi}\\\
\dot{\eta}\end{bmatrix}=\mathcal{A}_{\varepsilon}(t)\begin{bmatrix}\xi\\\
\eta\end{bmatrix},$ (8)

with

$\mathcal{A}_{\varepsilon}(t):=\left[\begin{matrix}A(t)-B(t)L_{\varepsilon}(t)&0\\\
0&{\varepsilon}^{-1}D(t)+L_{\varepsilon}(t)B(t)\end{matrix}\right].$ (9)

######  Remark 4.

It can be verified that $\det(T^{-1}_{\varepsilon}(t))=1$ for all $t\geq 0$
and all ${\varepsilon}>0$. Moreover, $T_{\varepsilon}$ is a Lyapunov
transformation, namely, it is stability-preserving (see [44, Ch. 5] for more
details).

######  Remark 5.

Theorem 3 guarantees that the matrices $L_{\varepsilon}(t)$
[$H_{\varepsilon}(t)$] converge when ${\varepsilon}\to 0$ to $L_{0}$ [$H_{0}$]
(uniformly in $t\geq 0$), i.e., to the solutions of (4) obtained by setting
${\varepsilon}=0$.

The reduced (slow) model associated to (II-A) is

$\dot{x}_{s}(t)=A_{0}(t)x_{s}(t),\text{ with }A_{0}(t):=A(t)-B(t)L_{0}(t),$
(10)

while the boundary-layer (fast) systems is given by

${\varepsilon}\dot{z}_{f}(t)=D(t)z_{f}(t),$ (11)

where here $t\geq 0$ is treated as a fixed parameter.

Singular perturbation theory allows to deduce the stability of (II-A) based on
properties of the slow and fast systems. The next result demonstrates this.

######  Theorem 6.

[44, Theorem 4.1 (Ch. 5)] Assume that the matrices $A,B,C,D$ in (II-A) satisfy
Assumptions 1 and 2. Further, assume that the slow system (10) is uniformly
asymptotically stable. Then, there exists an ${\varepsilon}^{*}>0$ such that
for any ${\varepsilon}\in(0,{\varepsilon}^{*})$ the singularly perturbed
system (II-A) is uniformly asymptotically stable. In particular, the state
transition matrix $\phi_{{\varepsilon}}$ of (II-A) satisfies

$\|\phi_{{\varepsilon}}(t,s)\|\leq me^{-\alpha(t-s)}\text{ for all }t\geq
s\geq 0,$

for some $m,\alpha>0$ that are independent of ${\varepsilon}$.

The proof of this theorem is based on using $T_{\varepsilon}$ in (7) to
transform (II-A) into (8), and observing that $\xi$ is a regular perturbation
of the uniformly asymptotically stable (slow) system (10) (see Theorem 3).
Similarly, the stability of $\eta$ is linked to that of the fast variable
$z_{f}$ in (11). For a detailed proof, we refer the reader to [44, Sec. 5.2].

##  III Main results

This section includes our main results.

###  III-A $p$-Dominance of a Singularly Perturbed LTV System

Our first result provides a sufficient condition for $p$-dominance of (II-A).

######  Theorem 7.

Consider the singularly perturbed LTV system (II-A), with $A,B,C,D$ satisfying
Assumption 2. Suppose that there exist symmetric matrices
$P_{r}\in{\mathbb{R}}^{n_{r}\times n_{r}}$ with
$\operatorname{{\mathrm{I}n}}(P_{r})=(p,0,n_{r}-p)$, and
$P_{f}\in{\mathbb{R}}^{n_{f}\times n_{f}}$ with
$\operatorname{{\mathrm{I}n}}(P_{f})=(0,0,n_{f})$, rates
$\lambda_{r},\lambda_{f}\geq 0$ and $\sigma_{r},\sigma_{f}>0$ such that

$P_{r}A_{0}(t)+A_{0}^{\mathsf{T}}(t)P_{r}\preceq-2\lambda_{r}P_{r}-\sigma_{r}I_{n_{r}},$
(12a)
$P_{f}D(t)+D^{\mathsf{T}}(t)P_{f}\preceq-2\lambda_{f}P_{f}-\sigma_{f}I_{n_{f}},$
(12b)

for all $t\geq 0$. Let $\mathcal{P}:=\begin{bmatrix}P_{r}&0\\\
0&P_{f}\end{bmatrix}$. Then there exists ${\varepsilon}^{*}>0$ such that for
any ${\varepsilon}\in(0,{\varepsilon}^{*})$, system (II-A) is $p$-dominant
w.r.t. $\mathcal{P}$ with rate $\lambda_{r}$.

Note that (12a) is a $p$-dominance condition for the reduced model (10). Since
$P_{f}$ is positive-definite, (12b) is a contraction condition on the fast
system (11) w.r.t. to a scaled $L_{2}$ norm (see, e.g., [53, 54]). This latter
condition is a “strong version” of Assumption 1.

###### Proof.

Eq. (12b) implies that Assumption 1 holds, so by Theorem 3 it is enough to
analyze (8). Let $\sigma:=(1/2)\min\\{\sigma_{r},\sigma_{f}\\}>0$. We claim
that there exists ${\varepsilon}^{*}>0$ such that for any
${\varepsilon}\in(0,{\varepsilon}^{*})$, we have

$\displaystyle\mathcal{P}\mathcal{A}_{\varepsilon}(t)+\mathcal{A}^{\mathsf{T}}_{\varepsilon}(t)\mathcal{P}\preceq-2\lambda_{m}\mathcal{P}-\sigma
I_{n_{r}+n_{f}},$

for all $t\geq 0$. To simplify the notation, we omit the dependence on $t$
from now on. By the block-diagonal form of $\mathcal{A}_{\varepsilon}$, it is
enough to show that for any $t\geq 0$, we have

$\displaystyle
P_{r}(A-BL_{{\varepsilon}})+(A-BL_{{\varepsilon}})^{\mathsf{T}}P_{r}\preceq-2\lambda_{r}P_{r}-\sigma
I_{n_{f}},$ (13)

and

$P_{f}({\varepsilon}^{-1}D+L_{{\varepsilon}}B)+({\varepsilon}^{-1}D+L_{{\varepsilon}}B)^{\mathsf{T}}P_{f}\\\
\preceq-2\lambda_{r}P_{f}-\sigma I_{n_{f}},$ (14)

Combining (12a), Assumption 2 and (6) implies that (13) holds. Furthermore,
since $L_{\varepsilon}$ and $B$ are bounded, it follows from (12b) that the
left hand side of (14) can be made arbitrarily negative-definite by taking
${\varepsilon}>0$ small enough, and in particular such that (14) holds, and
this completes the proof. ∎

Specializing Theorem 7 to the case of LTI systems yields the following result.

######  Corollary 8.

Consider the LTI singularly perturbed system:

$\displaystyle\dot{x}(t)$ $\displaystyle=Ax(t)+Bz(t),$
$\displaystyle{\varepsilon}\dot{z}(t)$ $\displaystyle=Cx(t)+Dz(t),$ (15)

with $D$ invertible, and let $A_{0}:=A-BD^{-1}C$. Suppose that there exist
symmetric matrices $P_{r},P_{f}\in{\mathbb{R}}^{n\times n}$ with
$\operatorname{{\mathrm{I}n}}(P_{r})=(p,0,n_{r}-p)$,
$\operatorname{{\mathrm{I}n}}(P_{f})=(0,0,n_{f})$, rates
$\lambda_{r},\lambda_{f}\geq 0$, and $\sigma_{r},\sigma_{f}>0$ such that

$P_{r}A_{0}+A_{0}^{\mathsf{T}}P_{r}\preceq-2\lambda_{r}P_{r}-\sigma_{r}I_{n_{r}},$
(16a)
$P_{f}D+D^{\mathsf{T}}P_{f}\preceq-2\lambda_{f}P_{f}-\sigma_{f}I_{n_{f}}.$
(16b)

Then there exists ${\varepsilon}^{*}>0$ such that for any
${\varepsilon}\in(0,{\varepsilon}^{*})$, system (8) is $p$-dominant with
respect to $\mathcal{P}$ with rate $\lambda_{r}$.

In the particular case $p=0$ (so $P_{r}\succ 0$), this implies that for any
${\varepsilon}>0$ sufficiently small the perturbed system is $0$-dominant
w.r.t. to the positive-definite matrix $\mathcal{P}$, and thus it is
asymptotically stable. This recovers Theorem 6.

###  III-B $p$-Dominance in a Singularly Perturbed Nonlinear System

We now extend the analysis to time-invariant nonlinear systems. The basic idea
is to consider the variational equation associated with the singularly
perturbed nonlinear system (this is sometimes referred to as _differential
analysis_ or _incremental analysis_ [42, 54, 55]). In our case, the
variational system is a singularly perturbed LTV system.

Consider the singularly perturbed nonlinear system

$\displaystyle\dot{x}$ $\displaystyle=f(x,z),$
$\displaystyle{\varepsilon}\dot{z}$ $\displaystyle=g(x,z),$ (17)

where ${\varepsilon}>0$, $f\in
C^{2}(\mathbb{R}^{n_{r}}\times\mathbb{R}^{n_{f}};\mathbb{R}^{n_{r}})$, $g\in
C^{2}(\mathbb{R}^{n_{r}}\times\mathbb{R}^{n_{f}};\mathbb{R}^{n_{f}})$, and
$f(0,0)=0$, $g(0,0)=0$.

We assume that (III-B) admits a compact and convex state-space
$\Omega_{x}\times\Omega_{z}\subset{\mathbb{R}}^{n_{r}}\times{\mathbb{R}}^{n_{f}}$
for any ${\varepsilon}>0$. Given an initial condition $\begin{bmatrix}x_{0}\\\
z_{0}\end{bmatrix}\in\Omega_{x}\times\Omega_{z}$, the variational system of
(III-B) is

$\begin{gathered}\dot{x}_{\delta}=\frac{\partial f}{\partial
x}(x,z)x_{\delta}+\frac{\partial f}{\partial z}(x,z)z_{\delta},\\\
{\varepsilon}\dot{z}_{\delta}=\frac{\partial g}{\partial
x}(x,z)x_{\delta}+\frac{\partial g}{\partial z}(x,z)z_{\delta},\end{gathered}$
(18)

where the Jacobians are evaluated along the trajectory
$\left[\begin{smallmatrix}x(t)\\\
z(t)\end{smallmatrix}\right]\in\Omega_{x}\times\Omega_{z}$ of (III-B). Note
that (18) is a singularly perturbed LTV system.

We assume that there exists $h\in
C^{2}(\mathbb{R}^{n_{r}};\mathbb{R}^{n_{f}})$ such that $g(x,h(x))=0$ for all
$x\in\mathbb{R}^{n_{r}}$. Then, the reduced model associated with (18) is

$\dot{x}_{s}=\left[\frac{\partial f}{\partial x}(x,z)+\frac{\partial
f}{\partial z}(x,z)\frac{\partial h}{\partial x}(x)\right]x_{s},$ (19)

where

$\frac{\partial h}{\partial x}(x)=-\left[\frac{\partial g}{\partial
z}(x,h(x))\right]^{-1}\frac{\partial g}{\partial x}(x,h(x)).$ (20)

The boundary-layer associated to (18) is

${\varepsilon}\dot{z}_{f}=\frac{\partial g}{\partial z}(x,z_{f}+h(x))z_{f},$
(21)

where here $x\in\mathbb{R}^{n_{r}}$ is treated as a fixed parameter. Let

$\begin{gathered}A:=\frac{\partial f}{\partial x}(x,z),\quad B:=\frac{\partial
f}{\partial z}(x,z),\\\ C:=\frac{\partial g}{\partial x}(x,z),\quad
D:=\frac{\partial g}{\partial z}(x,z),\end{gathered}$ (22)

where for simplicity we omit the dependence of $A,B,C,D$ on $(x(t),z(t))$. Let

$\begin{gathered}L_{0}:=D^{-1}C\quad\text{and}\quad
A_{0}:=A-BL_{0}.\end{gathered}$ (23)

######  Assumption 9.

The matrices $A,B,C,D$ are continuously differentiable, bounded, and with
bounded derivatives for any initial condition
$(x_{0},z_{0})\in\Omega_{x}\times\Omega_{z}$ of (III-B).

We can now state our second main result.

######  Theorem 10.

Consider the singularly perturbed nonlinear system (III-B), and assume that
Assumption 9 holds. Suppose that there exist symmetric matrices
$P_{r}\in{\mathbb{R}}^{n_{r}\times n_{r}}$ with
$\operatorname{{\mathrm{I}n}}(P_{r})=(p,0,n_{r}-p)$, and
$P_{f}\in{\mathbb{R}}^{n_{f}\times n_{f}}$ with
$\operatorname{{\mathrm{I}n}}(P_{f})=(0,0,n_{f})$, rates
$\lambda_{r},\lambda_{f}\geq 0$ and $\sigma_{r},\sigma_{f}>0$ such that

$P_{r}A_{0}+(A_{0})^{\mathsf{T}}P_{r}\preceq-2\lambda_{r}P_{r}-\sigma_{r}I_{n_{r}},$
(24a)
$P_{f}D+D^{\mathsf{T}}P_{f}\preceq-2\lambda_{f}P_{f}-\sigma_{f}I_{n_{f}},$
(24b)

for all $(x,z)$ emanating from initial conditions
$(x_{0},z_{0})\in\Omega_{x}\times\Omega_{z}$ of (III-B). Let

$\mathcal{P}:=\begin{bmatrix}P_{r}&0\\\ 0&P_{f}\end{bmatrix}.$

Then there exists ${\varepsilon}^{*}>0$ such that for any
${\varepsilon}\in(0,{\varepsilon}^{*})$, the system (III-B) is $p$-dominant
w.r.t. $\mathcal{P}$ with rate $\lambda_{r}$.

###### Proof.

Fix
$(x_{0},z_{0}),(\tilde{x}_{0},\tilde{z}_{0})\in\Omega_{x}\times\Omega_{z}$,
and let $(x(t),z(t)),(\tilde{x}(t),\tilde{z}(t))$ denote the corresponding
solutions of (III-B). Let $v(t):=x(t)-\tilde{x}(t)$,
$w(t):=z(t)-\tilde{z}(t)$, $\bar{x}(t,r):=rx(t)+(1-r)\tilde{x}(t)$, and
$\bar{z}(t,r):=rz(t)+(1-r)\tilde{z}(t)$, with $r\in[0,1]$. Then

$\displaystyle\dot{v}$ $\displaystyle=\int_{0}^{1}\frac{\partial f}{\partial
x}(\bar{x},\bar{z})\mathop{}\\!\mathrm{d}r\;v+\int_{0}^{1}\frac{\partial
f}{\partial z}(\bar{x},\bar{z})\mathop{}\\!\mathrm{d}r\;w,$ (25)
$\displaystyle{\varepsilon}\dot{w}$ $\displaystyle=\int_{0}^{1}\frac{\partial
g}{\partial
x}(\bar{x},\bar{z})\mathop{}\\!\mathrm{d}r\;v+\int_{0}^{1}\frac{\partial
g}{\partial z}(\bar{x},\bar{z})\mathop{}\\!\mathrm{d}r\;w.$

By Theorem 7, conditions (24) imply that (25) is $p$-dominant for all
${\varepsilon}>0$ sufficiently small. Using the compactness of
$\Omega_{x}\times\Omega_{z}$ implies that there exists ${\varepsilon}^{*}>0$
such that (25) is $p$-dominant for all ${\varepsilon}\in(0,{\varepsilon}^{*})$
and all $(x_{0},z_{0})\in\Omega_{x}\times\Omega_{z}$. In other words,

$\begin{bmatrix}x_{0}\\\ z_{0}\end{bmatrix}-\begin{bmatrix}\tilde{x}_{0}\\\
\tilde{z}_{0}\end{bmatrix}\in
C^{-}_{\mathcal{P}}\setminus\\{0\\}\implies\begin{bmatrix}x(t)\\\
z(t)\end{bmatrix}-\begin{bmatrix}\tilde{x}(t)\\\
\tilde{z}(t)\end{bmatrix}\in\operatorname{{\mathrm{i}nt}}(C^{-}_{\mathcal{P}})$

for all $t>0$, and this completes the proof. ∎

The next example demonstrates Theorem 10 using a singularly perturbed version
of a mechanical system with a nonlinear spring from [42].

######  Example 11.

Consider the non-linear singularly perturbed system:

$\displaystyle\dot{x}_{1}$ $\displaystyle=x_{2},$ $\displaystyle\dot{x}_{2}$
$\displaystyle=v(x_{1})-5z,$ $\displaystyle{\varepsilon}\dot{z}$
$\displaystyle=x_{2}-z,$ (26)

where $v:{\mathbb{R}}\to{\mathbb{R}}$ is $C^{2}$, $v(0)=0$, and
$v^{\prime}(s)\in[-5,2]$ for all $s\in{\mathbb{R}}$. The associated
variational system is the LTV:

$\displaystyle\dot{\delta x}_{1}$ $\displaystyle=\delta x_{2},$
$\displaystyle\dot{\delta x}_{2}$ $\displaystyle=v^{\prime}(x_{1})\delta
x_{1}-5\delta z,$ $\displaystyle{\varepsilon}\dot{\delta z}$
$\displaystyle=\delta x_{2}-\delta z.$ (27)

We can write this as the LTV system (II-A) with matrices

$A=\begin{bmatrix}0&1\\\ v^{\prime}(x_{1})&0\end{bmatrix},\
B=\begin{bmatrix}0\\\ -5\end{bmatrix},\ C=\begin{bmatrix}0&1\end{bmatrix},\
D=-1.$

Following Sec. II, we define

$L_{0}:=D^{-1}C=-C,\quad A_{0}:=A-BL_{0}=\begin{bmatrix}0&1\\\
v^{\prime}(x_{1})&-5\end{bmatrix}.$

Clearly, $A_{0}$ is always in the convex hull of the matrices

$\underline{M}:=\begin{bmatrix}0&1\\\
-5&-5\end{bmatrix},\quad\overline{M}:=\begin{bmatrix}0&1\\\
2&-5\end{bmatrix}.$

We choose

$P_{r}:=\begin{bmatrix}-5.1987&3.6260\\\ 3.6260&6.1987\end{bmatrix}.$

Then $\operatorname{{\mathrm{I}n}}(P_{r})=(1,0,1)$, and

$\displaystyle P_{r}\underline{M}+\underline{M}^{\mathsf{T}}P_{r}$
$\displaystyle\preceq-2\lambda_{r}P_{r}-\sigma_{r}I_{2},$ $\displaystyle
P_{r}\overline{M}+\overline{M}^{\mathsf{T}}P_{r}$
$\displaystyle\preceq-2\lambda_{r}P_{r}-\sigma_{r}I_{2},$

for $\lambda_{r}=2$, $\sigma_{r}=0.01$, which corresponds to (24a). Similarly,
for $P_{f}=1$, $\lambda_{f}=1/2$, and $\sigma_{f}=1$, we have

$P_{f}D+D^{\mathsf{T}}P_{f}\preceq-2\lambda_{f}P_{f}-\sigma_{f},$

which corresponds to (24b). We conclude that all the conditions in Theorem 10
hold, so the system is $1$-dominant. Thus, every bounded trajectory converges
to an equilibrium point. Fig. 1 depicts several trajectories of (11) with
$v(x)=7\tanh(x)-5x$ and ${\varepsilon}=0.01$. It may be seen that indeed every
trajectory converges to an equilibrium point.

Figure 1: Several trajectories of (11). Initial conditions [equilibrium
points] are marked with ’$\circ$’ [’x’].

##  IV Conclusion

Systems that are monotone w.r.t. a cone of rank $k$ satisfy useful asymptotic
properties. This follows from the fact that, roughly speaking, almost all
bounded solutions of such a system can be injectively projected into a
$k$-dimensional subspace, so essentially the dynamics is $k$-dimensional [16].

We derived a sufficient condition guaranteeing that a singularly perturbed
nonlinear system is monotone w.r.t. a matrix cone of rank $k$. The analysis is
relatively simple and does not require using geometric singular perturbations
theory. Another advantage of our approach is that it provides an explicit
expression for the matrix $k$-cone $C_{\mathcal{P}}^{-}$.

We demonstrated our results using a synthetic example, but we believe that it
may be useful in the analysis of real-world systems, e.g., power systems.
Another possible direction for future research is to study the relation of our
results to singularly perturbed $k$-contractive systems.

### Acknowledgments

We are grateful to Yi Wang for helpful comments.

## References

  * [1] L. Farina and S. Rinaldi, _Positive Linear Systems: Theory and Applications_. Wiley-Interscience, 2000\.
  * [2] H. L. Smith, _Monotone Dynamical Systems: An Introduction to the Theory of Competitive and Cooperative Systems_ , ser. Math. Surveys and Monographs. Providence, RI: Amer. Math. Soc., 1995, vol. 41.
  * [3] M. W. Hirsch, “The dynamical systems approach to differential equations,” _Bull. Amer. Math. Soc._ , vol. 11, pp. 1–64, 1984.
  * [4] ——, “Stability and convergence in strongly monotone dynamical systems,” _J. Reine Angew. Math._ , vol. 383, pp. 1–53, 1988.
  * [5] ——, “Systems of differential equations which are competitive or cooperative I: Limit sets,” _SIAM J. Math. An._ , vol. 13, pp. 167–179, 1982.
  * [6] ——, “Systems of differential equations which are competitive or cooperative II: Convergence almost everywhere,” _SIAM J. Math. Anal._ , vol. 16, pp. 423–439, 1985.
  * [7] H. Matano, “Asymptotic behavior and stability of solutions of semilinear diffusion equations,” _RIMS, Kyoto Univ._ , vol. 15, p. 401–454, 1979.
  * [8] ——, “Strongly order-preserving local semi-dynamical systems-theory and applications,” in _Semigroups, Theory and Applications_ , H. Brezis, M. Crandall, and F. Kappel, Eds. London: Longman Scientific and Technical, 1986, p. 178–185.
  * [9] P. Poláčik, “Convergence in smooth strongly monotone flows defined by semilinear parabolic equations,” _J. Diff. Eqns._ , vol. 79, pp. 89–110, 1989.
  * [10] ——, “Generic properties of strongly monotone semiflows defined by ordinary and parabolic differential equations,” in _Qualitative theory of differential equations (Szeged 1988)_. Amsterdam: North-Holland, 1990, pp. 519–530.
  * [11] H. Smith and H. Thieme, “Convergence for strongly order-preserving seliflows,” _SIAM J. Math. Anal._ , vol. 22, pp. 1081–1101, 1991.
  * [12] D. Angeli and E. Sontag, “Monotone control systems,” _IEEE Trans. Automat. Control_ , vol. 48, no. 10, pp. 1684–1698, 2003.
  * [13] G. Fusco and W. Oliva, “Jacobi matrices and transversality,” _Proc. R. Soc., Edinb. A_ , vol. 109, pp. 231–243, 1988.
  * [14] ——, “A Perron theorem for the existence of invariant subspaces,” _Ann. Mat. Pura Appl._ , vol. 160, pp. 63–76, 1991.
  * [15] M. Krasnoselśkii, E. Lifshits, and A. Sobolev, _Positive Linear Systems, the Method of Positive Operators_. Berlin: Heldermann Verlag, 1989.
  * [16] L. A. Sanchez, “Cones of rank 2 and the Poincaré–Bendixson property for a new class of monotone systems,” _J. Diff. Eqns._ , vol. 246, no. 5, pp. 1978–1990, 2009.
  * [17] S. Baigent, “Geometry of carrying simplices of 3-species competitive Lotka-Volterra systems,” _Nonlinearity_ , vol. 26, pp. 1001–1029, 2013\.
  * [18] ——, “Carrying simplices for competitive maps,” in _Difference Equations, Discrete Dynamical Systems and Applications_ , S. Elaydi, C. Pötzsche, and A. L. Sasu, Eds. Cham, Switzerland: Springer, 2019, p. 3–29.
  * [19] M. W. Hirsch, “Systems of differential equations which are competitive or cooperative III: Competing species,” _Nonlinearity_ , vol. 1, pp. 51–71, 1988.
  * [20] J. Jiang, J. Mierczyński, and Y. Wang, “Smoothness of the carrying simplex for discrete-time competitive dynamical systems: a characterization of neat embedding,” _J. Diff. Eqns._ , vol. 246, pp. 1623–1672, 2009.
  * [21] J. Mierczyński, “The $C^{1}$ property of convex carrying simplices for competitive maps,” _Ergod. Theory Dyn. Syst._ , vol. 40, pp. 1335–1350, 2020\.
  * [22] ——, “The $C^{1}$ property of convex carrying simplices for a class of competitive system of ODEs,” _J. Diff. Eqns._ , vol. 111, pp. 385–409, 1994.
  * [23] J. Mierczyński, L. Niu, and A. Ruiz-Herrera, “Linearization and invariant manifolds on the carrying simplex for competitive maps,” _J. Diff. Eqns._ , vol. 267, pp. 7385–7410, 2019.
  * [24] J. Jiang and L. Niu, “On the equivalent classification of three-dimensional competitive Leslie/Gower models via the boundary dynamics on the carrying simplex,” _J. Math. Biol._ , vol. 74, pp. 1223–1261, 2017.
  * [25] Y. Wang and J. Jiang, “The general properties of discrete-time competitive dynamical systems,” _J. Diff. Eqns._ , vol. 176, pp. 470–493, 2001.
  * [26] R. Ortega and L. Sanchez, “Abstract competitive systems and orbital stability in $\mathbb{R}^{3}$,” _Proc. Amer. Math. Soc._ , vol. 128, pp. 2911–2919, 2000.
  * [27] R. A. Smith, “Existence of periodic orbits of autonomous ordinary differential equations,” _Proc. R. Soc., Edinb. A_ , vol. 85, pp. 153–172, 1980.
  * [28] ——, “Orbital stability for ordinary differential equations,” _J. Diff. Eqns._ , vol. 69, pp. 265–287, 1987.
  * [29] L. Feng, Y. Wang, and J. Wu, “Generic convergence to periodic orbits for monotone flows with respect to 2-cones and applications to SEIRS models,” _SIAM J. Appl. Math._ , vol. 82, no. 5, pp. 1829–1850, 2022.
  * [30] J. Mallet-Paret and R. Nussbaum, “Tensor products, positive linear operators, and delay-differential equations,” _J. Dynam. Diff. Eqns._ , vol. 25, pp. 843–905, 2013.
  * [31] J. Mallet-Paret and G. Sell, “The Poincaré-Bendixson theorem for monotone cyclic feedback systems with delay,” _J. Diff. Eqns._ , vol. 125, pp. 441–489, 1996.
  * [32] J. Mallet-Paret and H. Smith, “The Poincaré-Bendixson theorem for monotone cyclic feedback systems,” _J. Dynam. Diff. Eqns._ , vol. 2, pp. 367–421, 1990.
  * [33] T. Ben-Avraham, G. Sharon, Y. Zarai, and M. Margaliot, “Dynamical systems with a cyclic sign variation diminishing property,” _IEEE Trans. Automat. Control_ , vol. 65, pp. 941–954, 2020.
  * [34] M. Margaliot and E. D. Sontag, “Compact attractors of an antithetic integral feedback system have a simple structure,” 2019. [Online]. Available: https://www.biorxiv.org/content/10.1101/868000v1
  * [35] R. A. Smith, “The Poincaré–Bendixson theorem for certain differential equations of higher order,” _Proc. R. Soc., Edinb. A_ , vol. 83, no. 1-2, p. 63–79, 1979.
  * [36] ——, “Existence of periodic orbits of autonomous ordinary differential equations,” _Proc. R. Soc., Edinb. A_ , vol. 85, pp. 153–172, 1980.
  * [37] L. A. Sanchez, “Existence of periodic orbits for high-dimensional autonomous systems,” _J. Math. Anal. Appl._ , vol. 363, pp. 409–418, 2010.
  * [38] L. Feng, Y. Wang, and J. Wu, “Semiflows “monotone with respect to high-rank cones” on a Banach space,” _SIAM J. Math. Anal._ , vol. 49, pp. 142–161, 2017.
  * [39] ——, “Generic behavior of flows strongly monotone with respect to high-rank cones,” _J. Diff. Eqns._ , vol. 275, pp. 858–881, 2021.
  * [40] Y. Wang, J. Yao, and Y. Zhang, “Prevalent behavior and almost sure Poincaré–Bendixson theorem for smooth flows with invariant $k$-cones,” _J. Dyn. Diff. Equat._ , 2022, to appear.
  * [41] E. Weiss and M. Margaliot, “A generalization of linear positive systems with applications to nonlinear systems: Invariant sets and the Poincaré-Bendixson property,” _Automatica_ , vol. 123, p. 109358, 2021\.
  * [42] F. Forni and R. Sepulchre, “Differential dissipativity theory for dominance analysis,” _IEEE Trans. Automat. Control_ , vol. 64, no. 6, pp. 2340–2351, 2018.
  * [43] F. A. Miranda-Villatoro, F. Forni, and R. J. Sepulchre, “Analysis of Lur’e dominant systems in the frequency domain,” _Automatica_ , vol. 98, pp. 76–85, 2018.
  * [44] P. Kokotović, H. K. Khalil, and J. O’reilly, _Singular Perturbation Methods in Control: Analysis and Design_. SIAM, 1999.
  * [45] H. Khalil, _Nonlinear Systems_. Prentice Hall, 2002.
  * [46] P. Lorenzetti and G. Weiss, “Saturating PI control of stable nonlinear systems using singular perturbations,” _IEEE Trans. Automat. Control_ , vol. 68, no. 2, pp. 867–882, 2023.
  * [47] ——, “PI control of stable nonlinear plants using projected dynamical systems,” _Automatica_ , vol. 146, p. 110606, 2022.
  * [48] P. Lorenzetti, Z. Kustanovich, S. Shivratri, and G. Weiss, “The equilibrium points and stability of grid-connected synchronverters,” _IEEE Trans. on Power Systems_ , vol. 37, no. 2, pp. 1184–1197, 2022.
  * [49] L. Wang and E. D. Sontag, “Singularly perturbed monotone systems and an application to double phosphorylation cycles,” _J. Nonlinear Sci._ , vol. 18, p. 527–550, 2008.
  * [50] L. Niu and X. Xie, “Generic Poincaré-Bendixson theorem for singularly perturbed monotone systems with respect to cones of rank-2,” 2021. [Online]. Available: https://arxiv.org/abs/2110.11783v1
  * [51] N. Fenichel, “Geometric singular perturbation theory for ordinary differential equations,” _J. Diff. Eqns._ , vol. 31, p. 53–98, 1979.
  * [52] K. Sakamoto, “Invariant manifolds in singular perturbation problems for ordinary differential equations,” _Proc. R. Soc., Edinb. A_ , vol. 116, p. 45–78, 1990.
  * [53] W. Lohmiller and J.-J. E. Slotine, “On contraction analysis for non-linear systems,” _Automatica_ , vol. 34, pp. 683–696, 1998.
  * [54] Z. Aminzare and E. D. Sontag, “Contraction methods for nonlinear systems: A brief introduction and some open problems,” in _Proc. 53rd IEEE CDC_ , Los Angeles, CA, 2014, pp. 3835–3847.
  * [55] C. Wu, I. Kanevskiy, and M. Margaliot, “$k$-contraction: theory and applications,” _Automatica_ , vol. 136, p. 110048, 2022.


Mandator and Sporades: Robust Wide-Area Consensus with Efficient Request Dissemination

Pasindu Tennage

Antoine Desjardins

IST Austria
Eleftherios Kokoris Kogias

IST Austria

Consensus algorithms are deployed in the wide area to achieve high availability for geographically replicated applications. Wide-area consensus is challenging due to two main reasons: (1) low throughput due to the high latency overhead of client request dissemination and (2) network asynchrony that causes consensus protocols to lose liveness. In this paper, we propose Mandator and Sporades, a modular state machine replication algorithm that enables high performance and resiliency in the wide-area setting.

To address the high client request dissemination overhead challenge, we propose Mandator, a novel consensus-agnostic asynchronous dissemination layer. Mandator separates client request dissemination from the critical path of consensus to obtain high performance. Composing Mandator with Multi-Paxos (Mandator-Paxos) delivers significantly high throughput under synchronous networks. However, under asynchronous network conditions, Mandator-Paxos loses liveness which results in high latency. To achieve low latency and robustness under asynchrony, we propose Sporades, a novel omission fault-tolerant consensus algorithm. Sporades consists of two modes of operations – synchronous and asynchronous – that always ensure liveness. Sporades leverages the synchronous network to minimize the communication cost to $O(n)$ and matches the lower bound of $O(n^2)$ at worse-case executions. The combination of Mandator and Sporades (Mandator-Sporades) provides a robust and high-performing state machine replication system.

We implement and evaluate Mandator-Sporades in a wide-area deployment running on Amazon EC2. Our evaluation shows that in the synchronous execution, Mandator-Sporades achieves 300k tx/sec throughput in less than 900ms latency, outperforming Multi-Paxos, EPaxos and Rabia by 650% in throughput, at a modest expense of latency. Furthermore, we show that Mandator-Sporades outperforms Mandator-Paxos, Multi-Paxos, and EPaxos in the face of targeted distributed denial-of-service attacks.

§ INTRODUCTION

State machine replication (SMR) [8] is a distributed computing abstraction that is widely used in data center-based applications [7, 23, 27]. SMR enables a distributed set of replicas to consistently replicate the state while remaining resilient to a minority of replica failures. At the heart of SMR lies consensus which allows replicas to agree on the total order of many values. While the early approaches to consensus focused on in-data-center deployments [30, 38, 46], recent research [32, 3, 44] has focused on the wide-area consensus algorithms. Consensus algorithms are often used in the wide-area setting to achieve high availability for applications that are geographically replicated and use the public Internet infrastructure.

Existing wide-area SMR protocols deliver low throughput due to high client request dissemination overhead: monolithic designs that encapsulate a batch of client requests inside consensus messages result in a bottleneck as the system throughput is then bound by the speed of consensus [15]. When the consensus messages carry a batch of client requests, the asymptotic linear message complexity of consensus algorithms does not necessarily reflect the experimental performance when deployed in the wide area. This is because, in practice, the size of a consensus message is mostly influenced by the request batch size (sizes in the order of 100KB), whereas the theoretical message complexity accounts for metadata messages (sizes in the order of 100B).

To address the high client request dissemination overhead problem, existing research has focused on monolithic approaches that incorporate wide-area latency optimization strategies into the consensus logic. Multi-leader-based approaches [13, 48, 29, 41] aim at off-loading the leader request dissemination overhead to non-leader replicas. EPaxos [32] addresses the high request dissemination overhead challenge by taking advantage of application-dependent request dependency commutativity. However, we identified that existing approaches provide sub-optimal wide-area throughput, because monolithic protocols place client request dissemination in the critical path of consensus, impacting the performance when deployed in the wide area.

In this paper, we propose Mandator, an asynchronous and consensus-agnostic request dissemination protocol, that reliably replicates client request batches among replicas to address the high client request dissemination overhead problem. Mandator decouples client request dissemination from the total ordering, such that Mandator can run in parallel with the consensus protocol without any codependency. Mandator builds on the intuition that reliable client request dissemination is an embarrassingly parallelizable task that can run at the speed of the network (in contrast to monolithic protocols that disseminate client requests at the speed of consensus). Moreover, as we prove in Section <ref>, reliable client request dissemination requires a simpler primitive than consensus, namely best effort broadcast with acknowledgements. Mandator leverages this best effort broadcast with acknowledgements primitive, together with a primitive that closely reflects vector clocks to build a high-performance wide-area request dissemination protocol. Consensus algorithms such as Multi-Paxos can employ Mandator as a building block and use the lightweight vector clock returned from the Mandator as the payload for consensus. With Mandator in place, consensus message sizes are lightweight and are no longer dominated by the client request batch size.

To showcase the performance advantage of Mandator, we composed Mandator with Multi-Paxos (Mandator-Paxos). In a wide-area deployment running on AWS EC2, we observed that Mandator-Paxos can deliver 300k tx/sec throughput under 900ms latency when the network is synchronous while outperforming Multi-Paxos by 650% in throughput, at a modest expense of latency. However, in the presence of leader replica failures and network asynchrony, we observed that Mandator-Paxos provides low throughput (250k tx/sec) with significantly high latency (5s). Since Mandator guarantees liveness under asynchrony, we attribute this loss of performance under faults and asynchrony to Multi-Paxos's liveness guarantees: Multi-Paxos is a partially synchronous protocol that loses liveness under an asynchronous network and leader replica failures. Hence, as the second challenge of wide-area SMR, we focus on the loss of liveness problem under an asynchronous network and replica failures.

Previous research addressing the liveness impact of replica failures and network asynchrony on the performance falls into two categories: (1) partially synchronous algorithms that eliminate the single leader dependency, thus minimizing the impact of partitioned replicas on the liveness of consensus, and (2) asynchronous protocols such as Ben-Or [5] that guarantee liveness under an asynchronous network. Partially synchronous protocols such as EPaxos [32] and Mencius [46] avoid the single leader bottleneck, and are immune to leader network partitions, but they lose liveness under an asynchronous network. Asynchronous protocols such as Ben-Or [5] are immune to asynchronous network conditions, but have quadratic message complexity and low performance in the typical synchronous case. As a result, asynchronous protocols are not typically deployed in the wide-area[Rabia [38] is a protocol built on top of Ben-Or [5], but Rabia operates in a synchronous network and loses liveness in an asynchronous network]. We believe that a practical wide-area consensus algorithm should have the best of both worlds (1) high performance under synchrony, and (2) high resilience and liveness under asynchronous networks and replica failures.

To address the challenge of liveness under network asynchrony and replica failures in SMR, we propose Sporades, a novel omission fault-tolerant consensus algorithm, that combines an optimistic, linear overhead synchronous path protocol with a pessimistic path protocol that guarantees liveness under asynchrony. Sporades, has two modes; (1) a synchronous mode and (2) an asynchronous mode. The synchronous mode of Sporades commits a batch of client requests in a single network round-trip when the network is synchronous. However, when the network is asynchronous, Sporades falls back to an asynchronous mode that commits client requests with quadratic message complexity. This makes the Sporades guarantee liveness in the face of replica failures, asynchronous networks and DDoS attacks. The composition of Mandator with Sporades (Mandator-Sporades) is a novel SMR algorithm that guarantees high performance in the wide area while providing liveness guarantees under asynchronous networks and replica failures.

We make three contributions in this paper:

* We design and implement Mandator: a novel consensus-agnostic request dissemination protocol. We implement Multi-Paxos on top of Mandator, which we refer to as Mandator-Paxos

* We design Sporades, a novel omission fault tolerant consensus algorithm that guarantees liveness under asynchronous network conditions. We implement Sporades on top of Mandator (Mandator-Sporades)

* We experimentally show that Mandator-Paxos and Mandator-Sporades achieve 300k tx/sec throughput under 900ms median latency, compared to EPaxos [32] (6.5k tx/s under 720ms), Multi-Paxos [30] (40k under 295ms) and Rabia [38] (0.5k under 500ms) in the synchronous network conditions in a wide-area deployment running on AWS EC2. We also show that Mandator-Sporades outperforms Mandator-Paxos by 60% in throughput in the face of DDoS attacks.

§ PRELIMINARIES

This section provides an overview of the system model and SMR.

§.§ System Model

We consider a system with $n$ replicas. We assume omission fault-tolerant replicas. An omission fault occurs when a replica does not send (or receive) a message that it is supposed to send (or receive) according to the specification of the algorithm [8]. Up to $f$ (where $n$ $\geq$ 2$f$ + 1) number of replicas can display omission-fault behaviors, but replicas do not equivocate.

We assume perfect point-to-point links between each pair of replicas; messages from any correct replica pi to any correct replica pj are eventually delivered. The replicas are connected in a logical-complete graph. We say that a replica broadcasts a message $m$ if it sends $m$ to all $n$ replicas. We assume an adversarial network that can arbitrarily reorder and delay the messages.

Let $\Delta$ be the upper bound on message transmission delay and GST be the global stabilization time. An execution of a protocol is considered synchronous if each message sent from a correct replica pi is delivered by replica pj within $\Delta$. An execution of a protocol is considered asynchronous if there exists no time bound $\Delta$ for message delivery. An execution of a protocol is said to be partially synchronous, if there is an unknown GST such that once GST is reached, each message sent by process pi is delivered by process pj within a known $\Delta$[16].

Due to the FLP impossibility result [18], any deterministic algorithm cannot solve consensus under asynchrony even under a single replica failure. In Sporades, we circumvent the FLP impossibility result using partial synchrony and randomization. In a typical wide-area network, there are periods in which the network behaves synchronously, followed by phases where the network shows asynchronous behaviour. Sporades makes use of this network behaviour and operates in two modes: (1) synchronous mode and (2) asynchronous mode. During the synchronous periods, Sporades assumes partial synchrony for liveness and during the asynchronous mode, Sporades assumes an asynchronous network and uses randomization.

§.§ Consensus and State Machine Replication

Consensus is a distributed system abstraction that enables a set of replicas to reach an agreement on a single value. A correct consensus algorithm satisfies four properties [8]: (1) validity: the agreed upon value should be previously proposed by a replica, (2) termination: every correct process eventually decides some value, (3) integrity: no process decides twice and (4) agreement: no two correct processes decide differently.

SMR is a use-case of consensus, where replicas run multiple instances of the consensus algorithm to agree on a series of values [8][4]. In this paper, we solve the SMR problem. A correct SMR algorithm satisfies two properties; (1) safety: no two replicas commit different client requests for the same log position and (2) liveness: each client request is eventually committed. We assume that each client request will be repeatedly proposed by replicas until it is committed.

We focus on the chaining approach to SMR similar to Raft [37], in which each new proposal to SMR has a reference (parent link) to the previous proposal, and each commit operation commits the entire history of client requests.

§ DESIGN

In this section, we discuss the design of Mandator and Sporades as two building blocks and then present how to build a high-performing and resilient wide-area SMR algorithm by combining the Mandator and Sporades in section <ref>.

§ IMPLEMENTATION

We implemented Sporades and Mandator using Golang version 1.18.3. We first implemented Mandator and implemented Sporades and Paxos on top of Mandator, which we refer to as Mandator-Sporades and Mandator-Paxos, respectively. We used standard Golang TCP library to achieve reliable point-to-point links. We used Protobuf encoding [21] to marshal and unmarshal messages.

In our implementation, we used a classic design principle in systems design; separation of control plane from the data plane. We optimized the reliable request dissemination of Mandator by delegating the task of client request dissemination to a separate child process that runs in the same replica machine: each replica has one or more child processes that are assigned to it. Child processes are stateless, and are concerned only about reliably broadcasting client request batches. With child processes in place, the typical execution of Mandator is as follows. The client sends a batch of requests to a child process, the child process collects one or more such client request batches, forms a child-batch, and sends it to a majority of child processes in other replica machines. Each child process, upon receiving a new child-batch, will send an acknowledgement to the originator, and will also send the received child batch to the main replica process. The sending child process, upon receiving a majority of acknowledgements, will send a child-batch-confirm message to the replica. The replica uses the confirmed child batch identifiers in the Mandator batches.

We also employed selective-broadcast, a novel memory-efficient pull-based broadcast primitive in the Mandator implementation. Namely, each Mandator replica keeps track of the last received <Mandator-vote> for each replica and sends the new Mandator-batches only to the replicas that are most up-to-date, with the restriction that there is at least a majority of receivers. Replicas that do not receive the new batch use a pull-based mechanism to request missing batches. Selective broadcast helps to avoid memory overflow resulting from increasing queue lengths in the face of network asynchrony.

§ EVALUATION

The goal of our evaluation is to answer the following four questions: (1) How efficient is Mandator in disseminating client requests in the wide-area? (2) How robust is Mandator-Sporades in the face of replica failures? (3) How robust is Mandator-Sporades in the face of targeted DDoS attacks? and (4) How does Mandator-Sporades scale with increasing replica count in the wide-area when deployed with Redis [12]?

To showcase the performance and resilience of Mandator-Sporades, we compare Mandator-Sporades against three state-of-the-art consensus algorithms; Rabia [38], EPaxos (with 3% conflict rate) [32], and Multi-Paxos [30]. Rabia is a randomized consensus algorithm that builds on top of Ben-Or [5]. EPaxos is a consensus algorithm that achieves high throughput in the cluster and low latency in the wide-area. Multi-Paxos is a popular choice in production systems due to its simplicity [7].

§.§ Setup

We conducted our experiments using c4.4xlarge (16 virtual CPUs, 30 GB memory, and up to 10 Gbps network bandwidth) and c4.2xlarge (8 virtual CPUs, 15 GB memory, and up to 10 Gbps network bandwidth) virtual machines for replicas and clients, respectively. We used Ubuntu Linux 20.04.3 LTS for all the machines. We employed the same evaluation setup as in Mencius[46] and Baxos[44], where each AWS location has a single replica machine and a single client machine. We experimented with three to nine replicas and three to nine clients located in nine geographically separated AWS regions in N.Virginia, Ireland, Mumbai, St.Paulo, Tokyo, Oregon, Ohio, Singapore and Sydney.

§.§ Benchmarks and Workload

We employ two benchmarks in our evaluation; (1) a resident key-value store written in Go-Lang and (2) Redis [12]. As the resident key-value store, we use the same implementation as Rabia [38] key-value store, which uses a Go-Lang map object to save keys and values of type string. For the Redis benchmark, we used a Go-Redis connector [1]. Our Redis integration with Mandator-Sporades uses the same approach used in Redis-Rabia [38], and we use Redis native MGet and MPut commands to process a batch of requests.

Median latency

Tail latency

Best-case wide-area performance of Mandator with 5 replicas and 5 clients. Note that the x-axis is in the log-scale

We use open loop model [42] Poisson arrival of client requests, due to its wide adoption in client request generation tools [44, 45]. All four consensus algorithms use batching on the replica side and the client side. We set the client-side batch size to 100. Interestingly, we found that different algorithms have different optimum replica batch sizes, and following the previous studies [32, 38] we use 1000, 5000, and 300 as the replica side batch sizes for EPaxos, Multi-Paxos, and Rabia, respectively. For Sporades, we used 2000 as the replica-side batch size. Furthermore, we set the maximum batch time to 5ms which is the standard batch time used in EPaxos [32]. We do not use pipe-lining in our evaluation, which is an orthogonal approach to improve wide-area performance.  We set the size of a client request to 16B (8B key length and 8B value length). We chose these request sizes after observing the request sizes used in deployed systems; e.g. in Facebook’s production TAO system [6], 50% of requests have a value field smaller than 16B.

In our experiments, all client requests are totally ordered and executed. When a replica receives a request, it uses consensus to totally order it, and upon committing and executing, sends a response back to the client. After each experiment, we use the replica commit log to verify that each replica learns the same history of requests. In all algorithms, we measure the execution latency[commit latency: latency for total ordering]  [execution latency: commit latency + latency for executing the command and the causal history] [For Multi-Paxos, Sporades and Rabia the commit latency and the execution latency differ by a negligible amount whereas for EPaxos the execution latency is significantly higher than the commit latency when the conflict rate of EPaxos is non-zero] in the client side starting from when a new request is first sent by a client until the client receives the corresponding response. Following the evaluation approach of the revised version of EPaxos [45], we opted to measure the execution latency instead of the commit latency, because the commit latency does not represent all the application use-cases; if a client depends on the response returned by an operation, then the client has to wait for the execution to be completed [23] [12]. Each experiment was run for 60 seconds and was repeated 5 times.

§.§ Mandator Performance

This experiment evaluates the performance of Mandator in the wide-area deployment. We deployed the consensus algorithms in five AWS regions located in N.Virginia, Ireland, Mumbai, St.Paulo, and Tokyo. We configured the clients to send requests with different arrival rates in a Poisson open loop. We measure the throughput, median and 99% latency for different arrival rates. Figure <ref> depicts the experiment results.

Rabia: We observe that the throughput of Rabia saturates at 500 tx/sec in less than 500ms median latency. This is a significantly different result compared to the Rabia performance evaluated inside a local area network (LAN) (inside a LAN Rabia delivers 300k tx/sec throughput [38]). We identified that this mismatch between the local-area and wide-area performance is a direct consequence of Rabia design; Rabia is designed to achieve high performance when each replica receives the same client request approximately at the same time. In a LAN deployment this timing assumption holds, but not in the WAN. Since the performance of Rabia under best-case deployment provides low throughput, we do not use Rabia in our following experiments in sections <ref> <ref> and <ref>.

EPaxos and Multi-Paxos: We observe that the throughput of Epaxos saturates at 6,500 tx/sec in less than 720ms median latency. We also observe that Multi-Paxos delivers a throughput of 40,000 tx/sec in less than 295ms median latency, which is significantly higher than that of EPaxos. These behaviours conform to the observations made in the revised evaluation of EPaxos [45]. We explain these behaviours as follows.

In our experiments, we measured the execution latency (we used the $-exec$ and $-dreply$ flags of EPaxos). When measured for the execution latency, EPaxos fails at achieving high throughput due to two main reasons: (1) infinitely growing dependency chains and (2) high execution delay for dependent requests. When the conflict rate of EPaxos is non-zero, it has been shown that the execution latency of EPaxos can be more than 2x the commit latency [45]. Hence Epaxos delivers low throughput under a specified median latency upper bound. Moreover, for both Multi-Paxos and EPaxos, we observed that the throughput is bottlenecked by the speed of consensus:  since EPaxos and Multi-Paxos have to carry a batch of client requests inside the consensus messages, the maximum attainable throughput is bottlenecked by the speed of consensus, thus delivering sub-optimal results.

Mandator-Paxos and Mandator-Sporades: We make two observations in Mandator-Paxos and Mandator-Sporades: (1) both Mandator-Paxos and Mandator-Sporades deliver the same throughput and latency and (2) Mandator-Paxos and Mandator-Sporades achieve 300,000 tx/sec throughput in less than 900ms median latency, and outperform Rabia, Epaxos and Multi Paxos by 650% in throughput, at a 200% higher latency.

First, Mandator-Paxos and Mandator-Sporades achieve the same best case performance because the message complexity of Paxos and Sporades are similar in synchronous execution. Second, the 650% increase of throughput in Mandator-Paxos and Mandator-Sporades is a direct consequence of the Mandator design: Mandator uses an efficient method of batching multiple client requests in a single Mandator batch. Consequently, when a single consensus block gets committed, a larger batch of client requests gets committed. Mandator-based protocols disseminate the client requests without waiting for consensus acknowledgment, hence utilizing the network link bandwidth more efficiently. Stated differently, the performance of Mandator is bottlenecked by the speed of the network. In contrast, Multi-Paxos, EPaxos, and Rabia employ batching inside the critical path of consensus, such that the throughput is bottlenecked by the speed of consensus. This validates our hypothesis that separating the request dissemination from the total-ordering improves throughput.

Latency overhead of Mandator: The median and tail latency of Mandator-Paxos and Mandator-Sporades are 200% higher than Multi-Paxos for throughput values less than 40k tx/sec. Mandator-Paxos and Mandator-Sporades consume 10 message hops for each client request when deployed with a single child process, and this results in high latency. This latency cost is acceptable for applications such as strongly consistent distributed file sharing, where throughput is more critical than latency. In contrast, if the latency is more critical, then we propose to use Sporades without Mandator. When deployed without Mandator, Sporades provides the same latency and throughput behaviors as Multi-Paxos, because the asymptotic message complexities and the communication patterns are similar between synchronous mode of Sporades and Multi-Paxos. A more practical approach would be to dynamically enable Mandator depending on the application SLO latency guarantees and client arrival rate.

§.§ Crash failures

In this experiment, we evaluate the impact of replica failures on throughput. In Mandator-Paxos and Mandator-Sporades, we crash the leader replica and in EPaxos we crash a random replica (since EPaxos is leaderless). Figure <ref> shows the throughput with respect to time.

Crash-Fault Performance with 3 replicas and 2 clients. At t=30s the leader replica in Mandator-Paxos and Mandator-Sporades and a random replica in EPaxos are crashed

We observe that both EPaxos and Mandator-Sporades are not affected by the node failure, whereas Mandator-Paxos has transient low and high spikes in throughput. EPaxos is resilient to node failures given that there exists no leader replica. Mandator-Sporades is resilient to leader node failures because of the asynchronous path of Sporades: in the face of leader failures, Sporades falls back to an asynchronous path which commits transactions. Hence when a new leader is elected Sporades keeps committing new requests. In contrast, Mandator-Paxos (and also Multi-Paxos) fails at committing new requests during the view change, hence the throughput approaches zero just after the leader failure. However, during this period when a new leader is elected, Mandator continues to reliably broadcast client requests, and as a result, when a new Multi-Paxos leader is elected, requests are committed with high throughput (with 5,000 tx/sec as the maximum in this experiment). This is the reason for observing an upward spike for Mandator-Paxos after the leader election.

§.§ Performance under DDoS attacks

In this experiment, we focus on the impact of targeted DDoS attacks on throughput and latency. We use a more generalized version of delayed-view-change attack; a DDoS attack previously presented in [44, 43]. In a delayed-view-change-attack, a DDoS attack is simulated by continuously attacking the leader node dynamically upon each view change. However, a delayed-view-change-attack does not consider the overhead on the attacker, given that performing a dynamic network traffic analysis to find the new leader node is a time-consuming task. In our work, we modify this attack such that the attacker randomly chooses a minority of the replicas and attacks them. We believe that our approach is more practical, given that the attacker does not have to do a wide-area network traffic analysis to find the leader.

Figure <ref> shows the throughput and median latency under DDoS attacks. Since this attack measures the performance under worst-case network scenarios, in the following we discuss the throughput values under 5s median latency upper bound (in contrast, we discussed throughput under 1s median latency in the best case evaluation in subsection <ref>). We first observe that the attack has the highest impact on EPaxos by having a maximum throughput of 7200 tx/sec (under 5s median latency). This is due to the high delayed-execution latency resulting from the expensive instance revocation path of the EPaxos. Second, the throughput of Multi-Paxos is also affected by the DDoS attack by having a throughput of 45,000 tx/sec (under 5s median latency), due to liveness loss during the leader elections. Third, Mandator-Paxos delivers 250,000 tx/sec throughput (under 5s median latency) which is significantly less than its synchronous performance. However, the DDoS performance of Mandator-Paxos is still large enough due to the impact of Mandator: Mandator is not affected by the attack due to its asynchronous nature, and hence continues to reliably disseminate requests at the speed of the network. Though Paxos is affected by the DDoS attack, the impact on the average throughput of Mandator-Paxos is low, because upon a new leader election Mandator-Paxos can commit a large batch of requests that is disseminated by Mandator. Finally, Mandator-Sporades delivers 400,000 tx/sec throughput under 5s median latency. We attribute this high throughput to Sporades's liveness guarantees during network asynchrony: the asynchronous mode of Sporades continues to commit client requests during network asynchrony. Hence this experiment confirms our design hypothesis that Mandator-Sporades is resilient to DDoS attacks due to its asynchronous liveness guarantees.

Performance under DDoS attack with 5 replicas. Up to a minority (=2) of nodes are attacked at a given time, dynamically. Note that the x-axis is in log-scale.

§.§ Scalability with Redis

In this experiment, we aim to quantify the scalability of Mandator-Sporades with Redis integration. Redis is an in-memory data store that supports data structures and operations on them, such as hash maps, lists, and sets. Since the real-world deployments have strict service level objectives for the latency, we fix the maximum allowed median latency to be 1.5s. We evaluated the scalability of Mandator-Sporades by running it with an ensemble of three, five, seven and nine replicas. It should be noted that, unlike blockchain algorithms where consensus algorithms are measured for up to a hundred nodes, crash fault tolerant protocols are designed to scale up to 9 nodes in practice [46, 24]. Figure <ref> shows the scalability results.

We observe that Mandator-Sporades can scale up to 9 nodes while delivering a throughput of 150,000 tx/sec, in the 9 replica deployment. We also observe that with an increasing replica count the median latency increases, and we attribute this behaviour to the increasing broadcast message overhead with the increasing number of replicas.

Scalability with respect to increasing replica count

§ RELATED WORK

Partially synchronous consensus: Leader-based partially synchronous consensus algorithms such as Multi-Paxos [30], Raft [37], and View Stamp Replication [36] use a single leader node to totally order requests. While using the leader-based approach is simple, it suffers from leader computational and network bottlenecks, thus failing to achieve high performance. To address the single leader bottleneck, multi-leader consensus algorithms such as Baxos [44], Mencius [46], EPaxos [32], Generalized Paxos [26] and Multi-Coordination Paxos [11] were proposed. At the core of the multi-leader design, there are two design principles: (1) statically partition the replicated log space and (2) exploit request commutativity to parallelize total ordering. These Multi-leader approaches suffer from low performance when concurrent requests have conflicting dependencies. All leader-based and leaderless partially synchronous protocols fail at guaranteeing liveness in the face of network asynchrony and DDoS attacks. In contrast, Sporades continues to commit requests in the presence of network asynchrony.

Asynchronous consensus: Ben-Or [5] proposed an asynchronous binary consensus algorithm using randomization. Following Ben-Or, several theoretical research [2, 17, 19, 39] have proposed improvisations for Ben-Or that enables (1) Byzantine tolerance[33], (2) reducing the message complexity [40] and supporting multi-valued consensus [47]. However, all of these works are of theoretical interest, with no practical evaluation. To the best of our knowledge, the first practical system that employs Ben-Or as its core is Rabia [38]. As we showed in section <ref>, Rabia does not provide throughput values greater than 1000 tx/sec in the wide-area. In contrast, Sporades provides 300k tx/sec throughput in the wide-area. Previous research [9, 10, 31] have proposed Byzantine asynchronous consensus algorithms, but they are not directly related to our scope.

Protocol switching consensus: Turtle consensus [34, 35] is the closest work to Sporades that employs a synchronous path and an asynchronous path. Turtle consensus works by statically switching between Multi-Paxos and Ben-Or. Statically switching is sub-optimal given that the asynchronous path can be triggered by a transient network delay (in a synchronous setting), such that performance will be degraded. In contrast, in Sporades, we use dynamic mode switching between the synchronous mode and the asynchronous mode, such that Sporades stays in the synchronous path whenever the network is synchronous. Several works [20, 22, 25] have explored the protocol switching approach with Byzantine failure tolerance for blockchain applications, but fall outside our scope.

Efficient request dissemination Previous research have focused on improving the request dissemination using two approaches: (1) sharding [28] [3] [14] and (2) overlay networks [29] [41] [13] [48]. We find that sharding is an orthogonal approach to our design of Mandator: Mandator can be extended to support sharding by deploying Mandator in multiple shards. Overlay networks such as Ring Paxos [29], Canopus [41], PigPaxos [13], and SD-Paxos [48] improve the performance of the consensus algorithm by using non-leader replicas to relay the requests such that the overhead imposed on the leader node is minimized. However, the performance gain of such approaches is relatively low compared to Mandator, and we find the monolithic design of existing protocols as the main cause of this problem. In contrast, we present Mandator as a stand-alone and generic consensus agnostic overlay, that can run at the speed of the network, thus delivering high performance as shown in section <ref>.

§ CONCLUSION

We presented Mandator and Sporades, a novel wide-area SMR algorithm that can achieve high performance and robustness under network asynchrony. We first presented Mandator, a consensus agnostic asynchronous request dissemination layer, that efficiently disseminates client requests. Then we presented Sporades, a novel consensus algorithm that can achieve optimum one round-trip consensus in the synchronous network setting, as well as liveness in the face of network asynchrony using an asynchronous fallback path. Our evaluation shows that Mandator-Sporades delivers 300k tx/sec under 900ms in the wide-area, and out-performs Multi-Paxos by 650%, at a modest expense of latency. We also showed that Mandator-Sporades outperforms Mandator-Paxos by 60% in throughput, in the presence of DDoS attacks.

[1]
Redis client for golang.
<https://github.com/go-redis/redis/>, 2021.

[2]
Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, and Ling Ren.
Synchronous byzantine agreement with expected o(1) rounds, expected
o(n2) communication, and optimal resilience.
International Conference on Financial Cryptography and Data
Security, 2019.

[3]
Ailidani Ailijiang, Aleksey Charapko, Murat Demirbas, and Tevfik Kosar.
Wpaxos: Ruling the archipelago with fast consensus.
arXiv preprint arXiv:1703.08905, 2017.

[4]
Karolos Antoniadis, Rachid Guerraoui, Dahlia Malkhi, and Dragos-Adrian
State machine replication is more expensive than consensus.
Technical report, 2018.

[5]
Michael Ben-Or.
Another advantage of free choice (extended abstract) completely
asynchronous agreement protocols.
In Proceedings of the second annual ACM symposium on Principles
of distributed computing, pages 27–30, 1983.

[6]
Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui
Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, et al.
Tao:facebook’s distributed data store for the social graph.
In 2013 USENIX Annual Technical Conference (USENIX ATC 13),
pages 49–60, 2013.

[7]
Mike Burrows.
The chubby lock service for loosely-coupled distributed systems.
In Proceedings of the 7th symposium on Operating systems design
and implementation, pages 335–350, 2006.

[8]
Christian Cachin, Rachid Guerraoui, and Luís Rodrigues.
Introduction to reliable and secure distributed programming.
Springer Science & Business Media, 2011.

[9]
Christian Cachin, Klaus Kursawe, and Victor Shoup.
Random oracles in constantinople: Practical asynchronous byzantine
agreement using cryptography.
Journal of Cryptology, 18(3):219–246, 2005.

[10]
Christian Cachin, Simon Schubert, and Marko Vukolic.
Non-determinism in byzantine fault-tolerant replication.
arXiv preprint arXiv:1603.07351, 2016.

[11]
Lásaro Jonas Camargos, Rodrigo Malta Schmidt, and Fernando Pedone.
Multicoordinated paxos.
In Proceedings of the twenty-sixth annual ACM symposium on
Principles of distributed computing, pages 316–317, 2007.

[12]
Josiah Carlson.
Redis in action.
Simon and Schuster, 2013.

[13]
Aleksey Charapko, Ailidani Ailijiang, and Murat Demirbas.
Pigpaxos: Devouring the communication bottlenecks in distributed
In Proceedings of the 2021 International Conference on
Management of Data, pages 235–247, 2021.

[14]
James C Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher
Frost, Jeffrey John Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher
Heiser, Peter Hochschild, et al.
Spanner: Google’s globally distributed database.
ACM Transactions on Computer Systems (TOCS), 31(3):1–22, 2013.

[15]
George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander
Narwhal and tusk: a dag-based mempool and efficient bft consensus.
In Proceedings of the Seventeenth European Conference on
Computer Systems, pages 34–50, 2022.

[16]
Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer.
Consensus in the presence of partial synchrony.
Journal of the ACM (JACM), 35(2):288–323, 1988.

[17]
Paul Ezhilchelvan, Achour Mostefaoui, and Michel Raynal.
Randomized multivalued consensus.
In Fourth IEEE International Symposium on Object-Oriented
Real-Time Distributed Computing. ISORC 2001, pages 195–200. IEEE, 2001.

[18]
Michael J Fischer, Nancy A Lynch, and Michael S Paterson.
Impossibility of distributed consensus with one faulty process.
Journal of the ACM (JACM), 32(2):374–382, 1985.

[19]
Roy Friedman, Achour Mostefaoui, and Michel Raynal.
Simple and efficient oracle-based consensus protocols for
asynchronous byzantine systems.
IEEE Transactions on Dependable and Secure Computing,
2(1):46–56, 2005.

[20]
Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander
Spiegelman, and Zhuolun Xiang.
Jolteon and ditto: Network-adaptive efficient consensus with
asynchronous fallback.
arXiv preprint arXiv:2106.10362, 2021.

[21]
Protocol buffers.
<https://developers.google.com/protocol-buffers/>, 2020.

[22]
Rachid Guerraoui, Nikola Knezevic, Vivien Quema, and Marko Vukolic.
The next 700 bft protocols.
Proceedings of the 5th European conference on Computer systems,
10:363–376, 2010.

[23]
Patrick Hunt, Mahadev Konar, Flavio P Junqueira, and Benjamin Reed.
Zookeeper: Wait-free coordination for internet-scale systems.
In 2010 USENIX Annual Technical Conference (USENIX ATC 10),

[24]
Marios Kogias and Edouard Bugnion.
Hovercraft: achieving scalability and fault-tolerance for
microsecond-scale datacenter services.
In Proceedings of the Fifteenth European Conference on Computer
Systems, pages 1–17, 2020.

[25]
Klaus Kursawe and Victor Shoup.
Optimistic asynchronous atomic broadcast.
In International Colloquium on Automata, Languages, and
Programming, pages 204–215. Springer, 2005.

[26]
Leslie Lamport.
Generalized consensus and paxos.

[27]
John MacCormick, Nick Murphy, Marc Najork, Chandramohan A Thekkath, and Lidong
Boxwood: Abstractions as the foundation for storage infrastructure.
In OSDI, volume 4, pages 8–8, 2004.

[28]
Parisa Jalili Marandi, Marco Primi, and Fernando Pedone.
Multi-ring paxos.
In IEEE/IFIP International Conference on Dependable Systems and
Networks (DSN 2012), pages 1–12. IEEE, 2012.

[29]
Parisa Jalili Marandi, Marco Primi, Nicolas Schiper, and Fernando Pedone.
Ring paxos: A high-throughput atomic broadcast protocol.
In 2010 IEEE/IFIP International Conference on Dependable Systems
& Networks (DSN), pages 527–536. IEEE, 2010.

[30]
David Mazieres.
Paxos made practical, 2007.

[31]
Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song.
The honey badger of bft protocols.
In Proceedings of the 2016 ACM SIGSAC conference on computer and
communications security, pages 31–42, 2016.

[32]
Iulian Moraru, David G Andersen, and Michael Kaminsky.
There is more consensus in egalitarian parliaments.
In Proceedings of the Twenty-Fourth ACM Symposium on Operating
Systems Principles, pages 358–372, 2013.

[33]
Achour Mostefaoui, Hamouma Moumen, and Michel Raynal.
Signature-free asynchronous byzantine consensus with t< n/3 and o
(n2) messages.
In Proceedings of the 2014 ACM symposium on Principles of
distributed computing, pages 2–9, 2014.

[34]
Stavros Nikolaou and Robbert Van Renesse.
Turtle consensus: Moving target defense for consensus.
In Proceedings of the 16th Annual Middleware Conference, pages
185–196, 2015.

[35]
Stavros Nikolaou and Robbert van Renesse.
Moving participants turtle consensus.
arXiv preprint arXiv:1611.03562, 2016.

[36]
Brian M Oki and Barbara H Liskov.
Viewstamped replication: A new primary copy method to support
highly-available distributed systems.
In Proceedings of the seventh annual ACM Symposium on Principles
of distributed computing, pages 8–17, 1988.

[37]
Diego Ongaro and John Ousterhout.
In search of an understandable consensus algorithm.
In 2014 USENIX Annual Technical Conference USENIX ATC 14),
pages 305–319, 2014.

[38]
Haochen Pan, Jesse Tuglu, Neo Zhou, Tianshu Wang, Yicheng Shen, Xiong Zheng,
Joseph Tassarotti, Lewis Tseng, and Roberto Palmieri.
Rabia: Simplifying state-machine replication through randomization.
In Proceedings of the ACM SIGOPS 28th Symposium on Operating
Systems Principles, pages 472–487, 2021.

[39]
Michael O Rabin.
Randomized byzantine generals.
In 24th annual symposium on foundations of computer science
(sfcs 1983), pages 403–409. IEEE, 1983.

[40]
Michel Raynal.
Fault-tolerant message-passing distributed systems: an
algorithmic approach.
Springer, 2018.

[41]
Sajjad Rizvi, Bernard Wong, and Srinivasan Keshav.
Canopus: A scalable and massively parallel consensus protocol.
In Proceedings of the 13th International Conference on emerging
Networking EXperiments and Technologies, pages 426–438, 2017.

[42]
Bianca Schroeder, Adam Wierman, and Mor Harchol-Balter.
Open versus closed: A cautionary tale.
USENIX, 2006.

[43]
Alexander Spiegelman and Arik Rinberg.
Ace: Abstract consensus encapsulation for liveness boosting of state
machine replication.
arXiv preprint arXiv:1911.10486, 2019.

[44]
Pasindu Tennage, Cristina Basescu, Eleftherios Kokoris Kogias, Ewa Syta,
Philipp Jovanovic, and Bryan Ford.
Baxos: Backing off for robust and efficient consensus.
arXiv preprint arXiv:2204.10934, 2022.

[45]
Sarah Tollman, Seo Jin Park, and John K Ousterhout.
Epaxos revisited.
In NSDI, pages 613–632, 2021.

[46]
Mao Yanhua, Junqueira Flavio P., and Marzullo Keith.
Mencius: building efficient replicated state machines for wans.
In 8th USENIX Symposium on Operating Systems Design and
Implementation (OSDI 08), 2008.

[47]
Jialin Zhang and Wei Chen.
Bounded cost algorithms for multivalued consensus using binary
consensus instances.
Information Processing Letters, 109(17):1005–1009, 2009.

[48]
Hanyu Zhao, Quanlu Zhang, Zhi Yang, Ming Wu, and Yafei Dai.
Sdpaxos: Building efficient semi-decentralized geo-replicated state
In Proceedings of the ACM Symposium on Cloud Computing, pages
68–81, 2018.

§ APPENDIX

§.§ Mandator Formal Proofs

§.§ Sporades Example Execution

§.§ Sporades Formal Proofs