††thanks: These authors contributed equally to this work.††thanks: These
authors contributed equally to this work.

# Learning dynamical behaviors in physical systems

Rituparno Mandal  James Franck Institute, The University of Chicago, Chicago,
IL 60637  Rosalind Huang  James Franck Institute, The University of Chicago,
Chicago, IL 60637  Department of Physics, The University of Chicago, Chicago,
IL 60637  Michel Fruchart  Gulliver, ESPCI Paris, Université PSL, CNRS, Paris,
France  Pepijn G. Moerman  Chemical Engineering and Chemistry, Eindhoven
University of Technology, Eindhoven 5612 AP, Netherlands  Suriyanarayanan
Vaikuntanathan  James Franck Institute, The University of Chicago, Chicago, IL
60637  Department of Chemistry, University of Chicago, Chicago, Illinois
60637, USA  Arvind Murugan<EMAIL_ADDRESS>Department of Physics, The
University of Chicago, Chicago, IL 60637  Vincenzo Vitelli
<EMAIL_ADDRESS>James Franck Institute, The University of Chicago,
Chicago, IL 60637  Department of Physics, The University of Chicago, Chicago,
IL 60637  Kadanoff Center for Theoretical Physics, The University of Chicago,
Chicago, Illinois 60637, USA

###### Abstract

Physical learning is an emerging paradigm in science and engineering whereby
(meta)materials acquire desired macroscopic behaviors by exposure to examples.
So far, it has been applied to static properties such as elastic moduli and
self-assembled structures encoded in minima of an energy landscape. Here, we
extend this paradigm to dynamic functionalities, such as motion and shape
change, that are instead encoded in limit cycles or pathways of a dynamical
system. We identify the two ingredients needed to learn time-dependent
behaviors irrespective of experimental platforms: (i) learning rules with time
delays and (ii) exposure to examples that break time-reversal symmetry during
training. After providing a hands-on demonstration of these requirements using
programmable LEGO toys, we turn to realistic particle-based simulations where
the training rules are not programmed on a computer. Instead, we elucidate how
they emerge from physico-chemical processes involving the causal propagation
of fields, like in recent experiments on moving oil droplets with chemotactic
signalling. Our trainable particles can self-assemble into structures that
move or change shape on demand, either by retrieving the dynamic behavior
previously seen during training, or by learning on the fly. This rich
phenomenology is captured by a modified Hopfield spin model amenable to
analytical treatment. The principles illustrated here provide a step towards
von Neumann’s dream of engineering synthetic living systems that adapt to the
environment.

Biological systems adapt to their environment by changing their behavior in
response to past events: once bitten, twice shy. In the brain, for instance,
neurons wire together (i.e. increase their interactions) if they fire
together. But the ability to learn is not limited to sentient or animate
beings: it can emerge in natural physical processes in which interactions
increase between entities that happen to be correlated, a paradigm known as
Hebbian learning [1, 1]. Inanimate systems too can evolve their microscopic
interactions to effectively learn desired behaviors after experiencing
examples of that behavior, a phenomenon often referred to as physical learning
[2, 3, 4]. So far, physical learning has been applied to static behaviors,
such as elastic responses or self-assembled shapes and particles
configurations characteristic of equilibrium systems [5, 6, 7, 8, 9, 10, 11,
12, 9, 13, 14, 15, 10, 16, 17]. Such static targets are encoded in fixed
points, i.e. local minima of an energy landscape.

In this article, we ask: how can a physical system learn time-dependent
functionalities like pathways, trajectories, or dynamic states such as limit
cycles? The essence of our approach is conceptualized schematically in Fig. 1:
an external operator first imposes a dynamic state, that breaks time-reversal
symmetry, on the system during a period called training (e.g. moves the wings
of the origami bird in Fig. 1a). Next, during a period that we call retrieval,
the desired time-dependent state (e.g. wings flapping) can be recovered as the
system evolves according to asymmetric microscopic interactions learned during
training (Fig. 1b).

Fig. 1:  Learning dynamic states. Panels a-b show the general strategy: during
a training period (panel a), a time-dependent state is imposed on the system.
This is pictured by an origami bird whose wings are periodically moved by an
external agent. After training (panel b), a retrieval period during which the
physical system evolves under the learned dynamics should lead to a dynamic
state, such as a limit cycle, that matches the training as best as possible.
(c-d) Demonstration of the training and retrieval procedure using a
programmable LEGO toy (see also Movie 1). The angular positions
$\theta_{1}(t)$ and $\theta_{2}(t)$ of two motors are imposed by hand during a
training phase (panel c), during which couplings $J_{12}$ and $J_{21}$ between
the motors are learned. Dynamics during retrieval, with fixed couplings
$J_{ij}$, can produce fixed points as well as dynamic states where the angles
constantly change (panel d). (e-f) We sketch how this learning and retrieval
procedure can be implemented in a model physical system composed of moving oil
droplets that interact through Marangoni flows [18, 19, 20, 21, 22, 23, 24,
25, 26, 27]. The droplets are composed of a mixture of an oil that can easily
be solubilized in water by micelles (in red) and a less soluble oil (in blue).
During training (panel e), two droplets with identical compositions (in
purple) are driven by an external force (e.g. optical tweezers) at high enough
Péclet number, leading to a comet-like diffusion cloud of oil behind the
droplets. (The Péclet number is $\text{Pe}=av_{\text{ext}}/D$ in which $a$ is
the separation between the particles, $v_{\text{ext}}$ the velocity during
training, and $D$ the diffusion coefficient of the solubilized oil.) As a
consequence, the composition of both droplets changes (middle row), with the
front droplet having more insoluble oil and the back droplet more soluble oil.
During retrieval (panel f), we start with two droplets with different
compositions. These can have non-reciprocal interactions leading to a run-and-
chase dynamics originating from Marangoni effects [18].

Our foundational step is to identify the basic ingredients needed to learn
dynamical states irrespective of experimental platforms. We begin with a
hands-on demonstration of these requirements using the programmable LEGO toy
shown in Fig. 1c-d and Movie 1. The toy has two angular degrees of freedom
$\theta_{1}$ and $\theta_{2}$ that can be controlled by hand very much like
the angles of the origami-bird wings. These angles follow a dynamics enabled
by sensors and actuators where each angle tends to align or antialign with the
other depending on the tunable couplings $J_{12}$ and $J_{21}$ (here $J_{12}$
represents the effect of $\theta_{2}$ on $\theta_{1}$). During the training
phase, the operator changes the angles by hand over time. The time series of
the angles are in turn mapped into distinct values of the couplings $J_{ij}$
by a learning rule programmed on a computer. The simplest Hebbian learning
rule, in which $J_{ij}$ increases when $\theta_{i}$ and $\theta_{j}$ are
simultaneously aligned, precludes dynamic states because only symmetric
interactions ($J_{12}=J_{21}$) are learned. In order to retrieve dynamic
states (Fig. 1d), asymmetric couplings ($J_{12}\neq J_{21}$) are generically
needed [28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44,
45, 46, 47, 48, 49, 50].

Asymmetric couplings can be learned if a time delay $\tau$ is added in the
learning rule (Movie 1). For instance, we can impose that $J_{ij}$ tends to
increase when $\theta_{i}(t)$ is correlated with $\theta_{j}(t-\tau)$. This
creates the desired asymmetry between $i$ and $j$. But it is not enough: the
system must be trained using examples that break time-reversal symmetry, in
order for the asymmetry not to be washed out over time (see Movie 1). Learning
rules with signal-propagation delays naturally arise from causality and are
reminiscent of spike-timing-dependent plasticity (STDP) in neuroscience [51,
52, 53, 54, 55, 56]: the influence of neuron $j$ on neuron $i$ increases if
$j$ fires just before $i$ fires (but not if $j$ fires just after $i$).

Learning time-dependent states in physical systems.—In the example of Fig.
1c-d, a computer is needed to program the dynamics of the system during both
training and retrieval. We now demonstrate our approach in situations where
the learning rule capable of learning non-reciprocal interactions is not
programmed on a computer, but instead naturally emerge from basic physico-
chemical processes. Figure 1e-f shows an example of trainable interaction
between oil droplets [18, 19, 20, 22, 23, 24, 25, 26, 27, 57]. The droplets
are composed of a mixture of two chemicals: the red oil can easily be
solubilized in water, while the blue one is less soluble. It has been observed
experimentally that this asymmetry in their composition can lead to a motion
of the droplets in which the red droplet chases the blue one [18].

The aforementioned process is what we need in our proposal of a concrete
training protocol for learning time-dependent states in droplets experiments.
In the training phase, forces are applied on two droplets with identical
initial composition (purple in panel e). When the droplets move fast enough
(i.e. at large enough Péclet number, see caption and next section), the
asymmetric diffusion of the red miscible oil due to the motion of the droplets
(see the comet-like diffusion cloud in top part of panel e) leads to a change
in their composition (bottom part of panel e). Crucially, the red oil of the
front droplet can be captured by the back droplet, but not vice-versa. As a
consequence, the droplets tend to reproduce the motion seen in training during
the retrieval phase where they are left to freely evolve (panel f). We refer
the reader to Methods for more detailed experimental considerations.

The key feature of the example of Fig. 1e-f is the appearance of time-delayed
interactions arising from the combination of the particles’ motion during
training with the causal propagation of signals through a field (e.g., oil
concentration in Fig. 1). Beyond this specific example, all physical
interactions are subject to retarded potentials due to causality, for example
asymmetric forces between acoustically levitated particles or hydrodynamic
interactions mediated by the wakes of objects moving in a fluid [47]. We now
consider a simplified particle-based model that captures this ubiquitous
feature in a minimal mathematical setting amenable to analytic treatment.

Particles with field-mediated interactions.—Consider particles at positions
$\mathbf{r}_{i}(t)$ (Fig. 2a) that are sources for distinct fields (e.g.
chemicals such as different types of oil with distinct solubilities as in Fig.
1e-f) with concentration $c_{i}(\bm{r},t)$ (shown in yellow in Fig. 2a). These
concentration fields evolve according to

$\displaystyle\partial_{t}c_{i}(\mathbf{r},t)=\tau_{\text{c}}^{-1}\Theta(|\mathbf{r}-\mathbf{r}_{i}(t)|-\ell_{\text{c}})-\lambda
c_{i}+D\nabla^{2}c_{i}.$ (1)

The first term describes the emission of $c_{i}(\bm{r},t)$ with rate
$\tau_{\text{c}}^{-1}$ in a circle of radius $\ell_{\text{c}}$ around particle
$i$ ($\Theta$ is the Heaviside function). The second and third terms describe
respectively decay at rate $\lambda$ and diffusion with diffusion constant
$D$.

