Search

Hoare-style inference rules for program constructs permit the copying of expressions and tests from program text into logical contexts. It is known that this requires care even for sequential programs but further issues arise for concurrent programs because of potential interference to the values of variables. The "rely-guarantee" approach does tackle the issue of recording acceptable interference and offers a way to provide safe inference rules. This paper shows how the algebraic presentation of rely-guarantee ideas can clarify and formalise the conditions for safely re-using expressions and tests from program text in logical contexts for reasoning about programs., Comment: 17 pages, 1 figure

Developers of low-level systems code providing core functionality for operating systems and kernels must address hardware-level features of modern multicore architectures. A particular feature is pipelined "out-of-order execution" of the code as written, the effects of which are typically summarised as a "weak memory model" - a term which includes further complicating factors that may be introduced by compiler optimisations. In many cases, the nondeterminism inherent in weak memory models can be expressed as micro-parallelism, i.e., parallelism within threads and not just between them. Fortunately Jones' rely/guarantee reasoning provides a compositional method for shared-variable concurrency, whether that be in terms of communication between top-level threads or micro-parallelism within threads. In this paper we provide an in-depth verification of the lock algorithm used in the seL4 microkernel, using rely/guarantee to handle both interthread communication as well as micro-parallelism introduced by weak memory models.

Competing and intertwined orders are ubiquitous in strongly correlated electron systems, such as the charge, spin, and superconducting orders in the high-Tc cuprates. Recent scanning tunneling microscopy (STM) measurements provide evidence for a charge density wave (CDW) that coexists with superconductivity in the heavy Fermion metal UTe2. This CDW persists up to at least 7.5 K and, as a CDW breaks the translational symmetry of the lattice, its disappearance is necessarily accompanied by thermodynamic phase transition. Here, we report high-precision thermodynamic measurements of the elastic moduli of UTe2. We observe no signature of a phase transition in the elastic moduli down to a level of 1 part in 10^7, strongly implying the absence of bulk CDW order in UTe2. We suggest that the CDW and associated pair density wave (PDW) observed by STM may be confined to the surface of UTe2.

The concurrent refinement algebra has been developed to support rely/guarantee reasoning about concurrent programs. The algebra supports atomic commands and defines parallel composition as a synchronous operation, as in Milner's SCCS. In order to allow specifications to be combined, the algebra also provides a weak conjunction operation, which is also a synchronous operation that shares many properties with parallel composition. The three main operations, sequential composition, parallel composition and weak conjunction, all respect a (weak) quantale structure over a lattice of commands. Further structure involves combinations of pairs of these operations: sequential/parallel, sequential/weak conjunction and parallel/weak conjunction, each pair satisfying a weak interchange law similar to Concurrent Kleene Algebra. Each of these pairs satisfies a common biquantale structure. Additional structure is added via compatible sets of commands, including tests, atomic commands and pseudo-atomic commands. These allow stronger (equality) interchange and distributive laws. This paper describes the result of restructuring the algebra to better exploit these commonalities. The algebra is implemented in Isabelle/HOL.

Specifications of significant systems can be made short and perspicuous by using abstract data types; data reification can provide a clear, stepwise, development history of programs that use more efficient concrete representations. Data reification (or "refinement") techniques for sequential programs are well established. This paper applies these ideas to concurrency, in particular, an algebraic theory supporting rely-guarantee reasoning about concurrency. A concurrent version of the Galler-Fischer equivalence relation data structure is used as an example.

Distributive laws are important for algebraic reasoning in arithmetic and logic. They are equally important for algebraic reasoning about concurrent programs. In existing theories such as Concurrent Kleene Algebra, only partial correctness is handled, and many of its distributive laws are weak, in the sense that they are only refinements in one direction, rather than equalities. The focus of this paper is on strengthening our theory to support the proof of strong distributive laws that are equalities, and in doing so come up with laws that are quite general. Our concurrent refinement algebra supports total correctness by allowing both finite and infinite behaviours. It supports the rely/guarantee approach of Jones by encoding rely and guarantee conditions as rely and guarantee commands. The strong distributive laws may then be used to distribute rely and guarantee commands over sequential compositions and into (and out of) iterations. For handling data refinement of concurrent programs, strong distributive laws are essential., Comment: 20 pages, 1 Figure

