# Can we reveal the core-chemical composition of ultra-massive white dwarfs
through their magnetic fields?

Maria E. Camisassa,1 Roberto Raddi,2 Leandro G. Althaus, 3,4 Jordi Isern,5,6,7
Alberto Rebassa-Mansergas,2,6 Santiago Torres,2,6 Alejandro H. Córsico,3,4 and
Lydia Korre 1
1 Applied Mathematics Department, University of Colorado, Boulder, CO
80309-0526, USA
2 Departament de Física, Universitat Politècnica de Catalunya, c/Esteve
Terrades 5, 08860 Castelldefels, Spain
3 Instituto de Astrofísica de La Plata, UNLP-CONICET, Paseo del Bosque s/n,
1900 La Plata, Argentina
4 Facultad de Ciencias Astronómicas y Geofísicas, Universidad Nacional de La
Plata, Paseo del Bosque s/n, 1900 La Plata, Argentina
5 Institute of Space Sciences (ICE, CSIC), Campus UAB, Carrer de Can Magrans
s/n, 08193 Barcelona, Spain
6 Institut d’Estudis Espacials de Catalunya (IEEC), c/Gran Capità 2-4, Edif.
Nexus 201, 08034 Barcelona, Spain
7 Fabra Observatory (RACAB), Rambla dels Estudis 115, 08002 Barcelona, Spain
E-mail<EMAIL_ADDRESS>
(Accepted 2022 July 13. Received 2022 July 12; in original form 2022 March 24)

###### Abstract

Ultra-massive white dwarfs ($1.05\rm M_{\odot}\lesssim M_{WD}$) are
particularly interesting objects that allow us to study extreme astrophysical
phenomena such as type Ia supernovae explosions and merger events.
Traditionally, ultra-massive white dwarfs are thought to harbour oxygen-neon
(ONe) cores. However, recent theoretical studies and new observations suggest
that some ultra-massive white dwarfs could harbour carbon-oxygen (CO) cores.
Although several studies have attempted to elucidate the core composition of
ultra-massive white dwarfs, to date, it has not been possible to distinguish
them through their observed properties. Here, we present a new method for
revealing the core-chemical composition in ultra-massive white dwarfs that is
based on the study of magnetic fields generated by convective mixing induced
by the crystallization process. ONe white dwarfs crystallize at higher
luminosities than their CO counterparts. Therefore, the study of magnetic
ultra-massive white dwarfs in the particular domain where ONe cores have
reached the crystallization conditions but CO cores have not, may provide
valuable support to their ONe core-chemical composition, since ONe white
dwarfs would display signs of magnetic fields and CO would not. We apply our
method to eight white dwarfs with magnetic field measurements and we suggest
that these stars are candidate ONe white dwarfs.

###### keywords:

stars: interiors – stars: magnetic fields – white dwarfs

††pubyear: 2015††pagerange: Can we reveal the core-chemical composition of
ultra-massive white dwarfs through their magnetic fields?–Can we reveal the
core-chemical composition of ultra-massive white dwarfs through their magnetic
fields?

##  1 Introduction

White dwarf (WD) stars are the most common end-point of stellar evolution.
Therefore, the WD population in our Galaxy is considered a powerful tool to
investigate a wide variety of astrophysical problems, from the formation and
evolution of our Galaxy to the ultimate fate of planetary systems (see Althaus
et al., 2010, for a review). Among all the WD stars, of special interest are
those WDs with masses larger than $\sim 1.05\rm M_{\odot}$, commonly referred
to as ’ultra-massive’ WDs. Observations of these stars have been largely
reported in the literature (Kilic et al., 2021; Hollands et al., 2020; Caiazzo
et al., 2021; Miller et al., 2022), and are considered of special interest as
they are related to stellar merger episodes, the occurrence of physical
processes in the super asymptotic giant-branch (SAGB) phase, and type Ia
Supernovae and micronovae explosions.

Despite the large interest in ultra-massive WDs, there is not a clear
consensus on the core-chemical composition of such objects. Traditionally,
these stars are thought to be born as a result of the isolated evolution of
massive intermediate-mass stars with masses larger than $6-9\,\rm M_{\odot}$,
which reach the SAGB with a degenerate core that develops temperatures high
enough to ignite carbon. The violent carbon flame propagates through the core,
leading to the formation of an ultra-massive WD with a core composed mainly by
oxygen (O) and neon (Ne) (Garcia Berro & Iben, 1994; Siess, 2010). However,
recent theoretical models of the isolated progenitors of ultra-massive WDs
suggest that they can avoid carbon burning on the SAGB, leading to the
formation of ultra-massive WDs with cores composed mainly by C and O (Althaus
et al., 2021). An alternate scenario for the formation of ultra-massive WDs
has gained relevance in the last years. It is thought that a relevant fraction
of the single massive WDs in our Galaxy have been formed as a result of
stellar mergers (Temmink et al., 2020; Cheng et al., 2020; Torres et al.,
2022). Although this scenario has been explored in several hydrodynamical
simulations (Yoon et al., 2007; Lorén-Aguilar et al., 2009), the core-chemical
composition of single ultra-massive WDs born in stellar mergers is a matter of
debate. Schwab (2021) simulated the merger of two CO WDs and found that that,
if the remnant has a mass larger than $\sim 1.05$ M⊙, then the initial CO core
is converted into ONe. On the other hand, Wu et al. (2022) studied the
evolution of the remnant of a merger of a massive CO-core WD with a He-core WD
and showed that this scenario can lead to the formation of ultra-massive CO-
core WDs with masses up to $\sim 1.20$ M⊙.

Several studies in the literature have tried to distinguish ONe from CO ultra-
massive WDs. Hollands et al. (2020) observed a $1.14\rm M_{\odot}$ WD with a
unique hydrogen/carbon atmosphere composition. These authors tried to use the
atmospheric non-detection of O to test the core-chemical composition of this
WD. However, despite the distinct core-structures, the outer layers of CO- and
ONe-core WDs are almost indistinguishable and, therefore, the degree of O
dredge-up does not depend on the core-composition. A promising avenue to infer
the inner chemical stratification of ultra-massive WDs is through
Asteroseismology (Córsico et al., 2019a, b, 2021). Nevertheless, in order to
pursue such task it is necessary to find a large number of pulsating ultra-
massive WDs with abundant detected pulsation periods.

Despite the persisting efforts, the inference of the core composition of
ultra-massive WDs has not been possible to date. Here, we present a new method
to accomplish this goal, by using the magnetic field measurements in ultra-
massive WDs. According to two-component phase diagrams (Horowitz et al., 2010;
Blouin et al., 2020; Medin & Cumming, 2010) for both CO and ONe mixtures,
during the crystallization process, the solid core is enriched in the heavier
element (i.e. O in a CO mixture, Ne in an ONe mixture). Therefore, the liquid
mantle surrounding the solid core will be depleted in the heavier element,
thus having a molecular weight lower than the regions above it and hence
inducing a Rayleigh-Taylor mixing in a significant portion of the WD. The
pioneering study of Isern et al. (2017) suggested that the compositionally
driven convection occurring in these stars could drive dynamo magnetic fields
similar to those found in Solar System planets. The studies of Schreiber et
al. (2021a, b) showed that these crystallization-induced dynamos can generate
magnetic fields in cataclysmic variables and in cold metal polluted WDs,
explaining their large fraction among the observed population and Belloni et
al. (2021) demonstrated that such dynamos can account for the observed
rareness of bright intermediate polars in globular clusters. Furthermore,
Bagnulo & Landstreet (2021) have analyzed the complete volume-limited WD
sample within $20\,$pc from the Sun, showing that the occurrence of magnetic
fields is significantly higher in WDs that have fully or partially
crystallized cores than in WDs that have not started the crystallization
process yet. Here, we propose that crystallization-induced dynamo magnetic
fields can be used to infer the core-chemical composition of ultra-massive
dwarfs. As previously found in Camisassa et al. (2021, 2022) and Bauer et al.
(2020), ONe-core WDs crystallize at higher luminosities and effective
temperatures than their CO-core counterparts, due to the larger coulomb
interactions between their ions. Therefore, we expect a particular region in
the color-magnitude diagram where ONe ultra-massive WDs have started the
crystallization process, and hence could be dominated by crystallization-
driven dynamos, but CO WDs have not. By analyzing eight magnetic WDs in this
particular domain, we propose that the presence of magnetic fields in WDs
located within that region is evincing their ONe core-chemical composition.

##  2 The white dwarf sample

We selected all known magnetic WDs that are listed in the Montreal White Dwarf
Database (Dufour et al., 2017). These stars are shown in the Gaia EDR3 color-
magnitude diagram in Fig. 1, together with the hydrogen-rich CO-core and ONe-
core WD evolutionary models of Camisassa et al. (2016); Camisassa et al.
(2019); Camisassa et al. (2022). We have employed the model atmospheres of
Koester (2010) and Koester & Kepler (2019) to convert these evolutionary
models into the magnitudes in Gaia EDR3 passbands. Crystallization onset in
these models is determined by the phase diagrams of Horowitz et al. (2010) and
Medin & Cumming (2010) and is shown as black circles and blue squares,
respectively. Colour coding indicates the intensity of the magnetic fields
(see Ferrario et al., 2015, 2020, for reviews on magnetic WDs). The magnetic
ultra-massive WDs that have larger luminosities than the ONe crystallization
onset are not expected to be crystallizing and, therefore, their magnetic
fields must be originated by mechanisms other than crystallization-driven
dynamos.

