# Derivation of Conservation Laws in 2nd order Quantum-Correlation Theory

Sobhan Sounda and Dibyendu jana  Department of Physics, Presidency University,
Kolkata 700073, India

###### Abstract

This paper extends the foundational concept to second-order quantum
correlation tensors, representing intensity-intensity correlations.As their
application in diverse optical field experiments gaining importance, we
investigate conserved quantities such as energy, linear and angular momentum
and illuminate the dynamic nature of quantum correlations.

##  1 Introduction

Quantum optics explores the fundamental interaction between light and matter,
unveiling the quantum nature of electromagnetic radiation and its interaction
with atoms and other quantum systems. It encompasses the study of phenomena
such as photon absorption, emission, and manipulation, leading to
groundbreaking advancements in fields like quantum information processing and
precision metrology.Untill now,discussions on the statistical properties of
photon beams have predominantly relied on classical or semiclassical
perspectives. While such discussions provide insights, they overlook quantum
phenomena that lack classical counterparts, raising questions of self-
consistency. The classical limit fails to preserve the wave-particle duality,
which is crucial for an accurate treatment of photon statistics. Recognizing
the need for a more coherent theory, we have embarked on a comprehensive
quantum-mechanical approach to address the challenges of photon statistics.

The correlation function serves as a crucial tool for understanding the
coherence properties of photons by quantifying the correlation between
electromagnetic fields at different spacetime points. Wolf’s concept of
optical correlation [1] introduced a unifying framework that proved
instrumental in addressing significant problems within classical statistical
optics.We embark on an exploration of quantum field theoretic quantities,
specifically their relevance to the field of quantum optics and their profound
implications for field measurement. Photon detection and quantum correlation
emerge as indispensable factors in the measurement of electromagnetic fields
in optics. By harnessing the photoelectric effect, which involves the
absorption of photons, the detection process becomes possible. Moreover,
quantum correlation plays a pivotal role in elucidating the intricate
interrelationships and connections between individual photons, enabling a
comprehensive understanding of their behavior in complex optical systems.

This study delves into various practical applications of the theoretical
framework. For instance, we delve into the first-order quantum correlation
function (QCF), which finds its significance in Young’s double-slit
interference experiment [2]. By analyzing the correlation between the fields
from the two slits, we gain valuable insights into the interference phenomena
and the wave-particle duality inherent in the behavior of light. Another
pivotal contribution to the field comes from the groundbreaking work of
Hanbury Brown and Twiss in 1956, who reported the correlated arrival of photon
pairs in a narrow-spectral-width light beam. This phenomenon, now known as the
Hanbury Brown and Twiss effect [3], provides key insights into the statistical
properties of light and has far-reaching implications in areas such as quantum
optics and quantum information processing.

1963 was the revolutionary year for optics when photon correlation was
described by Glauber’s quantum theory of optical coherence [4] [5] [6] by
employing the principles of quantum electrodynamics. Using this elegant
theory, we gain deeper insights into the distribution of the number of photons
in an incoherent beam and unravel the intricate coherence properties of light.

In the classical description of light, Maxwell’s four equations captured its
behavior, involving the electric and magnetic fields through two divergence
equations and two curl equations. These dynamical equations governed the
propagation of the optical field, dictating its evolution with time. However,
a more comprehensive understanding of light propagation emerged when
considering classical correlation functions, which offered a broader
perspective on the dynamics of light. In the quantum realm, correlation
functions also played a vital role and remained consistent with Maxwell’s
equations. The quantized fields, being subject to quantum mechanics, exhibited
their own dynamic behavior over time. This connection between quantum
correlation dynamics and the evolving nature of the fields was an intriguing
aspect to explore. In the study of any dynamical system, physicists naturally
sought conserved quantities, such as energy, momentum, and angular momentum,
as they provided valuable insights into the system’s behavior. Remarkably, M.
Takeda and Wang [7] contributed to this area of research by investigating
quantum correlation tensors, namely $E_{jk}$ and $S_{jk}$, which encompassed
mixed correlation terms involving both electric and magnetic fields. Their
significant work revealed that these tensors followed conservation laws,
highlighting the importance of these quantities in understanding the
underlying dynamics of quantum correlations.

Building upon this foundation, this paper aims to extend the concept to
second-order correlation tensors, namely $E_{jklm}$ and $S_{jklm}$ which are
nothing but the intensity intensity correlation. By considering their
applicability in various optical field experiments, we can explore their
conservation properties and delve deeper into the dynamic nature of quantum
correlations.This newly developed framework offers a comprehensive approach to
understanding the dynamics of quantum correlations in optical systems, opening
up avenues for further exploration and theoretical advancements.

##  2 2nd Order Quantum Coherence Tensor

Theory will be complete when we take the electric field as well as magnetic
field.In 1963, Roy Glauber first encounter photon with full quantum mechanical
treatment and came up with 1st order quantum correlation function,consisting
$\hat{E}^{+},\hat{E}^{-}$ field only.After one year, Mehta and Wolf [8]
jointly published a paper on black-body radiation where he first introduced
mixed correlation terms.Now we are defining 2nd order correlations which can
also be termed as intensity-intensity correlation.We would like to study their
conserved quantities just like Takeda and Wang did for 1st order correlation
tenors,

$\displaystyle
E_{jklm}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=\operatorname{Tr}\left\\{\hat{\rho}\hat{\mathbf{E}}_{j}^{(-)}\left(\mathbf{x}_{1};\mathbf{t}_{1}\right)\hat{\mathbf{E}}_{k}^{(-)}\left(\mathbf{x}_{2};\mathbf{t}_{2}\right)\mathbf{E}_{l}^{(+)}\left(\mathbf{x}_{3};\mathbf{t}_{3}\right)\hat{\mathbf{E}}_{m}^{(+)}\left(\mathbf{x}_{4};\mathbf{t}_{4}\right)\right\\},$
(1) $\displaystyle
H_{jklm}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=\operatorname{Tr}\left\\{\hat{\rho}\hat{\mathbf{B}}_{j}^{(-)}\left(\mathbf{x}_{1};\mathbf{t}_{1}\right)\hat{\mathbf{B}}_{k}^{(-)}\left(\mathbf{x}_{2};\mathbf{t}_{2}\right)\mathbf{B}_{l}^{(+)}\left(\mathbf{x}_{3};\mathbf{t}_{3}\right)\hat{\mathbf{B}}_{m}^{(+)}\left(\mathbf{x}_{4};\mathbf{t}_{4}\right)\right\\},$
$\displaystyle
M_{jklm}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=\operatorname{Tr}\left\\{\hat{\rho}\hat{\mathbf{E}}_{j}^{(-)}\left(\mathbf{x}_{1};\mathbf{t}_{1}\right)\hat{\mathbf{E}}_{k}^{(-)}\left(\mathbf{x}_{2};\mathbf{t}_{2}\right)\mathbf{B}_{l}^{(+)}\left(\mathbf{x}_{3};\mathbf{t}_{3}\right)\hat{\mathbf{B}}_{m}^{(+)}\left(\mathbf{x}_{4};\mathbf{t}_{4}\right)\right\\}$
$\displaystyle
N_{jklm}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=\operatorname{Tr}\left\\{\hat{\rho}\hat{\mathbf{B}}_{j}^{(-)}\left(\mathbf{x}_{1};\mathbf{t}_{1}\right)\hat{\mathbf{B}}_{k}^{(-)}\left(\mathbf{x}_{2};\mathbf{t}_{2}\right)\mathbf{E}_{l}^{(+)}\left(\mathbf{x}_{3};\mathbf{t}_{3}\right)\hat{\mathbf{E}}_{m}^{(+)}\left(\mathbf{x}_{4};\mathbf{t}_{4}\right)\right\\},$

where $\hat{\rho}$ is the density operator describing the state of the
field,$\operatorname{Tr}$ the symbol stands for the trace operation, the
indices $(jklm=1,2,3)$ label Cartesian components:$\hat{x},\hat{y},\hat{z}$
,using this notation
$\left(\mathbf{x}_{i};\mathbf{t}_{i}\right)=\left(\mathbf{r}_{i}\right)$ and
from the knowledge of quantization of electromagnetic field,we have separated
the electromagnetic field operators into their positive-frequency parts
$\hat{E}^{+}$ and $\hat{B}^{+}$ and their negative-frequency parts
$\hat{E}^{-}$ and $\hat{B}^{-}$, respectively.
In contrast with classical electrodynamics where $E$ and $B$ field follows the
maxwells equation, here negative-frequency parts of quantized $\hat{E}^{-}$
and $\hat{B}^{-}$ also be expressed in the tensor form as,

$\varepsilon_{jkl}\partial_{k}\widehat{\mathbf{E}}_{l}^{(-)}\left(\mathbf{r}_{1}\right)+\frac{1}{c}\frac{\partial}{\partial
t}\widehat{\mathbf{B}}_{j}^{(-)}\left(\mathbf{r}_{1}\right)=0$ (2)
$\varepsilon_{jkl}\partial_{k}\widehat{\mathbf{B}}_{l}^{(-)}\left(\mathbf{r}_{1}\right)-\frac{1}{c}\frac{\partial}{\partial
t}\widehat{\mathbf{E}}_{j}^{(-)}\left(\mathbf{r}_{1}\right)=0$ (3)
$\partial_{j}\widehat{\mathbf{E}}_{j}^{(-)}\left(\mathbf{r}_{1}\right)=0$ (4)
$\partial_{j}\widehat{\mathbf{B}}_{j}^{(-)}\left(\mathbf{r}_{1}\right)=0$ (5)

