A Survey on Analog Models of Computation
A Survey on Analog Models of Computation
Olivier Bournez, Amaury Pouly
To cite this version:
Olivier Bournez, Amaury Pouly. A Survey on Analog Models of Computation. Handbook of Computability and Complexity in Analysis, Springer International Publishing, pp.173-226, 2021, Theory
and Applications of Computability, �10.1007/978-3-030-59234-9_6�. �hal-04303956�
HAL Id: hal-04303956
https://cnrs.hal.science/hal-04303956v1
Submitted on 5 Feb 2024
HAL is a multi-disciplinary open access
archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.
L’archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d’enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
A Survey on Analog Models of Computation
arXiv:1805.05729v1 [cs.CC] 14 May 2018
Olivier Bournez and Amaury Pouly
Abstract We present a survey on analog models of computations. Analog can
be understood both as computing by analogy, or as working on the continuum. We
consider both approaches, often intertwined, with a point of view mostly oriented
by computation theory.
1 Introduction
There is a clear ambiguity about the sense of the word analog when talking about
analog computations. Nowadays, it is often understood as being the opposite of digital: the former is working on continuous quantities, while the latter is working over
discrete values, typically bits or words. However, historically, analog computation
got its name from computation by analogy, i.e. by systems built in such a way that
they evolve exactly as the system intended to model or simulate [243, 328]. These
two understandings are orthogonal and various machines analog in both or one and
not the other sense have been conceived [328]. Notice also that even discrete vs
continuous is not a clear dichotomy, and most of the analog machines that were
historically built were actually hybrid [328].
We will mainly focus on models of computation, with a point of view possibly oriented by computation theory (computability, complexity, models of computation).
All considered models can be described as particular dynamical systems: a dynamical system is mathematically defined as the action of a subgroup T of R on
a space X, i.e. by a function (a flow) φ : T × X → X satisfying the following two
Olivier Bournez
Olivier Bournez, Campus de L’Ecole Polytechnique, 91128 Palaiseau Cedex France, e-mail:
bournez@lix.polytechnique.fr
Amaury Pouly
MPI-SWS, E1 5, Campus, 66123 Saarbrücken, Germany e-mail: pamaury@mpi-sws.org
1
2
Olivier Bournez and Amaury Pouly
equations:
φ (0, x) = x
(1)
φ (t, φ (s, x)) = φ (t + s, x).
(2)
Function φ (t, x) is intended to give the position at time t of the system if started
at position x at time 0, and the above equations simply express expected properties.
Subgroups T of R are known to be either dense in R or isomorphic to the integers. In the first case, the time is said to be continuous, in the latter case, discrete.
A dynamical system is often alternatively described by some space X and some
function f : X → X. Indeed, in the discrete time case, giving φ is equivalent to
giving f : X → X with f (x) = φ (1, x): the trajectory starting from some state x0 then
corresponds to the iterations of f on x0 from Equation (2). In the continuous time
case, not all dynamical systems correspond to differential equations, but at soon as
φ is continuously differentiable, a case covering a very wide class of systems in
practice, we can write y′ = f (y) where f (y) = dtd φ (t, y) t=0 . Giving φ is then also
equivalent to giving a function f : X → X: the trajectory starting from some state x0
corresponds to the solution of the Initial Value Problem (IVP) y′ = f (y), y(0) = x0 .
We can then classify models according to their space X: we will mainly focus in
this chapter on the case where the space X involves real numbers, i.e. is continuous.
Typically X = Rn or X = Rn × Nk or can be encoded naturally in similar spaces.
We will say that such a space is continuous, by opposition to spaces like Nk (or
the set of words over a given alphabet, or the set of configurations of a model such
as a Turing machine) that would correspond to a discrete space. Discrete time and
space corresponds to classical computability and complexity and are not intended
to be covered by this chapter. We will nevertheless consider some unconventional
discrete time and space models, such as population protocols or chemical reaction
networks, as they are unconventional and turn out to be closely related to analog
models as shown by various recent results.
A classification of some of the models considered in this chapter according to
this discrete/continuous time/space dichotomies is provided by Figure 1. This classification is not perfect and debatable. For example, cellular automata (that we will
consider later on as a spatial model) are here considered as evolving over a discrete
space. But there may also be considered as evolving over {0, 1}N (i.e. Baire’s space),
and we agree that there is no fundamental difference between R and {0, 1}N . As another example, the discrete-space / continuous-time quadrant is rather empty, but we
agree that many models have an underlying semantics that can be expressed in the
language of continuous-time Markov chains, and for example stochastic chemical
reaction networks could also fall in this quadrant. Actually, many models come indeed in various flavours and could be turned into various quadrants: For example,
asynchronous cellular automata can arguably be considered as being continuous
time and discrete space, or continuous time and continuous space.
Notice that many quantum models of computation can also be considered possibly as analog and would fit to this description: as we have to make choices, we
decided that they are out of the scope of the current chapter. Notice that analog
models, in particular models in the continuum, can be seen as fitting in some way
A Survey on Analog Models of Computation.
Space
Time
Discrete
Continuous
3
Discrete
Continuous
Turing machines
Lambda calculus
Recursive functions
Post systems
Cellular automata
Stack automata
Finite State Automata
Neural networks (Section 2.3)
Deep Learning models (Section 2.3)
Blum Shub Smale machines (Section 2.5)
Hybrid Systems (Section 2.4)
Natural Computing Influence Dynamics (Section 2.6)
Signal machines (Section 2.10.3)
Continuous Automata (Section 5.3)
..
.
Population Protocols (Section 2.8)
Chemical Reaction Networks (Section 6.5)
Petri Nets
..
.
Boolean Difference Equation models
Shannon’s GPACs and (Section 2.2.1)
Hopfield’s neural networks (Section 6.1)
Physarum computing (Section 2.6.2)
Reaction-Diffusion Systems (Section 2.11)
Hybrid Systems (Section 2.4)
Timed automata (Section 2.4.1)
Large Population Protocols (Section 2.8.1)
Black Hole Models (Section 2.9)
Computational Fields (Section 2.10.1)
R-recursive functions (Section 5.2)
Spiking neuron models (Section 2.3)
..
.
Fig. 1: A tentative classification of some computational models, according to their
space and time.
in between classical and quantum models. Several results about quantum models
are deeply using the fact that the underlying space is the field C of complex numbers, while analog models can sometimes emulate some of the constructions by
working over R2 . Similarly, computations with quantum models sometimes assume
measurements to be possible at unit cost, while this is not considered as possible in
most analog models. Discussing analog models helps to understand in that spirit the
aspects which are closely coupled to quantum world from the others.
Since most of the other chapters of this book are dedicated to the computable
analysis framework, we will intentionally not discuss this approach in the current
chapter.
Previous surveys on the field of analog computation include Pekka Orponen’s
[269], Olivier Bournez and Manuel L. Campagnolo’s [65] focusing on continuous
time computation, and Bruce J. MacLennan’s chapter on “Analog Computation” of
the Encyclopedia of complexity and systems science. [243]. A recent very instructive
book about the history of analog machines has recently been published [328]. There
4
Olivier Bournez and Amaury Pouly
is also an extensive literature, mostly forgotten today, about analog machines dating
to the times where most of machine programming was analog.
2 Various Analog Machines and Models
2.1 Historical Accounts
As we said, historically, analog computation was mainly referring to computation
by analogy. Very instructive quotations supporting this claim can be found in [328]
and [243].
Actually, several of the historical first computers presented as among the first
ever built digital computers turn out to be analog in this above primary sense. This
includes the ENIAC, which interestingly stands for “Electronic Numerical Integrator and Computer’’. The ENIAC is often said to be “programmed” but the term
“wired” would be closer to reality, since this sytem mainly consisted of a large
collection of arithmetic machines.
It may also help to understand that the term computer was historically referring
to a person who carried out calculations or computations. From the middle of the
20th century only, the word started to refer to a machine that carries out computations. Determining which systems can actually be considered as computers is a very
intriguing question, related to deep philosophical questions out of the scope of the
present chapter.
We however list here some of the first ever built machines that can be classified as analog: This includes Blaise Pascal’s 1642 Pascaline, as well as Johann
Martin Hermann’s 1814 Planimeter (a simple device to compute surfaces based
on Green’s theorem), or Bill Phillips’s 1949 MONIAC (Monetary National Income
Analogue Computer, a machine that was using fluidic logic to model the behavior of
an economy). The Antikythera mechanism, discovered close to the greek island of
Antikythera in 1901, dated from earlier than 87 BC, whose purpose was to predict
astronomical positions and phenomena, is also often considered as an analog computer. However, even if these machines were clearly computing various quantities
or data and may or may not be called computers, we admit that even the question of
whether such machines can be classified as analog is debatable. Indeed, many articles or books consider them as such nowadays (see e.g. [328]), but these statements
are conflicting with the literature in the history of computing from historians.
However, with no contest, the first truly programmable (“general purpose” using
Shannon’s 1941 terminology) analog computer is Vannevar’s Bush 1931 Differential
Analyser, which is the topic of the next section due to its historical and fundamental
importance.
Further detailed historical accounts about analog machines and computations can
be found in the recent monograph [328]. Its author, Bernd Ulmann also maintains
an informative web site with instructive pictures and videos [1].
A Survey on Analog Models of Computation.
5
The history of analog computation and devices, is also discussed by historians.
For general literature on history of analog computers, refer to [110], [252] or [335].
For references related to history of analog instruments, see [170], [169]. The history
of Differential Analyser is discussed in [271]. See also [200] and [199] for national
accounts about the developments of differential analysers. Historical accounts for
ENIAC can be found in [197]. Recently published accounts also include monograph
[292], the analysis of the work of Douglas R. Hartree [159] , Charles Babbage [156]
or of particular devices or techniques [157, 158] before differential analysers.
2.2 Differential Analysers
The probably best known universal continuous time machine is the Differential Analyzer (DA), built for the first time in 1931 at the MIT under the supervision of
Vannevar Bush [91]. The idea of assembling integrator devices to solve differential
equations dates back to Lord Kelvin in 1876 [323]. Kelvin was looking for a faster
way to compute the harmonics of a function using its Fourier transform, with applications to tidal and meteorological observations. He came up with the idea of using
a rotating disc-cylinder-globe system to compute the integral of a product: this is
essentially the fundamental operation of the Differential Analyzer, although it took
over 50 years to solve the mechanical problems involved in this machine.
The first DAs were entirely mechanical, and later became electronic: see [81,
328]. Their primary purpose was to solve differential equations, especially the ones
coming from problems in engineering. By the 1960s, differential analysers were
progressively discarded in favor of digital technology. Many accounts on the history
and applications of these machines can be found in [328].
2.2.1 Mathematical Model of the Differential Analyzer: the GPAC
The General Purpose Analog Computer (GPAC) was introduced by Shannon in
1941 as a mathematical idealization of the Differential Analyzer [305], while he
was working on this machine at the MIT to get money for his studies. A GPAC is
basically a circuit made up of a finite number of units, described in Figure 2, that are
interconnected by wires, possibly with loops (retroactions) on some of the wires. A
function f : R → R is said to be generated if it corresponds to the value read on
some of the wires of the circuit as a function of time.
The model was later refined in a series of papers [286, 229, 188, 186]. Indeed, a
GPAC circuit may not define a unique function (it could have no or several solutions)
which is problematic. An arguably more modern presentation of the GPAC is to use
ordinary differential equations instead of circuits. The equivalence of GPAC circuits
with polynomial ordinary differential equations will be discussed in Section 7.1.
Rubel also introduced the Extended Analog Computer (EAC) as an extension
of the GPAC [295]. The EAC features a broader class of operations such as par-
6
Olivier Bournez and Amaury Pouly
tial differentiation and restricted limits, allowing to solve boundary value problems.
Rubel’s motivation for introducing the EAC was that the GPAC was “a limited machine”. This claim has been somewhat changed since then (see Section 7.1) and the
EAC has seen few theoretical developments. Although Rubel envisioned the EAC
as a “purely conceptual machine”, there is ongoing research to implement it, with
some currently working prototypes [254, 256, 255].
k
k
u
v
+
u+v
A constant unit
An adder unit
u
v
u
v
×
uv
A multiplier unit
R
R
w = u dv
An integrator unit
Fig. 2: Basic units used in a GPAC circuit.
2.3 Neural Networks and Deep Learning Models
In the 80’s and 90’s, artificial neural networks gave birth to a renewal of interest
in analog computations. This enthusiasm declined until recently and the success of
deep learning in several impressive applications in various fields of artificial intelligence, such as speech recognition, image recognition and natural language processing. The first machine able to beat all best professional Go players is based on deep
learning technology.
Current deep learning models may have a rather complex architecture built from
various modules, but most of these modules are essentially artificial neural network
models. An artificial neural network (ANN) consists of many simple, connected
processors called neurons. The state of each neuron is given by some real number called its activation value. Designated input neurons get their activation values
from the environment. All other neurons evolve by applying a composition of a certain one-variable function σ (usually a sigmoid) with an affine combination of the
activations of the neurons to which they are connected. Finally, specific neurons,
considered as output neurons, may trigger actions on the environment: see [55] for
an overview.
Most of the work related to (deep) artificial neural networks is nowadays devoted
to finding architectures and weights that make an ANN exhibit a desired behavior
in a given context of application A popular library to describe corresponding architectures is Tensor Flow [2]. This is basically a library to describe such architectures,
A Survey on Analog Models of Computation.
7
and hence can be considered in many aspects as a library for particular analog computations.
A very popular and successful method to determine suitable weights for solving
a given problem is back-propagation, which is reinforcement learning technique
based on a gradient descent method applied to an error function expected to be
minimized over the learning set, see [55].
Applying any gradient descent method requires a differentiable error function
with respect to all involved parameters. The very large number of applications of
deep learning techniques have recently led to the emergence of various other analog models of computation. All these models have in common to be differentiable
end-to-end versions of models inspired by classical computability. This includes
the popular Long Term Short Memory (LTSM) architecture [206], or the so-called
Differentiable Neural Computers [190], or the Neural Turing machines [189]. The
underlying principle of these constructions is to extend an artificial neural network
by coupling it to an external memory resource. This external resource can also be
a stack as in the so-called Neural Network Pushdown Automata [320] and Neural
Stack machines [191].
The models discussed previously all work in discrete time, but models with a
continuous time dynamics have also been considered, such as symmetric Hopfield
networks. The convergence behavior of these networks has been used in various
applications such as associative memory, or combinatorial optimization problems
after first applications in [212].
Models based on spiking neurons have been claimed to be biologically more
realistic [236]. Various coding methods exist to interpret the outgoing spike train as
a real value number either relying on the frequency of spikes, or the timing between
spikes. This yields to various ways of encoding information and the computational
power of spiking neuron models has been investigated in series of papers: see [311],
[236] or [179] for surveys. Recent years have seen practical implementations [249]
as well as their use to solve practical problems efficiently [149].
2.4 Models from Verification
The development of algorithms and techniques for verification or control of socalled hybrid systems or cyberphysical systems have also generated several lines
of research related to analog computation. Hybrid and cyberphysical systems have
in common to mix discrete evolutions, often a digitally engineered controller, with
continuous dynamics that often comes from the environment or from some natural
continuous variables that the controller acts upon.
There is an extensive literature on the hybrid automata modeling approach to determine the exact frontier between decidability and non-decidability for reachability
properties, according to the type of dynamics, guards, and resets allowed. The same
holds for the frontier about applicability of techniques coming from control to prove
properties about these systems such as stability. Providing a complete panorama on
8
Olivier Bournez and Amaury Pouly
this literature is out of the ambition of the current chapter. Classical survey references are [204, 14]. See also [65] for discussions.
This literature is the source of many dynamic undecidability results to which we
will come back in Section 3.3.
Hybrid systems are known to exhibit the so-called Zeno’s phenomenon. In short,
they may happen to have an unbounded number of discrete transitions in a bounded
(continuous) time. In this context, it is classical to distinguish various types of
Zeno’s behaviour: Chattering Zeno vs Genuine Zeno, following [16]. The first type
can often be eliminated and corresponds more to an artefact of the model, which
can be avoided by considering an appropriate notion of solution, while the second
is more problematic to detect and harder to avoid in simulation [17]. We will come
back in Section 4.4 to Zeno’s phenomenon in the wider perspective of space time
contraction phenomena in analog systems.
Despite some promising early results in the field, open problems even for very
simple classes of systems still remain. In particular, the decidability of the reachability problem for piecewise affine maps on the real line is a famous open problem,
with some partial progress such as [223, 47]. Several other questions seem to be
closely related to that issue [32]. The decidability of point to hyperplane reachability for discrete time linear systems, known as the Skolem problem, is famously
open. The continuous time version of point to hyperplane has recently been shown
to be related to conjectures from transcendental number theory [122]. Hardness of
recurrent reachability for continuous linear dynamical systems of low dimensions
has been investigated in [123].
Several recent results have also focused on the hardness of bounded time versions
of reachability problems. The complexity of the reachability problem has been characterized for hybrid automata in [87], and for piecewise affine systems in [48] and
[39]. Complexity of problems or methods from control theory have also been explicitly derived [10, 11, 8, 9].
In relation with other chapters of this handbook, we mention that the recursive
analysis approach has also been explored. Computability of reachable and invariant
sets in the framework of computable analysis have been investigated for continuous
time systems [126] and for hybrid systems [127].
A method to approximate hybrid systems with a polynomial hybrid automaton,
i.e. a Taylor approximation, has also been proposed [225], as well as interval methods and Taylor model methods for ODEs [266]. There have been attempts to provide
a formal semantics to Simulink based on non-standard analysis tools [53]. More
generally, providing models of systems using ordinary differential equations is an
hard task in practice: See e.g. very instructive discussions in [226] about all the
difficulties in modeling a simple system such as Newton’s pendulum.
2.4.1 Timed Automata
Timed automata [13] can be considered as a restricted version of hybrid systems for
which decidability of reachability holds. They can also be considered as an exten-
A Survey on Analog Models of Computation.
9
sion of finite automata with clocks. The model has clear practical applications and
is at the heart of several computer tools for verification: see e.g. recent survey [78].
From a more fundamental point of view, timed automata can be seen as language
recognizers [13], and there has been various attempts to generalize concepts from
finite automata theory to this framework. This includes closure properties of recognized languages [13], pumping lemmas [41] as well as variants of Kleene’s theorem
[26, 27, 28, 79, 80, 29]. For a recent survey about timed automata, see [78].
2.5 Blum-Shub-Smale’s Model
The Blum-Shub-Smale (BSS) model [58] has been introduced as a discrete time
model of computation over the reals in order to discuss hardness of problems in
algebraic complexity. In the initial presentation of the model, operations of the field
R are assumed to be realizable at unit cost, leading to classes such as PR and NPR ,
with complete problems such as the existence of a real zero of a given polynomial.
Later, it has been generalized to other fields or rings with extended or restricted
operations [57], or to an abstract model over arbitrary logical structures [285]. Notice that classical discrete computability models have been generalized to abstract
structures in various ways in parallel, and also before [58]: See e.g. [174], [260] or
[325].
The obtained computability and complexity theory subsumes classical discrete
computation theory since the latter can be seen as the specific case of logical structures with a finite domain.
There is an extensive literature on the related computation theory. Many results
have been obtained in this model, mostly studying the corresponding complexity
classes, and their relations with classical questions in computability theory, or providing lower or upper complexity bounds on various problems based in this framework: See [57, 285].
Recent results include non-trivial generalizations to this framework of Toda’s
theorem [36, 37] or the PCP theorem [35], interactive proofs [34], Ladner’s result
[246], as well as separation of degrees [178, 177].
The model is different in spirit from most others discussed in this section, as it is
usually not considered to be an attempt at modeling analog machines in a realistic
way, but rather as a mathematical tool. It has proven to be relevant for the discussion
of lower bounds in algebraic complexity, or for some classical questions from complexity theory in a wider generalized setting, where sometimes complexity classes
such as P and NP can be separated. The model has also clear connexions with the
generalized finite automata models discussed in Section 5.3.
10
Olivier Bournez and Amaury Pouly
2.6 Natural Computing
The interest in unconventional models of computation, and in particular for natural
computing, has revived interest in analog computing.
2.6.1 Dissipative Influence Dynamics
The framework of natural algorithms, has motivated a series of works about models of influence systems and their computational capabilities. A manifesto in favor of
the fact that the study of natural systems can benefit from an algorithmic perspective
has been published in [115]. This has motivated the exploration of several models of
influence dynamics such as the Hegselmann-Krause’s model. In particular, bounds
on the time required by a group of birds to stabilize in a standard bird flocking
model have been established in [116]. Turing completness and almost sure asymptotic periodicity of diffusive influence systems have also been obtained in [118].
For a general discussion on the merits and challenges of an algorithmic approach to
natural algorithms, see [117].
2.6.2 Physarum Computing
Physarum polycephalum is a slime mold that has been shown to be able to solve
various natural problems: this includes realization of boolean logic gates, implementation of delay in computing circuits, geometry computations such as Voronoi
diagrams or Delaunay triangulations, or computation of shortest paths [5]. Models
of various aspects of its behaviour have been established. Convergence proofs and
complexity bounds for computing shortest paths have been investigated [42], based
on mathematical model for the slime’s behavior proposed in the form of a coupled
system of differential equations [322]. Implementation of Kolmogorov-Uspensky in
biological substrate has also been investigated [4]. For a survey about these fields of
research, see [5].
2.6.3 DNA and Molecular Computing
Areas such as systems biology aim at understanding complex biological processes in
terms of their basic mechanisms at the molecular level. Many attempts of applying
concepts and tools from theoretical computer science to this framework (logic, algebra, etc..) have been investigated, with numerous successes and concrete software
systems: see [165].
However, even if the primary purpose of these fields was to explain concrete
biological features, various approaches have considered computations by chemical
reactions as a programming tool. The idea is to consider computations by reactions
as programs to solve various tasks, as nature does in the context of cell biology, but
A Survey on Analog Models of Computation.
11
not restricting to this context. In particular, various attempts to relate this concept
of programmation to computation theory have been proposed. In most of these approaches, the underlying principle is to get inspiration from concrete chemical phenomenon in order to derive abstract models of computation which are potentially
usable. This includes the model of biomolecular computation [198], the Chemical
Abstract Machine [54], Membrane Computing models [273], Biochemical Ground
Form process algebra’s approaches [109], DNA based computation models [287],
or Chemical Reaction Networks (CRN) discussed in Section 6.5.
Simulations of Turing machines has been demonstrated in several of the above
mentioned articles, both at an abstract level or concretely. A very challenging question is to compare the actual implementations in nature of some of the tasks to other
possible more efficient ones that could be derived theoretically [166].
For a presentation of natural computing models and results not covered in this
chapter, see [293, 272]. In this chapter, we will only briefly discuss the case of DNA
computing (below) as well as that of CRNs (Section 6.5).
DNA computing started with a work [7] which proposed to solve the directed
Hamiltonian path problem on a graph using DNA as well as enzymes to implement
the computation. Molecular computation had been investigated in various ways before popular Adlmenan’s article (see e.g. [129]), including the idea of using DNA
computing to implement computations of formal language theory [201]. This has
been extended later on to other known NP-complete problems [230], even if the
required resources have been demonstrated to be unrealistic. Approaches based on
evolutionary computation to control resources have also been proposed [319]. The
field developed meanwhile in many impressive ways. Visible facts include the development of a programmable molecular computing machine [235], the demonstration
of the use of DNA as digital storage medium encoding a 5.27-megabit book [124],
or the construction of the analog of a DNA transistor [61].
2.7 Solving Various Problems Using Dynamical Systems
Several authors have shown that certain, possibly discrete, decision or optimization
problems such as graph connectivity or linear programming, can be solved by specific continuous dynamical systems. Some examples and references can be found in
the papers [312, 329, 90, 168, 202, 50, 259, 56]. This has links with various mechanical computer models (e.g. “billard ball computers”) investigated by several papers
in the 70s and 80s, with discussions about physical limits to computations such as
thermodynamic reversibility [51, 173, 52, 244]. Relevant concepts have turned out
to still be important in quantum computing (e.g. Tofolli gates, etc.). This is also
related to discussions about various phenomena possibly capable of hypercomputation [245, 300]: see in particular Section 2.9 about Black Hole computations for
more recent references.
Observe that, if analog computation is to be understood in the sense of computing
by analogy, then almost any historical analog machine can be considered as falling
12
Olivier Bournez and Amaury Pouly
under this framework. In his monograph, Ulmann develops with sometimes great
and instructive details some of the machines for particular problems such as finding
zeros of a polynomial, linear algebra, optimization and simulation [328]. In more
than 70 pages various historical applications in about 20 fields such as Mathematics,
Physics, Mechanics, Geology and Economics are described.
The question of whether some of the discrete problems could actually be solved
faster using continuous methods is very intriguing: this is the object of Section 4.4.
Many dynamical systems of the form H ′ = [H, [H, N]], where the notation [B, L]
stands for BL − LB, have been shown to be continuously solving some particular
discrete problems [90, 89] such as sorting lists, diagonalizing matrices and linear
programming problems. One key property is that this equation is equivalent to some
gradient flow on the space of orthogonal matrices. Many examples in this spirit
are discussed in details in [203]. More recently a system of nonlinear differential
equations of a similar form to sort numbers fed to the input has been investigated
[183].
Notice that several discrete time algorithms or methods have some analog equivalent. This includes Newton’s method which leads to Newton’s flow dynamics for
finding roots. Gradient descent methods (this includes the very popular Backpropagation method for Neural Networks) can also be considered as the (explicit) Euler’s
discretization method of a continuous flow, the so-called gradient’s flow.
The use of analog methods for solving k-SAT problems has been investigated
in [161]: the problem is mapped to an ordinary differential equation about which
some properties are established, such as chaotic transience of trajectories above a
constraint density threshold and fractality of the boundaries between the basin of
attraction. The system is stated to always find solutions in polynomial continuous
time, but at the expense of exponential fluctuations in its energy function [161]. An
attempt to physically implement the proposed dynamic has been proposed [337].
Previous statements that k-SAT can be formulated continuously can be found in
[193, 265, 330].
Notice that polynomial-size continuous-time Hopfield nets have been proven able
to simulate PSPACE Turing machines [310]: This implies that even ODEs with
Lyapunov-function controlled dynamics can actually do much more than solving
NP-complete problems in some sense.
2.7.1 Interior Point Methods
A particular class of methods falls very naturally into this framework: the so-called
interior point methods, which correspond to a particular class of algorithms to solve
linear and nonlinear convex optimization problems. The principle, already proposed
by John von Neumann, and very popular in the 1960s, is to build a continuous system whose trajectories are evolving in the interior of the feasible region. A common
method to guarantee evolution in the feasible regions was the use of barrier functions acting as a potential energy. By making these functions tend to infinity on the
boundary, the evolution is guaranteed to remain feasible.
A Survey on Analog Models of Computation.
13
Later, these methods were mostly considered as inefficient until Karmakar triggered a revolution in the field of optimization by providing the second polynomial
time algorithm for linear programming [217, 215]. It has then been realized that
Karmakar’s algorithm is equivalent to a particular interior point method [180, 38].
Notice that, historically, the first polynomial time algorithm for linear programming
is due to Khachiyan and is based on ellipsoid method (which is not an interior point
method).
A very elegant presentation of Karmakar’s algorithm and the associated flow,
inspired from [24], can be be found in [259], including an elegant presentation of its
polynomiality based on ordinary differential equation arguments. Refer to [290] for
a general introduction to interior point methods.
2.8 Distributed Computing
Recent years have also seen the birth of new classes of models in distributed computing. In particular, the model of population protocols consists of passively mobile
anonymous agents, with finitely many states, that interact in pairs according to some
rules, i.e. a given program [21]. Passively mobile means that agents have no control
over the other agents with whom they will interact. The model was initially introduced in the context of sensor networks, but it is nowadays considered as a fundamental model for large passively mobile populations of agents with resource-limited
anonymous mobile agents.
Most works on the model have considered these protocols as computing predicates over multisets of states. Given some input configuration, the agents have to
decide whether this input satisfies a given predicate: the population of agents has
to eventually stabilize to a configuration in which every agent is in a particular accepting (respectively rejecting) state if and only if the predicate is true (resp. false).
The model is uniform: the program is assumed to be independent of the size of the
population.
The seminal work of Angluin et al. [22, 21] proved that predicates decided by
population protocols are precisely those on counts of agents definable by a firstorder formula in Presburger arithmetic – equivalently, this corresponds to semilinear
sets. An elegant proof of this result can be found in [162]. Note that this computational power is rather restricted, as multiplication for example is not expressible in
Presburger arithmetic.
The model has been intensively investigated since its introduction. Several variants have been studied in order to strengthen it with additional realistic and implementable assumptions. This includes natural restrictions, like modifying hypotheses on interactions between agents (e.g., one-way communications [22], particular
interaction graphs [20]). This also includes probabilistic population protocols that
assumes random interactions [21]. Fault tolerance has also been considered [145],
including self-stabilizing solutions [23]. For some introductory texts about population protocols, see for instance [33, 251].
14
Olivier Bournez and Amaury Pouly
The model can be seen as a particular case of the (stochastic) chemical reaction
networks discussed in Section 6.5.
Here, we focus on models and results in the context of distributed computing,
and mainly discuss computability issues. Covering all works devoted to variants of
population protocols in the distributed computing community is out of the ambition
of this chapter: see [33, 251] for surveys. Among many variants of population protocols, the passively mobile (logarithmic space) machine model was introduced by
Chatzigiannakis et al. [114]. It this model, each agent carries a bounded space Turing machine, instead of a finite state automaton. In an orthogonal way, community
protocols, where each agent has a unique identifier and can only store O(1) other
agent identifiers, exclusively from agents that it met, were introduced by Guerraoui
and Ruppert [194]. They proved, using results about the so-called storage modification machines [304], that such protocols simulate Turing machines very efficiently.
A hierarchy between the two models has also been studied recently, by considering the case of homonyms, that is to say when several agents may share the same
identifier [67, 68].
The population protocols can also capture natural models of dynamics of some
opinion spreading models by considering probabilistic rules of interactions: results
on the convergence and threshold properties of the so-called Lotka-Volterra population protocol have been established [142].
Notice that many models coming from dynamics of rational agents in the context
of (learning equilibria in) Game Theory can also be considered as analog distributed
models of computation [331, 207].
2.8.1 Large Population Protocols
When considering probabilistic interaction rules, as in the previously mentioned
settings, the underlying dynamical system is a Markov chain.
If the population of agents is large, the random process converges to its (deterministic) limit continuous dynamic given by some ordinary differential equation
(also called its mean-field limit): this corresponds to the differential semantics discussed in Section 4.1 for chemical reactions.
These considerations led to the so-called Large Population Protocols [71]: real
numbers which correspond to limit ratio of programmable dynamics by such model
have been demonstrated to correspond precisely to algebraic numbers [71]. This
results has many similarities with [213] obtained in the context of stochastic reaction
networks, but with a slightly d