Among all the magnetic WDs, we identified eight objects that lie in the region
delimited by the CO and ONe crystallization onset and by the 1.29$\,\rm
M_{\odot}$ and 1.10$\,\rm M_{\odot}$ evolutionary sequences. If these ultra-
massive WDs harbour an ONe-core, they are undergoing the crystallization
process. Otherwise, if they have a CO-core, they have not started this process
yet. This set of eight WDs is shown on the Gaia color-magnitude diagram in
Fig. 2. All the selected objects are fully within our region of interest,
except for SDSS J112030.34-115051.1 that has larger error bars. All of our
selected WDs have hydrogen dominated envelopes and only one of them,
WD$1628+440$, has an estimation for its rotation period, which has a lower
limit of 6hr and an upper limit of 4d (Brinkworth et al., 2013). The names and
properties of these selected WDs are listed in Table 1.

Figure 1: All known magnetic WDs in the Gaia EDR3 color-magnitude diagram
taken from the Montreal White Dwarf Database. Color coding indicates the
magnetic field intensity in $10^{6}$ G. The DA CO-core WD evolutionary models
with 0.53, 0.66, 0.82, 0.95, 1.10, 1.16, 1.23 and 1.29 M⊙ from Camisassa et
al. (2016, 2022) are indicated using solid black lines. The DA ONe-core WD
evolutionary models with 1.10, 1.16, 1.23 and 1.29 M⊙ from Camisassa et al.
(2019) are displayed using dot-dashed blue lines. The black circles and blue
squares indicate the crystallization onset in each sequence, respectively.
Figure 2: Zoomed-in view of the ONe crystallization region for ultra-massive
WDs in the Gaia color-magnitude diagram. That is, we plot those WDs that, if
they harbour ONe cores, they have started the crystallization process, but if
they harbour CO cores, they have not. The adopted colours and symbols are the
same as in Fig. 1. The error bars account for photometric and parallax
uncertainties.

##  3 The white dwarf models

We have employed the ONe-core ultra-massive evolutionary models of Camisassa
et al. (2019) to analyze the selected magnetic WDs. These models were
calculated using the La Plata stellar evolutionary code LPCODE (see Althaus et
al., 2005, 2015, for details). This evolutionary code has been amply used in
the study of different aspects of low-mass star evolution (see Camisassa et
al., 2016; Camisassa et al., 2017; Althaus et al., 2021, and references
therein). These evolutionary models include a realistic treatment of the
crystallization process for ONe mixtures, using an updated phase diagram
(Medin & Cumming, 2010), and include the energy released as latent heat and by
the phase separation process induced by crystallization. Furthermore, the
initial chemical profiles are the result of the full progenitor evolution
through the thermally pulsing SAGB, calculated by Siess (2010). These accurate
initial chemical profiles play a key role in determining the extension of the
Rayleigh-Taylor convective region that will be responsible for generating the
dynamos. According to the phase diagram employed, in an ONe WD, the solid core
is enriched in Ne and, therefore, the immediate surrounding liquid layer is
depleted in it, leading to a convective region that takes place in a large
portion of the star. The extension of this convective region in the 1.16M⊙
ONe-core model as a function of the logarithm of the stellar luminosity is
shown in the top panel of Figure 3. The inner (outer) boundary of this region
is displayed using a dotted blue (solid purple) line. The inner boundary moves
outwards as crystallization proceeds, whereas the outer boundary barely moves.
These boundaries are determined by the chemical abundances that result from
the calculation of the full progenitor evolution.

The bottom panel of Figure 3 shows the extension of the convective region in
the 1.16M⊙ CO model of Camisassa et al. (2022) as a function of the logarithm
of the stellar luminosity. By comparing the top and bottom panels of this
figure, we see that for $-2.35\lesssim\log(L/L_{\odot})\lesssim-2$, the 1.16
M⊙ ONe-core model is developing a convective mantle covering up to $\sim 88\%$
of its mass, that is absent in the 1.16 M⊙ CO model.

We have interpolated the magnitude G and the colour index $\rm G_{BP}-G_{RP}$
in our ONe-core WD sequences to obtain the values of the mass, the luminosity,
the cooling age, the effective temperature and the logarithm of the surface
gravity of the target stars. These quantities are listed in Table 1. For those
WDs whose masses are not encompassed in Camisassa et al. (2019), we have
specifically calculated evolutionary models, by scaling the initial chemical
profile of the most similar model from Camisassa et al. (2019). On the basis
of these models, we obtained the fraction of crystallized mass ($\rm
M_{s}/M_{WD}$) and the thickness of the convective region ($r_{o}-r_{i}$),
also listed in Table 1, among other parameters.

##  4 The white dwarf dynamo

The magnetic Reynolds number and the magnetic Prandtl number are defined as
${\rm Rm}=ul/\eta$ and $\rm Pm=\nu/\eta$, respectively, where $u$ is a typical
velocity, $l$ is a typical length, $\eta$ is the magnetic diffusivity and
$\nu$ is the kinematic viscosity. The Ohmic decay time can be estimated as
$\tau_{\Omega}\sim R_{\rm WD}^{2}/\eta$, where $R_{\rm WD}$ is the WD radius.
Isern et al. (2017) estimated that, in a typical massive WD, $\rm Rm\sim
10^{14}-10^{15}$, $\rm Pm\sim 0.58$ and $\tau_{\Omega}$ is much longer than
the WD age. Thus, once the magnetic field has been generated by the
convection-driven dynamo, it will be sustained against Ohmic dissipation. In
that sense, it is practical to use the dynamo scaling theory of Christensen
(2010) to estimate the intensity of the magnetic field in terms of the
properties of the convective region, that takes into account the balance
between the Ohmic dissipation and the energy flux (in the rapidly rotating
regime). Following Christensen (2010) (see also Christensen et al., 2009), we
obtain:

$\frac{B^{2}}{8\pi}=cf_{\Omega}\frac{1}{V}\int_{r_{i}}^{r_{o}}\left[\frac{q_{c}(r)\lambda(r)}{H(r)}\right]^{2/3}\rho(r)^{1/3}4\pi
r^{2}dr,$ (1)

where the integral is the energy of the convective region ($E$), $B$ is the
magnetic field intensity, $c$ is an adjustable parameter, $f_{\Omega}$ is the
ratio between the Ohmic dissipation and the total dissipation, $V$ is the
volume of the convective mantle, $r_{i}$ and $r_{o}$ are its inner and outer
radius, respectively, $q_{c}$ is the convected energy flux, $H$ is the scale
height and $\lambda$ is the mixing length. We adopt $f_{\Omega}=1$ and
$\lambda=H$. The energy density $E/V$ was calculated for each of our selected
WDs, and it is listed in Table 1.

Figure 3: Top panel: Solid purple (dotted blue) line displays the mass
fraction at the outer (inner) boundary of the convective region in terms of
the logarithm of the stellar luminosity, for our 1.16 M⊙ ONe-core WD model.
Bottom panel: Same as top panel, but for our 1.16 M⊙ CO-core WD model.

This scaling law is applicable for WDs in the rapidly rotating regime, whereby
the Rossby number, which is the ratio of inertial force to Coriolis force, is
much lower than 1, and the equipartition field strength is achieved. We
estimate the Rossby number as $\rm Ro\sim\frac{P}{t_{\rm conv}}$, where $P$ is
the rotation period and $t_{\rm conv}$ is the convective turnover timescale.
We cannot measure the convective turnover timescale in the WD interior, but we
can provide an estimation for it. The density contrast between the floating O
enriched material and the surrounding liquid ONe mixture is
$\Delta\rho/\rho\sim 10^{-4}$ and, therefore, its upwards acceleration is
$a=g\Delta\rho/\rho\sim 2\times 10^{5}\rm cm/s^{2}$. Assuming a limiting
velocity of the turbulent eddies as in Isern et al. (2017), we obtain a
characteristic convective velocity of $3\times 10^{5}\rm cm/s$. Therefore, we
estimate the convective turnover timescale for ONe composition to be $\sim
500$ s. Measuring the rotation period in WDs is a difficult task. Among the
eight WDs analyzed in this paper, only WD 1658+440 has a poorly constrained
rotation period with an upper limit of 4 days, which suggests that this star
is not in a fast-rotating regime.

The dynamo energy density and the measured magnetic field intensity of our
selected ultra-massive WDs are plotted in Figure 4, together with the
predictions for the Earth, Jupiter, M dwarfs and T Tauri stars (Christensen et
al., 2009) and the WDs studied by Isern et al. (2017). The scaling law of
Christensen et al. (2009) considering $c=0.63$ and a deviation of a factor 3
from it are displayed using solid and dotted black lines, respectively. Five
of our eight ultra-massive WDs in our sample match the scaling law within a
factor of 10, and the other three match it within a factor of 25. In
particular, for WD 1658+440 the agreement between the observed and predicted
magnetic field is remarkably good. This generally good agreement suggests that
these eight WDs could have ONe cores, since CO-core models would not have
reached the crystallization onset and, hence, they would not hold
crystallization-driven dynamos. However, we wish to remark that although the
agreement we found for our eight ultra-massive WDs is better than the one
found in Isern et al. (2017), the observed field distribution of our ONe WD
candidates (from $\sim 3$ to $\sim 40$MG) is not significantly different from
the field distribution of all isolated magnetic WDs, since $\sim 60$ per cent
of them have field strengths in the range 3-40MG (see Figure 11 in Ferrario et
al., 2020).

