\chapter{Background}

\label{ch:background}

\section{Data Propagation}

Data propagation is a concurrent programming paradigm proposed by
Alexey Radul \cite{radul2009thesis,radul2009art}.  Based on the
principles of message-passing concurrency, data propagation relies on
messages sent over networks of monotonic computational blocks, called
``propagators'', and state-bearing ``cells''.  Propagator networks
perform computation when an update of a cell's state triggers the
execution of the propagators that are connected to it.  These
propagators may then update the state of other cells, causing further
propagation.

Although the state of a cell may change, its value may only be
assigned once.  This may seem to be a contradiction at first glance,
but the value assigned to a cell may be a partial value, rather than
one that has been fully-specified.  This allows for continued
modification of its state.  When we discuss ``changing'' a cell's
state, or ``updating'' its contents, what we really mean is that the
partial value of a cell has been updated with additional data.

Cells are initially created with an ``empty'' partial value.  This
special partial value represents a complete absence of knowledge of a
cell's contents and provides no constraints on the value of the cell.
A cell with an empty partial value closely resembles an unassigned
variable, except that it can be easily identified as such during
execution.

% TODO: Depict examples visually?

Partial values stored in a cell need not be objects with partially
defined fields, such as a \texttt{cons} pair in Lisp with a
\texttt{cdr} that has been marked for delayed evaluation
\cite{friedman1976lazy}.  Partial values in a propagator network may,
in fact, be any value, including sets and ranges that may be refined
through appropriate mathematical operations.

The process of refining the partial value of a cell is dependent on a
user-defined merge operation.  This merge operation unifies an
existing partial value with additional information provided in an
``update'' message sent to the cell.  While the merge operation may be
simple assignment when a cell is empty, merge operations are more
interesting when they operate on cells that are not empty.

\begin{figure}
\begin{center}
\includegraphics{cell-merge.pdf}
\caption{A cell applying a merge operation to merge two temperature
  readings.}
\label{fig:cell-merge}
\end{center}
\end{figure}

For example, a cell might contain a range of temperature values that
represents the current air temperature recorded by a thermometer,
including its measurement error.  If a second thermometer is connected
to the cell and sends its \textit{own} measurement as an update, the
merge operation of the cell may take the intersection of the two
temperature ranges to obtain a more precise estimate of the current
air temperature than either thermometer gives on its own.  The cell
may then take the intersection as its new partial value, as depicted
in Figure~\ref{fig:cell-merge}.

A merge operation may be arbitrarily complex.  If a cell is capable of
performing logical deductions to construct its complete contents, we
might be able to employ a merge operation that removes redundant facts
for more efficient storage.  For example, such a cell might contain
two facts: ``Socrates is a man'' and ``Socrates is mortal''.  If the
cell were to receive an update stating that ``All men are mortal'', it
could employ a logically-consistent merge operation that would not
only add the fact ``All men are mortal'' to the cell, but also remove
``Socrates is mortal'', as it may be concluded from the other two
facts.  Despite the fact that the facts stored in the cell are not
strictly increasing (i.e. the cell is not strictly monotonic), if the
cell can still conclude ``Socrates is mortal'', the actual knowledge
that the cell contains is still monotonically increasing.

\begin{figure}
\begin{center}
\includegraphics[width=15cm]{data-propagation.pdf}
\caption{Data propagation at work: a temperature converter.}
\label{fig:data-propagation}
\end{center}
\end{figure}

% TODO: Should I mention stateless vs. monotonic?

Once a cell has merged an update and its partial value has changed,
propagators connected to the cell wake up and perform computation.
These propagators will use the newly updated partial value where they
originally used the cell's previous contents.  During computation,
these propagators may generate updates for \textit{additional} cells.
For example, in Figure~\ref{fig:data-propagation} above, an update to
the top cell at time (b) causes the \texttt{temp-converter} propagator
to fire at time (c).  Upon receiving these updates, these cells will
apply their own merge operations to update their partial data,
starting another merge-and-compute cycle.  This can be seen above when
the propagator at time (c) causes an update to the bottom cell at time
(d).  These repeated cycles of merging and propagation of data drive
computation within a propagator network.

No constraints are placed on the structure of propagator networks.
For example, cycles may be used in propagator networks to create
standard looping control-flow structures.  By allowing a propagator to
update a cell that indirectly contributed to its being fired, the
propagator may ensure that it fires again to include additional
information.  Other propagators may prevent the forwarding of updates
when the input cells meet some criteria.  Such propagators would halt
propagator loops, allowing for switch-like control-flow structures and
finite loops.

We may also perform recursive computation with propagator networks.
As propagators are opaque computational units, and networks of
propagators also perform computation, we may define a class of
propagators called ``compound propagators''.  These compound
propagators may construct a propagator network when they are first
triggered.  This new propagator network may then act as a part of the
original network, and may perform computation based on the original
input cells of the compound propagator by mapping those input cells
appropriately to the newly constructed propagator.

Constructing such networks on demand permits recursive computation; a
compound propagator need only include itself as one of the propagators
in its constructed sub-network to do so.  Propagation of data may
cause as many recursive expansions of the propagator as necessary
simply by repeatedly waking each recursive copy of the compound
propagator in turn.

Ordering of propagation events is undefined, outside of the implicit
cause-effect chain caused by the propagate-and-merge cycle.
Furthermore, propagator networks feature a strong modularity of
computation that is enforced by strictly separating cell state from
propagator computations.  Together, these properties make data
propagation a reasonable candidate for parallel processing and
distributed computation.

% TODO: I almost feel like there should be more citations here.

\section{Representational State Transfer}

\label{sec:rest}