The positions of the particles follow the overdamped dynamics

$\displaystyle\frac{d\mathbf{r}_{i}}{dt}$
$\displaystyle=v_{0}\tilde{\mathbf{n}}_{i}-\sum_{j\neq
i}\nabla_{i}V_{ij}+{\bm{\xi}}(t).$ (2)

with steric repulsion $V_{ij}$, translational noise ${\bm{\xi}}(t)$, and self-
propulsion with speed $v_{0}$ and a direction
$\tilde{\mathbf{n}}_{i}\propto\sum_{j\neq i}\omega_{ij}\nabla
c_{j}(\mathbf{r}_{i},t)$ set by the (generalized) mobilities $\omega_{ij}$,
that describe the tendency of particle $i$ to move along gradients of $c_{j}$.
The $\omega_{ij}$ could be, for example, chemotactic or diffusiophoretic
mobilities whose values are fixed at the end of the training phase (see
Methods for detailed modelling, e.g. the influence of angular inertia).

Fig. 2: Learning dynamic states in a particle system. (a) Proposed physical
system to learn dynamic steady states. A collection of active, chemotactic
particles that release chemical concentration $c_{i}(\mathbf{r},t)$. The
chemical concentration field around a particle breaks fore-aft symmetry, with
exponential decay having different decay length scale in front vs. behind the
moving particle, obtained both from simulation and analytical solution
(detailed in Methods). (b) Training protocols involve constrained motion of
the particles while chemotactic affinities evolve. Particles learn chemotactic
affinities according to concentrations they sense. The learned interactions
can become symmetric (for $\text{Pe}=0.18$) or asymmetric (for
$\text{Pe}=1.88$) depending on parameters such as diffusivity $D$ or velocity
$v$ etc. The degree of asymmetry, defined as
$\kappa=\frac{|\bar{\omega}_{12}-\bar{\omega}_{21}|}{|\bar{\omega}_{12}+\bar{\omega}_{21}|}$increases
monotonically with Pe (the overbar denotes an average over time and over all
nearest neighbour pairs). (c) Using the learned affinities, the particles
assemble and move. Snapshots from a simulation with $10$ particles and
$\tau_{c}=1.0$, $\ell_{c}=0.5$, $\lambda=0.1$, $D=0.5$, $v=0.5$. (d) Training
for a functional behavior where particles (violet) learn to assemble into a
triangular formation and collectively chase a different target particle
(orange). The training was performed for $v=1.5$, $l_{c}=0.5$, $\lambda=0.5$,
$D=1.0$ for all the particles, where we used for the chasing ones
$\tau_{c}=1.0$ and for the target $\tau_{c}=0.025$. During the retrieval we
first the see formation of a triangular assembly which subsequently chases and
captures the target.

Inspired by the experimental proposal in Fig. 1e-f, we formulate the following
training rule that captures mathematically how the $\omega_{ij}$ evolve as a
function of the trajectories $\bm{r}_{i}(t)$ that the operator imposes by hand
during training (overruling Eq. (2)):

$\displaystyle\frac{d{\omega}_{ij}}{dt}$
$\displaystyle=\alpha\big{[}c_{j}(\mathbf{r}_{i}(t),t)-c_{0}\big{]}-\frac{\omega_{ij}}{\tau_{0}}.$
(3)

Here $\alpha$ is the learning rate and $\tau_{0}$ is a relaxation time. In a
nutshell, this learning rule increases the mobility $\omega_{ij}$ when
particle $i$ detects a greater-than-average value of $c_{j}$. In addition to
the mechanism sketched in Fig. 1, such strengthening of interactions based on
spatial co-localization of chemical species or other constituents can be
achieved experimentally by exploiting a family of proximity-based ligation,
polymerization or other chemical mechanisms [2, 58, 59, 60, 61, 62, 63, 13,
5].

Fig. 3: Learning on the fly. (a) Schematic understanding of learning through
external training. In a (fictitious) energy landscape for the system’s state
$s$ and interactions $J$, training fixes the state $s^{\text{tr}}$ while the
interactions find an effective minimum at $J^{\ell}$. Then, the retrieval
fixes $J^{\ell}$ while the state evolves to an effective minimum at
$s^{\ell}$. Generically, this procedure cannot reproduce the training
behaviour exactly, i.e. $s^{\text{tr}}\neq s^{\ell}$. (b) Schematic
understanding of learning without external training. (c) The dynamics can lead
to fixed points in reciprocal $J^{+}$ and $s$ (top), or fixed points in non-
reciprocal $J^{-}$ with limit cycle steady states in $\mathbf{s}$ (bottom).
(d) Evidence from simulation for self-learning fixed points (top) and limit
cycles (bottom) in the chemotactic particle system. (e) Analogous simulation
results in the spin system. (f)-(j) Self-learning in the system of two spins.
(f) Trajectories for the system’s evolution in configuration space. Basins of
attraction for fixed point (limit cycle) solutions are shaded blue (red). (g)
Basins of attraction as a function of parameters describing STDP, $\sigma$ and
$\tau$. (h) Analytical calculations of fixed point solutions (dashed lines)
with numerical validation (solid points). (i) Simulation data of $s_{i}$ and
$J^{\pm}$ at steady state in the limit cycle case. (j) Limit cycle solutions
(dashed lines are analytical, solid points from simulation.)

Time-delayed learning rule from causal propagation.—We now integrate out the
concentration field $c_{j}(\mathbf{r},t)$ to obtain a closed-form dynamics for
the mobilities $\omega_{ij}$ in terms of the (causal) Green function $G$ of
Eq. (1). In the limit where
$\Theta(|\mathbf{r}-\mathbf{r}_{j}(t)|-\ell_{c})\simeq\delta(\mathbf{r}-\mathbf{r}_{j}(t))$,
the learning rule Eq. (3) becomes

$\displaystyle\frac{d{\omega}_{ij}}{dt}$
$\displaystyle=\alpha\bigg{[}\int_{-\infty}^{t}G(\mathbf{r}_{i}(t),t;\mathbf{r}_{j}(t^{\prime}),t^{\prime})dt^{\prime}-c_{0}\bigg{]}-\frac{\omega_{ij}}{\tau_{0}}.$
(4)

Here a memory kernel appears explicitly. This shows that the learning rule
effectively takes into account the past state of the system
$\mathbf{r}_{j}(t^{\prime}<t)$.

Consider now a particle $i$ moving in a straight line at constant velocity
$\mathbf{v}=v\hat{\mathbf{x}}$ (Fig. 2a). In this case, the Green function in
Eq. (4) can be found analytically (Methods). As shown in Fig. 2a, the
corresponding comet-shaped concentration field exhibits a fore-aft asymmetry
that originates from the motion, in a way similar to the oil droplets in Fig.
1e. As a consequence, a particle $j$ passing just behind $i$ (i.e., where $i$
was in the past) experiences a stronger signal from $i$ than if it passed just
in front of it (i.e., where $i$ will be in the future), see Fig. 2a. The
emergence of this time-asymmetric delay in the learning rule, which would
occur with any causal (non-instantaneous) form of interaction, is the key to
learn asymmetric interactions and dynamic states. Note that the fore-aft
asymmetry of the comet-like diffusion cloud is only appreciable during
training when the Péclet number $\text{Pe}=av/D$ is high enough ($v$ is the
velocity of the particles during training, and $a$ their separation). In
Methods, we show analytically that this asymmetry scales as $\sinh(\text{Pe})$
in the limit of fast decay $\lambda a^{2}\gg D$.

Learning to self-assemble and move.—Figure 2b shows that the system indeed
learns asymmetric mobilities $\omega_{ij}\neq\omega_{ji}$ during training as
long as Pe is large enough. These lead to the dynamic behavior during
retrieval, where particles evolve according to Eq. (2) with the value of the
interactions $\omega_{ij}$ obtained at the end of the learning phase (Fig. 2c
and Movie 2). We are now in the position of exploring what dynamic
functionalities are enabled by this learning rule. We first choose the
particles to self-assemble into a ring-like structure with the additional
requirement of rotating on demand in either the clockwise or counter-clockwise
direction (see Movie 2 and Fig. 2c). Note that despite the simplicity of the
structure, we observe in Extended Data Fig. 3 that the learning rule leads to
a complex graph of interactions that contribute to the stability of the ring.

Next, we train the particles (violet) to learn to self-assemble into a
triangular formation and collectively chase a different target particle
(orange) by imposing on them examples of the motion shown in Fig. 2d and Movie
2. During the retrieval period, we indeed see the particles self-assemble into
a flying-wing shaped object (blue box) that cohesively maneuvers in space to
chase (green box) and finally capture the moving target (red box).

As we illustrated with the LEGO toy in Movie 1, the examples in the training
protocol (i.e. the motions imposed to the droplets or particles) should be
time irreversible in order for the emergent time-delayed learning rule to
produce asymmetric couplings. Here, it means that, for instance, particle 1
should systematically follow particle 2, as we demonstrate in Extended Data
Fig. 2 and Movie 3.

Modified Hopfield spin model.—In order to to determine the basins of
attraction and domain of existence of the fixed point and limit cycle
solutions encoding the learned functionalities, we introduce a minimal model
in which the time-delayed learning rule is put by hand rather than emergent.
In this model, inspired by the Hopfield spin network [64, 65, 66, 67, 28, 29,
30, 31, 32, 37, 38, 68], the physical degrees of freedom are continuous spins
$s_{i}(t)\in\mathbb{R}$ following the equation

$\displaystyle\frac{ds_{i}}{dt}=\sum_{j\neq i}J_{ij}s_{j}-ks_{i}^{3}$ (5)

in which $J_{ij}$ represent the effect of spin $j$ on spin $i$. We consider
the Hebbian-like learning rule with a time delay $\tau$,

$\displaystyle\frac{d{J}_{ij}}{dt}=\alpha\,\big{[}s_{i}(t)s_{j}(t-\tau)-\sigma\,s_{j}(t)s_{i}(t-\tau)\big{]}-\kappa
J_{ij}^{3}$ (6)

in which $\sigma$ controls the degree of asymmetry in time, while $\alpha$ is
a learning rate. Insights on the robustness of the learning phenomenon can
already be obtained from considering the simplest non-trivial case of two
spins.