Figure 4:  Magnetic field intensity in terms of the dynamo energy density. Earth and Jupiter are indicated using black crosses with error bars, whereas M dwarfs and T Tauri are plotted using magenta and cyan circles, respectively Christensen et al. (2009). The DA and non-DA WDs from Isern et al. (2017) are shown using green and orange squares, respectively. The ultra-massive WDs listed in Table 1 are plotted using purple crosses. The solid line is the scaling law from Christensen et al. (2009) for the Earth, Jupiter, T Tauri and M dwarf stars considering $c=0.63$, and the dotted lines allow for a deviation of a factor of 3 from it. Table 1: Name, spectral type and magnetic field intensity of our selected ultra-massive WDs, together with our estimations for the mass, luminosity, cooling times, effective temperature, surface gravity, crystallized mass fraction, and length and dynamo energy density of the convective mantle. Name | Type | B | M | $\log(L/L_{\odot})$ | $t_{\rm cool}$ | $T_{\rm eff}$ | $\log{g}$ | $\rm M_{s}/M_{WD}$ | $r_{o}-r_{i}$ | E/V | Ref.
---|---|---|---|---|---|---|---|---|---|---|---
|  | [MG] | [$\rm M_{\odot}$] |  | [Gyrs] | [k] | [cgs] |  | [$\times 10^{8}$ cm] | [$\times 10^{11}$ erg cm-3] |
WD 1658+440 | DA | 3.5 | 1.243 | -1.87 | 0.291 | 28763 | 9.19 | 0.14 | $1.47$ | $8.62$ | (a)
SDSS J205233.51-001610.6 | DA | 13.42 | 1.097 | -2.36 | 0.504 | 18168 | 8.83 | 0.19 | $1.77$ | $1.77$ | (b)
SDSS J080359.93+122943.9 | DA | 40.7 | 1.093 | -2.43 | 0.570 | 17424 | 8.83 | 0.28 | $1.56$ | $1.43$ | (b)
SDSS J155708.02+041156.4 | DA | 41 | 1.165 | -2.20 | 0.430 | 21403 | 8.98 | 0.20 | $1.63$ | $2.70$ | (c)
WD 1131+521 | DA | 8.64 | 1.165 | -2.17 | 0.409 | 21690 | 8.98 | 0.16 | $1.71$ | $2.93$ | (b)
SDSS J142703.40+372110.5 | DA | 27.04 | 1.133 | -2.36 | 0.536 | 18885 | 8.91 | 0.30 | $1.40$ | $1.97$ | (b)
WD 1327+594 | DQAP | 18 | 1.161 | -2.03 | 0.305 | 23392 | 8.96 | 0.01 | $2.34$ | $3.68$ | (d)
SDSS J112030.34-115051.1 | DA | 8.9 | 1.22 | -2.01 | 0.359 | 25383 | 9.11 | 0.23 | $1.41$ | $5.58$ | (b)
References: (a) Schmidt et al. (1992); (b) Külebi et al. (2009); (c) Kepler et
al. (2015); (d) Vanlandingham et al. (2005)

##  5 Summary and conclusions

Despite the large interest in ultra-massive WDs, there is not a clear
consensus in the literature on whether these stars harbour an ONe or a CO
core. Aiming at obtaining information on their core-chemical composition, we
have analyzed a sample of eight magnetic ultra-massive WDs selected from the
Montreal White Dwarf Database. These stars lie within a particular domain that
implies that, if they harbour an ONe core, they are undergoing the
crystallization process, whereas if they harbour a CO core, they have not
started this process yet. That is, ONe core WDs in this region should have a
convective region that drives dynamo magnetic fields, but CO WDs should not.
Relying on precise ONe ultra-massive WD evolutionary models from Camisassa et
al. (2019) that include realistic chemical profiles that result from the full
progenitor evolution, and an updated treatment of the chemical redistribution
induced by crystallization, we have modeled these candidate ONe WDs. We have
estimated their mass, their luminosity, their percentage of crystallized mass,
the length of their convective mantles and their convective energy density,
among other parameters.

We have compared the measured magnetic fields of these stars with the
estimations of the dynamos predicted by the scaling law of Christensen et al.
(2009), which is suitable for the Earth, Jupiter, M dwarfs and T Tauri stars
in the rapidly rotating regime. Among our sample of eight WDs, only WD
1658+440 has a poorly constrained measurement of the rotating period, with an
upper limit of 4 days. Therefore, we cannot predict whether these eight WDs
are in the rapidly rotating regime. The magnetic field measurements of WD
1658+440, SDSS J205233.51-001610.6, WD 1131+521, WD 1327+594, SDSS
J112030.34-115051.1 match the magnetic field intensity predicted by the
scaling law within a factor of 10, indicating that they will likely harbour
ONe cores. In particular, the agreement between the predicted and observed
magnetic field for WD 1658+440 is remarkably good, evincing its ONe core. The
magnetic field measurements for SDSS J080359.93+122943.9, SDSS
J155708.02+041156.4 and SDSS J142703.40+372110.5 exceed the scaling law by a
factor of $\sim 20$. The high magnetic fields in these WDs could be indicating
that these stars are very fast rotators. Recent numerical simulations suggest
that fast rotating convective dynamos with $\rm Ro\ll 1$ can achieve super-
equipartition magnetic fields (Augustson et al., 2016, 2019). In that context,
Ginzburg et al. (2022) claimed that the density contrast driving the
convective zone could be smaller than the one used in this paper and in
Mochkovitch (1983) and Isern et al. (2017), yielding convective turnover
timescales longer than those used here, opening the possibility to these white
dwarf to be fast rotators with strong magnetic fields. Furthermore, the
scaling law that we use has been determined for planets, M dwarfs and T-Tauri
stars, where the magnetic Prandtl number is 5-6 orders of magnitudes smaller
than in WDs. Considering a likely dependence of the dynamo efficiency on the
magnetic Prandtl number, we could expect that the WD dynamo can generate
magnetic fields larger than the predictions of the scaling law (see Schreiber
et al., 2021a, for a thorough discussion), implying that SDSS
J080359.93+122943.9, SDSS J155708.02+041156.4 and SDSS J142703.40+372110.5 can
also have an ONe core.

Finally, we cannot disregard that the magnetic fields in these WDs could be
fossil fields (Braithwaite & Spruit, 2004), generated during the merger of two
WDs (Garcia Berro et al., 2012) or in a common envelope phase, if the binary
companion has been destroyed or is in a wide orbit (Tout et al., 2008).
However, none of these scenarios can account for the number of observed
magnetic cataclysmic variables, intermediate polar WDs in globular clusters
and cold metal polluted WDs (Schreiber et al., 2021a; Belloni et al., 2021;
Schreiber et al., 2021b), implying that the crystallization-induced dynamos
must take place. Furthermore, the analysis of the complete volume-limited WD
sample within $20\,$pc from the Sun (Bagnulo & Landstreet, 2021) has shown
that the occurrence of magnetic fields is significantly higher in WDs that
have fully or partially crystallized cores than in WDs with fully liquid
cores. In this study, magnetic WDs account for 20 per cent of the sample and
the presence of magnetic fields in WDs with fully liquid cores is $\sim 11$
per cent, whereas this percentage raises to $\sim 30$ per cent for WDs that
are undergoing or have undergone the crystallization process. This trend is
indicating that the crystallization process could be one important cause for
developing magnetic fields in WDs. Due to the absence of ultra-massive WDs
within the 20-pc sample, such a population analysis should be extended to a
larger volume in the Solar neighbourhood. However, the spectral
characterization of the volume-complete $100\,$pc is still scarce. Within
$100\,$pc from the Sun, the frequency of the occurrence of magnetic fields in
ultra-massive WDs with fully liquid cores is $\sim 21$ per cent, whereas this
frequency decreases to $3$ per cent for WDs with partially or fully
crystallized cores. This drop does not imply that magnetic fields are more
frequent in bright young WDs, but it is the likely consequence of various
observational biases. Because the main methods for detecting and measuring
magnetic fields take advantage of the Zeeman effect that splits the spectral
lines and polarizes them, high signal-to-noise ratio as well as high spectral
resolution are needed for the analysis of both weak ($<1$–2 MG) and very
strong ($\gtrsim 100$ MG) magnetic fields (Landstreet & Bagnulo, 2019; Bagnulo
& Landstreet, 2021). Both requirements, combined to the only recent making of
the Gaia 100-pc sample (Jiménez-Esteban et al., 2018), have worked against the
completeness of an intrinsically fainter sample of ultra-massive magnetic WDs.
By extrapolating the population analysis of magnetic WDs within 20-pc to the
larger volume, we estimate that there should be nearly 2700 magnetic WDs
within $100\,$pc, but just 125 of them are known so far. An exhaustive search
for magnetic fields in all ultra-massive WDs within $100\,$pc would be needed
to fully confirm our results.

Finally, the fact that some WDs that lie in our region of interest have no
detected magnetic fields does not imply that these WDs have a CO core, since
these WDs could have ONe cores and be crystallizing, but their dynamos are not
efficient enough to generate observable magnetic fields. We suggest that, in
order to elucidate the core-chemical composition of ultra-massive WDs, efforts
should be placed in measuring magnetic fields for large samples of such stars.
We expect that close-to-complete large samples of magnetic WDs will be
achieved in the next 5–10 years, thanks to the ongoing and currently
developing multi-fibre spectroscopic surveys such as DESI (DESI Collaboration
et al., 2016), SDSS-V (Kollmeier et al., 2017), WEAVE (Dalton et al., 2012),
and 4MOST (de Jong et al., 2012).

## Acknowledgements

This work was supported by the NASA grants 80NSSC17K0008, 80NSSC20K0193 and
80NSSC21K0455, the postdoctoral fellowship programme Beatriu de Pinós
agreement No 801370, by AGENCIA through the Programa de Modernización
Tecnológica BID 1728/OC-AR, by the PIP 112200801-00940 grant from CONICET, by
grant G149 from University of La Plata, by the MINECO grant
PID2020-117252GB-I00, by the ESP 2017-82674-R, by Grant RYC-2016-20254 funded
by MCIN/AEI/10.13039/501100011033 and by ESF Investing in your future. This
work has made use of data from the European Space Agency (ESA) mission Gaia,
processed by the Gaia Data Processing and Analysis Consortium.

## Data Availability