Uranium ditelluride (UTe$_2$) is the strongest contender to date for a $p$-wave superconductor in bulk form. Here we perform a spectroscopic study of the ambient pressure superconducting phase of UTe$_2$, measuring conductance through point-contact junctions formed by metallic contacts on different crystalline facets down to 250 mK and up to 18 T. Fitting a range of qualitatively varying spectra with a Blonder-Tinkham-Klapwijk(BTK) model for $p$-wave pairing, we can extract gap amplitude and interface barrier strength for each junction. We find good agreement with the data for a $p_y$ -wave gap function with amplitude in 0.26 $\pm$ 0.06 meV. Our work provides spectroscopic evidence for a gap structure consistent with the proposed spin-triplet pairing in the superconducting state of UTe$_2$.

The superconducting state of the heavy-fermion metal UTe$_2$ has attracted considerable interest because of evidence for spin-triplet Cooper pairing and non-trivial topology. Progress on these questions requires identifying the presence or absence of nodes in the superconducting gap function and their dimension. In this article we report a comprehensive study of the influence of disorder on the thermal transport in the superconducting state of UTe$_2$. Through detailed measurements of the magnetic field dependence of the thermal conductivity in the zero-temperature limit, we obtain clear evidence for the presence of point nodes in the superconducting gap for all samples with transition temperatures ranging from 1.6~K to 2.1~K obtained by different synthesis methods, including a refined self-flux method. This robustness implies the presence of symmetry-imposed nodes throughout the range studied, further confirmed via disorder-dependent calculations of the thermal transport in a model with a single pair of nodes. In addition to capturing the temperature dependence of the thermal conductivity up to $T_c$, this model allows us to limit the possible locations of the nodes, suggesting a B$_{1u}$ or B$_{2u}$ symmetry for the superconducting order parameter. Additionally, comparing the new, ultra-high conductivity samples to older samples reveals a crossover between a low-field and a high field regime at a single value of the magnetic field in all samples. In the high field regime, the thermal conductivity at different disorder levels differ from each other by a simple offset, suggesting that some simple principle determines the physics of the mixed state, a fact which may illuminate trends observed in other clean nodal superconductors.

This paper introduces Concurrent Valuation Algebras (CVAs), a novel extension of ordered valuation algebras (OVAs). CVAs include two combine operators representing parallel and sequential products, adhering to a weak exchange law. This development offers theoretical and practical benefits for the specification and modelling of concurrent and distributed systems. As a presheaf on a space of domains, CVAs enable localised specifications, supporting modularity, compositionality, and the ability to represent large and complex systems. Furthermore, CVAs align with lattice-based refinement reasoning and are compatible with established methodologies such as Hoare and Rely-Guarantee logics. The flexibility of CVAs is explored through three trace models, illustrating distinct paradigms of concurrent/distributed computing, interrelated by morphisms. The paper also highlights the potential to incorporate a powerful local computation framework from valuation algebras for model checking in concurrent and distributed systems. The foundational results presented have been verified with the proof assistant Isabelle/HOL., Comment: 26 pages

Reentrant superconductivity is a phenomenon in which the destructive effects of magnetic field on superconductivity are mitigated, allowing a zero-resistance state to survive under conditions that would otherwise destroy it. Typically, the reentrant superconducting region derives from a zero-field parent superconductor. Here, we show that in specifically-prepared UTe$_2$ crystals, extremely large magnetic field gives rise to an unprecedented high field superconductor that lacks a zero-field parent phase. This orphan superconductivity exists at fields between 37 T and 52 T, over a smaller angular range than observed in superconducting UTe$_2$. The stability of field-induced orphan superconductivity is a challenge to existing theoretical explanations, and underscores the likelihood of a field-induced modification of the electronic structure of UTe$_2$., Comment: 10 pages, 3 figures

Resonant ultrasound spectroscopy (RUS) is a powerful technique for measuring the full elastic tensor of a given material in a single experiment. Previously, this technique was limited to regularly-shaped samples such as rectangular parallelepipeds, spheres, and cylinders. We demonstrate a new method for determining the elastic moduli of irregularly-shaped samples, extending the applicability of RUS to a much larger set of materials. We apply this new approach to the recently-discovered unconventional superconductor UTe$_2$ and provide its elastic tensor at both 300 and 4 kelvin., Comment: 18 pages, 3 figures, 12 tables