where $c$ denotes the speed of light, $\varepsilon_{jkl}$ is the anti
symmetric tensor Levi-Civita , $\partial_{j}$ and $\partial/\partial t$ are
the differential operator,and Einstein’s summation convention has been
employed. One of the essential aspects in which quantum field theory differs
from classical theory is that two values of the field operators taken at
different space-time points do not, in general, commute with one another.
After multiplying both sides of (2) by
$\widehat{\mathbf{E}}_{m}^{(+)}\left(\mathbf{r}_{2}\right)\widehat{\mathbf{E}}_{n}^{(+)}\left(\mathbf{r}_{3}\right)\widehat{\mathbf{E}}_{0}^{(+)}\left(\mathbf{r}_{4}\right)$
and writing it by maintaining normal ordering.

$\varepsilon_{jkl}\partial_{k}\widehat{\mathbf{E}}_{l}^{(+)}\left(\mathbf{r}_{1}\right)\widehat{\mathbf{E}}_{m}^{(+)}\left(\mathbf{r}_{2}\right)\widehat{\mathbf{E}}_{n}^{(+)}\left(\mathbf{r}_{3}\right)\widehat{\mathbf{E}}_{0}^{(+)}\left(\mathbf{r}_{4}\right)+\frac{1}{c}\frac{\partial}{\partial
t}\hat{\mathbf{B}}_{j}^{(-)}\left(\mathbf{r}_{1}\right)\widehat{\mathbf{E}}_{m}^{(+)}\left(\mathbf{r}_{2}\right)\widehat{\mathbf{E}}_{n}^{(+)}\left(\mathbf{r}_{3}\right)\widehat{\mathbf{E}}_{0}^{(+)}\left(\mathbf{r}_{4}\right)=0$
(6)

If we take the quantum average of (6) and interchange the order of the quantum
average and differential operator, from the definition of coherence tensor in
(1), we have

$\varepsilon_{jkl}\partial_{k}E_{lmno}+\frac{1}{c}\frac{\partial}{\partial
t}N_{jmno}=0$ (7)

If we apply the same procedure, we obtain

$\varepsilon_{jkl}\partial_{k}M_{lmno}+\frac{1}{c}\frac{\partial}{\partial
t}H_{jmno}=0,$ (8)
$\varepsilon_{jkl}\partial_{k}N_{lmno}-\frac{1}{c}\frac{\partial}{\partial
t}E_{jmno}=0,$ (9)
$\varepsilon_{jkl}\partial_{k}H_{lmno}-\frac{1}{c}\frac{\partial}{\partial
t}M_{jmno}=0$ (10)

In a similar manner, the divergence condition yields the following equations:

$\partial_{j}E_{jmno}=0$ (11) $\partial_{j}H_{jmno}=0$ (12)
$\partial_{j}M_{jmno}=0$ (13) $\partial_{j}N_{jmno}=0$ (14)

After adding (7) to (10), and subtracting (9) from (8), we obtain two
equations, respectively:

$\varepsilon_{jkl}\partial_{k}\mathbb{E}_{lmno}-\frac{1}{c}\frac{\partial}{\partial
t}\mathbb{S}_{jmno}=0$ (15)
$\varepsilon_{jkl}\partial_{k}\mathbb{S}_{lmno}+\frac{1}{c}\frac{\partial}{\partial
t}\mathbb{E}_{jmno}=0$ (16)

Moreover, from (11) and (12), or from (13) and (14), one has

$\partial_{j}\mathbb{E}_{jmno}=0$ (17) $\partial_{j}\mathbb{S}_{jmno}=0$ (18)

where,

$\displaystyle\mathbb{E}_{jmno}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)$
$\displaystyle=E_{jmno}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)+H_{jmno}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)$
$\displaystyle=\operatorname{Tr}\left\\{\hat{\rho}\left[\hat{\mathbf{E}}_{j}^{(-)}\left(\mathbf{r}_{1}\right)\hat{\mathbf{E}}_{m}^{(-)}\left(\mathbf{r}_{2}\right)\hat{\mathbf{E}}_{n}^{(+)}\left(\mathbf{r}_{3}\right)\hat{\mathbf{E}}_{o}^{(+)}\left(\mathbf{r}_{4}\right)+\hat{\mathbf{B}}_{j}^{(-)}\left(\mathbf{r}_{1}\right)\hat{\mathbf{B}}_{m}^{(-)}\left(\mathbf{r}_{2}\right)\hat{\mathbf{B}}_{n}^{(+)}\left(\mathbf{r}_{3}\right)\hat{\mathbf{B}}_{o}^{(+)}\left(\mathbf{r}_{4}\right)\right]\right\\}$
$\displaystyle\mathbb{S}_{jmno}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)$
$\displaystyle=M_{jmno}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)-N_{jmno}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)$
$\displaystyle=\operatorname{Tr}\left\\{\hat{\rho}\left[\hat{\mathbf{E}}_{j}^{(-)}\left(\mathbf{r}_{1}\right)\hat{\mathbf{E}}_{m}^{(-)}\left(\mathbf{r}_{2}\right)\hat{\mathbf{B}}_{n}^{(+)}\left(\mathbf{r}_{3}\right)\hat{\mathbf{B}}_{o}^{(+)}\left(\mathbf{r}_{4}\right)-\hat{\mathbf{B}}_{j}^{(-)}\left(\mathbf{r}_{1}\right)\hat{\mathbf{B}}_{m}^{(-)}\left(\mathbf{r}_{2}\right)\hat{\mathbf{E}}_{n}^{(+)}\left(\mathbf{r}_{3}\right)\hat{\mathbf{E}}_{o}^{(+)}\left(\mathbf{r}_{4}\right)\right]\right\\}$

The tensor $\mathbb{E}_{jmno}$ and $\mathbb{S}_{jmno}$ may be called the 2nd
order version of quantum energy coherence tensor and the quantum energy-flow
coherence tensor, which does not have formal resemblance to those of the
classical theory of electrodynamics where total energy of the electromagnetic
field is $(E^{2}+B^{2})$ but for the 1st order correlation tensors it takes
the same shape $(EE^{*}+BB^{*})$.

##  3 Conservation laws

###  3.1 Energy

Drawing inspiration from the resemblance to Maxwell’s equations in free space,
we can introduce essential concepts that help us to understand how the energy
coherence tensor and the energy-flow coherence tensor evolve over space and
time. This approach allows us to gain valuable insights into their dynamics
and significance within our research context.Let us now take the complex
conjugate of eq-(15) and multiply by $\mathbb{S}_{jmno}$. We then obtain

$\varepsilon_{jkl}\mathbb{S}_{jmno}\partial_{k}\mathbb{E}_{lmno}^{*}-\frac{1}{c}\mathbb{S}_{jmno}\frac{\partial}{\partial
t}\mathbb{S}_{jmno}^{*}=0.$ (19)

Now, we add eq-(19) with its complex conjugate, we have

$\frac{1}{c}\frac{\partial}{\partial
t}\left(\mathbb{S}_{jmno}^{*}\mathbb{S}_{jmno}\right)-\varepsilon_{jkl}\left(\mathbb{S}_{jmno}^{*}\partial_{k}\mathbb{E}_{lmno}+\mathbb{S}_{jmno}\partial_{k}\mathbb{E}_{lmno}^{*}\right)=0.$
(20)

If we make use of relation $\varepsilon_{jkl}=-\varepsilon_{lkj}$ and
interchange the dummy suffices $j$ and $l$, we have

$\frac{1}{c}\frac{\partial}{\partial
t}\left(\mathbb{S}_{jmno}^{*}\mathbb{S}_{jmno}\right)+\varepsilon_{jkl}\left(\mathbb{S}_{lmno}^{*}\partial_{k}\mathbb{E}_{jmno}+\mathbb{S}_{lmno}\partial_{k}\mathbb{E}_{jmno}^{*}\right)=0.$
(21)

In a similar way, we obtain from eq-(16),multiply by $\mathbb{E}_{jmno}$ and
ending up with this,

$\frac{1}{c}\frac{\partial}{\partial
t}\left(\mathbb{E}_{jmno}^{*}\mathbb{E}_{jmno}\right)+\varepsilon_{jkl}\left(\mathbb{E}_{jmno}^{*}\partial_{k}\mathbb{S}_{lmno}+\mathbb{E}_{jmno}\partial_{k}\mathbb{S}_{lmno}^{*}\right)=0$
(22)

After simply adding eq-(21) and (23) we get back,

$\frac{\partial}{\partial
t}\mathbf{W}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)+\partial_{k}\mathbf{T}_{k}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=0$
(23)

where,
2nd order version of quantum-correlation-function energy density :

$\mathbf{W}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=\mathbb{E}_{jmno}^{*}\mathbb{E}_{jmno}+\mathbb{S}_{jmno}^{*}\mathbb{S}_{jmno}$