Supplementary material will be shared on request to the corresponding author.

## References

  * Althaus et al. (2005) Althaus L. G., Serenelli A. M., Panei J. A., Córsico A. H., Garcia Berro E., Scóccola C. G., 2005, A&A, 435, 631
  * Althaus et al. (2010) Althaus L. G., Córsico A. H., Isern J., Garcia Berro E., 2010, A&ARv, 18, 471
  * Althaus et al. (2015) Althaus L. G., Camisassa M. E., Miller Bertolami M. M., Córsico A. H., Garcia Berro E., 2015, A&A, 576, A9
  * Althaus et al. (2021) Althaus L. G., et al., 2021, A&A, 646, A30
  * Augustson et al. (2016) Augustson K. C., Brun A. S., Toomre J., 2016, ApJ, 829, 92
  * Augustson et al. (2019) Augustson K. C., Brun A. S., Toomre J., 2019, ApJ, 876, 83
  * Bagnulo & Landstreet (2021) Bagnulo S., Landstreet J. D., 2021, MNRAS, 507, 5902
  * Bauer et al. (2020) Bauer E. B., Schwab J., Bildsten L., Cheng S., 2020, ApJ, 902, 93
  * Belloni et al. (2021) Belloni D., Schreiber M. R., Salaris M., Maccarone T. J., Zorotovic M., 2021, MNRAS, 505, L74
  * Blouin et al. (2020) Blouin S., Daligault J., Saumon D., Bédard A., Brassard P., 2020, A&A, 640, L11
  * Braithwaite & Spruit (2004) Braithwaite J., Spruit H. C., 2004, Nature, 431, 819
  * Brinkworth et al. (2013) Brinkworth C. S., Burleigh M. R., Lawrie K., Marsh T. R., Knigge C., 2013, ApJ, 773, 47
  * Caiazzo et al. (2021) Caiazzo I., et al., 2021, Nature, 595, 39
  * Camisassa et al. (2016) Camisassa M. E., Althaus L. G., Córsico A. H., Vinyoles N., Serenelli A. M., Isern J., Miller Bertolami M. M., Garcia Berro E., 2016, ApJ, 823, 158
  * Camisassa et al. (2017) Camisassa M. E., Althaus L. G., Rohrmann R. D., Garcia Berro E., Torres S., Córsico A. H., Wachlin F. C., 2017, ApJ, 839, 11
  * Camisassa et al. (2019) Camisassa M. E., et al., 2019, A&A, 625, A87
  * Camisassa et al. (2021) Camisassa M. E., Althaus L. G., Torres S., Córsico A. H., Rebassa-Mansergas A., Tremblay P.-E., Cheng S., Raddi R., 2021, A&A, 649, L7
  * Camisassa et al. (2022) Camisassa M. E., Althaus L. G., Koester D., Torres S., Pons P. G., Córsico A. H., 2022, MNRAS, 511, 5198
  * Cheng et al. (2020) Cheng S., Cummings J. D., Ménard B., Toonen S., 2020, ApJ, 891, 160
  * Christensen (2010) Christensen U. R., 2010, Space Sci. Rev., 152, 565
  * Christensen et al. (2009) Christensen U. R., Holzwarth V., Reiners A., 2009, Nature, 457, 167
  * Córsico et al. (2019a) Córsico A. H., Althaus L. G., Miller Bertolami M. M., Kepler S. O., 2019a, A&ARv, 27, 7
  * Córsico et al. (2019b) Córsico A. H., De Gerónimo F. C., Camisassa M. E., Althaus L. G., 2019b, A&A, 632, A119
  * Córsico et al. (2021) Córsico A. H., Althaus L. G., Gil Pons P., Torres S., 2021, A&A, 646, A60
  * DESI Collaboration et al. (2016) DESI Collaboration et al., 2016, arXiv e-prints, p. arXiv:1611.00036
  * Dalton et al. (2012) Dalton G., et al., 2012, in McLean I. S., Ramsay S. K., Takami H., eds, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series Vol. 8446, Ground-based and Airborne Instrumentation for Astronomy IV. p. 84460P, doi:10.1117/12.925950
  * Dufour et al. (2017) Dufour P., Blouin S., Coutu S., Fortin-Archambault M., Thibeault C., Bergeron P., Fontaine G., 2017, in Tremblay P. E., Gaensicke B., Marsh T., eds, Astronomical Society of the Pacific Conference Series Vol. 509, 20th European White Dwarf Workshop. p. 3 (arXiv:1610.00986)
  * Ferrario et al. (2015) Ferrario L., de Martino D., Gänsicke B. T., 2015, Space Sci. Rev., 191, 111
  * Ferrario et al. (2020) Ferrario L., Wickramasinghe D., Kawka A., 2020, Advances in Space Research, 66, 1025
  * Garcia Berro & Iben (1994) Garcia Berro E., Iben I., 1994, ApJ, 434, 306
  * Garcia Berro et al. (2012) Garcia Berro E., et al., 2012, ApJ, 749, 25
  * Ginzburg et al. (2022) Ginzburg S., Fuller J., Kawka A., Caiazzo I., 2022, MNRAS, 514, 4111
  * Hollands et al. (2020) Hollands M. A., et al., 2020, Nature Astronomy,
  * Horowitz et al. (2010) Horowitz C. J., Schneider A. S., Berry D. K., 2010, Physical Review Letters, 104, 231101
  * Isern et al. (2017) Isern J., Garcia Berro E., Külebi B., Lorén-Aguilar P., 2017, ApJ, 836, L28
  * Jiménez-Esteban et al. (2018) Jiménez-Esteban F. M., Torres S., Rebassa-Mansergas A., Skorobogatov G., Solano E., Cantero C., Rodrigo C., 2018, MNRAS, 480, 4505
  * Kepler et al. (2015) Kepler S. O., et al., 2015, MNRAS, 446, 4078
  * Kilic et al. (2021) Kilic M., Bergeron P., Blouin S., Bédard A., 2021, MNRAS, 503, 5397
  * Koester (2010) Koester D., 2010, Mem. Soc. Astron. Italiana, 81, 921
  * Koester & Kepler (2019) Koester D., Kepler S. O., 2019, A&A, 628, A102
  * Kollmeier et al. (2017) Kollmeier J. A., et al., 2017, arXiv e-prints, p. arXiv:1711.03234
  * Külebi et al. (2009) Külebi B., Jordan S., Euchner F., Gänsicke B. T., Hirsch H., 2009, A&A, 506, 1341
  * Landstreet & Bagnulo (2019) Landstreet J. D., Bagnulo S., 2019, A&A, 623, A46
  * Lorén-Aguilar et al. (2009) Lorén-Aguilar P., Isern J., Garcia Berro E., 2009, A&A, 500, 1193
  * Medin & Cumming (2010) Medin Z., Cumming A., 2010, Phys. Rev. E, 81, 036107
  * Miller et al. (2022) Miller D. R., Caiazzo I., Heyl J., Richer H. B., Tremblay P.-E., 2022, ApJ, 926, L24
  * Mochkovitch (1983) Mochkovitch R., 1983, A&A, 122, 212
  * Schmidt et al. (1992) Schmidt G. D., Bergeron P., Liebert J., Saffer R. A., 1992, ApJ, 394, 603
  * Schreiber et al. (2021a) Schreiber M. R., Belloni D., Gänsicke B. T., Parsons S. G., Zorotovic M., 2021a, Nature Astronomy, 5, 648
  * Schreiber et al. (2021b) Schreiber M. R., Belloni D., Gänsicke B. T., Parsons S. G., 2021b, MNRAS, 506, L29
  * Schwab (2021) Schwab J., 2021, ApJ, 906, 53
  * Siess (2010) Siess L., 2010, A&A, 512, A10
  * Temmink et al. (2020) Temmink K. D., Toonen S., Zapartas E., Justham S., Gänsicke B. T., 2020, A&A, 636, A31
  * Torres et al. (2022) Torres S., Canals P., Jiménez-Esteban F. M., Rebassa-Mansergas A., Solano E., 2022, MNRAS, 511, 5462
  * Tout et al. (2008) Tout C. A., Wickramasinghe D. T., Liebert J., Ferrario L., Pringle J. E., 2008, MNRAS, 387, 897
  * Vanlandingham et al. (2005) Vanlandingham K. M., et al., 2005, AJ, 130, 734
  * Wu et al. (2022) Wu C., Xiong H., Wang X., 2022, arXiv e-prints, p. arXiv:2202.02040
  * Yoon et al. (2007) Yoon S. C., Podsiadlowski P., Rosswog S., 2007, MNRAS, 380, 933
  * de Jong et al. (2012) de Jong R. S., et al., 2012, in McLean I. S., Ramsay S. K., Takami H., eds, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series Vol. 8446, Ground-based and Airborne Instrumentation for Astronomy IV. p. 84460T (arXiv:1206.6885), doi:10.1117/12.926239


11institutetext: 11email<EMAIL_ADDRESS>22institutetext: Victoria University
of Wellington
22email<EMAIL_ADDRESS>
# Collapsing Threads Safely with Soft Invariants

David Friggens 11 Lindsay Groves 22

###### Abstract

Canonical abstraction is a static analysis technique that represents states as
3-valued logical structures, and produces finite abstract systems. Despite
providing a finite bound, these abstractions may still suffer from the state
explosion problem. Notably, for concurrent programs with arbitrary
interleaving, if threads in a state are abstracted based on their location,
then the number of locations will be a combinatorial factor in the size of the
statespace.

We present an approach using canonical abstraction that avoids this state
explosion by “collapsing” all of the threads in a state into a single abstract
representative. Properties of threads that would be lost by the abstraction,
but are needed for verification, are retained by defining conditional “soft
invariant” instrumentation predicates. This technique is used to adapt
previous models for verifying linearizability of nonblocking concurrent data
structure algorithms, resulting in exponentially smaller statespaces.