In the training phase, a sinusoidal oscillation of the two spins $s_{i}(t)$ is
imposed, with $0$ or $\pi/2$ phase difference, corresponding to time-reversal
symmetric or asymmetric training protocols respectively. We first confirm that
the asymmetric coefficient $J_{12}\neq J_{21}$ are obtained only when the
training examples are time-irreversible (Extended Data Fig. 2), very much like
in the LEGO toy and particle based models. Furthermore, we can suppress
$J^{-}=J_{12}-J_{21}$ completely by removing the delay $\tau=0$ (Methods). As
a consequence, both fixed points and limit cycles can be obtained in the
retrieval phase (Extended Data Fig. 2).

Learning on the fly.—So far, we have considered physical learning as a two-
step process with separate training and retrieval phases. However, this strict
distinction may be impractical in experiments. For instance, with the oil
droplets of Fig. 1, the same physico-chemical processes are at play during
training and retrieval, only with different Péclet numbers. Hence, the system
may continue learning “on the fly” during retrieval, with potentially
detrimental consequences if it ends up relaxing to an untrained state.

To assess the consequences of this intertwining, we formalize the training and
retrieval process using a dynamical system perspective. The degrees of freedom
in the system are split into degrees of freedom of interest $s_{i}(t)$ (e.g.
spins) and learning degrees of freedom $J_{a}(t)$ (e.g. interactions between
spins). The learning dynamics
$\mathbf{\dot{J}}=\mathbf{f}_{J}(\mathbf{J},\mathbf{s})$ and the retrieval
dynamics
$\mathbf{\dot{s}}=\mathbf{f}_{s}[\mathbf{J},\mathbf{s}]+\mathbf{h}_{\text{ext}}$
can be seen as two “slices” of a dynamical system handling both $\mathbf{J}$
and $\mathbf{s}$ (green and brown lines in Fig. 3a). In the limit of strong
training, that we considered up to now, a trajectory
$\mathbf{s}_{\text{tr}}(t)$ is imposed by an external operator through the
external field $\mathbf{h}_{\text{ext}}$ during the training period, leading
to a learned $\mathbf{J^{*}}$ that is frozen and used during the retrieval
period. Another extreme case, that we call weak training, consists in reducing
the training to setting an initial condition for $\mathbf{s}$, after which
$\mathbf{J}$ and $\mathbf{s}$ simultaneously evolve towards the attractors of
the dynamical system with $\mathbf{h}_{\text{ext}}=\bm{0}$ (see Fig. 3),
without the need of an external operator.

In Fig. 3, we have overlaid a unified “learning landscape” $V(\bm{s},\bm{J})$
that schematically describes the relaxation of both training $\bm{J}$ and
physical degrees of freedom $\bm{s}$ towards (dynamic or static) attractors
111Note that when $\bm{f}[\bm{s},\bm{J}]$ depends on the past trajectory of
the system, then $\bm{s}$ in the figure represents the full past trajectory of
the system. In practice, when $\bm{f}$ does not only depend on the values of
$\bm{s}(t^{\prime})$ in the recent past, it approximated by the instantaneous
values of $\bm{s}$, $\bm{\dot{s}}$, $\bm{\ddot{s}}$, … up to a certain order..
In the case of non-potential dynamical systems, $V$ can be constructed as a
Lyapunov function that captures the relaxation towards dynamic attractors such
as limit cycles, but not the motion on the attractors [70]. As shown in Fig.
3b, we expect that the strong learning that we used up to now does not
necessarily lead to minima of the learning landscape: the state obtained in
the free evolution after learning $\bm{s}^{\ell}$ may not exactly reproduce
the training state $\bm{s}^{\text{tr}}$ (Fig. 3b).

This is indeed what we observe, in the particle system (see Methods, in which
we also describe the effect of a finite training time) as well as in the
minimal spin model with $N=2$ where exact solutions can be obtained (see
Methods and Fig. 3h-j). Here, the training is reduced to the bare minimum of
an initial condition for $\mathbf{s}$, while we set $\mathbf{J}=\mathbf{0}$ at
the initial time $t=0$. Figure 3f shows the results of our calculations of the
basins of attraction of the fixed point (in blue) and limit cycles (in red):
sufficiently asymmetric initial conditions spiral towards limit cycles, while
more symmetric ones converge to fixed points. In the Methods, we show that an
exact solution of the minimal model in Eq. 6 allows us to prove that the size
of the basins of attraction is controlled by the degree of asymmetry $\sigma$
and the time delay $\tau$ of the time-delayed learning rule (Fig. 3g). In
addition, limit cycles disappear at critical values $\sigma_{c}<1$ and
$\tau_{c}>0$ (Fig. 3h-j). We find that, when the time delay $\tau$ is larger
than the critical value $\tau_{c}$, asymmetric interactions are suppressed
before they can be learned. This suggests that there is a trade-off between
large basins of attraction (at large $\tau$) and large non-reciprocity (at
small but finite $\tau$).

To sum up, when the interactions are not frozen at the end of training, the
system evolves towards its natural attractors, potentially leading to
undesired configurations. However, the analysis behind Fig.3 reveals that one
can also harness this feature as a shortcut to reduce the training time so
that the evolution of the interactions $\mathbf{J}$ and of the physical
degrees of freedom $\mathbf{s}$ reinforce each other.

Conclusions.—We have shown how to train and retrieve dynamic states through
physical learning by combining time-delayed interactions, that emerge
naturally from causal propagation, with a time-reversal asymmetric training
protocol. This strategy can not only be applied in robotic matter by directly
programming a computer, but also in physico-chemical active matter systems
where it naturally emerges. Looking forward, programmable colloids based on
DNA and other biomolecules [2, 58, 59, 60, 61, 62] would greatly enhance the
potential complexity of learned behaviors by providing multiple interacting
species and chemical feedback loops through enzymatic reactions. The
principles illustrated here provide a step towards von Neumann’s dream of
engineering synthetic living systems that adapt to the environment.

## Materials and Methods

### Proposal of experimental realization using chemotactic oil droplets

Extended Data Figure 1:  Proposed training mechanisms for oil droplets to
learn asymmetric interactions. In panel (a) the training consists of spending
time near either a predator or a prey droplets. In panel (b), the training
consists of moving the droplets in a pair with some external force (optical
tweezers, electric field). In panel (c), the droplets are also moved but in a
reservoir of soluble oil, causing the droplets to move during the retrieval
phase in the opposite direction from which they moved in the training phase.

In this section, we discuss how a system of oil droplets that learn asymmetric
interactions (such as that in Fig. 1e-f of the main text) can be realized
experimentally. We suggest a recipe based on the chemotactic chasers from Ref.
[18] but expect that learning rules with time delays could be implemented in
other situations as long as there is an exergonic process coupled to the
objects’ motion that can drive their dynamics.

The chasing droplets in Ref. [18] have asymmetric interactions that stem from
asymmetric oil exchange. Two types of droplets, each consisting of an oil that
is fully miscible with the oil in the other droplet, exchange oils through the
aqueous continuous phase via micellar solubilization. One of the two oils is
more soluble in the continuous phase than the other, so that the oil transport
of droplet 1 to droplet 2 is faster than the transport of droplet 2 to droplet
1. The consequence is a net loss of soluble oil by droplet 1 and a net gain of
soluble oil by droplet 2. This directional oil exchange leads to motion
because the droplets tend to move away from areas with high solubilized oil
concentrations; the solubilized oil increase the interfacial tension of the
oil droplets driving a Marangoni flow. The droplets made of soluble oil thus
moves toward the droplets made of the insoluble oil and, conversely, the
droplet made of insoluble oil moves away from the droplet made of soluble oil.
The net result is an asymmetric interaction where the soluble oil droplets act
as predators and chase the insoluble oil droplets that act as prey.

The predator and prey droplets have an inherent memory effect through their
composition; their oil exchange rate depends on their local chemical
environment: droplets near predators lose less soluble oil, and droplets near
prey lose more soluble oil. The droplets ‘remember’, through their
composition, how many predator or prey droplets they have been near on
average.

This memory effect could be used to have droplets of initially identical
composition—and thus symmetric interactions—develop asymmetric interactions
over time by evolving their oil exchange process in differing environments
(Extended Data Fig. 1a). A mixed-composition droplet that spends time near
mostly predator droplets loses less soluble oil (or may even gain soluble oil
depending on its initial composition) so that its composition becomes more
predator-like. Conversely, a mixed-composition droplet that spends time near
mostly prey droplets loses more soluble oil and becomes more prey-like. When
removed from their training chemical environment and placed together, the
droplet that has evolved to a predator-like composition would likely chase the
droplet that has evolved to a prey-like composition.

The same physical process of chemical-environment-dependent oil exchange could
lead to droplets learning asymmetric interactions by the act of imposing the
droplet motion in which the asymmetric interactions will result (Extended Data
Fig. 1b). Imagine two droplets of equal mixed oil composition are forced to
move in a pair with one droplet in front and the other at the back. When this
motion if fast compared to diffusive transport (i.e. the Péclet number is much
larger than one), the droplet in the back experiences a chemical environment
with more soluble oil than the droplet in front. The back droplet can thus
uptake oil from the front droplet but not the other way around, which causes
the front droplet to have less soluble oil and become more prey-like, and the
back droplet to have more soluble oil and become more predator-like.

Note that in the two cases described above, the training would be
mechanistically similar to the retrieval. However, this is not necessarily the
case: for instance, we expect that the same training protocol performed in a
reservoir of soluble oil would cause the droplets to move in opposite
directions during training and retrieval (Extended Data Fig. 1c).

Extended Data Figure 2: Dynamic steady states require both time delay in the
learning rule and broken time-reversal invariance (TRI). (a) Simulation data
for the evolution of $\omega_{ij}^{\pm}$ during training show symmetric
interactions being learned (top) when the training protocol is time reversal
invariant and asymmetric interactions emerging (bottom) where $i$ consistently
follows $j$ (TRI broken). (b) Snapshots showing retrieval periods for the TRI
(top) and TRI broken (bottom) training protocols. (c) The spins $s_{i}$ learn
symmetric interactions during the training protocol with sinusoidal
oscillation and no phase difference, and they learn asymmetric coefficients
when the phase difference is $\pi/2$. (d) During the retrieval period spins
with symmetric interactions reach an aligned, stationary steady state whereas
the ones with asymmetric interactions show oscillatory steady state. Colors
match the labels in (c).

### Demonstration with LEGO toys

In Movie 1, we illustrate the ingredients required to learn dynamical states
using a programmable toy. Two “Technic Medium Angular Motor” from a “LEGO
Education SPIKE Prime” set are used, both as motors and angle sensors, to
realize active XY-like spins. The LEGO toy is programmed to approximate the
dynamics

$\dot{\theta}_{i}=f_{i}(\vec{\theta})\equiv\sum_{j}J_{ij}\sin(\theta_{j}-\theta_{i})$
(7)