Our objective is to formally verify the correctness of the hundreds of expression optimization rules used within the GraalVM compiler. When defining the semantics of a programming language, expressions naturally form abstract syntax trees, or, terms. However, in order to facilitate sharing of common subexpressions, modern compilers represent expressions as term graphs. Defining the semantics of term graphs is more complicated than defining the semantics of their equivalent term representations. More significantly, defining optimizations directly on term graphs and proving semantics preservation is considerably more complicated than on the equivalent term representations. On terms, optimizations can be expressed as conditional term rewriting rules, and proofs that the rewrites are semantics preserving are relatively straightforward. In this paper, we explore an approach to using term rewrites to verify term graph transformations of optimizations within the GraalVM compiler. This approach significantly reduces the overall verification effort and allows for simpler encoding of optimization rules., Comment: 14 pages, 7 figures, to be published in CPP2023

We want to verify the correctness of optimization phases in the GraalVM compiler, which consist of many thousands of lines of complex Java code performing sophisticated graph transformations. We have built high-level models of the data structures and operations of the code using the Isabelle/HOL theorem prover, and can formally verify the correctness of those high-level operations. But the remaining challenge is: how can we be sure that those high-level operations accurately reflect what the Java is doing? This paper addresses that issue by applying several different kinds of differential testing to validate that the formal model and the Java code have the same semantics. Many of these validation techniques should be applicable to other projects that are building formal models of real-world code., Comment: 8 pages, 6 figures

We present a lattice of distributed program specifications, whose ordering represents implementability/refinement. Specifications are modelled by families of subsets of relative execution traces, which encode the local orderings of state transitions, rather than their absolute timing according to a global clock. This is to overcome fundamental physical difficulties with synchronisation. The lattice of specifications is assembled and analysed with several established mathematical tools. Sets of nondegenerate cells of a simplicial set are used to model relative traces, presheaves model the parametrisation of these traces by a topological space of variables, and information algebras reveal novel constraints on program correctness. The latter aspect brings the enterprise of program specification under the widening umbrella of contextual semantics introduced by Abramsky et al. In this model of program specifications, contextuality manifests as a failure of a consistency criterion comparable to Lamport's definition of sequential consistency. The theory of information algebras also suggests efficient local computation algorithms for the verification of this criterion. The novel constructions in this paper have been verified in the proof assistant Isabelle/HOL., Comment: 22 pages

The optimization phase of a compiler is responsible for transforming an intermediate representation (IR) of a program into a more efficient form. Modern optimizers, such as that used in the GraalVM compiler, use an IR consisting of a sophisticated graph data structure that combines data flow and control flow into the one structure. As part of a wider project on the verification of optimization passes of GraalVM, this paper describes a semantics for its IR within Isabelle/HOL. The semantics consists of a big-step operational semantics for data nodes (which are represented in a graph-based static single assignment (SSA) form) and a small-step operational semantics for handling control flow including heap-based reads and writes, exceptions, and method calls. We have proved a suite of canonicalization optimizations and conditional elimination optimizations with respect to the semantics., Comment: 16 pages, 8 figures, to be published to ATVA 2021

This paper presents a theory for the refinement of shared-memory concurrent algorithms from specifications. We augment pre and post condition specifications with Jones' rely and guarantee conditions, all of which are encoded as commands within a wide-spectrum language. Program components are specified using either partial or total correctness versions of postcondition specifications. Operations on shared data structures and atomic machine operations (e.g. compare-and-swap) are specified using an atomic specification command. All the above constructs are defined in terms of a simple core language, based on a small set of primitive commands and a handful of operators. A comprehensive set of laws for refining such specifications to code is derived in the theory. The approach supports fine-grained concurrency, avoiding atomicity assumptions on expression evaluation and assignment commands. The theory has been formalised in Isabelle/HOL, and the refinement laws and supporting lemmas have been proven in Isabelle/HOL.