and,
2nd order version of quantum-correlation-function flow density :

$\mathbf{T}_{\mathrm{k}}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=c\varepsilon_{klj}\left(\mathbb{S}_{lmno}\mathbb{E}_{jmno}^{*}+\mathbb{S}_{lmno}^{*}\mathbb{E}_{jmno}\right)$

Based on its formal analogy to the energy conservation law in
electromagnetism, equation (23) can be interpreted as a continuity equation.
In this equation, the scalar quantity $\mathbf{W}$ represents a quantum-
correlation-function energy density, while the vector quantity
$\mathbf{T}_{k}$ represents a quantum-correlation-function flow density.

Analogous to how the magnitude and direction of the Poynting vector in classic
optics represent the field intensity and direction of light energy flow,
respectively, the magnitude and direction of the quantum-correlation-function
flow density vector $\mathbf{T}$ provide insights into the intensity and
direction of quantum correlation flow.

By integrating equation (23) over a volume $V$ bounded by a closed surface $S$
and applying Gauss’ theorem, further insights and implications can be derived.

$\frac{\partial}{\partial
t}\iiint_{V}\mathbf{W}_{i}(r_{1};r_{2};r_{3};r_{4})\,dV+\iint_{S}\mathbf{T}_{k}(r_{1};r_{2};r_{3};r_{4})\cdot\mathbf{n}\,dS=0$
(24)

where n denotes the unit outward normal to S.Equation (24) can be interpreted
as follows: The change in quantum-correlation-function energy within the
volume $V$ is equal to the rate at which quantum-correlation-function energy
flows into or out of $V$ through the boundary $S$ via the quantum-correlation-
function flow. With this understanding, equation (24) represents the
conservation law for quantum-correlation-function energy, which can be seen as
a natural extension of those derived from classical scalar coherence theory.

###  3.2 Linear Momentum

Next, let us examine a novel law governing the conservation of a momentum-like
quantity within the realm of 2nd order quantum correlation theory.Take the
complex conjugate of eq-(15) and multiply by
$\varepsilon_{ipj}\mathbb{E}_{pmno}$ and make use of tensor identity
$\varepsilon_{jkl}\varepsilon_{ipj}=\varepsilon_{klj}\varepsilon_{ipj}=$
$\delta_{ki}\delta_{lp}-\delta_{kp}\delta_{li}$

$-\mathbb{E}_{pmno}\partial_{i}\mathbb{E}_{pmno}^{*}+\mathbb{E}_{pmno}\partial_{p}\mathbb{E}_{imno}^{*}+\mathbb{E}_{imno}^{*}\partial_{p}\mathbb{E}_{pmno}+\frac{1}{c}\varepsilon_{ipj}\mathbb{E}_{pmno}\frac{\partial}{\partial
t}\mathbb{S}_{jmno}^{*}=0,$ (25)

lets take cc to eq-(16),multiplying with $\varepsilon_{ipj}\mathbb{S}_{pmno}$
,

$-\mathbb{S}_{pmno}\partial_{i}\mathbb{S}_{pmno}^{*}+\mathbb{S}_{pmno}\partial_{p}\mathbb{S}_{imno}^{*}+\mathbb{S}_{imno}^{*}\partial_{p}\mathbb{E}_{pmno}+\frac{1}{c}\varepsilon_{ipj}\mathbb{S}_{pmno}\frac{\partial}{\partial
t}\mathbb{E}_{jmno}^{*}=0,$ (26)

now add these 4 equations eq-(24)
,$eq-\left(24\right)^{*}$,eq-(25),$eq-\left(25\right)^{*}$

finally,

$\frac{\partial}{\partial
t}\mathbb{T}_{i}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)+\partial_{p}W_{pi}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=0$
(27)

where,
quantum-correlation-function momentum density :

$\mathbb{T}_{i}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=\frac{1}{c}\varepsilon_{ipj}\left(\mathbb{S}_{pmno}\mathbb{E}_{jmno}^{*}+\mathbb{S}_{pmno}^{*}\mathbb{E}_{jmno}\right)$

and the Quantum Coherence Energy density $\mathbb{W}_{pi}$,

$\displaystyle\mathbb{W}_{pi}=$
$\displaystyle\left(\mathbb{E}_{pmno}\mathbb{E}_{imno}^{*}+\mathbb{E}_{pmno}^{*}\mathbb{E}_{imno}\right)-\delta_{pi}\left(\mathbb{E}_{pmno}\mathbb{E}_{pmno}^{*}\right)$
$\displaystyle+\left(\mathbb{S}_{pmno}\mathbb{S}_{imno}^{*}+\mathbb{S}_{pmno}^{*}\mathbb{S}_{imno}\right)-\delta_{pi}\left(\mathbb{S}_{pmno}\mathbb{S}_{pmno}^{*}\right).$

If we integrate (27) throughout the volume V bounded by a closed surface S and
apply Gauss’ theorem in the tensor form, we have

$\frac{\partial}{\partial
t}\iiint_{V}\mathbb{T}_{i}(r_{1};r_{2};r_{3};r_{4})\,dV+\iint_{S}\mathbb{W}_{pi}(r_{1};r_{2};r_{3};r_{4})\cdot\mathbf{n}_{k}\,dS=0$
(28)

In analogy with momentum conservation law in electromagnetism, we interpret
the vector $\mathbf{T}(r_{1};r_{2};r_{3};r_{4})$ as a momentum-density-like
quantity of quantum correlation, termed as the quantum-correlation-function
momentum density. Additionally, the symmetric tensor
$W_{ki}(r_{1};r_{2};r_{3};r_{4})$ can be seen as a quantum-correlation-
function stress tensor, resembling the Maxwell-stress-tensor. This tensor
represents the flux of the $k$th component of quantum-correlation-function
momentum in the $i$th direction.

Hence, the equation indicates that the rate of gain or loss of quantum-
correlation-function momentum within a closed volume is equal to the flux of
quantum-correlation-function momentum flowing into or out of the volume across
its bounding surface. This interpretation establishes the conservation law of
quantum-correlation-function momentum, which shares a remarkable resemblance
with the classical counterpart [9].

###  3.3 Angular Momentum

In classical electrodynamics [10],angular momentum is written like
$\mathbf{x}\times(\mathbf{E}\times\mathbf{B})$.if we write B in terms of
vector potential and then perform the vector curl identity we will find out
that angular momentum can be further decomposed into two parts,coordinate-
independent term which is called spin angular momentum and another one is
depended on choice of coordinate,named as orbital angular momentum.The
presence of spin angular momentum is due to the transverse vector nature of
the electromagnetic field.so lets first define vector potential in the context
of Quantum coherence tensor ,

$\mathbb{E}_{jmno}\left(\mathbf{r}_{1};\mathbf{r}_{2}\right)=\varepsilon_{jtl}\partial_{t}\mathbb{A}_{lmno}\left(\mathbf{r}_{1};\mathbf{r}_{2}\right)$
(29)

lets put this tensor potential(29) into momentum $T_{i}$ and rewriting whole
equation in terms of $S_{pmno}$ and $A_{lmno}$,

$\begin{split}\mathbb{T}_{i}&=c^{-1}\varepsilon_{ipj}\left(\mathrm{~{}S}_{pmno}\mathbb{E}_{jmno}^{*}+\mathrm{S}_{pmno}^{*}\mathbb{E}_{jmno}\right)\\\
&=c^{-1}\varepsilon_{ipj}\left[\mathrm{~{}S}_{pmno}\left(\varepsilon_{jtl}\partial_{t}\mathrm{~{}A}_{lmno}\right)^{*}+\mathrm{S}_{pmno}^{*}\left(\varepsilon_{jtl}\partial_{t}\mathrm{~{}A}_{lmno}\right)\right]\end{split}$
(30)

Making use of tensor identity
$\varepsilon_{ipj}\varepsilon_{jtl}=\varepsilon_{ipj}\varepsilon_{tlj}=\delta_{it}\delta_{pl}$
$-\delta_{il}\delta_{pt}$ (where $\delta_{it}$ is equal to $0$ if $i\neq t$
and equal to unity if $i=t$ ), then manipulate using divergence free term.At
the end the equation becomes,

$\displaystyle\mathbb{T}_{i}$
$\displaystyle=\frac{1}{c}\left(\mathbb{S}_{lmno}\partial_{i}\mathbb{A}_{lmno}^{*}+\mathbb{S}_{lmno}^{*}\partial_{i}\mathbb{A}_{lmno}-\mathbb{S}_{tmno}^{*}\partial_{t}\mathbb{A}_{imno}-\mathbb{S}_{tmno}\partial_{t}\mathbb{A}_{imno}^{*}\right)$
(31)
$\displaystyle=\frac{1}{c}\left(\mathbb{S}_{lmno}\partial_{i}\mathbb{A}_{lmno}^{*}+\mathbb{S}_{lmno}^{*}\partial_{i}\mathbb{A}_{lmno}-\partial_{t}\left(\mathbb{S}_{tmno}^{*}\mathbb{A}_{imno}+\mathbb{S}_{tmno}\mathbb{A}_{imno}^{*}\right)\right)$