##  1 Introduction

Canonical abstraction [13] is a powerful technique for reasoning about heap-
manipulating programs. It is effective for analyzing concurrent systems with
interleaving threads, allowing on-the-fly model checking of safety properties.
However, the standard abstraction is still affected by the statespace
explosion problem. In this paper, we introduce a way of using canonical
abstraction for concurrent systems that is combinatorially more efficient.

###  1.1 Motivation

Canonical abstraction represents states as 3-valued logical structures. A
(potentially infinite) concrete statespace is abstracted to a finite abstract
statespace by mapping the (potentially infinite) heap objects in each state to
a finite number of abstract heap objects. The abstract heap objects are
equivalence classes with respect to a predetermined (finite) set of unary
predicates. Each abstract heap object represents all of the heap objects in
the concrete state with the same truth valuation of the abstraction
predicates.

Canonical abstraction was initially developed for sequential systems, but
Yahav and Sagiv [15] showed how it can be used for concurrent systems with
interleaving threads. The logical structures are extended to include an object
for each thread, and predicates for the possible program locations (labels) of
the threads. The set of abstraction predicates includes the location
predicates and possibly properties of thread fields, such as whether a
particular field is null. As a result, the number of equivalence classes of
abstract thread objects is determined by the number of locations and possibly
some user defined properties.

This approach has some benefits. For example, if an important property of a
system is that the $Y$ field of a thread is always null at location $X$, then
this is implicitly recorded in the abstract statespace. In every reachable
abstract state there will only be a thread object with the “at location $X$”
predicate true and with the “$Y$ is null” predicate true, never with “$Y$ is
null” false.

There is an important downside to this approach, however. For each abstract
heap configuration, there is an abstract state with a different combination of
interleaving thread states. For example, if there are three interleaving
locations $X$, $Y$ and $Z$, then every abstract heap configuration has seven
corresponding abstract states: three when all threads are at the same location
($X$, $Y$ or $Z$), three when all threads are at one of two locations
($\\{X,Y\\}$, $\\{X,Z\\}$ or $\\{Y,Z\\}$), and one when there are threads at
all three locations.

As the number of possible interleaving thread states increases, the number of
these combinations increases, and the less efficient the abstract statespace
becomes. Can we avoid the statespace explosion, but still make the abstraction
precise enough to verify interesting properties?

###  1.2 Soft Invariants

The “obvious” fix is to map all thread objects to a single abstract thread
object in each abstract state. This avoids the problem of combinatorial thread
objects, but loses too much precision — for example, the abstract thread
object can record whether $Y$ is null for all threads, whatever location they
are in, but not for only threads at location $X$.

We propose new derived unary predicates to explicitly preserve certain
properties of threads at particular locations. These predicates are defined
using conditional formulas of the form, e.g. “if the location is $X$ then the
field $Y$ is null”. The predicate will be true for all threads at locations
other than $X$, and if $Y$ is always null at location $X$, then the predicate
will be true for all those threads also. Thus the predicate will be true for
the single abstract thread object in each abstract state.

If $Y$ is sometimes non-null at location $X$, then the predicate will be false
for those thread objects, and will be “unknown” for the resulting abstract
thread object.111In the 3-valued semantics, “unknown” indicates that the
abstract predicate represents instances in corresponding concrete states when
it is true, and when it is false. We call these predicates “soft invariants”,
as they allow us to explicitly preserve invariants of the system (such as “at
location $X$, field $Y$ is always null”) but without having to prove that the
property is invariant. If they are not actually invariant then the predicate
does not affect the analysis.

The paper is structured as follows. In Section 2, we give some background
details about canonical abstraction. In Section 3, we illustrate the use and
effects of soft invariants with a simple example, advancing a pointer along a
circular linked list. In Section 4, we show the results of using soft
invariants to verify two nonblocking data structures, improving on our
previous work. In Section 5, we discuss choosing soft invariants, and
demonstrate that they can be safely over-defined. Finally, in Section 6 we
discuss related work.

##  2 Preliminaries

####  2.0.1 States as logical structures

Sagiv et al. [13] represent states as 3-valued logical structures, where
predicates describe relationships between objects, and multiple concrete
objects can be represented by a single abstract “summary object”. Since a
summary object can represent two or more concrete objects, an abstract state
with summary objects can represent an infinite number of concrete states.

First, a finite set of predicates
$\mathcal{P}=\\{\mathsf{eq},\mathsf{p}_{1},\dots,\mathsf{p}_{n}\\}$ is fixed
for the analysis, and we define $\mathcal{P}_{k}$ to be the set of $k$-ary
predicates in $\mathcal{P}$ (the equality predicate $\mathsf{eq}$ has arity
2). Then, an (_abstract_) _configuration_ $S=\left<U,\iota\right>$ has a
_universe_ $U$ that is a (finite or infinite) set of objects and an
_interpretation_ $\iota$ over the logical values true ($1$), false ($0$) and
unknown ($\frac{1}{2}$). For each $k$-ary predicate $\mathsf{p}$,

$\iota(\mathsf{p}):U^{k}\to\\{1,0,\frac{1}{2}\\}$

Additionally, for each $u_{1},u_{2}\in U$ where $u_{1}\neq u_{2}$,
$\iota(\mathsf{eq})(u_{1},u_{2})=0$. An object $u$, for which
$\iota(\mathsf{eq})(u,u)=\frac{1}{2}$ is called a _summary object_. A
_concrete configuration_ is one where all interpretations are 1 or 0.

Intuitively, one configuration represents a less abstract one if it contains
the same information, except for some conservative information loss. In other
words, it has the same universe of objects, though some may have been merged
together into summary objects, and it has the same predicate interpretations,
though some may have become unknown. This is formalised by the notion of
embedding, which relates configurations that are related by conservative
information loss.

We say that a configuration $S_{1}=\left<U_{1},\iota_{1}\right>$ _embeds_ into
a configuration $S_{2}=\left<U_{2},\iota_{2}\right>$ if there exists a
surjective function $f:U_{1}\to U_{2}$ such that for every $k$-ary predicate
$\mathsf{p}$, and $u_{1},\dots,u_{k}\in U_{1}$,

$\iota_{1}(\mathsf{p})(u_{1},\dots,u_{k})\sqsubseteq\iota_{2}(\mathsf{p})(f(u_{1}),\dots,f(u_{k}))$

where, for $l_{1},l_{2}\in\\{1,0,\frac{1}{2}\\}$, $l_{1}\sqsubseteq l_{2}$ iff
$l_{1}=l_{2}$ or $l_{2}=\frac{1}{2}$.

We further define a _tight embedding_ to be one that minimises information
loss, i.e. a predicate interpretation only becomes unknown if two objects are
being merged together, one which has a true interpretation and the other a
false interpretation. Formally, there exists a surjective function $f:U_{1}\to
U_{2}$ such that for every $k$-ary predicate $\mathsf{p}$, and
$u_{1},\dots,u_{k}\in U_{2}$,