in which $i,j=1,2$ label the XY spins with angles $\theta_{i}(t)$ (see Ref.
[40] for an exact solution of this dynamical system). This is realized by
moving the positions of the robots by an increment $f_{i}(\vec{\theta})\delta
t$ every time step. In order to allow the user to move the spins by hand
during the operation, the motors are also paused for a fixed time
$\tau_{\text{pause}}$ every time step.

In the training phase, the motors are disabled and time series of the angular
positions $\theta_{i}$ imposed by the operator are recorded. The couplings are
learned from these time series as

$\dot{J}_{ij}=J_{ij}-\kappa
J_{ij}^{3}+\alpha\int_{-\infty}^{t}g(t-t^{\prime})\cos(\theta_{1}(t)-\theta_{2}(t^{\prime}))\text{d}t.$
(8)

in which the memory kernel is taken as $g(\tau)=\text{e}^{-\tau/\tau_{0}}$
(and is set to zero for times going before the beginning of the recording).
The parameters $\kappa$, $\alpha$, and $\tau_{0}$ are adjusted to be in a
regime where learning is successful (see the main text for an analysis of the
influence of training parameters).

### Agent-based particle model

####  .0.1 Simulation details

As mentioned in the main text, for the particle based simulation we use
overdamped dynamics of self-propelled particles following,

$\frac{d{\mathbf{r}}_{i}}{dt}=v_{0}\mathbf{n}_{i}-\sum_{j\neq
i}\nabla_{i}V_{ij}+{\bm{\xi}}(t)$ (9)

where $\mathbf{r}_{i}$ is the position of the $i$ the particle, $v_{0}$ is the
propulsion speed which acts along the direction
$\mathbf{n}_{i}=(\cos{\theta_{i}},\sin{\theta_{i}})$. Here $V_{ij}$ is a short
range repulsive power law potential of the form

$V_{ij}(r)=\begin{cases}\epsilon\left(\frac{\sigma}{r}\right)^{10}+V_{0}+\frac{1}{2}V_{2}r^{2}&\text{if
}r\leq r_{c}\\\ 0&\text{otherwise}\end{cases}$ (10)

where $\epsilon$ and $\sigma$ determines the energy scale and length scale of
this steric interaction and $r_{c}$ is the cutoff distance. We have chosen
$\epsilon=1.0$, $\sigma=1.0$, and $r_{c}=1.05\sigma$ throughout our
simulation. Also we have added the constant and the quadratic term in the
potential to make both the potential and the corresponding force continuous at
$r=r_{c}$ by choosing $V_{0}=-6\epsilon\left(\frac{\sigma}{r_{c}}\right)^{10}$
and $V_{2}=10\epsilon\left(\frac{\sigma^{10}}{{r_{c}}^{12}}\right)$. In the
equation of motion mentioned above we used a small translational noise
${\bm{\xi}}$ whose components are uniformly distributed between
$[-\eta_{t},\eta_{t}]$. The trained coefficients $\\{\omega_{ij}\\}$ are used
to determine the direction of self-propulsion
$\mathbf{n}_{i}\equiv(\cos{\theta_{i}},\sin{\theta_{i}})$ mentioned before.
The equation of motion for $\theta_{i}$ is

$\frac{d\theta_{i}(t)}{dt}=\frac{\sin{\left(\theta^{T}_{i}(t)-\theta_{i}(t)\right)}}{\tau_{\theta}}+2\pi\xi_{r}$
(11)

where $\theta_{i}^{T}(t)$ represents the instantaneous target angle for the
$i$-th particle and it reflects the orientation of the vector $\sum_{j\neq
i}\omega_{ij}\nabla c_{j}(\mathbf{r}_{i},t)$. Note that this introduces a
finite time relaxation mechanism in the orientational dynamics and in the
limit $\tau_{\theta}\to 0$, we get $\mathbf{n}_{i}\to\tilde{\mathbf{n}}_{i}$
as mentioned in the main text. The timescale for the relaxation dynamics is
controlled by $\tau_{\theta}$ and $\xi_{r}$ is a rotational noise which is
uniformly distributed between $[-\eta_{r},\eta_{r}]$. In the trial phase the
system is initialised with randomised configuration of particles and zero
pheromone concentration in the box. Particles then start releasing the
pheromones (following Eq. 1 of the main text) and have constant self
propulsive overdamped dynamics with speed $v_{0}$ which try to align towards a
target angle $\theta_{i}^{T}(t)$, determined by the trained affinities
$\omega_{ij}$.

####  .0.2 Order parameters

To identify the nature of the dynamic steady state observed during the trial
in the particle based simulation, we construct the following order parameter
for a pair ($i,j$)

$\eta_{ij}=\tfrac{1}{2}(\hat{\mathbf{n}}_{i}+\hat{\mathbf{n}}_{j})\cdot\hat{\mathbf{r}}_{ij}$
(12)

where $\hat{\mathbf{n}}_{i}$ is the unit vector associated with the propulsion
vector of the $i$ th particle and $\hat{\mathbf{r}}_{ij}$ is the unit vector
along the line joining the pair ($i,j$). This order parameter by construction
will be $\eta_{ij}\sim$ zero for reciprocal attraction or repulsion as the
center of mass velocity is zero when particle $i$ and $j$ either approach or
run away from each other. However for a chase and run scenario,
$\tfrac{1}{2}(\hat{\mathbf{n}}_{i}+\hat{\mathbf{n}}_{j})\sim\hat{\mathbf{r}}_{ij}$
and the order parameter will be $\sim 1$.

Extended Data Figure 3: Evolution of interaction during training. (a) Pair-
wise interaction map in the beginning (left) and at the end (right) of the
training phase for low Péclet number. The symmetric part of the interaction
$\omega_{ij}^{+}$ is plotted in blue and the anti-symmetric part of the
interaction $\omega_{ij}^{-}$ is plotted in red. (b) Both the symmetric and
the anti-symmetric part of the interactions ($\omega^{+}_{ij}$) and
($\omega^{-}_{ij}$) are plotted as a function of time $t$ during the training
for low Péclet number. The interactions are colored according to the distance
between the pairs ($i$ and $j$) where $d_{ij}=|i-j|$. (c) and (d) are
analogous plots to (a) and (b) for high Péclet number. The emergent
interaction is more asymmetric (the network has more red connections) when the
Péclet number is high (bottom row) than when the Péclet number is low (upper
row). Note that the symmetry in (d) arises because
$\omega_{ij}^{-}=-\omega_{ji}^{-}$.

### Field created by a particle moving at constant speed

In this section, we compute the steady-state field profile in the co-moving
frame of reference of a particle moving at constant velocity $v_{0}$. In this
case, $c(\mathbf{r},t)$ follows the equation

$\frac{\partial c(\mathbf{r},t)}{\partial
t}={\tau_{c}}^{-1}\delta(\mathbf{r}-\mathbf{r}_{0}(t))-\lambda
c(\mathbf{r},t)+D\nabla^{2}c(\mathbf{r},t)$ (13)

in which $\mathbf{r}_{0}(t)=v_{0}t$ is the position of the particle (we set
$\mathbf{r}_{0}(0)=\bm{0}$). In the co-moving frame of reference, we define
two coordinates $u=x-v_{0}t$ and $w=y$.

A Fourier transform of Eq. (13) yields

$\tilde{c}(q_{u},q_{w})=\frac{1}{2\pi\tau_{c}\left(\lambda-
iv_{0}q_{u}+D({q_{u}}^{2}+{q_{w}}^{2})\right)}$ (14)

where $(q_{u},q_{w})$ is the spatial frequency. The inverse Fourier transform
is evaluated using the residue theorem and we end up with

$c(u,w)=\frac{1}{4\pi^{2}D\tau_{c}}\,I(u,w)$ (15)

in which

$I(u,w)=2\pi\,e^{-u/\xi}\,K_{0}[\zeta^{-1}(u^{2}+w^{2})^{1/2}]$ (16)

where we have defined $\xi^{-1}={v_{0}}/{2D}$ and
$\zeta^{-2}=\xi^{-2}+{\lambda}/{D}$ and where $K_{\nu}$ is the modified Bessel
function of the second kind of order $\nu$ [71, §10.25].

In the limit $w\to 0$, an asymptotic expansion of the Bessel function [71,
§10.25.3] yields

$c(u,w\to
0)=\frac{1}{2D\tau_{c}}\sqrt{\frac{\zeta}{2\pi|u|}}e^{-\left(\frac{1}{\zeta}+\text{sign}(u)\frac{1}{\xi}\right)|u|}.$
(17)

We can then quantify the fore-aft asymmetry by computing

$c(-a)-c(a)=\frac{1}{D\tau_{c}}\sqrt{\frac{\zeta}{2\pi
a}}e^{-a/\zeta}\sinh(a/\xi)$ (18)

for $a>0$, in which we identify $a/\xi=v_{0}a/[2D]=\text{Pe}_{a/2}$ as the
Péclet number associated with the length $a/2$.

### Modified Hopfield spin model

The model is defined by Eqs. (5) and (6) of the main text, for
$i,j=1,\dots,N$. It is convenient to introduce the symmetric and antisymmetric
parts of the coupling $J_{ij}^{\pm}=({J}_{ij}\pm{J}_{ji})/2$ (for $i\geq j$,
as the others $J_{ij}^{\pm}$ are redundant).

####  .0.3 Role of delay time $\tau$

In this section, we elucidate how the time delay in the learning rule enables
the emergence of asymmetric interactions during training. Fig. 2 compares the
outcome when the oscillatory training protocol of Fig. 2q-x is performed on
the spin system with delay times $\tau=0$ (non-STDP) and $\tau\neq 0$ (STDP).
When the training protocol is time-reversal invariant (Fig. 2a), neither case
results in non-reciprocity. However, when the training protocol breaks time-
reversal invariance (Fig. 2b), it is only in the STDP case $\tau\neq 0$ that
results in $J_{ij}^{-}\neq 0$ after training. The non-STDP case has
$J_{ij}^{-}=0$ throughout the entire training period, even as $J_{ij}^{+}$
oscillates around zero.

Indeed, when $\tau=0$, the equation of motion for
$J_{ij}^{-}=({J}_{ij}-{J}_{ji})/2$ obtained from Eq. (6) becomes

$\begin{split}\dot{J}_{ij}^{-}=-\kappa
J_{ij}^{-}\big{[}3(J_{ij}^{+})^{2}+(J_{ij}^{-})^{2}\big{]}\end{split}$ (19)

so $J_{ij}^{-}$ can only monotonically decay to zero. In contrast,
$J_{ij}^{+}$ may remain finite.