Representational State Transfer, or REST, is an architectural style
for network-based software architectures based on the principles of
hypertext and the HyperText Transfer Protocol (HTTP) and developed by
Roy Fielding \cite{fielding2000thesis}.  Architectures that make use
of Representational State Transfer, also called ``RESTful
architectures'', are designed to store and maintain opaque data
objects, called ``resources'', that represent an abstract concept or
another, more concrete, data object.  Resources generally have four
operations that may be performed on them: creation, retrieval, update,
and deletion.  Together, these four operations are known as CRUD
operations.

Since an abstract concept associated with a resource may not be easily
serialized, RESTful architectures are designed to be platform- and
content-agnostic through the use of resource ``representations''.  For
example, a data set of hourly temperatures may have an image
representation in the form of a graph in GIF format, as well as a
tabular representation in plain-text.  The four fundamental CRUD
operations may be performed in a RESTful architecture by using any
number of these resource representations to specify the relevant
aspects of that resource.

More complex operations on resources, such as those often implemented
as remote procedure calls, may be modelled in a RESTful architecture
by applying the fundamental resource operations with appropriate
representations.  By restricting the number of fundamental operations
and allowing the use of different resource representations, a RESTful
architecture reduces the complexity of software implementations that
use it.  Software uses of a RESTful architecture need only be able to
perform the basic operations with representations they are prepared to
handle; there is no need to support all representations of a resource,
only those relevant to the application.

In the doctoral thesis that first laid out the principles of REST,
Fielding defines an architectural style as ``a coordinated set of
architectural constraints that restricts the roles/features of
architectural elements and the allowed relationships among those
elements within any architecture that conforms to this style.''  In
accordance with this principle, a proper RESTful architecture adheres
to five constraints:

\begin{enumerate}
\item REST assumes a \textit{client-server model} of communication.
  This separates the resources on the server from the software that
  modifies them.  It also determines how data may be stored; only the
  server must find a suitable intermediate format for storage.
  Clients may use any representations they find appropriate.
\item RESTful designs are \textit{stateless}.  Information transmitted
  between the client and server of a RESTful architecture should be
  sufficient to perform the desired operation without maintaining any
  additional state (such as session variables) on the server or
  client.
\item Representations of resources transmitted as part of an operation
  should be \textit{cache-able}.  This constraint is particularly
  useful in terms of the retrieval operation.  By caching information
  that has been previously retrieved, future requests may be optimized
  by referring to a nearby cache, rather than waiting on the central
  server.  It also reduces the burden on the server, as many requests
  may be serviced by a cache instead.
% THOUGHT: This does, however, reduce the usefulness of caches when
% there are a lot of updates.  Expand on this.
\item RESTful designs should employ a \textit{uniform interface}.  By
  standardizing the interface by which resource operations are
  performed, many different client and server implementations may be
  deployed in an inter-operable way.  A uniform interface also reduces
  client and server complexity.
\item Finally, RESTful architectures are \textit{layered
  architectures}.  This allows for the separation of network
  administration from the application itself, providing increased
  scalability.  Caches, back-ends, and proxies may be implemented on
  the network layer without restricting the functionality of the
  application itself.
\end{enumerate}

\begin{table}
\begin{center}
\begin{tabular}[c]{llp{6.5cm}}
CRUD Operation & HTTP Method & RESTful Meaning \\
\hline
Creation & PUT & Create a new resource based on the representation presented. \\
Retrieval & GET & Fetch the desired representation of an existing resource. \\
Update & POST & Modify an existing resource based on a given (partial) representation. \\
Deletion & DELETE & Delete an existing resource. \\
\hline
\end{tabular}
\caption{The four CRUD operations and corresponding HTTP methods.}
\label{tab:http-methods}
\end{center}
\end{table}

Most REST-based applications use the Hypertext Transfer Protocol
(HTTP) as the underlying network protocol of their RESTful
architecture.  HTTP handles data transfers as a series of requests for
data and responses to those requests.  Each request may be made for a
resource identified by its Uniform Resource Locator (URL).  These
requests are also associated with the HTTP method corresponding to the
operation desired.  Four HTTP methods are usually used to implement
REST design: PUT, GET, POST, and DELETE.  These methods are aligned
with the CRUD operations of creation, retrieval, updating, and
deletion, as outlined in Table~\ref{tab:http-methods}.  The PATCH
method \cite{rfc5789} may also be used in place of the POST method to
perform updates.

I have chosen to implement a propagator network by employing RESTful
techniques for several reasons:

\begin{enumerate}
\item Propagator networks need minimal modification to adhere to the
  five constraints of REST.  The stateless constraint in REST is
  stricter than the computational monotonicity of propagators in
  propagator networks.  This means that it is possible to model
  RESTful communication as a propagator in a propagator network.
  Furthermore, the implicit atomicity of update messages sent to cells
  makes these messages well-suited to being representations of
  resources in our implementation.
\item If we assume that update messages are the representations being
  transferred, it seems possible to consider cells to be the resources
  within the design.  Just as cells are the only state-bearing objects
  within propagator networks, resources are the only state-bearing
  objects in a RESTful architecture.
\item Enforcing uniformity of interface in an implementation of a
  distributed propagator network creates an extensible system.  My
  implementation of distributed propagation, DProp, is built using
  Python and has been tested for use on GNU/Linux systems.  By requiring
  that DProp use standard HTTP for cell synchronization, it is
  possible to construct a heterogeneous propagator network that has
  nodes that run various different operating systems and propagator
  implementations.  This makes DProp a suitable platform for
  distributed systems, which already assume a heterogeneous network.
\end{enumerate}

% TODO: Provided that all nodes adhere to the protocol.

Together, these points make Representational State Transfer a
desirable architectural design on which to build our system for
distributed propagation.