$\mathbb{T}_{i}$ is written in terms of cross product between tensor-potential
and the eclectic field like quantity,energy-flow-coherence-tensor.

$\displaystyle\mathbb{L}_{p}\left(\mathbf{r}_{1},\mathbf{r}_{2}\right)$
$\displaystyle\equiv\left(r_{1}-r_{0}\right)\times\mathbb{T}\left(\mathbf{r}_{1},\mathbf{r}_{2}\right)$
(32)
$\displaystyle=\varepsilon_{pji}\left(r_{1j}-r_{0j}\right)\mathbb{T}_{i}\left(\mathbf{r}_{1},\mathbf{r}_{2}\right)$

Now it is ready to cook for making coherence angular momentum $\mathbb{L}_{p}$
via putting the expression of $\mathbb{T}_{i}$,we got from eq(30) into
eq(31).Final expression is ,

$\begin{split}\mathbb{L}_{p}=&c^{-1}\varepsilon_{nji}\left(r_{1j}-r_{0j}\right)\left[\mathrm{S}_{km}\partial_{i}^{1}\mathrm{A}_{km}^{*}+\mathrm{S}_{km}^{*}\partial_{i}^{1}\mathrm{A}_{km}\right]\\\
=&c^{-1}\varepsilon_{pji}\left(r_{1j}-r_{0j}\right)\left(\mathbb{S}_{lmno}\partial_{i}\mathbb{A}_{lmno}^{*}+\mathbb{S}_{lmno}^{*}\partial_{i}\mathbb{A}_{lmno}\right)\\\
&-c^{-1}\varepsilon_{pji}\partial_{t}\left[\left(r_{1j}-r_{0j}\right)\left(\mathbb{S}_{tmno}\mathbb{A}_{imno}^{*}+\mathbb{S}_{tmno}^{*}\mathbb{A}_{imno}\right)\right]\\\
&+c^{-1}\varepsilon_{pji}\left[\partial_{t}\left(r_{1j}-r_{0j}\right)\right]\left(\mathbb{S}_{tmno}\mathbb{A}_{imno}^{*}+\mathbb{S}_{tmno}^{*}\mathbb{A}_{imno}\right).\end{split}$
(33)

Now $\partial_{t}\left(r_{1j}-r_{0j}\right)=\delta_{tj}$, so that we obtain,

$\begin{split}\mathbb{L}_{p}=&c^{-1}\mathbb{S}_{lmno}\left[\left(r_{1}-r_{0}\right)\times\nabla\right]_{p}\mathbb{A}_{lmno}^{*}+c^{-1}\mathbb{S}_{lmno}^{*}\left[\left(r_{1}-r_{0}\right)\times\nabla\right]_{p}\mathbb{A}_{lmno}\\\
&-c^{-1}\partial_{t}\left\\{\mathbb{S}_{tmno}\left[\left(r_{1}-r_{0}\right)\times\mathbb{A}_{imno}^{*}\right]+\mathbb{S}_{tmno}^{*}\left[\left(r_{1}-r_{0}\right)\times\mathbb{A}_{imno}\right]\right\\}\\\
&+c^{-1}\varepsilon_{pti}\left(\mathbb{S}_{tmno}\mathbb{A}_{imno}^{*}+\mathbb{S}_{tmno}^{*}\mathbb{A}_{imno}\right)\end{split}$
(34)

taking volume integral in the both side of eq(34) and discarding surface term
and arrived with orbital angular momentum part and the intrinsic part which is
independent of choice of coordinate,termed as spin angular momentum.

$\mathcal{L}_{p}=\left(\mathcal{L}_{p}\right)^{o}+\left(\mathcal{L}_{p}\right)^{s}$
(35)

where,

$\displaystyle\left(\mathcal{L}_{p}\right)^{o}=c^{-1}\iiint_{v}\left[\mathbb{S}_{lmno}\left[\left(r_{1}-r_{0}\right)\times\nabla\right]_{p}\mathbb{A}_{lmno}^{*}+\mathbb{S}_{lmno}^{*}\left[\left(r_{1}-r_{0}\right)\times\nabla\right]_{p}\mathbb{A}_{lmno}\right]dv$
$\displaystyle\left(\mathcal{L}_{p}\right)^{s}=c^{-1}\iiint_{v}\left[\varepsilon_{pti}\left(\mathbb{S}_{tmno}\mathbb{A}_{imno}^{*}+\mathbb{S}_{tmno}^{*}\mathbb{A}_{imno}\right)\right]\,dv$

similarly we can say

$\mathbb{M}_{pk}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=\varepsilon_{pji}x_{j}\mathbb{W}_{ik}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)$

where $W_{ik}$ is the quantum-correlation-function stress tensor which is
symmetric as well,given above (26).Now to make it compatible ,integrating over
volume give rise to $\mathcal{M}_{pk}$. Conservation of angular momentum in
quantum correlation function is also expressed by

$\frac{\partial}{\partial
t}\mathcal{L}_{p}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)+\partial_{k}\mathcal{M}_{pk}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)=0,$
(36)

which again bears the close analogy to the classical theories of coherence
[9].The first term of Eq. (36) represents the time rate of increase (or
decrease) of the p component of angular coherence momentum $\mathcal{L}$
within the volume $V$, while the second term
$\mathcal{M}_{pk}\left(\mathbf{r}_{1};\mathbf{r}_{2};\mathbf{r}_{3};\mathbf{r}_{4}\right)$
denotes the p component of coherence angular momentum flow density into volume
$V$ across the surface $S$. Therefore, Eqs. (28) and (36) express the
conservation law of linear coherence momentum and angular coherence momentum.

In summary, this research marks the first known derivation of linear and
angular coherence momentum expressions for the second-order coherence theory
of classical electromagnetic fields. Through a classical electrodynamics
model, we have introduced novel density quantities based on energy and energy-
flow coherence tensors, interlinked by continuity equations that reveal fresh
conservation principles within the coherence domain.

Moreover, gaining insights into coherence flow dynamics through fully
vectorial electromagnetic field correlation introduces intriguing
possibilities for statistical optics. It paves the way for a new field that
could be termed as classical coherence dynamics, offering exciting prospects
for future investigations in this realm.

##  4 Conclusion

In conclusion, our research has successfully derived energy coherence and
energy-flow coherence tensors using advanced quantum field theory techniques
beyond first order. These tensors offer valuable insights into photon
statistics and quantum correlations at four different space-time points.
Additionally, we have introduced new quantities to the quantum theory of
optical coherence, linking them through continuity equations. This process has
led to the discovery of new conservation laws governing quantum correlation
functions.

Furthermore, our work aims to generalize this theory to nth order, ensuring
mathematical consistency through tensor index manipulation. This
generalization involves taking nth degrees of freedom, represented by (j k l m
…….n) indices, while preserving the conservation laws. Different ordered
theories can be interpreted through various experiments or physical
explanations.

The significance of this research paper illuminates the dynamic attributes of
quantized fields. In any dynamic process, essential conservation laws such as
momentum, energy, and angular momentum can be computed. When considering the
photon, a quantum particle, Quantum Electrodynamics (QED) advances the photon
theory by introducing the notions of creation and annihilation. The
development of correlation functions using quantized fields, represented by
$\hat{E}$ and $\hat{B}$, has paved the way for understanding various optical
field experiments. Now, our focus shifts to inquiries concerning the
conservation laws governing the dynamics characterized by correlation tensors.

## References

  * [1] L. Mandel and E. Wolf.  Optical Coherence and Quantum Optics.  EBL-Schweitzer. Cambridge University Press, 1995.
  * [2] DF Walls.  A simple field theoretic description of photon interference.  American Journal of Physics, 45(10):952–956, 1977.
  * [3] R. Q. Twiss R. Hanbury Brown.  The intensity interferometer, phi1. mag. 1 § , 663 (l954).  Nature l1, 1046, 1956.
  * [4] Roy J. Glauber.  The quantum theory of optical coherence.  Phys. Rev., 130:2529–2539, Jun 1963.
  * [5] Roy J. Glauber.  Coherent and incoherent states of the radiation field.  Phys. Rev., 131:2766–2788, Sep 1963.
  * [6] Roy J. Glauber.  Photon correlations.  Phys. Rev. Lett., 10:84–86, Feb 1963.
  * [7] Wei Wang and Mitsuo Takeda.  Conservation laws in quantum-correlation-function dynamics.  Advances in Optical Technologies, 2010:171254, Jun 2010.
  * [8] C. L. Mehta and E. Wolf.  Coherence properties of blackbody radiation. ii. correlation tensors of the quantized field.  Phys. Rev., 134:A1149–A1153, Jun 1964.
  * [9] Wei Wang and Mitsuo Takeda.  Linear and angular coherence momenta in the classical second-order coherence theory of vector electromagnetic fields.  Opt. Lett., 31(17):2520–2522, September 2006.
  * [10] J.D. Jackson.  Classical Electrodynamics.  Wiley, 1998.