####  .0.4 Weak learning: exact solution for $N=2$.

The dynamical system composed of spins $s_{1}$, $s_{2}$ and their interactions
$J_{12}$ and $J_{21}$ (or equivalently $J^{\pm}=(J_{12}\pm J_{21})/2$) has
fixed point and limit cycle steady states, as shown in Fig. 3b-d. Here, we
exactly solve for these steady states, in particular to understand how they
depend on the STDP parameters $\tau$ and $\sigma$. We have

$\displaystyle\dot{s}_{1}$ $\displaystyle=(J^{+}+J^{-})s_{2}-ks_{1}^{3}$ (20a)
$\displaystyle\dot{s}_{2}$ $\displaystyle=(J^{+}-J^{-})s_{1}-ks_{2}^{3}$ (20b)
and
$\begin{split}\dot{J}^{+}=\frac{\alpha}{2}\,(1-\sigma)\,\big{[}s_{1}(t)s_{2}(t-\tau)+\,s_{2}(t)s_{1}(t-\tau)\big{]}\\\
-\kappa J^{+}\big{[}3(J^{-})^{2}+(J^{+})^{2}\big{]}\end{split}$ (20c) and
$\begin{split}\dot{J}^{-}=\frac{\alpha}{2}\,(1+\sigma)\,\big{[}s_{1}(t)s_{2}(t-\tau)-\,s_{2}(t)s_{1}(t-\tau)\big{]}\\\
-\kappa J^{-}\big{[}3(J^{+})^{2}+(J^{-})^{2}\big{]}\end{split}$ (20d)

##### Fixed points.

Fixed points are obtained by setting
$\dot{s}_{1}=\dot{s}_{2}=\dot{J}^{+}=\dot{J}^{-}=0$ (note that this implies
$s_{i}(t)=s_{i}(t-\tau)$). We obtain

$\displaystyle s_{i}$ $\displaystyle=\pm\sqrt{\tfrac{\left\lvert
J^{+}\right\rvert}{k}}$ (21a) $\displaystyle J^{+}$
$\displaystyle=\text{sign}(s_{1}s_{2})\sqrt{\tfrac{\alpha}{k\kappa}(1-\sigma)}$
(21b) $\displaystyle J^{-}$ $\displaystyle=0$ (21c)

where the signs of $s_{1}$ and $s_{2}$ are independent.

##### Limit cycles.

To find limit cycle solutions, we set $\dot{J}^{-}=0$ (to match numerical
observations) and assume that $\left\lvert J^{+}\right\rvert\ll\left\lvert
J^{-}\right\rvert$ (we will later derive conditions for this to be true). In
this case, we neglect $J^{+}$ in Eq. (20b) and obtain

$\displaystyle s_{1}(t)=s\,\cos(J^{-}t)$ (22a) $\displaystyle
s_{2}(t)=s\,\sin(J^{-}t)$ (22b)

where we assumed $s^{2}\ll J^{-}$. We will solve for $s$ and derive conditions
for this as as well.

Next, the solutions for $s_{i}$ can be placed into Eq. (20c) and (20d) to find
$J^{\pm}$. With $\dot{J}^{-}=0$, Eq. (20d) the relation between $J^{-}$ and s

$\displaystyle\frac{2\kappa}{\alpha(1+\sigma)}=\frac{s^{2}\sin(J^{-}\tau)}{(J^{-})^{2}}.$
(23)

while Eq. (20c) can be integrated to get

$\displaystyle
J^{+}(t)=-J^{+}\cos{\left(2J^{-}t-J^{-}\tau+\phi\right)},\quad\quad.$ (24)

with

$\displaystyle J^{+}$
$\displaystyle=\kappa\left(\frac{1-\sigma}{1+\sigma}\right)\left(\frac{(J^{-})^{2}}{\sin(J^{-}t)}\right)\left(4+9\kappa^{2}(J^{-})^{2}\right)^{-1/2}$
(25) $\displaystyle\phi$ $\displaystyle=\tan^{-1}\left(\frac{3}{2}\kappa
J^{-}\right)$ (26)

We see that the initial assumption of $\left\lvert
J^{+}(t)\right\rvert\ll\left\lvert J^{-}\right\rvert$ is valid when $\sigma$
is sufficiently close to 1, corresponding to the antisymmetric limit of STDP.

The steady state value of the amplitude $s$ is obtain using the above
solutions for $s_{i}$ and $J^{\pm}$ as follows:

$\displaystyle s\frac{ds}{dt}$
$\displaystyle=s_{1}\frac{ds_{1}}{dt}+s_{2}\frac{ds_{2}}{dt}$
$\displaystyle=-s^{2}J^{+}\,\sin(2J^{-}t)\cos{\left(2J^{-}t-J^{-}\tau+\phi\right)}$
$\displaystyle\qquad-ks^{4}\left(\sin^{4}(J^{-}t)+\cos^{4}(J^{-}t)\right).$

Averaging over a cycle of time $2\pi/J^{-}$ (with $\langle\rangle$ denoting
cycle average),

$\displaystyle\left\langle\frac{ds}{dt}\right\rangle=\frac{1}{2}sJ^{+}\sin{\left(-J^{-}\tau+\phi\right)}-\frac{3}{4}ks^{3}.$

Note that $J^{+}$ can no longer be ignored since the contribution of $J^{-}$
vanishes. Then, the steady state solution $\left\langle ds/dt\right\rangle=0$
yields

$\displaystyle s^{2}=\frac{2J^{+}\sin{\left(-J^{-}\tau+\phi\right)}}{3k}.$
(27)

Similar to the condition on $J^{+}$, the assumption $s^{2}\ll J^{-}$ is valid
for $\sigma$ close to 1.

Finally, we can use the solutions for $s$ (27) and $J^{+}$ (24) to eliminate
these variables in Eq. (23). The resulting equation reads

$\displaystyle\frac{3k}{\alpha(1-\sigma)}=\frac{\sin{\left(-J^{-}\tau+\phi\right)}}{J^{-}\left(4+9\kappa^{2}(J^{-})^{2}\right)^{-1/2}}$
(28)

and can be solved numerically for $J^{-}$. Note that the solutions $\pm J^{-}$
are identical upon interchanging spin indices 1 and 2.

Together, Eqs. (22), (24), (27), and (28) constitute the limit cycle solutions
of the dynamical system as discussed in the text and shown in Fig. 3(d)(ii).
We now derive the condition for existence of solutions that establishes the
critical values $\sigma=\sigma_{c}$ and $\tau=\tau_{c}$. The left side of Eq.
(28) is maximized at $J^{-}\rightarrow 0$, implying the condition

$\displaystyle\alpha\left(\frac{3}{2}\kappa-\tau_{c}\right)>\frac{6k}{(1-\sigma_{c})}$
(29)

for limit cycle solutions to exist. Solutions vanish as $\sigma$ or $\tau$
increase past the critical values.

###  .1 Sloppy trainer

In the main text we formulated the problem in such a way that during the
training the trajectory of the learning particles were either perfectly micro-
managed by the trainer or left completely free during the self learning. We
now ask, what happens if the trainer is sloppy i.e. the scenario is between
these two extremes.

We address this in two different ways: (a) by reducing the spatial control and
(b) by decreasing temporal one. To understand the role of sloppiness of the
trainer, we consider that the particles are confined in an annular domain
(which acts as a quasi-linear track with harmonic confinement with stiffness
$\kappa=100$) during the training. In this set up, the particles are supposed
to perform a periodic circular motion during the training. The presence of the
trainer is implemented in the equation of motion of the learning particles via
a tangential flow field $\mathbf{v}_{f}(t)=v_{f}(t)\hat{\phi}$ (here
$\hat{\phi}$ is the unit vector along the azimuthal direction) along with a
uniformly distributed translational noise,

$\dot{\mathbf{r}}_{i}=v_{f}(t)\hat{\bm{\phi}}-\sum_{j\neq
i}\nabla_{i}V_{ij}+\bm{\xi}_{t}$ (30)

For the first part, i.e. for lack of spatial control, we use a time
independent flow where $v_{f}(t)=v_{f}$. One can see that this training
protocol does not preserve the relative distance between the particles and
therefore due to the fluctuations in the inter-particle distance the learned
coefficients shows giant fluctuations compared to the case where the training
is carried out by a strict trainer (see Fig. 4(a)). This fluctuations lead to
set of learned ${\omega_{ij}}$ that is insufficient to retrieve the assembly
where the system was trained. The particles can still learn meaningful
interactions during the learning process by ramping up the time scale
associated with learning or $\tau_{0}$ (see Eq.3 of the main text). In the
last panel of Fig. 4(a) one can see the coefficients ${\omega_{ij}}$ reach
similar values as compared to the case which is carried out by a strict
trainer. This suggests when the trainer is sloppy a slow learner (with larger
$\tau_{0}$) is a better learner.

Extended Data Figure 4: Sloppy trainer. (a) Schematic of the set up for strict
training where the inter-particle distances are maintained precisely at a
fixed value during the training. The evolution of the inter-particle
interaction for the pair 1-2, ($\omega_{12}$ and $\omega_{21}$) shows a steady
value and using these learned interactions the system successfully retrieves
the circular motion. (b) During “sloppy training”, the role of trainer is
implemented via a confining harmonic potential and a constant tangential flow
field ($\mathbf{v_{f}}(t)=v_{f}(t)\hat{\phi}$ and $\hat{\phi}$ is the unit
vector along the azimuthal direction). In the case of the sloppy trainer, the
interparticle distances can fluctuate and this leads to strong fluctuations in
the learned interactions, which prevents a successful retrieval of the
behavior. However, if the learning is slow ($\tau_{0}>>1$), the learning
process averages out the fluctuation and a successful retrieval is possible.
(c) (Left) Temporal sloppiness in the training procedure is implemented by a
exponentially declining velocity field $v_{f}(t)=\exp(-t/\tau_{t})$. (Right)
The performance of the particles improves with increasing $\tau_{t}$,
especially after crossing a threshold at $\tau_{t}\sim 1$ which is depicted by
a dynamic order parameter $m$ (see Materials and Methods: “Sloppy trainer” for
details).

Next, to understand the role of temporal control, the flow field is slowly
withdrawn (in an exponential manner) with a timescale $\tau$ (see Fig. 4(b)).
In this case we combine both training and retrieval into a single process
where the particles keeps on learning on the fly and interact via the
instantaneous values learned interaction. Now the question we ask is, how
large $\tau$ has to be so that the particles learn to systematically circle
around in the annular chamber. Fig. 4(c) shows if $\tau<1$ particles don’t
learn anything meaningful or $m\sim 0$ (measured by a dynamic order parameter
$m=\sum_{i}\mathbf{v}_{i}(t)\cdot\hat{\phi}(\mathbf{r}_{i}(t))$ where
$\hat{\phi}(\mathbf{r})$ is the unit vector along the azimuthal direction
measured at position $\mathbf{r}$ at the steady state) whereas with $\tau>1$
the performance during the trial is significant ($m\sim 1$).