$\iota_{2}(\mathsf{p})(u_{1},\dots,u_{k})=\\\
\t{1}\left\\{\begin{array}[]{cl}1&\mathrm{if~{}}\all{u_{1}^{\prime}\in
f^{-1}(u_{1})},\dots,{u_{k}^{\prime}\in
f^{-1}(u_{k})}@\iota_{1}(\mathsf{p})(u_{1}^{\prime},\dots,u_{k}^{\prime})=1\\\
0&\mathrm{if~{}}\all{u_{1}^{\prime}\in f^{-1}(u_{1})},\dots,{u_{k}^{\prime}\in
f^{-1}(u_{k})}@\iota_{1}(\mathsf{p})(u_{1}^{\prime},\dots,u_{k}^{\prime})=0\\\
\frac{1}{2}&\mathrm{otherwise}\end{array}\right.$

####  2.0.2 Canonical abstraction

_Canonical abstraction_ is a method for constructing tight embeddings. Given a
subset of the unary predicates $\mathcal{A}\subs\mathcal{P}_{1}$, called the
_abstraction predicates_ , we map objects in the original configuration to the
same abstract object if they have the same interpretations over the
abstraction predicates. The interpretation in the abstract configuration is
constructed as per the definition of tight embeddings above. We say that a
configuration is canonically abstract, with respect to $\mathcal{A}$, if it is
the canonical abstraction of itself.

Canonical abstraction has a number of important properties:

  * •

Every configuration has a single canonical abstraction, as each object has a
single canonical mapping in the embedding function.

  * •

Since there are a finite number of abstraction predicates, it follows that
there is a finite bound on the number of objects in the universe of a
canonically abstract configuration, and thus a finite bound on the number of
potential states in an abstract system.

The soundness of the canonical abstraction approach rests upon the Embedding
Theorem [13, Theorem 4.9]. Informally, this says that if a structure $S$
embeds into a structure $S^{\prime}$, then any information extracted from
$S^{\prime}$ via a formula $\varphi$ is a conservative approximation of the
information extracted from $S$ via $\varphi$. Alternatively, if we prove a
property $\varphi$ true or false in $S^{\prime}$, then we know it has the same
value in $S$.

####  2.0.3 Graphical representation

It is often helpful for comprehension to represent logical structures using
graphs. We use graph nodes to represent objects in the universe, with a double
line indicating a summary object. Labels on nodes represent unary predicates —
for each object, they are present if true, present with annotation (e.g.
“$\mathsf{x}=\frac{1}{2}$”) if unknown, or absent if false. Labelled arrows
represent binary predicates — for each pair of objects, a solid line if true,
a dotted line if unknown, or absent if false. Additionally, we use different
node shapes to represent object type predicates, instead of labels — hexagons
for threads and rectangles for linked list nodes.

####  2.0.4 Refining abstractions

Canonical abstraction using the fixed predicates $\mathcal{P}$ is often too
coarse, resulting in too much information being lost (i.e. evaluating to
unknown) for a property to be verified. A key method for refining abstractions
is to introduce additional predicates that record properties derived from the
other predicates. These _instrumentation predicates_ add no new information to
a concrete state, since they evaluate to the same truth values as their
defining formulas. However, in an abstract state they may add information: an
instrumentation predicate may evaluate to a definite value (true or false)
whilst its defining formula may evaluate to unknown. Additionally, unary
instrumentation predicates are usually included in the set of abstraction
predicates $\mathcal{A}$, which can prevent some objects from being merged
together into summary objects. In this paper, we make a point of removing
certain instrumentation predicates from $\mathcal{A}$ so that thread objects
_are_ merged together.

####  2.0.5 Tool Support

Canonical abstraction has been implemented in
TVLA222http://www.cs.tau.ac.il/~tvla/ (for Three Valued Logic Analyzer),
produced at Tel Aviv University [9, 3]. All of the results in this paper use
the “partial join” option [11].

##  3 Example

Figure 1 shows a simple operation to advance a global pointer $\mathit{x}$
along a linked list. The thread takes a snapshot ($\mathit{a}$) of
$\mathit{x}$, then of that node’s $\mathit{next}$ field ($\mathit{b}$). If the
snapshot is unchanged, the atomic Compare-and-Swap (CAS)
command333$\mathrm{CAS}(\mathit{x},\mathit{a},\mathit{b})$ is an atomic
command that sets $\mathit{x}$ to $\mathit{b}$ and returns true only if
$\mathit{x}=\mathit{a}$; otherwise it just returns false. advances
$\mathit{x}$. Otherwise, if another thread has altered $\mathit{x}$, then the
loop is restarted to try again.

1:operation Inc( )

2: repeat

3: $\mathit{a}\mathbin{:=}\mathit{x}$

4: $\mathit{b}\mathbin{:=}\mathit{a}.\mathit{next}$

5: until $\mathrm{CAS}(\mathit{x},\mathit{a},\mathit{b})$

6: return

7:end operation

Figure 1: Operation to advance a pointer $\mathit{x}$ along a linked list

To illustrate the use of soft invariants, we will consider a system composed
of an arbitrary number of threads that repeatedly perform the Inc operation.
The system is initialised with a circular linked list with a single shared
variable $\mathit{x}$ pointing at one of the list nodes. We will check the
safety property that $\mathit{x}$ is never null.

###  3.1 Predicates

To begin the model, we define unary core predicates for the object types,
global variable, and thread locations:444The square brackets have no meaning
other than being a visual indicator.

$\mathsf{is\\_{thread}},\mathsf{is\\_{node}},\mathsf{x},\mathsf{at[idle]},\mathsf{at[line3]},\mathsf{at[line4]},\mathsf{at[line5]},\mathsf{at[line6]}$

and binary core predicates for the object’s fields:

$\mathsf{next},\mathsf{a},\mathsf{b}$

To preserve the fact that the nodes’ $\mathit{next}$ fields are always non-
null, and to record whether the thread fields are null or not, we define the
following unary instrumentation predicates:

$\mathsf{has[next]}(v)\iff\exi u@\mathsf{next}(v,u)\\\
\mathsf{has[a]}(v)\iff\exi u@\mathsf{a}(v,u)\\\ \mathsf{has[b]}(v)\iff\exi
u@\mathsf{b}(v,u)$

To record whether a thread’s $\mathit{b}$ field is the
$\mathit{next}$-successor of its $\mathit{a}$ field, we define the following
unary shape predicate [7]:

$\mathsf{succ[a,b,next]}(v)\iff\exi
u_{1},u_{2}@\mathsf{a}(v,u_{1})\land\mathsf{b}(v,u_{2})\land\mathsf{next}(u_{1},u_{2})$

###  3.2 Initial State

In the initial state, all threads are at the idle location, and all their
fields are null. The node objects are indistinguishable except for the one
pointed to by $\mathit{x}$. Figure 2 shows a diagram of the state.

$\mathsf{at[idle]}$$\mathsf{x}$$\mathsf{has[next]}$$\mathsf{has[next]}$$\mathsf{next}$$\mathsf{next}$$\mathsf{next}$
Figure 2: Initial state of the example system

###  3.3 Combinatorial States

By default, the set of abstraction predicates is the set of unary predicates.
In this simple example system, the circular list is identical in every
abstract state — when $\mathit{x}$ advances along the list, the old node is
abstracted with the rest and the abstract representation remains unchanged.
Thus the differences between the abstract states are solely due to the thread
objects.

$\mathsf{at[idle]}$ | $\mathsf{at[line3]}$ | $\mathsf{at[line4]}$ | $\mathsf{at[line5]}$ | $\mathsf{at[line6]}$ | $\mathsf{has[a]}$ | $\mathsf{has[b]}$ | $\mathsf{succ[a,b,next]}$
---|---|---|---|---|---|---|---
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0
0 | 0 | 1 | 0 | 0 | 1 | 0 | 0
0 | 0 | 0 | 1 | 0 | 1 | 1 | 1
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1
0 | 1 | 0 | 0 | 0 | 1 | 1 | 1
0 | 0 | 1 | 0 | 0 | 1 | 1 | 0
0 | 0 | 1 | 0 | 0 | 1 | 1 | 1
Table 1: Predicate values for abstract thread objects

There are five thread locations, but eight possible distinct abstract thread
objects, as shown in Table 1. At the idle location, the fields $\mathit{a}$
and $\mathit{b}$ are null, so the instrumentation predicates
$\mathsf{has[a]}$, $\mathsf{has[b]}$ and $\mathsf{succ[a,b,next]}$ are false
(0). They remain null/false at line 3, but at line 4, $\mathit{a}$ is assigned
a value so $\mathsf{has[a]}$ is true (because $\mathit{x}$ is also non-null).
Then at line 5, $\mathit{b}$ is assigned to $\mathit{a}$’s (non-null)
successor, so $\mathsf{has[b]}$ and $\mathsf{succ[a,b,next]}$ are true. At
line 6 after a successful CAS step, the fields are unchanged, so the
instrumentation predicates remain unchanged. The fields are similarly
unchanged after an unsuccessful CAS step, when the thread returns to line 3;
since the instrumentation predicates differ, threads at line 3 repeating the
loop are distinguished from those that have just started the operation.
Similarly at line 4, the instrumentation predicates distinguish initial from
repeating threads; in the latter case, the $\mathit{a}$ field has been
reassigned, so the $\mathsf{succ[a,b,next]}$ instrumentation predicate may be
false or may (by coincidence) still be true.

Knowing that there are eight distinct types of interleaving threads, we can
predict that there will be 255 abstract states — the number of different
possible combinations. Indeed, that is the number reported by TVLA (see Table
2).

###  3.4 Soft Invariants

If we remove the location predicates and instrumentation predicates on thread
fields from the set of abstraction predicates, then all threads get mapped to
a single abstract thread object. The abstraction is too coarse though, and
TVLA gives a spurious error for our property — the fact that $\mathit{b}$ is
non-null at line 5 is not preserved, so a successful CAS step can result in
$\mathit{x}$ being set to null.

The properties we need to preserve are:

  1. 1.

At line 4, $\mathsf{has[a]}$ is true.

  2. 2.

At line 5, $\mathsf{has[a]}$, $\mathsf{has[b]}$ and $\mathsf{succ[a,b,next]}$
are true.

To do this, we define the following instrumentation predicates:

$\mathsf{if[line4,\mathsf{has[a]}]}(v)\iff\mathsf{is\\_{thread}}(v)\land(\mathsf{at[line4]}(v)\rightarrow\mathsf{has[a]}(v))\\\
\mathsf{if[line5,\mathsf{succ[a,b,next]}]}(v)\iff\mathsf{is\\_{thread}}(v)\land(\mathsf{at[line5]}(v)\rightarrow\mathsf{succ[a,b,next]}(v))$

We could also have defined similar instrumentation predicates
$\mathsf{if[line5,\mathsf{has[a]}]}$ and $\mathsf{if[line5,\mathsf{has[b]}]}$,
but $\mathsf{has[a]}$ and $\mathsf{has[b]}$ are both logical consequences of
$\mathsf{succ[a,b,next]}$, so they are not necessary.

With these two soft invariant instrumentation predicates, TVLA constructs an
abstract system that verifies our property, and has just one abstract state —
shown in Figure 3 — two orders of magnitude less than without soft invariants.
Table 2 shows the results reported by TVLA with and without soft invariants,
for unbounded ($\infty$) threads.

$\mathsf{at[idle]}$:$\frac{1}{2}$$\mathsf{at[line3]}$:$\frac{1}{2}$, $\mathsf{at[line4]}$:$\frac{1}{2}$$\mathsf{at[line5]}$:$\frac{1}{2}$, $\mathsf{at[line6]}$:$\frac{1}{2}$$\mathsf{has[a]}$:$\frac{1}{2}$, $\mathsf{has[b]}$:$\frac{1}{2}$$\mathsf{succ[a,b,next]}$:$\frac{1}{2}$$\mathsf{if[line4,\mathsf{has[a]}]}$:$\frac{1}{2}$$\mathsf{if[line4,\mathsf{succ[a,b,next]}]}$:$\frac{1}{2}$$\mathsf{x}$$\mathsf{has[next]}$$\mathsf{has[next]}$$\mathsf{a}$$\mathsf{b}$$\mathsf{a}$$\mathsf{b}$$\mathsf{next}$$\mathsf{next}$$\mathsf{next}$ Figure 3: Single abstract state |  | Heap |  | Ave | Max |  |
---|---|---|---|---|---|---|---
|  | Limit | Time | RAM | RAM | CA | Stored
SIs | Th. | (MB) | (s) | (MB) | (MB) | States | States
N | $\infty$ | 800 | 6.1 | 131 | 279 | 255 | 4,335
Y | $\infty$ | 800 | 0.3 | 1 | 1 | 1 | 7
Table 2: Example verification results

###  3.5 Safety

In this example, we chose two soft invariants, which were both necessary and
sufficient to verify the property of interest. We could have defined further
soft invariant predicates though, without affecting the safety of the
analysis. There are three possible cases: properties that:

  1. 1.

are invariant and needed, but are logical consequences of others specified;

  2. 2.

are invariant but not needed; or

  3. 3.

are not invariant.

For the first case, we previously mentioned the possibility of defining the
predicates $\mathsf{if[line5,\mathsf{has[a]}]}$ and
$\mathsf{if[line5,\mathsf{has[b]}]}$. For the second case, we can look at
Table 1 and see the possibility of defining, e.g.

$\mathsf{if[idle,\mathsf{has[a]}]}(v)\iff\mathsf{is\\_{thread}}(v)\land(\mathsf{at[idle]}(v)\rightarrow\lnot\mathsf{has[a]}(v))\\\
\mathsf{if[line6,\mathsf{succ[a,b,next]}]}(v)\iff\mathsf{is\\_{thread}}(v)\land(\mathsf{at[line6]}(v)\rightarrow\mathsf{succ[a,b,next]}(v))$

However, these properties, whilst invariant, do not impact on the verification
of the property, so can be left out to avoid the overhead they would incur.
For the third case, we could for example “mistakenly” define

$\mathsf{if[line3,\mathsf{has[a]}]}(v)\iff\mathsf{is\\_{thread}}(v)\land(\mathsf{at[line3]}(v)\rightarrow\lnot\mathsf{has[a]}(v))$

This property is not invariant because of the loop, but defining it does not
assert the property in the system. When a thread performs an unsuccessful CAS
step at line 5, the resulting thread object would have
$\mathsf{if[line3,\mathsf{has[a]}]}$ false. Thus the single abstract thread
object would have this soft invariant unknown. There is some overhead incurred
maintaining the non-invariant predicate, but the analysis is otherwise
unaffected.

See Section 5 for more discussion on this topic.

##  4 Application

In previous work [7] we have used canonical abstraction to (attempt to) verify
linearizability [8] for three nonblocking concurrent data structure
algorithms. We had mixed success, due to the size of the abstract statespaces
exceeding memory resources. Here we demonstrate greatly improved results using
soft invariants.

###  4.1 Stack

The first algorithm is a stack, introduced by Treiber [14]. Versions of the
algorithm have been formally verified by many authors [4, 2, 7]; our analysis
adds to this and demonstrates the applicability of canonical abstraction.

####  4.1.1 Base Model

The model is described in detail elsewhere [6, 7] but contains 30 core
predicates, including 16 location predicates, and 19 instrumentation
predicates. Because TVLA does not implement partial order reduction, we
constructed two models — one with manually specified restrictions on thread
interleaving at certain locations, and one with full interleaving. We were
able to verify linearizability for the restricted interleaving model with
unbounded threads, list nodes and data values. For the model with full
interleaving, we were only able to verify linearizability with three threads —
with four or more threads the statespace was too large.

####  4.1.2 Soft Invariants

To identify the necessary and sufficient soft invariants, we used the same
approach we took to identify instrumentation predicates in the initial model —
a combination of inference and trial-and-error. We constructed tables
equivalent to Table 1 for the example, and for the restricted model we were
able to check this against the abstract statespace reported by TVLA.

We defined 12 soft invariants for the restricted interleaving model and 22 for
the full interleaving model — the lists and full discussion are omitted for
space reasons, but are available elsewhere [6, Chapter 8].

There are two notable points to be made, relating to more complex properties.
First, there were cases where the value of a predicate at a location depended
on the value of another predicate, so we defined conditional soft invariants
with structures like:

$\mathsf{if[X,Q]}(v)\iff\mathsf{is\\_{thread}}(v)\land(\mathsf{at[X]}(v)\rightarrow(\mathsf{P}(v)\rightarrow\mathsf{Q}(v)))\\\
\mathsf{if[X,R]}(v)\iff\mathsf{is\\_{thread}}(v)\land(\mathsf{at[X]}(v)\rightarrow(\lnot\mathsf{P}(v)\rightarrow\mathsf{R}(v)))$

Second, there was a more complicated property that was most easily addressed
by defining a new instrumentation predicate, and then defining a soft
invariant for the value of that new predicate. Adding another instrumentation
predicate to the model was extra work, but was an extension of the work
involved in identifying the instrumentation predicates in the inital model.

####  4.1.3 Results

We analysed the models using TVLA 3.0$\alpha$ on a machine with an Intel Core
2 3.0 GHz processor and 4 GB of RAM, running Java 1.6.0 on a 32-bit GNU/Linux
operating system. Tables 3 and 4 show the results of verifying linearizability
for both models, with and without soft invariants. The first three columns
note whether soft invariants were used, the bound on the number of threads and
how much RAM was allocated to TVLA; the remainder are numbers reported by
TVLA’s output.

Collapsing threads using soft invariants is very effective, with a 99.2%
reduction in the abstract statespace, and a 99.4% reduction in states stored,
for the restricted interleaving model.

|  | Heap |  | Ave | Max |  |
---|---|---|---|---|---|---|---
|  | Limit | Time | RAM | RAM | CA | Stored
SIs | Th. | (MB) | (s) | (MB) | (MB) | States | States
N | 3 | 800 | 102 | 173 | 336 | 440 | 6,493
N | $\infty$ | 2,048 | 1,934 | 849 | 1,603 | 1,910 | 74,056
Y | $\infty$ | 800 | 25 | 115 | 280 | 16 | 447
Table 3: Stack verification results with restricted interleaving

The collapsed threads approach is even more effective for the full
interleaving model, with the collapsed unbounded statespace 99.8% reduced
compared to the non-collapsed 3-thread statespace. This indicates that the
reduction compared to the non-collapsed unbounded statespace should be far
greater.

Compared to the results in Table 3, the collapsed unbounded model stores more
than twice the number of states, a great improvement over the non-collapsed
3-thread model, which stores nearly 23 times as many states. The amount of
memory used by TVLA only increases slightly, but the analysis takes nearly six
times as long. However, the analysis is still 13 times faster than the model
_with_ restricted interleaving and _without_ collapsed threads.

|  | Heap |  | Ave | Max |  |
---|---|---|---|---|---|---|---
|  | Limit | Time | RAM | RAM | CA | Stored
SIs | Th. | (MB) | (s) | (MB) | (MB) | States | States
N | 3 | 2,048 | 2,931 | 1,089 | 1,946 | 21,107 | 148,191
Y | $\infty$ | 800 | 141 | 149 | 295 | 32 | 932
Table 4: Stack verification results with full interleaving

###  4.2 Queues

The remaining algorithms are two nonblocking concurrent queue algorithms, the
original introduced by Michael and Scott [12] (“MS queue”), and a modified
version by Doherty et al. [5] (“DGLM queue”); the latter authors provided the
first formal verification of linearizability.

####  4.2.1 Base Models

These algorithms have a similar singly-linked-list structure, so construction
of the canonical abstraction models was relatively straightforward — most of
the core and instrumentation predicates were able to be copied from the stack
model. The models were larger, with 44 core predicates, including 26 thread
locations, and 22 instrumentation predicates.

As with the stack, we constructed two models for each queue — one with
manually restricted interleaving and one with full interleaving.

Previously [7], we were able to verify linearizability for the restricted
interleaving models with two threads, but not three. For the models with full
interleaving, even when bounded to two threads the statespace was too large
for the memory available.

####  4.2.2 Soft Invariants

We followed a similar process as for the stack, and defined 25–57 soft
invariants. The lists and full discussion are omitted for space reasons, but
are available elsewhere [6, Chapter 8]. Table 5 shows the number of distinct
interleaving thread configurations and the number of defined soft invariants
for each component of the two algorithms — idle state (in between operations),
enqueue operation (shared by both), the MS and DGLM dequeue operations, and
then the two algorithms in total.

| Restricted | Full
---|---|---
| locs | SIs | locs | SIs
idle | 1 | 1 | 1 | 1
enqueue | 5 | 11 | 10 | 18
dequeueM | 5 | 23 | 12 | 38
dequeueD | 5 | 13 | 12 | 24
MS | 11 | 35 | 23 | 57
DGLM | 11 | 25 | 23 | 43
Table 5: Interleaving location and soft invariant counts for queue models

As with the stack, we defined conditional soft invariants. We also had to
define a new instrumentation predicate for the MS queue, but for a different
property than the stack.

####  4.2.3 Results

For both the restricted and full interleaving models, we were able to verify
linearizability for unbounded threads, list nodes and data values, with
relatively small resources — a considerable improvement over the models
without soft invariants. Tables 6 and 7 show the results.

|  |  | Heap |  | Ave | Max |  |
---|---|---|---|---|---|---|---|---
|  |  | Limit | Time | RAM | RAM | CA | Stored
Deq | SIs | Th. | (MB) | (s) | (MB) | (MB) | States | States
MS | N | 2 | 800 | 393 | 260 | 476 | 3,770 | 24,271
MS | Y | $\infty$ | 800 | 81 | 151 | 309 | 12 | 523
DGLM | N | 2 | 800 | 83 | 189 | 354 | 1,506 | 10,746
DGLM | Y | $\infty$ | 800 | 216 | 181 | 310 | 14 | 591
Table 6: Queue verification results with restricted interleaving |  |  | Heap |  | Ave | Max |  |
---|---|---|---|---|---|---|---|---
|  |  | Limit | Time | RAM | RAM | CA | Stored
Deq | SIs | Th. | (MB) | (s) | (MB) | (MB) | States | States
MS | Y | $\infty$ | 800 | 3,109 | 304 | 727 | 96 | 4,148
DGLM | Y | $\infty$ | 800 | 2,887 | 290 | 731 | 112 | 4,604
Table 7: Queue verification results with full interleaving

An interesting observation is that for the statespaces of the non-collapsed
models, the MS queue is much larger — 2.5 times larger with a bound of two
threads. For the statespaces of the collapsed models though, the DGLM queue is
larger, by 17%. The DGLM queue allows the Head and Tail pointers to “cross”
[5], unlike the MS queue, which results in more canonically abstract list
configurations, and accounts for the collapsed model differences. In the non-
collapsed models, the MS queue has more canonical thread objects — which is
related to the larger number of soft invariants needed — and this becomes a
larger factor than the differing number of list structures.

##  5 Choosing Soft Invariants

Collapsing thread objects with soft invariants provides an exponential
reduction in the size of the statespace, as evidenced by the results presented
so far. Extending models with soft invariants requires extra manual effort
though, so some discussion on the subject is warranted.

Ultimately, soft invariants do not add anything technically new to canonical
abstraction — they are “just” instrumentation predicates — so their discovery
and definition is an extension of the effort necessary for these anyway. In
the basic case, a spurious error is reported, which indicates that the
abstraction is too coarse. Examining the output, the user can infer what
property is needed to be preserved, and then define an instrumentation
predicate to refine the abstraction.

For the models we have looked at, defining soft invariants was relatively
little extra effort, as they mostly built on the effort of determining the
thread instrumentation predicates. Consider the example system from Section 3
— the two soft invariants require an understanding of the values and mutual
relationship of the $\mathit{a}$ and $\mathit{b}$ fields at lines 4 and 5. But
those facts had already been determined in order to define the instrumentation
predicates $\mathsf{has[a]}$, $\mathsf{has[b]}$ and $\mathsf{succ[a,b,next]}$.
Constructing a model with collapsed threads initially — as opposed to
extending an existing model — may make determining soft invariants less
straightforward. In these cases we expect that over defining the soft
invariants may be effective.

###  5.1 Over Defining Soft Invariants

The amount of effort needed to identify soft invariants could be mitigated,
especially for unfamiliar systems, by exploiting the “soft” nature of soft
invariants and over defining them. As mentioned in Section 3.5, if a property
is not actually invariant, there is no consequence for the abstract
statespace, it just adds some overhead to the analysis. Thus we can define a
range of soft invariants, many of which may not be necessary or even correct.

To confirm and quantify this idea, we modified the stack model with full
interleaving from Section 4.1 with soft invariants for every thread predicate.
For every thread predicate $\mathsf{p}$, and every location _loc_ , we defined
two soft invariants:

$\mathsf{if[loc,\mathsf{p}]}(v)\iff\mathsf{is\\_{thread}}(v)\land(\mathsf{at[loc]}(v)\rightarrow\mathsf{p}(v))\\\
\mathsf{nif[loc,\mathsf{p}]}(v)\iff\mathsf{is\\_{thread}}(v)\land(\mathsf{at[loc]}(v)\rightarrow\lnot\mathsf{p}(v))\\\
$

We kept the six conditional soft invariants, distinguishing them with a ‘c’
prefix.

Table 8 shows the results of the analysis, with the first line repeated from
Table 4. The canonically abstract statespace is unchanged with 32 states,
though fewer intermediate states are stored. Memory use increases and the time
roughly doubles.

| Heap |  | Ave | Max |  |
---|---|---|---|---|---|---
Over | Limit | Time | RAM | RAM | CA | Stored
def. | (MB) | (s) | (MB) | (MB) | States | States
N | 800 | 141 | 149 | 295 | 32 | 932
Y | 800 | 278 | 202 | 338 | 32 | 726
Table 8: Stack verification results with extra soft invariants

These results show that the tradeoff between analysis efficiency and
determining a minimal set of soft invariants is likely to be a practical one.
Here, at least half of the properties defined are not invariant, with some
being false in the initial state, and the increases in time and memory are
acceptable.

##  6 Related Work

The closest work to ours is by Manevich et al. [10] and Berdine et al. [2],
who also attempt to address the state explosion problem caused by canonical
thread objects. Their approaches are orthogonal to ours, as they attempt to
improve the storage of states by decomposing each state in to thread
components and storing each unique component only once. They verify the same
algorithms that we do, but it is difficult to directly compare results, as
they extend previous work [1] that uses an additional technique (delta heap
abstraction) to abstract lists for verifying linearizability, and which does
not abstract threads; we extend previous work [7] that verifies
linearizability for unbounded threads using canonical abstraction alone.
Nonetheless, their approach reduces, but does not remove, the effect of
canonical thread permutations, so our approach may scale better for larger
systems.

##  7 Conclusions

We have presented a novel approach to canonical abstraction, which
exponentially reduces the statespace size by collapsing all thread objects in
a state into a single summary object. This has allowed us to verify
linearizability for three concurrent data structure algorithms with unbounded
threads, list lengths and data values, where previously the statespaces were
impractically large.

The coarse abstraction on threads is refined by defining “soft invariant”
instrumentation predicates, which preserve properties of threads at specific
locations. The identification of sufficient soft invariants is currently a
manual process. However, the soft invariants are safe to define — correctness
is not affected if the properties are not actually invariant — so they can be
over-defined to reduce the manual effort. Identifying the minimal set, or even
a likely superset, may well be a problem amenable to automation.

This approach should be applicable to any multi-process canonical abstraction
model. In fact, there is nothing inherently process/thread-specific about
these instrumentation predicates, so the same idea could be applied to other
types of models to reduce the abstract statespace.

## References

  * [1] Amit, D., Rinetzky, N., Reps, T., Sagiv, M., Yahav, E.: Comparison under abstraction for verifying linearizability. In: Damm, W., Hermanns, H. (eds.) Proceedings of the 19th International Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 4590, pp. 477–490. Springer (2007)
  * [2] Berdine, J., Lev-Ami, T., Manevich, R., Ramalingam, G., Sagiv, M.: Thread quantification for concurrent shape analysis. In: Gupta, A., Malik, S. (eds.) Proceedings of the 20th International Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 5123, pp. 399–413. Springer (2008)
  * [3] Bogudlov, I., Lev-Ami, T., Reps, T., Sagiv, M.: Revamping TVLA: Making parametric shape analysis competitive. In: Damm, W., Hermanns, H. (eds.) Proceedings of the 19th International Conference on Computer Aided Verification (CAV). Lecture Notes in Computer Science, vol. 4590, pp. 221–225. Springer (2007)
  * [4] Colvin, R., Doherty, S., Groves, L.: Verifying concurrent data structures by simulation. In: Derrick, J., Boiten, E.A. (eds.) Proceedings of the Refinement Workshop. Electronic Notes in Theoretical Computer Science, vol. 137.2, pp. 93–110. Elsevier (2005)
  * [5] Doherty, S., Groves, L., Luchangco, V., Moir, M.: Formal verification of a practical lock-free queue algorithm. In: de Frutos-Escrig, D., Núñez, M. (eds.) Proceedings of the 24th International Conference on Formal Techniques for Networked and Distributed Systems (FORTE). Lecture Notes in Computer Science, vol. 3235, pp. 97–114. Springer (2004)
  * [6] Friggens, D.: On the Use of Model Checking for the Bounded and Unbounded Verification of Nonblocking Concurrent Data Structures. Ph.D. thesis, Victoria University of Wellington (2013)
  * [7] Friggens, D., Groves, L.: Shape predicates allow unbounded verification of linearizability using canonical abstraction. In: Thomas, B.H., Parry, D. (eds.) Proceedings of the 37th Australasian Computer Science Conference (ACSC). Conferences in Research and Practice in Information Technology, vol. 147, pp. 49–56. Australian Computer Society (2014)
  * [8] Herlihy, M.P., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems 12(3), 463–492 (Jul 1990)
  * [9] Lev-Ami, T., Sagiv, M.: TVLA: A system for implementing static analyses. In: Palsberg, J. (ed.) Proceedings of the 7th International Symposium on Static Analysis (SAS). Lecture Notes in Computer Science, vol. 1824, pp. 280–301. Springer (2000)
  * [10] Manevich, R., Lev-Ami, T., Sagiv, M., Ramalingam, G., Berdine, J.: Heap decomposition for concurrent shape analysis. In: Alpuente, M., Vidal, G. (eds.) Proceedings of the 15th International Symposium on Static Analysis (SAS). Lecture Notes in Computer Science, vol. 5079, pp. 363–377. Springer (2008)
  * [11] Manevich, R., Sagiv, M., Ramalingam, G., Field, J.: Partially disjunctive heap abstraction. In: Giacobazzi, R. (ed.) Proceedings of the 11th International Symposium on Static Analysis (SAS). Lecture Notes in Computer Science, vol. 3148, pp. 265–279. Springer (2004)
  * [12] Michael, M.M., Scott, M.L.: Non-blocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. Journal of Parallel and Distributed Computing 51(1), 1–26 (1998)
  * [13] Sagiv, M., Reps, T., Wilhelm, R.: Parametric shape analysis via 3-valued logic. ACM Transactions on Programming Languages and Systems 24(3), 217–298 (2002)
  * [14] Treiber, R.K.: Systems programming: Coping with parallelism. Tech. Rep. RJ 5118, IBM Almaden Research Centre (Apr 1986)
  * [15] Yahav, E., Sagiv, M.: Verifying safety properties of concurrent heap-manipulating programs. ACM Transactions on Programming Languages and Systems 32(5) (2010), article 18