11institutetext:  ITMO University, _Addr:_ 49, Kronverksky ave, Saint-
Petersburg, Russia, 197101; _Email:_<EMAIL_ADDRESS>_Phone:_
+79516623399 22institutetext: Ben-Gurion University, _Addr_ : P.O.B. 653 Beer-
Sheva, Israel, 8410501; _Email:_<EMAIL_ADDRESS>_Phone:_ +97286461600
33institutetext: Ben-Gurion University, _Addr_ : P.O.B. 653 Beer-Sheva,
Israel, 8410501; _Email:_<EMAIL_ADDRESS>_Phone:_ +97286461600
44institutetext: ITMO University, _Addr:_ 49, Kronverksky ave, Saint-
Petersburg, Russia, 197101; _Email:_<EMAIL_ADDRESS>_Phone:_
+79811639149 55institutetext: Ben-Gurion University, _Addr_ : P.O.B. 653 Beer-
Sheva, Israel, 8410501; _Email:_<EMAIL_ADDRESS>_Phone:_ +97286461600

# Execution of NVRAM Programs with Persistent Stack

Vitaly Aksenov 11 Ohad Ben-Baruch 22 Danny Hendler 33 Ilya Kokorin 44 Matan
Rusanovsky 55

###### Abstract

Non-Volatile Random Access Memory (NVRAM) is a novel type of hardware that
combines the benefits of traditional persistent memory (persistency of data
over hardware failures) and DRAM (fast random access). In this work, we
describe an algorithm that can be used to execute NVRAM programs and recover
the system after a hardware failure while taking the architecture of real-
world NVRAM systems into account. Moreover, the algorithm can be used to
execute NVRAM-destined programs on commodity persistent hardware, such as hard
drives. That allows us to test NVRAM algorithms using only cheap hardware,
without having access to the NVRAM. We report the usage of our algorithm to
implement and test NVRAM CAS algorithm.

###### Keywords:

Concurrency Shared memory Persistency NVRAM.

##  1 Introduction

For a long time the industry assumed the existence of two distinct types of
the memory. The first one is a persistent memory that preserves its content
even in the presence of hardware (e.g., power) failures. This type of memory
was assumed to support mainly sequential block access with the poor
performance of random access. Due to its ability to persist data this kind of
memory is widely used to recover the system after a hardware failure: one can
load the data from the persistent memory and restore the state of the
application before the crash. The second type of the memory is DRAM that
supports fast random byte-addressable access but loses its content on hardware
failures. Due to its speed, this kind of memory is widely used in high-
performance computations.

Nowadays, we can get benefits from both of these worlds due to the invention
of Non-Volatile Random Access Memory (NVRAM)—a novel type of hardware that
combines both the persistency and the fast random access. This allows us to
implement low-latency persistent data structures that require random access to
the memory, e.g., binary search trees, linked lists, and etc. A lot of work
has been done to come up with data structures, hand-tuned for the NVRAM [16,
15, 18]. Some authors propose techniques, that can be used to transform DRAM-
resident data structures into the ones suitable for the NVRAM [14, 17].

Despite the speed of the NVRAM is compatible with the speed of the DRAM, the
NVRAM is not expected to replace volatile memory totally since processor
registers and the NVRAM cache are expected to remain volatile. Thus, even on
NVRAM systems, a system failure leads to: 1) the loss of the results of recent
computations since x86 computations are performed using volatile processor
registers, and 2) the loss of data that was written to the NVRAM cache and has
not been flushed to the NVRAM.

To make sure that the written data becomes persistent, we should flush one or
several cache lines to the NVRAM. Flush of a single cache line is an atomic
action: if a crash occurs during cache line flushing, the whole cache line is
either persisted or not. However, if we want to flush multiple cache lines at
a time, a crash event can occur between flushes — in such a case, only a part
of the data becomes persistent while the rest is lost.

This yields one of the major challenges of NVRAM. If a system failure happens
during a complex update, when some updated values have been flushed to the
NVRAM from the cache while others still reside in the cache, non-flushed
memory is lost and after the restart the NVRAM appears to be in an
inconsistent state.

Due to the difficulty of ensuring storage consistency in the presence of the
volatile NVRAM cache, a lot of works assume the absence of such cache [8, 9,
10, 12]. However, in this work we consider real-life systems, thus we take the
volatility of the NVRAM cache into account.

Another problem with the NVRAM is defining which executions are considered
“correct” in the presence of hardware failures, that can lead to the loss of
data. Despite a lot of correctness conditions were defined in the previous
years [7, 10, 19, 22, 8], only _Nesting Safe Recoverable Linearizability_ [8]
describes the work with nested functions. Thus, maintaining persistent call
stack is a crucial part of systems based on this concept. However, while
methods of maintaining NVRAM heap are well-studied [13, 11], methods of
maintaining the persistent program stack are not studied at all: other works
just assume the existence of a persistent call stack [8, 9, 17].

Moreover, the persistent stack allows us to design and implement novel complex
system recovery algorithms, which can be faster than traditional log-based
system recovery methods. Previously, such complex algorithms were considered
impractical for traditional persistent memory systems due to the high latency
of random access of traditional persistent memory, following directly from its
mechanical nature, but on NVRAM-based systems such complex algorithms may be
found useful.

In this work, we describe an algorithm, based on the implementation of the
persistent call stack, that can be used to execute NVRAM programs and recover
the system after a hardware failure while taking the architecture of real-
world NVRAM systems into account. Moreover, the algorithm can be used to
execute NVRAM-destined programs on commodity persistent hardware, such as hard
drives. That allows us to test NVRAM algorithms using only cheap persistent
hardware, such as HDD, SSD, etc., without having access to the NVRAM. We
report the usage of our algorithm to implement and test correct and incorrect
versions of the NVRAM CAS algorithm [8]. Also, we describe a method, that can
be used to verify executions of NVRAM CAS algorithm for serializability.

The rest of the work is organized as follows. In Section 2, we discuss the
system model, various failure models, operation execution model and talk about
different correctness conditions, suitable for the NVRAM. In Section 3, we
discuss the concept of the persistent program stack and its implementation. In
section 4 we present the solutions for the challenges we faced during the
implementation of our algorithm. Also, we show there the architecture of the
system along with the system recovery algorithm. In Section 5, we discuss the
usage of our algorithm to implement and verify the NVRAM CAS algorithm, along
with the method of checking executions of the NVRAM CAS algorithm for
serializability. In Section 6, we discuss the directions of the future
research. We conclude our work with Section 7.

##  2 Model

###  2.1 System model

Our system model is based on the model described in [8].

There are $N$ processes $\\{p_{i}\\}_{i=1}^{N}$ executing operations
concurrently. Also, there are $M$ objects $\\{O_{j}\\}_{j=1}^{M}$ located in
the shared non-volatile memory. Processes communicate with each other by
executing operations on shared objects (see Fig. 1), that can support read,
write or read-modify-write [20] operations.

In our model, all shared memory is considered non-volatile, i.e., it does not
lose its content even after a crash event. However, we assume the existence of
a volatile memory in the system. Each object $LO$, located in the volatile
memory, is considered local to some process $p$. In other words, only process
$p$ can access object $LO$. Thus, besides being able to execute operations on
shared objects, each process can access its local objects. Such objects
support only read and write operations (see Fig. 2).

Figure 1: Execution of operations on shared objects Figure 2: Execution of
operations on local objects

Figure 3: System execution model

However, our model still does not reflect some properties of the real-world
hardware: for example, it does not take into account the existence of the
volatile NVRAM cache and the existence of shared volatile memory.

###  2.2 Failure model

There exist two general failure models:

  * •

_Individual_ crash-recovery model [8]. In such a model, each process can face
a crash event independently of all other processes. When a process faces a
crash event, it stops working until it is restarted. All data, stored in the
volatile memory of the failed process, is lost. However, all data persisted to
the NVRAM is not lost and remains available to the failed process after its
restart.

  * •

_System_ crash-recovery model. In such a model, a crash event happens in the
whole system instead of an individual process. The whole systems stops working
until it is restarted. After the system restarts, the contents of all the
volatile memory is lost. As in the previous model, the data, persisted in the
NVRAM, is not lost and remains available to all processes after the system
restarts.

Note, that the _system_ crash-recovery model is a special case of the
_individual_ crash-recovery model, since a crash of the whole system can be
represented as a set of $N$ simultaneous crash events of individual processes
— one crash event per each process. Despite the fact that _individual_ crash-
recovery model is a more general model, in this work we focus mainly on
_system_ crash-recovery model. In real-world shared memory systems multiple
computational units are placed in a single server and thus a failure of a
single computational unit is impossible without a failure of the entire
system. That is why, in our opinion, _system_ crash-recovery model describes
more accurately the real-life crash event — for example, power loss.

###  2.3 Operation execution

We say that function F is being executed by process $p$ if execution of F has
been started by $p$ but has not been finished yet. As described in [8], we
work with the nested invocation of functions: at any moment, multiple
functions can be executed by any process. It happens when function F invokes
function G. Thus, executed functions in each process form a nested sequence.
In the above example execution of G is nested into the execution of F.

To allow the recovery of the system, we provide each function F with a dual
function F.Recover, which receives the same arguments as F. F.Recover is
called after the system restart to perform system recovery and it should
either finish the execution of F or roll back F.