###  .2 Movies

Supplementary movies are available in the following web link:
https://home.uchicago.edu/~vitelli/videos.html.

## References

  * Hebb [2002] D. O. Hebb,  _The Organization of Behavior: A Neuropsychological Theory_ (L. Erlbaum Associates, Mahwah, N.J, 2002).
  * Stern and Murugan [2023] M. Stern and A. Murugan, Learning Without Neurons in Physical Systems, Annual Review of Condensed Matter Physics 14, 417 (2023).
  * Keim  _et al._ [2019] N. C. Keim, J. D. Paulsen, Z. Zeravcic, S. Sastry, and S. R. Nagel, Memory formation in matter, Reviews of Modern Physics 91, 035002 (2019).
  * Scheibner  _et al._ [2022] C. Scheibner, M. Fruchart, and V. Vitelli, Soft metamaterials: Adaptation and intelligence (2022), arXiv:2205.01867 .
  * Murugan  _et al._ [2015] A. Murugan, Z. Zeravcic, M. P. Brenner, and S. Leibler, Multifarious assembly mixtures: Systems allowing retrieval of diverse stored structures, Proceedings of the National Academy of Sciences 112, 54 (2015).
  * Falk  _et al._ [2023a] M. J. Falk, J. Wu, A. Matthews, V. Sachdeva, N. Pashine, M. L. Gardel, S. R. Nagel, and A. Murugan, Learning to learn by using nonequilibrium training protocols for adaptable materials, Proceedings of the National Academy of Sciences 120, 10.1073/pnas.2219558120 (2023a).
  * Pashine  _et al._ [2019] N. Pashine, D. Hexner, A. J. Liu, and S. R. Nagel, Directed aging, memory, and nature’s greed, Science Advances 5, 10.1126/sciadv.aax4215 (2019).
  * Stern  _et al._ [2022] M. Stern, S. Dillavou, M. Z. Miskin, D. J. Durian, and A. J. Liu, Physical learning beyond the quasistatic limit, Physical Review Research 4, l022037 (2022).
  * McMullen  _et al._ [2022] A. McMullen, M. Muñoz Basagoiti, Z. Zeravcic, and J. Brujic, Self-assembly of emulsion droplets through programmable folding, Nature 610, 502–506 (2022).
  * Glotzer [2004] S. C. Glotzer, Some assembly required, Science 306, 419–420 (2004).
  * Lee  _et al._ [2022] S. Lee, H. A. Calcaterra, S. Lee, W. Hadibrata, B. Lee, E. Oh, K. Aydin, S. C. Glotzer, and C. A. Mirkin, Shape memory in self-adapting colloidal crystals, Nature 610, 674–679 (2022).
  * Djellouli  _et al._ [2024] A. Djellouli, B. Van Raemdonck, Y. Wang, Y. Yang, A. Caillaud, D. Weitz, S. Rubinstein, B. Gorissen, and K. Bertoldi, Shell buckling for programmable metafluids, Nature 628, 545–550 (2024).
  * Evans  _et al._ [2024] C. G. Evans, J. O’Brien, E. Winfree, and A. Murugan, Pattern recognition in the nucleation kinetics of non-equilibrium self-assembly, Nature 625, 500–507 (2024).
  * Wang  _et al._ [2023] T. Wang, C. Pierce, V. Kojouharov, B. Chong, K. Diaz, H. Lu, and D. I. Goldman, Mechanical intelligence simplifies control in terrestrial limbless locomotion, Science Robotics 8, 10.1126/scirobotics.adi2243 (2023).
  * Aguilar  _et al._ [2016] J. Aguilar, T. Zhang, F. Qian, M. Kingsbury, B. McInroe, N. Mazouchova, C. Li, R. Maladen, C. Gong, M. Travers, R. L. Hatton, H. Choset, P. B. Umbanhowar, and D. I. Goldman, A review on locomotion robophysics: the study of movement at the intersection of robotics, soft matter and dynamical systems, Reports on Progress in Physics 79, 110001 (2016).
  * King  _et al._ [2023] E. M. King, C. X. Du, Q.-Z. Zhu, S. S. Schoenholz, and M. P. Brenner, Programmable patchy particles for materials design (2023), arXiv:2312.05360 .
  * Niu  _et al._ [2019] R. Niu, C. X. Du, E. Esposito, J. Ng, M. P. Brenner, P. L. McEuen, and I. Cohen, Magnetic handshake materials as a scale-invariant platform for programmed self-assembly, Proceedings of the National Academy of Sciences 116, 24402–24407 (2019).
  * Meredith  _et al._ [2020] C. H. Meredith, P. G. Moerman, J. Groenewold, Y.-J. Chiu, W. K. Kegel, A. van Blaaderen, and L. D. Zarzar, Predator–prey interactions between droplets driven by non-reciprocal oil exchange, Nature Chemistry 12, 1136–1142 (2020).
  * Moran and Posner [2017] J. L. Moran and J. D. Posner, Phoretic self-propulsion, Annual Review of Fluid Mechanics 49, 511–540 (2017).
  * Michelin [2023] S. Michelin, Self-propulsion of chemically active droplets, Annual Review of Fluid Mechanics 55, 77–101 (2023).
  * Nguyen and Stebe [2002] V. X. Nguyen and K. J. Stebe, Patterning of small particles by a surfactant-enhanced marangoni-bénard instability, Physical Review Letters 88, 164501 (2002).
  * Maass  _et al._ [2016] C. C. Maass, C. Krüger, S. Herminghaus, and C. Bahr, Swimming droplets, Annual Review of Condensed Matter Physics 7, 171–193 (2016).
  * Michelin  _et al._ [2013] S. Michelin, E. Lauga, and D. Bartolo, Spontaneous autophoretic motion of isotropic particles, Physics of Fluids 25, 10.1063/1.4810749 (2013).
  * Izri  _et al._ [2014] Z. Izri, M. N. van der Linden, S. Michelin, and O. Dauchot, Self-propulsion of pure water droplets by spontaneous marangoni-stress-driven motion, Physical Review Letters 113, 248302 (2014).
  * Schmitt and Stark [2013] M. Schmitt and H. Stark, Swimming active droplet: A theoretical analysis, EPL (Europhysics Letters) 101, 44008 (2013).
  * Soto and Golestanian [2014] R. Soto and R. Golestanian, Self-assembly of catalytically active colloidal molecules: Tailoring activity through surface chemistry, Physical Review Letters 112, 068301 (2014).
  * Moerman  _et al._ [2017] P. G. Moerman, H. W. Moyses, E. B. van der Wee, D. G. Grier, A. van Blaaderen, W. K. Kegel, J. Groenewold, and J. Brujic, Solute-mediated interactions between active droplets, Physical Review E 96, 032607 (2017).
  * Parisi [1986] G. Parisi, Journal of Physics A: Mathematical and General 19, L675–L680 (1986).
  * Crisanti and Sompolinsky [1987] A. Crisanti and H. Sompolinsky, Dynamics of spin systems with randomly asymmetric bonds: Langevin dynamics and a spherical model, Physical Review A 36, 4922–4939 (1987).
  * Sompolinsky and Kanter [1986] H. Sompolinsky and I. Kanter, Temporal association in asymmetric neural networks, Physical Review Letters 57, 2861–2864 (1986).
  * Kanter and Sompolinsky [1987] I. Kanter and H. Sompolinsky, Mean-field theory of spin-glasses with finite coordination number, Physical Review Letters 58, 164–167 (1987).
  * Kleinfeld [1986] D. Kleinfeld, Sequential state generation by model neural networks., Proceedings of the National Academy of Sciences 83, 9469–9473 (1986).
  * Herron  _et al._ [2023] L. Herron, P. Sartori, and B. Xue, Robust retrieval of dynamic sequences through interaction modulation, PRX Life 1, 023012 (2023).
  * Dehaene  _et al._ [1987] S. Dehaene, J. P. Changeux, and J. P. Nadal, Neural networks that learn temporal sequences by selection., Proceedings of the National Academy of Sciences 84, 2727–2731 (1987).
  * Buhmann and Schulten [1987] J. Buhmann and K. Schulten, Noise-driven temporal association in neural networks, Europhysics Letters (EPL) 4, 1205–1209 (1987).
  * Kleinfeld and Sompolinsky [1988] D. Kleinfeld and H. Sompolinsky, Associative neural network model for the generation of temporal patterns. theory and application to central pattern generators, Biophysical Journal 54, 1039–1051 (1988).
  * Hertz  _et al._ [1987] J. A. Hertz, G. Grinstein, and S. A. Solla, Irreversible spin glasses and neural networks, in  _Lecture Notes in Physics_ (Springer Berlin Heidelberg, 1987) p. 538–546.
  * Hertz  _et al._ [1986] J. A. Hertz, G. Grinstein, and S. A. Solla, Memory networks with asymmetric bonds, in  _AIP Conference Proceedings_ (AIP, 1986).
  * Ivlev  _et al._ [2015] A. V. Ivlev, J. Bartnick, M. Heinen, C.-R. Du, V. Nosenko, and H. Löwen, Statistical mechanics where newton’s third law is broken, Physical Review X 5, 011035 (2015).
  * Fruchart  _et al._ [2021] M. Fruchart, R. Hanai, P. B. Littlewood, and V. Vitelli, Non-reciprocal phase transitions, Nature 592, 363 (2021).
  * Saha  _et al._ [2020] S. Saha, J. Agudo-Canalejo, and R. Golestanian, Scalar active mixtures: The nonreciprocal cahn-hilliard model, Physical Review X 10, 041009 (2020).
  * You  _et al._ [2020] Z. You, A. Baskaran, and M. C. Marchetti, Nonreciprocity as a generic route to traveling states, Proceedings of the National Academy of Sciences 117, 19767 (2020).
  * Yifat  _et al._ [2018] Y. Yifat, D. Coursault, C. W. Peterson, J. Parker, Y. Bao, S. K. Gray, S. A. Rice, and N. F. Scherer, Reactive optical matter: light-induced motility in electrodynamically asymmetric nanoscale scatterers, Light: Science and Applications 7, 10.1038/s41377-018-0105-y (2018).
  * Drescher  _et al._ [2009] K. Drescher, K. C. Leptos, I. Tuval, T. Ishikawa, T. J. Pedley, and R. E. Goldstein, Dancing volvox: Hydrodynamic bound states of swimming algae, Physical Review Letters 102, 168101 (2009).
  * Osat and Golestanian [2022] S. Osat and R. Golestanian, Non-reciprocal multifarious self-organization, Nature Nanotechnology 18, 79–85 (2022).
  * Baek  _et al._ [2018] Y. Baek, A. P. Solon, X. Xu, N. Nikola, and Y. Kafri, Generic long-range interactions between passive bodies in an active fluid, Physical Review Letters 120, 058002 (2018).
  * Banerjee  _et al._ [2022] J. P. Banerjee, R. Mandal, D. S. Banerjee, S. Thutupalli, and M. Rao, Unjamming and emergent nonreciprocity in active ploughing through a compressible viscoelastic fluid, Nature Communications 13, 4533 (2022).
  * Dinelli  _et al._ [2023] A. Dinelli, J. O’Byrne, A. Curatolo, Y. Zhao, P. Sollich, and J. Tailleur, Non-reciprocity across scales in active mixtures, Nature Communications 14, 10.1038/s41467-023-42713-5 (2023).
  * Mandal  _et al._ [2022] R. Mandal, S. S. Jaramillo, and P. Sollich, Robustness of travelling states in generic non-reciprocal mixtures (2022), arXiv:2212.05618 [cond-mat.stat-mech] .
  * Avni  _et al._ [2023] Y. Avni, M. Fruchart, D. Martin, D. Seara, and V. Vitelli, The non-reciprocal ising model (2023), arXiv:2311.05471 .
  * Abbott and Nelson [2000] L. F. Abbott and S. B. Nelson, Synaptic plasticity: taming the beast, Nature Neuroscience 3, 1178–1183 (2000).
  * Dan and Poo [2004] Y. Dan and M.-m. Poo, Spike timing-dependent plasticity of neural circuits, Neuron 44, 23–30 (2004).
  * Caporale and Dan [2008] N. Caporale and Y. Dan, Spike Timing–Dependent Plasticity: A Hebbian Learning Rule, Annual Review of Neuroscience 31, 25 (2008).
  * Shouval [2010] H. Shouval, Spike timing dependent plasticity: A consequence of more fundamental learning rules, Frontiers in Computational Neuroscience 10.3389/fncom.2010.00019 (2010).
  * Song  _et al._ [2000] S. Song, K. D. Miller, and L. F. Abbott, Competitive Hebbian learning through spike-timing-dependent synaptic plasticity, Nature Neuroscience 3, 919 (2000).
  * Fiete  _et al._ [2010] I. R. Fiete, W. Senn, C. Z. Wang, and R. H. Hahnloser, Spike-time-dependent plasticity and heterosynaptic competition organize networks to produce long scale-free sequences of neural activity, Neuron 65, 563–576 (2010).
  * Jambon-Puillet  _et al._ [2024] E. Jambon-Puillet, A. Testa, C. Lorenz, R. W. Style, A. A. Rebane, and E. R. Dufresne, Phase-separated droplets swim to their dissolution, Nature Communications 15, 10.1038/s41467-024-47889-y (2024).
  * Fredriksson  _et al._ [2002] S. Fredriksson, M. Gullberg, J. Jarvius, C. Olsson, K. Pietras, S. M. Gústafsdóttir, A. Östman, and U. Landegren, Protein detection using proximity-dependent dna ligation assays, Nature Biotechnology 20, 473–477 (2002).
  * Schaus  _et al._ [2017] T. E. Schaus, S. Woo, F. Xuan, X. Chen, and P. Yin, A dna nanoscope via auto-cycling proximity recording, Nature Communications 8, 10.1038/s41467-017-00542-3 (2017).
  * Moerman  _et al._ [2023] P. G. Moerman, H. Fang, T. E. Videbæk, W. B. Rogers, and R. Schulman, A simple method to alter the binding specificity of dna-coated colloids that crystallize, Soft Matter 19, 8779–8789 (2023).
  * Weinstein  _et al._ [2019] J. A. Weinstein, A. Regev, and F. Zhang, Dna microscopy: Optics-free spatio-genetic imaging by a stand-alone chemical reaction, Cell 178, 229 (2019).
  * Owen  _et al._ [2023] J. A. Owen, D. Osmanović, and L. Mirny, Design principles of 3d epigenetic memory systems, Science 382, 10.1126/science.adg3053 (2023).
  * Falk  _et al._ [2023b] M. Falk, A. Strupp, B. Scellier, and A. Murugan, Contrastive learning through non-equilibrium memory (2023b), arXiv:2312.17723 .
  * Hopfield [1982] J. J. Hopfield, Neural networks and physical systems with emergent collective computational abilities., Proceedings of the National Academy of Sciences 79, 2554–2558 (1982).
  * Ramsauer  _et al._ [2020] H. Ramsauer, B. Schäfl, J. Lehner, P. Seidl, M. Widrich, T. Adler, L. Gruber, M. Holzleitner, M. Pavlović, G. K. Sandve, V. Greiff, D. Kreil, M. Kopp, G. Klambauer, J. Brandstetter, and S. Hochreiter, Hopfield networks is all you need (2020), arXiv:2008.02217 .
  * Hopfield [1984] J. J. Hopfield, Neurons with graded response have collective computational properties like those of two-state neurons., Proceedings of the National Academy of Sciences 81, 3088–3092 (1984).
  * Koiran [1994] P. Koiran, Dynamics of discrete time, continuous state hopfield networks, Neural Computation 6, 459–468 (1994).
  * Clark and Abbott [2024] D. G. Clark and L. Abbott, Theory of coupled neuronal-synaptic dynamics, Physical Review X 14, 021001 (2024).
  * Note [1] Note that when $\bm{f}[\bm{s},\bm{J}]$ depends on the past trajectory of the system, then $\bm{s}$ in the figure represents the full past trajectory of the system. In practice, when $\bm{f}$ does not only depend on the values of $\bm{s}(t^{\prime})$ in the recent past, it approximated by the instantaneous values of $\bm{s}$, $\bm{\dot{s}}$, $\bm{\ddot{s}}$, … up to a certain order.
  * Fang  _et al._ [2019] X. Fang, K. Kruse, T. Lu, and J. Wang, Nonequilibrium physics in biology, Reviews of Modern Physics 91, 045004 (2019).
  * [71] DLMF, NIST Digital Library of Mathematical Functions, https://dlmf.nist.gov/, Release 1.1.10 of 2023-06-15 (2023), f. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.