The presence of a quantum critical point separating two distinct zero-temperature phases is thought to underlie the `strange' metal state of many high-temperature superconductors. The nature of this quantum critical point, as well as a description of the resulting strange metal, are central open problems in condensed matter physics. In large part, the controversy stems from the lack of a clear broken symmetry to characterize the critical phase transition, and this challenge is no clearer than in the example of the unconventional superconductor CeCoIn$_5$. Through Hall effect and Fermi surface measurements of CeCoIn$_5$, in comparison to ab initio calculations, we find evidence for a critical point that connects two Fermi surfaces with different volumes without apparent symmetry-breaking, indicating the presence of a transition that involves an abrupt localization of one sector of the charge degrees of freedom. We present a model for the anomalous electrical Hall resistivity of this material based on the conductivity of valence charge fluctuations., Comment: 17 pages, 4 figures, Supplement included

A central problem in modern condensed matter physics is the understanding of materials with strong electron correlations. Despite extensive work, the essential physics of many of these systems is not understood and there is very little ability to make predictions in this class of materials. In this manuscript we share our personal views on the major open problems in the field of correlated electron systems. We discuss some possible routes to make progress in this rich and fascinating field. This manuscript is the result of the vigorous discussions and deliberations that took place at Johns Hopkins University during a three-day workshop January 27, 28, and 29, 2020 that brought together six senior scientists and 46 more junior scientists. Our hope, is that the topics we have presented will provide inspiration for others working in this field and motivation for the idea that significant progress can be made on very hard problems if we focus our collective energies., Comment: 55 pages, 19 figures

The scaling of $H$-linear magnetoresistance in field and temperature was measured in under-doped (x = 0.19) and optimally-doped (x=0.31)~BaFe$_2$(As$_{1-x}$P$_x$)$_2$. We analyze the data based on an orbital model in the presence of strongly anisotropic quasiparticle spectra and scattering time due to antiferromagnetism. The magnetoresistance is dominated by the properties of small regions of the Fermi surface called `hot spots' where antiferromagnetic excitations induce a large quasiparticle scattering rate. Approximate temperature-magnetic field scaling relations are derived and shown to be consistent with the experimental data. We argue that these results link the origin of linear-in-temperature resistivity to hot spots arising from an antiferromagnetic critical point, and magnetoresistance measurements provide a route to quantify this link., Comment: 9 pages, 4 figures, Supplemental Material available on request

The search for a material platform for topological quantum computation has recently focused on unconventional superconductors. Such material systems, where the superconducting order parameter breaks a symmetry of the crystal point group, are capable of hosting novel phenomena, including emergent Majorana quasiparticles. Unique among unconventional superconductors is the recently discovered UTe2, where spin-triplet superconductivity emerges from a paramagnetic normal state. Although UTe2 could be considered a relative of a family of known ferromagnetic superconductors, the unique crystal structure of this material and experimentally suggested zero Curie temperature pose a great challenge to determining the symmetries, magnetism, and topology underlying the superconducting state. These emergent properties will determine the utility of UTe2 for future spintronics and quantum information applications. Here, we report observations of a non-zero polar Kerr effect and of two transitions in the specific heat upon entering the superconducting state, which together show that the superconductivity in UTe2 is characterized by an order parameter with two components that breaks time reversal symmetry. These data allow us to place firm constraints on the symmetries of the order parameter, which strongly suggest that UTe2 is a Weyl superconductor that hosts chiral Fermi arc surface states.