To perform the system recovery, for each process $p$ we should call F.Recover
for each function F being executed by $p$ at the crash moment. Moreover,
recovery functions should be called in the certain order: if the execution of
G is nested into the execution of F, G.Recover should be called before
F.Recover. Thus, each process should perform the recovery in the LIFO (stack)
order.

Also we should consider the possibility of _repeated failures_ — failures
which happen during the recovery procedure. Consider the system failure after
F was invoked. After the restart, we should call F.Recover to complete the
recovery. Suppose another system failure happens before F.Recover is finished.
After the second restart, we should again continue the recovery at executing
F.Recover. It means that there is no difference between the system failure
happening during the execution of F or during the execution of F.Recover: in
both cases, we should call F.Recover to complete the recovery. Thus, F.Recover
should be designed so that it can complete the operation (or roll it back) no
matter whether the crash occurred when executing F or F.Recover.

###  2.4 Correctness

Multiple correctness conditions for NVRAM exist. Here, we outline three most
important (from the strongest to the weakest):

  1. 1.

_Nesting Safe Recoverable Linearizability_ [8]. It requires each invoked
function F to be completed even if a crash event occurs while executing F.
Thus, under that correctness condition, F.Recover should finish the execution
of F either by completing it successfully or by rolling it back.

  2. 2.

_Durable Linearizability_ [22]. It requires that each function F, execution of
which has finished before a crash, should be completed. If a crash event
occurs while executing function F, such function may be either completed or
not.

  3. 3.

_Buffered Durable Linearizability_ [22]. It is a weaker form of _Durable
Linearizability_. Its difference is in that it allows function F not to be
completed even if its execution finished before a crash. However, that
correctness condition requires each object to provide sync operation — all
functions, finished before a call to sync must be completed, even if a crash
event occurs.

In this work, we propose an algorithm that can be used to run NVRAM-destined
programs under _Nesting Safe Recoverable Linearizability_ — the strongest
correctness condition.

##  3 Persistent Stack

###  3.1 Program stack concept

In order to execute programs for NVRAM, for each thread111When talking about
practical aspects of concurrent programming, we use the word “thread” in the
same context, as the word “process” in the theory of concurrent programming
$t$ we maintain an information about functions, which were executed by $t$
when a crash occurred. Also, to invoke recover functions in the correct order
we maintain the order in which these functions were invoked.

We maintain that order by using the notion of program stack: each thread $t$
has its own NVRAM-located stack, and each function executed by $t$ corresponds
to a single frame of the stack. When a function is invoked, the corresponding
frame is added to the top of the stack. After the end of the execution, the
frame is removed from the top. Therefore, when a crash occurs, the stack of
thread $t$ contains frames, that correspond to functions that were executed by
$t$ at the crash moment. Moreover, such frames are located in the correct
order: if execution of G was nested into the execution of F, a frame of G is
located closer to the top of the stack, than a frame of F.

###  3.2 Issues of existing implementations

The functionality of the program stack is already implemented by standard
execution systems: for example, x86 program stack. However, we cannot use them
as-is, even if we transfer it from the DRAM to the NVRAM.

Here we remind the implementation of the function call via the x86 stack [3,
6]. Suppose function F calls function G using x86 command CALL G. To perform
such an invocation, we should store a return address on the stack — the
address of the instruction in function F that follows the instruction CALL G.
After the execution of G is finished, we continue execution of F from that
instruction. This is exactly how x86 instruction RET works — it simply reads
the return address from the stack and performs JMP [5] to that address,
allowing it to the continue the execution from the desired point.

Note that such a program stack implementation has a number of drawbacks, that
makes it impossible for us to use such implementation as a persistent stack:

  * •

After the system restart due to the crash, the code segment may be relocated,
i.e., have a different offset in the virtual address space. That will make us
incapable of identifying which functions were executed at the crash moment —
we simply won’t be able to match return address from the stack with an address
of some instruction after the code segment relocation.

  * •

We cannot guarantee an atomicity of adding a new frame to the stack or
removing a frame from the top of the stack – if a crash occurs during adding
or removing stack frame, after the system restarts the stack might be in an
inconsistent state.

Thus, instead of using existing program stack implementations, we present our
persisted stack structure that overcomes the above drawbacks.

###  3.3 Persistent stack structure

Each thread has an access to its own persistent stack. For simplicity, in this
section we assume that the persistent stack is allocated in the NVRAM as a
continuous memory region of constant size. However, we explain how to make a
stack of unbounded size in Appendix 0.A.

Persistent stack consists of consequent persistent stack frames — one frame
per function that accesses NVRAM. 222Each such function must have a recover
version, as described above. Each frame ends with a one-byte end marker: it is
0x1 (_stack end marker_) if the frame is the last frame of the stack;
otherwise, it is 0x0 (_frame end marker_). Any data located after the _stack
end marker_ is considered invalid — it should never be read or interpreted in
any way (see Fig. 4).

Figure 4: Persistent stack structure

To finish the description of the data layout, each persistent stack frame
consists of: 1) a unique identifier of the invoked function that allows us to
call the appropriate recover function during the system recovery; 2) arguments
of the function, serialized into a byte array—during the system recovery we
pass them to the recover function; 3) a one-byte end marker (either 0x0 or
0x1).

###  3.4 Update of the persistent stack

The persistent stack should be updated: 1) when the function is invoked — a
new frame should be added to the top of the stack, 2) when the function
execution is finished — the top frame of the stack should be removed.

####  3.4.1 Adding the new frame to the top of the stack.

Suppose the stack at the beginning of the operation has two frames in it (see
Fig. 5):

To add a new frame to the top of the stack, we perform the following actions:

  1. 1.

After the _stack end marker_ , we write a new frame with the _stack end
marker_ set. Note that the new frame (frame 3) is located after the _stack end
marker_ of the previous frame (frame 2). Therefore, the new frame is not
considered as a stack frame, while the previous frame (frame 2) is still the
last stack frame (see Fig. 6).

  2. 2.

Change the end marker of the current last stack frame (frame 2) from 0x1 to
0x0. Thus, the last stack frame (frame 2) becomes the penultimate stack frame
and the new frame (frame 3) becomes the last stack frame (see Fig. 7). We name
that one-byte end marker changing operation as _moving the stack end forward_.

Figure 5: Persistent stack before the function invocation Figure 6: Persistent
stack after writing the new frame after the stack end marker

Figure 7: Persistent stack after adding the new frame to the top of the stack

Figure 8: Adding new frame to the top of the stack

####  3.4.2 Removing the top frame from the stack.

Suppose the stack at the beginning of the operation has three frames in it
(see Fig. 9):

To remove the top frame from the stack, we simply change the end marker of the
penultimate stack frame (frame 2) from 0x0 to 0x1, thus making the penultimate
stack frame the last stack frame (see Fig. 10). We name that one-byte end
marker changing operation as _moving the stack end backward_. Note, that frame
3 becomes the part of the invalid data and, therefore, it will not be
considered as a stack frame anymore.

Figure 9: Persistent stack before exiting from a function Figure 10:
Persistent stack after exiting from a function

Figure 11: Removing the top frame from the stack

####  3.4.3 Dummy frame.

Note that both frame removal and frame addition procedures assume the
existence of at least one frame in the stack, besides the one that is being
removed or added. Particularly, this assumption implies that the bottom stack
frame cannot be removed from the stack. We can simply satisfy that assumption
by introducing a dummy frame — the stack frame, located at the bottom of the
stack (i.e. the first frame, added to the stack). That frame is added to the
stack at the initialization of the stack and is never removed. By that, we
ensure that there is always at least one frame, thus making it possible for us
to use the stack update procedures, described above.

####  3.4.4 Flushing long frames.

Note that sometimes a new stack frame does not fit into a single cache line —
for example, that can happen when some function receives arguments list with
length greater than the cache line size. In such case, we will not be able to
add such frame to the stack atomically (since only single cache line can be
persisted atomically). Therefore, we can face a crash event that will force us
to write the new frame partially (see Fig. 12).

Figure 12: Persistent stack with partially flushed frame

In our algorithm, we, at first, add a new frame to the stack, and only after
the new frame has been written successfully we _move the stack end forward_.
Thus, even if the crash event happens, the stack will remain consistent:
partially written frame will be located after the _stack end marker_ and will
not be considered as a stack frame. Therefore, this scenario does not brake
_Nesting-safe Recoverable Linearizability_ , since the last function
invocation was not linearized before the crash event. We can simply think that
the crash happened before the function invocation and the function was never
invoked.

####  3.4.5 The atomicity of the stack update.

We can say that a function invocation linearizes only when we _move the stack
end forward_. This requires only the flushing of a single byte to the NVRAM.
Since a single byte always resides in a single cache line, this flush always
happens atomically.

The same observation can be made for _moving the stack end backward_ : an
execution of the function is finished when we change the end marker of the
penultimate stack frame from 0x0 to 0x1. As was described above, such action
happens atomically.

####  3.4.6 Persistent stack and the NVRAM

The procedure of adding and removing a stack frame requires only the ability
to flush a single byte atomically and not the entire cache line — this makes
us capable of implementing the stack maintenance algorithm on a hardware that
does not support atomic flushing of an entire cache line. Thus, the algorithm
described above, can be easily emulated without having access to an expensive
NVRAM hardware, using almost any existing persistent hardware such as HDD,
SSD, etc.