Using Conditional Access with Optimistic Data Structures sec:applyin-to-ds In
this section we discuss how can be used to achieve safe memory reclamation
with optimistic data structures such as lists heller2005lazy and external
binary search trees ellen2010non. Operations of many such data structures have
a search phase consisting of multiple reads, wherein a thread continuously
traverses the next fields of nodes until it has visited a set of nodes it is
interested in, where the operation eventually takes effect. After reaching the
nodes of interest, the operation may perform zero or more writes. For example,
in a linked list, a thread might traverse multiple links to find a predecessor
and current node where an operation should take effect.

For ease of exposition we assume that each node fits in a single cache line,
and a cache line contains only one node. Thus, adding a node to a core’s
implies adding a cache line containing the node to the core’s .

We start by stating the following high level directives required for all data
structures to be able to correctly use .

(DI) Replace and Analyse: Replace: all read/write accesses to nodes that can
be freed should be substituted by the corresponding and instructions. This
enables to tag a node and monitor it for concurrent modification and notify
programmers by updating a flag register. Analyze: If a or fails, the operation
should immediately and retry. A failed instruction implies a node could have
been concurrently freed, therefore any future access will not be safe.

(DII) Validate Reachablility: A node is tagged when it is first . In order to
ensure that the tagged node is valid, it should be verified it was reachable
in the data structure after the fact.

We now demonstrate how these directives can be applied to use in different
classes of optimistic data structures. Depending upon the data structures, DI
could be partially relaxed, as we will see in the example of a lazy list or
DII may not be needed as we will see in the example of a lock free stack. The
lazy list requires some more rules which are detailed in the ll.

In Data Structures with Single Writes Data structures with a single write in
their update phase include some list based stacks treiber1986systems and
queues michael1996simple, both of which we have implemented. For the purpose
of illustration, we will consider a list-based unbounded lock-free stack. In
such a stack, a push operation involves reading a top pointer, allocating a
new node for a key value to be pushed, and then doing a Compare-and-Swap (CAS)
to set the node as new top. Likewise, a pop operation consists of reading the
top, and then atomically setting the top to its next node. After a pop, the
unlinked node cannot be freed if a concurrent thread might still access it.

The original operations of the stack could be upgraded to enable by simply
replacing every read with and the CAS with (DI). Then the pop operation could
immediately free the unlinked node as shown in stack. Note, in our pseudocode
CAFAIL is set when a or fails. This is similar to updating a flag register.

Linearizability of the upgraded operations. The correctness follows from the
fact that the top is read using , which adds it to the corresponding thread’s
, upon which the thread starts monitoring for any subsequent modifications to
top. Since the top itself is never deleted it is guaranteed to be always in
the data structure at the time it is added to the (DII). At the beginning of
an operation the is clear and it is only set when the thread receives an
invalidation request for the top when it is modified elsewhere. Later, the
thread attempts to change the top using which atomically checks the for any
interfering memory access. It fails if the is set. This causes the thread to
remove the top from its , clear the using , and then retry the operation.
Otherwise, the thread succeeds by changing top to another node. The push and
pop operations can be linearized on the successful at pushlp and poplp in
stack, respectively. [!htbp] Using with unbounded lock free stack. Lines
annotated as LP are the linearization points.  [1] type Node {Key key, Node
*next} class Stack {Node *top} #define CA_CHECK CAFAILuntagAll(); goto retry;
pushkey newtop = new node(key); retry: t $\leftarrow$ top; CA_CHECK
newtop-¿next = t; &topnewtop; CA_CHECK LP pop retry: t $\leftarrow$ top;
CA_CHECK NULL == t untagAll(); and return; &topt-¿next; CA_CHECK LP free(t)
Note, the call to free at stackfree is safe because whenever a core C1
modifies the top (either for push or pop), any other core C2 having access to
top will fail its because C1 will invalidate C2’s tag by setting its . is ABA-
safe despite the fact that it allows immediate reuse of freed objects. Suppose
a thread T1, in order to insert a new node, reads an address A from the top
into a local variable $t$. Then just before it executes a CAS to set top to
$t$’s next, some other thread T2 removes A by setting a node at address B as
the new top, frees A, and then pushes a new node at this recycled address A,
making it the new top. Now T1 would succeed its CAS (based on address
comparison) as the top still contains the address A, which matches the
expected address stored in its local variable $t$. Thus it incorrectly
succeeds when it should have failed—a typical ABA case. prevents this error as
, unlike a CAS, is not based on comparing two values. Instead, it relies on
the underlying cache invalidation messages to detect that a location has been
modified since it was last read.