Many unconventional superconductors exhibit a common set of anomalous charge transport properties that characterize them as `strange metals', which provides hope that there is single theory that describes them. However, model-independent connections between the strange metal and superconductivity have remained elusive. In this letter, we show that the Hall effect of the unconventional superconductor BaFe$_2$(As$_{1-x}$P$_x$)$_2$ contains an anomalous contribution arising from the correlations within the strange metal. This term has a distinctive dependence on magnetic field, which allows us to track its behavior across the doping-temperature phase diagram, even under the superconducting dome. These measurements demonstrate that the strange metal Hall component emanates from a quantum critical point and, in the zero temperature limit, decays in proportion to the superconducting critical temperature. This creates a clear and novel connection between quantum criticality and superconductivity, and suggests that similar connections exist in other strange metal superconductors., Comment: 11 pages, 3 Figures, Supplementary Information on request

In a Kondo lattice system, suppression of effective Kondo coupling leads to the breakdown of the heavy-electron metal and a change in the electronic structure. Spin triplet superconductivity in the Kondo lattice UTe2 appears to be associated with spin fluctuations originating from incipient ferromagnetic order. Here we show clear evidence of twofold enhancement of spin-triplet superconductivity near the pressure-driven suppression of the Kondo coherence, implying that superconductivity is strengthened by the affiliated growth of both spin and charge fluctuations. The coherent Kondo state discontinuously transitions to ferromagnetic order at higher pressures. Application of magnetic field tunes the system back across a first-order phase boundary. Straddling this phase boundary, we find another example of reentrant superconductivity in UTe2. In addition to spin fluctuations associated with ferromagnetism, our results show that a Kondo-driven Fermi surface instability may be playing a role in stabilizing spin triplet superconductivity.

The rely/guarantee approach of Jones extends Hoare logic with rely and guarantee conditions in order to allow compositional reasoning about shared-variable concurrent programs. This paper focuses on localisation in the context of rely/guarantee concurrency in order to support local variables. Because we allow the body of a local variable block to contain component processes that run in parallel, the approach needs to allow variables local to a block to become shared variables of its component parallel processes. To support the mechanisation of the rely/guarantee approach, we have developed a synchronous concurrent refinement algebra. Its foundation consists of a small set of primitive commands plus a small set of primitive operators from which all remaining constructs are defined. To support local variables we add a primitive localisation operator to our algebra that is used to define local variable blocks. From this we can prove properties of localisation, including its interaction with rely and guarantee conditions., Comment: 16 pages

The purpose of this paper is to address some of the challenges of formally specifying components of shared-memory concurrent programs. The focus is to provide an abstract specification of a component that is suitable for use both by clients of the component and as a starting point for refinement to an implementation of the component. We present some approaches to devising specifications, investigating different forms suitable for different contexts. We examine handling atomicity of access to data structures, blocking operations and progress properties, and transactional operations that may fail and need to be retried., Comment: In Proceedings Refine 2018, arXiv:1810.08739

The Bardeen-Cooper-Schrieffer mechanism for superconductivity is a triumph of the theory of many-body systems. Implicit in its formulation is the existence of long-lived (quasi)particles, originating from the electronic building blocks of the materials, which interact to form Cooper pairs that move coherently in lock-step. The challenge of unconventional superconductors is that it is not only unclear what the nature of the interactions are, but whether the familiar quasi-particles that form a superconducting condensate even exist. In this work, we reveal, by the study of applied magnetic field in electronically diluted materials, that the metallic properties of the unconventional superconductor CeCoIn$_5$ are determined by the degree of quantum entanglement that (Kondo) hybridizes local and itinerant electrons. This work suggests that the properties of the strange metallic state are a reflection of the disentanglement of the many-body state into the underlying electronic building blocks of the system itself., Comment: 16 pages including 5 Figures and Supplemental Materials

Theories of the strange metal, the parent state of many high temperature superconductors, invariably involve an important role for correlations in the spin and charge degrees of freedom. The most distinctive signature of this state in the charge transport sector is a resistance that varies linearly in temperature, but this phenomenon does not clearly point to one mechanism as temperature is a scalar quantity that influences every possible mechanism for momentum relaxation. In a previous work we identified an unusual scaling relationship between magnetic field and temperature in the in-plane resistivity of the unconventional superconductor BaFe$_2$(As$_{1-x}$P$_{x}$)$_2$, providing an opportunity to use the vector nature of the magnetic field to acquire additional clues about the mechanisms responsible for scattering in the strange metal state. Here we extend this work by investigating other components of the conductivity tensor under different orientations of the magnetic field. We find that the scaling phenomenon involves only the out-of-plane component of the magnetic field and is, strikingly, independent of the direction of the applied current. This suggests that the origin of the strange magnetotransport is in the action of the magnetic field on the correlated behavior of spin and charge degrees of freedom, rather than on the simple cyclotron motion of individual quasiparticles., Comment: 5 pages, 3 figures

Concurrent program refinement algebra provides a suitable basis for supporting mechanised reasoning about shared-memory concurrent programs in a compositional manner, for example, it supports the rely/guarantee approach of Jones. The algebra makes use of a synchronous parallel operator motivated by Aczel's trace model of concurrency and with similarities to Milner's SCCS. This paper looks at defining a form of fairness within the program algebra. The encoding allows one to reason about the fair execution of a single process in isolation as well as define fair-parallel in terms of a base parallel operator, of which no fairness properties are assumed. An algebraic theory to support fairness and fair-parallel is developed., Comment: Formal Methods 2018