For the above reasoning to remain correct, we should maintain two following
invariants:

  1. 1.

We should flush the new stack frame before _moving the stack end forward_.

Suppose we violate that rule. Consider a crash event that happens at some time
after the _moving the stack end forward_. Suppose also, that new stack frame
(frame 3) has been written to the volatile NVRAM cache and was lost during the
crash. After the system restart we will not be able to call the recover
function for frame 3, because we have lost that frame (see Fig. 13).

  2. 2.

When changing the end marker of some frame (either from 0x0 to 0x1 or vice
versa) we should immediately flush it before staring the execution of the
invoked function or continuing the execution of the caller function.

Suppose we violate that rule. Consider a crash event, happening while
executing function F, corresponding to frame 3. Also consider that the _frame
end marker_ , written to frame 2, has been written to the volatile NVRAM cache
and thus has been lost (see Fig. 14). After the system restart, we do not
consider frame 3 as a stack frame, and, thus, we do not even invoke F.Recover.

Figure 13: New stack frame has been lost due to volatility of the NVRAM cache
Figure 14: End marker has been lost due to volatility of the NVRAM cache

Figure 15: Results of violating flushing invariants

##  4 System implementation

###  4.1 Pointers to the memory in NVRAM

When working with pointers to the NVRAM we face the problems similar to those
we faced when working with function addresses (Section 3.2). Suppose we have
acquired pointer ptr pointing to the NVRAM. We store ptr in the NVRAM (for
example, in some persistent stack frame, as an argument of some function F).
After that, we face a crash event. And when we restart the system, the mapping
of the NVRAM into the virtual address space can change, thus, making pointer
ptr invalid, since it does not point to the NVRAM anymore.

The same problem happens when we emulate NVRAM using HDDs, mapped to the
virtual address space using mmap syscall [2]: on each system restart, HDD is
mapped to a different location in the virtual address space.

This problem has a very simple solution: instead of using direct pointers to
the NVRAM, we shall use offsets from the beginning of the NVRAM mapping into
the virtual address space. Suppose the mapping of the NVRAM begins at address
MAP_ADDR. Then, instead of storing ptr we store ptr - MAP_ADDR — an offset of
the desired memory location. Note that such an offset does not depend on an
exact location of the mapping, thus making it safe for us to store it in the
NVRAM and use after the system restart.

###  4.2 Handling return values

Traditionally, on x86 architecture, functions return value using the volatile
memory — either in x86 register EAX, if the return value is an integer, or in
FPU register ST0, if the return value is floating-point. For example, cdecl,
one of the most popular x86 calling conventions [4], implies the above rules
for return value.

However, in our case we cannot use volatile processor registers to store
return value. Consider a crash event occurring after the callee function G has
saved the return value to the EAX and finished its execution by _moving the
stack end backward_. At that time, the caller function F has not persisted the
return value from EAX to the NVRAM. After the system restart, we will not
invoke G.Recover, but start from F.Recover instead. However, we cannot execute
F.Recover properly, because we have lost the result of G.

That is why functions should store their results directly in the NVRAM. We
could come up with two approaches where to store them:

  1. 1.

on the persistent stack. For example, we can use an especially-allocated place
in a persistent stack frame for that purpose.

  2. 2.

in the NVRAM heap. In such a case, the caller can preallocate a memory
location for the answer before invoking the callee, and pass the pointer to
that memory location in callee’s arguments (note, that as was mentioned in
Section 4.1, we should use offsets instead of pointers to the NVRAM). After
that, callee can store its answer in that memory location.

In both cases, the callee should flush the answer to the NVRAM before _moving
the stack end backward_. Our implementation supports returning of small values
(up to 8 bytes) on the persistent stack, while big values are returned in the
NVRAM heap.

###  4.3 Architecture of the system

The system consists of a single main thread and N worker threads.

Main thread can run in either a standard mode or a recovery mode.

When running in the standard mode, the main thread performs the following
steps.

  1. 1.

Initialize the NVRAM heap. This may include the initialization of the memory
allocator, the mapping of the NVRAM to the virtual address space and the
consequent initialization of the variable MAP_ADDR, mentioned in Section 4.1

  2. 2.

Initialize N new persistent stacks.

  3. 3.

Start N worker threads, giving each worker thread pointer to the beginning of
its persistent stack.

  4. 4.

Receive task that should be executed by the system and add them to the
producer-consumer queue.

When running in the standard mode, worker threads receive tasks from the
producer-consumer queue and execute them.

In case of a crash, the main thread starts in the recovery mode and performs
the following steps:

  1. 1.

Initialize the NVRAM heap.

  2. 2.

Start N recovery threads, giving each recovery thread the pointer to a
persistent stack of some worker thread.

  3. 3.

Wait for all recovery threads to finish.

  4. 4.

Restart the system in normal mode.

Each recovery thread executes the following algorithm:

  1. 1.

Traverse its persistent stack from the top to the bottom.

  2. 2.

Execute the corresponding recover operation for each stack frame.

  3. 3.

After the recovering of an operation on the top of the stack is finished, pop
the top frame.

  4. 4.

After all the frames (except for the dummy one) are removed from the stack,
finish the execution.

System recovery happens in parallel, which allows for a faster recovery than
an ordinary single-threaded recovery.

We note that our algorithm deals well with _repeated failures_. If such a
failure happens during the recovery, the new recovery continues not from the
beginning, but from where the previous recovery was interrupted. More
formally, consider a frame, corresponding to a function F. If during the
recovery we have completed execution of F.Recover and removed that frame from
the stack, even after the _repeated failure_ we will not run a recover
function for that frame once more. Thus, we achieve the progress even in the
presence of _repeated failures_.

##  5 Verification

The described algorithm of the persistent stack can be used to implement and
verify CAS algorithm for NVRAM, described in [8]. That paper assumes the
absence of the volatile NVRAM cache, i.e., all writes are performed right into
the memory. To emulate this, we should flush each written cache line to the
NVRAM immediately after the corresponding write. Also, we should implement the
algorithm so that each written value never crosses the border of a cache line
to allow atomic flush of each written value.

Multiple correctness conditions for concurrent algorithms exist: the most
popular are linearizability [21], sequential consistency and serializability
[23]. We want to perform the verification against some of these correctness
conditions.

From now on we take CAS algorithm for the NVRAM as the running example.
Consider the following execution. Multiple threads run a set of CAS operations
on a single register Reg: $\\{CAS(Reg,old_{i},new_{i})\\}_{i=1}^{N}$, and the
initial value of Reg is init. And for each operation we know whether it was
finished successfully or not.

We present an algorithm, that can be used to check such an execution for
serializability in a polynomial time.

###  5.1 Serializability

To verify the execution for serializability in polynomial time, we build a
graph $\langle
V,E\rangle,G=\\{old_{i}\\}_{i=1}^{N}\cup\\{new_{i}\\}_{i=1}^{N}\cup\\{init\\}$
and construct the set of edges $E$ the following way: $a\rightarrow b\in E$ if
and only if there exists a successful $CAS(Reg,a,b)$ in the execution. Also,
we read the final value of the register. We can read it after all the CAS
operations are finished.

Since each edge of $G$ corresponds to a successful CAS, each successful CAS
was executed exactly once, and each successful $CAS(Reg,a,b)$ changed value of
$Reg$ from $a$ to $b$, to verify the execution for serializability we should
find some Eulerian circuit that starts in the initial value of the register
and ends in the final value of the register — such a circuit corresponds to
the sequential execution. Thus, the execution is serializable if and only if
such a circuit can be found333Please, note that we can simply serialize
unsuccessful operation at the times when the register holds a value different
from $old_{i}$..

###  5.2 Running examples

We have implemented the algorithm, described above, using HDD-based memory-
mapped files [2] to emulate the NVRAM. We used UNIX utility kill [1] to
interrupt the system at random moments by that emulating system crashes.

We have generated random executions of the algorithm in the following way:

  1. 1.

Generate an initial integer value of the register;

  2. 2.

Generate $\\{new_{i}\\}_{i=1}^{N}$ and $\\{old_{i}\\}_{i=1}^{N}$ as integer
values, uniformly sampled from some range: either wide range
$[-10^{5},10^{5}]$), or narrow range ($[-10,10]$);

  3. 3.

Start the system in the normal mode, add descriptors of
$\\{CAS(Reg,old_{i},new_{i})\\}_{i=1}^{N}$ operations to the producer-consumer
queue in the random order;

  4. 4.

Run $4$ working threads that execute these CAS operations;

  5. 5.

At random moment, emulate system failure using the kill utility;

  6. 6.

Restart the system in the recovery mode waiting for all CAS operations, that
were executing at the crash moment, to complete;

  7. 7.

Restart the system in the normal mode, add all remaining descriptors to the
queue;

  8. 8.

Run steps 4-7 until all operations are completed;

  9. 9.

Get answers of all CAS operations, get the final value of the register, and,
finally, verify the execution for serializability.