##  In Data Structures having Multiple Writes with Locks

Another category of linked concurrent data structures have update operations
wherein threads optimistically traverses a sequence of nodes ending in
multiple updates within a critical section guarded by locks. One example is
the lazy list [heller2005lazy]. Operations of data structures with such design
patterns could be upgraded to enable the proposed technique’s using the
following broad guidance:

  1. 1.

In the search phase, use DI to replace all reads with . Use to remove
previously traversed nodes from current thread’s when they are no longer
required to prove that a node, to be accessed in the future, is reachable in
its data structure at the time it is tagged. If a fails during the traversal
then do and retry the search. For read only operations this will suffice.
Update operations require the following steps:

  2. 2.

Use try locks designed using / (lock) to lock all the nodes identified at the
end of the search. This marks the beginning of a critical section to execute
the updates atomically. If lock acquisition fails on any of the nodes then
unlock the previous nodes (if any), do and retry the operation.

  3. 3.

Within the critical section use normal writes to execute intended updates.
This is safe because the nodes are guarded by the critical section and
therefore cannot be concurrently updated or reclaimed (partial relaxation of
DI).

  4. 4.

If the update is a delete, mark the node before unlinking it. This satisfies
the _no unlinked access rule_.

  5. 5.

Finally, unlock any locked nodes and execute before exiting the operation.
Note that unlock may use regular stores instead of , since locked nodes cannot
be freed by other threads.

By the way of example of a lazylist (in reference to list) we will demonstrate
how we can easily upgrade it to use . Using D1, all the regular reads are
replaced by s in searches, as shown in list. As explained in the
specification, the s atomically: add a node to current thread’s , if it is not
in it already, check that the is clear, and complete a normal read, if the
condition succeeds. However, if the fails (when CAFAIL is set) then it could
be the case that a subset of the nodes in the have been modified (potentially
deleted) since they were last accessed, therefore it may not be safe to read
them. In such a case the is emptied, the is unset using , and the search is
retried. Otherwise it continues and eventually stops when some and nodes of
interest are found (locateret in list). Note, if we do not untag previous
nodes during searches, then since s tag nodes, we will have all the nodes in
the search path added to a thread’s . This could cause s to fail when any node
(relevant to current access or not) in the search path is modified, which
forces operations to retry repeatedly. In other words, certain updates will be
serialized, as if threads acquired a global lock, which will inhibit
concurrency. As a remedy to this problem, threads can untag previous nodes
using and are only required to keep two consecutive nodes tagged at any given
time, which is equal to the number of nodes required to carry out updates,
much like hand-over-hand locking. Furthermore, in order to guarantee searches
are safe we need to ensure that at the time a node is tagged it is reachable
in the list (DII). To see why, assume a case where a thread accesses content
of an arbitrary node using . During this , atomically: a cache line containing
the node will be tagged and then its content will be loaded. Now, if the node
was already marked before it was tagged by the , then a subsequent would
succeed even though the node is marked (logically deleted), which is not safe
as the node could be reclaimed (a error). This is resolved by validating that
a node is not marked, immediately after the that tagged it. If the node is
found to be marked, validation fails and the corresponding operation untags
all nodes and retries. For example, in the lazy list a node is first tagged
during at tagged in list, due to a validate() invoked from tagged2, , or . If
validate() returns False due to the node being marked then the operations
untags all nodes and retries. This way DII is satisfied. [t] based lock.
Precondition: the node containing the lock field should be so that it is
tagged. [1] tryLockbool *lock lockVal $\leftarrow$ lock; CAFAIL or 1 $==$
lockValreturn False; lock1; CAFAILreturn False; return True; unlockbool *lock
*lock $\leftarrow$ 0; safe as a node can only be mutated by owner.  [!t] Using
with lazylist [heller2005lazy]. Lines annotated as LP are the linearization
points.  [1] type Node {Key key, lock, mark, Node *next} class Lazylist {Node
*head} #define CA_CHECK CAFAILuntagAll(); goto retry; validateNode *node
isMarked $\leftarrow$ node-¿mark; CAFAILreturn False; isMarkedreturn
False;return True; locateKey key retry: pred $\leftarrow$ head; CA_CHECK
validatepred; $False$untagAll(); goto retry; curr $\leftarrow$ pred-¿next;
CA_CHECK validatecurr; $False$untagAll(); goto retry; currkey $\leftarrow$
curr-¿key; CA_CHECK currkey ¡ key pred; pred $\leftarrow$ curr; CA_CHECK curr
$\leftarrow$ curr-¿next; CA_CHECK validatecurr; $False$untagAll();goto retry;
currkey $\leftarrow$ curr-¿key; CA_CHECK return $\langle$ pred, curr, currkey
$\rangle$; containkey $\langle$ pred, curr, currkey $\rangle$ $\leftarrow$
locate(key); LP:When currkey was read. (); return (currkey == key); insertkey
retry: $\langle$ pred, curr, currkey $\rangle$ $\leftarrow$ locate(key); $LP$
when insert fails. currkey == key; & return False; False ==
tryLock(&pred-¿lock) attempt locking pred. & retry; False ==
tryLock(&curr-¿lock) attempt locking curr. unlock(&pred-¿lock); & retry; node
$\leftarrow$ new Node(key, curr); pred-¿next $\leftarrow$ node; $LP$ when
insert succeeds. unlockAll() and ; return True; deletekey retry: $\langle$
pred, curr, currkey $\rangle$ $\leftarrow$ locate(key); $LP$ when delete
fails. currkey != key; & return False; False == tryLock(&pred-¿lock) attempt
locking pred. ; & retry; False == tryLock(&curr-¿lock) attempt locking curr.
unlock(&pred-¿lock); ; & retry; curr-¿mark $\leftarrow$ true; $LP$ when delete
succeeds. pred-¿next $\leftarrow$ curr-¿next; unlockAll(); & ; free(curr);
return True;  One may further ask, what if the node was marked (already
logically deleted) and also freed before it is tagged? In that case a
subsequent could succeed as its will not be set since no update will occur
after the node was tagged. This could cause a error. However, this cannot
happen because, in order to free the node, a reclaimer has to unlink it by
modifying the next field of its predecessor, which is already in the thread’s
. Thus, if the predecessor node is modified the thread’s will be set and the
will fail, preventing unsafe access. This invariant is maintained during a
search that eventually yields a and that were reachable in list at the time
they were tagged. Later, before starting the updates, locks on the and nodes
are acquired (ilockpred & for insert() and dlockpred & for delete()). However,
it may happen that after the search returns the nodes and before the locks are
acquired some thread may delete these nodes. In that case if the lock is
accessed with normal reads and writes then the thread may attempt acquiring
lock on a freed node which could lead to undefined behaviour: unlike s,
regular reads do not have the ability to check whether the nodes have been
modified. Thus, to resolve this issue we provide / based try locks which only
acquire the lock on a node if it has not been modified (deleted) concurrently.
lock depicts the implementation of this lock. It has a precondition that the
node containing the lock field should have been previously accessed using so
that it gets added to its thread’s , enabling a / to verify through whether
the node has been modified since then. In further detail, a thread does a on
the lock variable. If it sets CAFAIL, the node of which the lock is part might
have been deleted; if it returns $1$, it means that lock is busy. In both the
cases, the lock acquisition fails. Otherwise, a thread proceeds to acquire the
lock by setting the lock field to 1 using a , which again checks if the node
containing the lock field has not been modified (possibly deleted). If the
check succeeds it writes 1 to the lock field and returns True, indicating that
lock acquisition is successful. Otherwise if the fails (by setting CAFAIL) it
returns False indicating that lock acquisition has failed, and the operation
which invoked the lock untags all nodes and retries. The insert
operation(insproc, list), first executes locate, which returns tagged and
nodes along with currkey (key field of ). If the key to be inserted is already
present in the list then the operation returns false. Otherwise, the key is
not present and needs to be inserted. To insert the key, first the based
trylocks on the and nodes are acquired, then a new node is created and
inserted between pred and curr. Following that all locks are released, nodes
are untagged, and then the operation returns true. Note, because the and nodes
are already locked, no other thread could ever modify them without acquiring
lock first. Therefore, validation to check whether the node has been
concurrently freed is not needed. This allows us to use normal reads and
writes instead of / within the critical section. The delete operation(delproc,
list) invokes locate, which returns tagged and nodes along with currkey. If
the key to be deleted is not present in the list then the operation untags the
nodes and returns false. Otherwise, similar to the insert operation, it
acquires the trylocks on both nodes, does a write on the node to set its mark
field, unlinks the node, unlocks and untags both the nodes, frees the node and
then returns true.

###  Correctness

If all the aforementioned rules are followed to enable in the lazylist then
the list is linearizable and all access in it are safe. Contains or
unsuccessful inserts and deletes, which behave like contains, can be
linearized at the time when the key of was read. Whereas, successful inserts
and deletes can be linearized when a new node is linked (insadd) or a node is
marked (delmark), respectively. Also, because s never dereference an
unreachable (unlinked) node, errors do not occur. Therefore the lazy list with
is safe. The following section discusses the correctness in detail. A node’s
predecessor is unmarked and its next field points to the node at the time it
is tagged. [Safety] Threads cannot access reclaimed nodes in the based list.

##  Using in data structures with multiple writes that do not use locks

I don’t think this subsection provides any value. In fact, it implies that CA
can’t do these other data structures, but I’m not convinced that’s true.
Rather than say we’d need to extend CA, why not just omit this, and the reader
can infer that we haven’t fully fleshed out the details. (Note: part of my
saying this is because we had that discussion about how one can use various
methods to ”pin” a location by refcounting it or installing a descriptor or
other things, and in part because even the M&S queue has more than one write
and no locks, so I don’t feel like 4.1 makes a strong case… this section may
lead to a reader to go back and say ”4.1 only applies to a simple stack” Data
structure that do not use locks in update phase and write on multiple
locations would require more complex variant of primitive that allows
validating and updating multiple location at the same time. Supporting HBR
based immediate reclamation for these data structures may seem to be a natural
extension of the current manuscript, but it would require careful design to
guarantee progress and correctness properties, so we leave it out of the scope
of the present work. listCorrectness