We have verified a lot of random executions along with emulated system
failures at random moments. All executions of the CAS algorithm presented in
[8] were found to be serializable. We also verified the executions of
incorrect CAS algorithm with especially-added bugs: we have removed the matrix
R from the CAS algorithm. The executions of such a wrong implementation were
reported to be non-serializable.

The implementation is publicly available at
https://github.com/KokorinIlya/NVRAM_runner.

##  6 Future work

We find three interesting directions for the future work: 1) implement and
test other NVRAM algorithms; 2) find the polynomial algorithm that verifies
executions of CAS algorithm for linearizability and sequential consistency, or
prove that the problem of such a verification is NP-complete; 3) develop a
plugin for one of the modern C++ compilers that can be used to reduce the
boilerplate code: e.g., automatically create a new stack frame on each
function call, remove the top frame when a function execution finishes, and
etc.

##  7 Conclusion

In this paper we presented an algorithm that can be used to run NVRAM
programs. The described algorithm takes into consideration different aspects
of real-world NVRAM systems. Moreover, the algorithm can be used to run NVRAM-
destined programs on commodity persistent hardware, which can be useful for
implementing and testing novel NVRAM algorithms without having an access to an
expensive NVRAM hardware. The algorithm was successfully used to implement and
verify the CAS algorithm for NVRAM.

## References

  * [1] kill(1) (2020), https://man7.org/linux/man-pages/man1/kill.1.html
  * [2] mmap(2) (2020), http://man7.org/linux/man-pages/man2/mmap.2.html
  * [3] x86 call instruction (2020), https://www.felixcloutier.com/x86/call
  * [4] x86 calling conventions (2020), https://en.wikipedia.org/wiki/X86_calling_conventions
  * [5] x86 jmp instruction (2020), https://www.felixcloutier.com/x86/jmp
  * [6] x86 ret instruction (2020), https://www.felixcloutier.com/x86/ret
  * [7] Aguilera, M.K., Frølund, S.: Strict linearizability and the power of aborting. Technical Report HPL-2003-241 (2003)
  * [8] Attiya, H., Ben-Baruch, O., Hendler, D.: Nesting-safe recoverable linearizability: Modular constructions for non-volatile memory. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. pp. 7–16 (2018)
  * [9] Ben-David, N., Blelloch, G.E., Friedman, M., Wei, Y.: Delay-free concurrency on faulty persistent memory. In: The 31st ACM Symposium on Parallelism in Algorithms and Architectures. pp. 253–264 (2019)
  * [10] Berryhill, R., Golab, W., Tripunitara, M.: Robust shared objects for non-volatile main memory. In: 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016)
  * [11] Bhandari, K., Chakrabarti, D.R., Boehm, H.J.: Makalu: Fast recoverable allocation of non-volatile memory. ACM SIGPLAN Notices 51(10), 677–694 (2016)
  * [12] Blelloch, G.E., Gibbons, P.B., Gu, Y., McGuffey, C., Shun, J.: The parallel persistent memory model. In: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures. pp. 247–258 (2018)
  * [13] Cai, W., Wen, H., Beadle, H.A., Hedayati, M., Scott, M.L.: Understanding and optimizing persistent memory allocation. In: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. pp. 421–422 (2020)
  * [14] Chauhan, H., Calciu, I., Chidambaram, V., Schkufza, E., Mutlu, O., Subrahmanyam, P.: $\\{$NVMOVE$\\}$: Helping programmers move to byte-based persistence. In: 4th Workshop on Interactions of NVM/Flash with Operating Systems and Workloads ($\\{$INFLOW$\\}$ 16) (2016)
  * [15] Chen, S., Jin, Q.: Persistent b+-trees in non-volatile main memory. Proceedings of the VLDB Endowment 8(7), 786–797 (2015)
  * [16] David, T., Dragojevic, A., Guerraoui, R., Zablotchi, I.: Log-free concurrent data structures. In: 2018 $\\{$USENIX$\\}$ Annual Technical Conference ($\\{$USENIX$\\}$$\\{$ATC$\\}$ 18). pp. 373–386 (2018)
  * [17] Friedman, M., Ben-David, N., Wei, Y., Blelloch, G.E., Petrank, E.: Nvtraverse: In nvram data structures, the destination is more important than the journey. In: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. 377–392 (2020)
  * [18] Friedman, M., Herlihy, M., Marathe, V., Petrank, E.: A persistent lock-free queue for non-volatile memory. ACM SIGPLAN Notices 53(1), 28–40 (2018)
  * [19] Guerraoui, R., Levy, R.R.: Robust emulations of shared memory in a crash-recovery model. In: 24th International Conference on Distributed Computing Systems, 2004. Proceedings. pp. 400–407. IEEE (2004)
  * [20] Herlihy, M.: Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS) 13(1), 124–149 (1991)
  * [21] Herlihy, M.P., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12(3), 463–492 (1990)
  * [22] Izraelevitz, J., Mendes, H., Scott, M.L.: Linearizability of persistent memory objects under a full-system-crash failure model. In: International Symposium on Distributed Computing. pp. 313–327. Springer (2016)
  * [23] Papadimitriou, C.H.: The serializability of concurrent database updates. Journal of the ACM (JACM) 26(4), 631–653 (1979)

##  Appendix 0.A Stack of unbounded size

###  0.A.1 Motivation

Sometimes we do not know the size of the program call stack in advance, so we
have to make it to be resizable. Consider the following example. We want to
consequently update a lot of separate data items $\\{a_{i}\\}_{i=1}^{N}$ in
the transactional behaviour: if we update only a part of the requested items
and face a crash event—after the system restart all modifications should be
rolled back. In short, we want to make a transactional for-loop.

Luckily, we can represent a for-loop using the recursive function F(i). This
function saves an old value of $a_{i}$, performs an update of $a_{i}$ and
calls F(i + 1). A function F.Recover(i) rolls back an update of $a_{i}$.

Therefore, if we face a crash event during the update procedure, we can
restore the system into the consequent state.

However, using such an implementation we face a problem with the constant size
of the persistent stack: if the number of updated items $N$ is big, we cannot
place frames of all update functions $\\{\texttt{F(i)}\\}_{i=1}^{N}$ on the
stack.

That is why we need to implement the persistent stack of unbounded size. We
achieve it in two different ways: using either the resizable array or linked
list.

###  0.A.2 Dynamically resizable array

The first approach to this problem is based on the idea of a dynamically
resizable array. Along with the continuous block we allocate a single pointer
in the NVRAM that points to the block storing the stack data (see Fig. 16).

We refer to the length of that continuous block in bytes as the _capacity_ of
the stack, while referring to the length of all frames in bytes as _size_ of
the stack.

Figure 16: Persistent stack using dynamically resizable array

Sometimes we need to change the capacity of the stack. This can happen in two
situations: either we want to add a new frame to the stack and it does not fit
into the current block, or we think that capacity is too big (e.g. capacity >
4 $\cdot$ size) and we want to shrink the stack.

To do so, we execute the following steps: 1) allocate a new memory block in
the NVRAM with the desired capacity; 2) copy the stack data from the old block
into the new block; 3) flush the copied data; 4) change the pointer to point
onto the new block; 4) flush the pointer to the NVRAM.

After that, we deallocate the old block and continue with the stack as usual.

The main disadvantage of this method is that on the resizing it requires
$O(\texttt{size of the stack})$ time to copy the contents from the old block
to the new block.

###  0.A.3 Linked list of blocks

The second approach uses a linked list of blocks (see Fig. 17). Each block
contains a pointer to the next block in the list, pointer to the first block
is stored in some well-known location.

We introduce two types of frames. The ones of the first type are the _ordinary
frames_ as introduced before: they correspond to some function, being executed
by current thread, and contain an identifier of that function and its
arguments. The ones of the second type are _pointer frames_ : they contain a
pointer to the next block in the linked list 444As was said in section 4.1, we
should use offsets instead of pointers to the NVRAM. To distinguish one frame
from another we may augment each frame with one-byte preamble: ordinary frames
begin with 0xA, while pointer frames begin with 0xB.

When we encounter the pointer frame at the current block, we seek the next
frame at the block pointed at by the pointer from the pointer frame. All the
data from the current block after the pointer frame should be considered
invalid.

####  0.A.3.1 Adding a new frame to the top of the stack

If the new frame fits into the current block, we add the new frame as we did
it in Section 3.4.1. Otherwise, we execute the following steps: 1) allocate a
new block that accommodates the new frame; 2) add a pointer frame, pointing to
the new block, to the top of the current block.

####  0.A.3.2 Removing a frame from the top of the stack

If the top frame of the stack is not the only frame of the current block, we
remove it as in Section 3.4.2. Otherwise, we execute the following steps: 1)
find the previous block; 2) in the previous block delete the last stack frame,
which is the pointer frame, pointing at the current block; 3) after that, we
deallocate the unnecessary block (see Fig. 19).

Figure 17: Persistent stack as a list of blocks Figure 18: Persistent stack
after removing the top frame

Figure 19: Removing the top frame from the stack

In order to be able to quickly fetch the previous block of the current block
we can use any of these two approaches:

  * •

Use a double linked list of blocks in which each block contains a pointer to
its previous block;

  * •

Load addresses of all blocks in some container with random access (e.g.,
dynamic array).