\chapter{DProp: Distributed Propagation in Practice}

\label{ch:dprop}

In developing the system for distributed propagation described in
Chapter~\ref{ch:design}, I have constructed a working implementation
of the protocol, called DProp. DProp makes use of Twisted, a
Python-based, event-driven networking framework to provide the HTTP
server functionality needed for distributed propagation. The Twisted
library may be used to easily construct an HTTP-based server
application with optional SSL encryption. Together with Python's
built-in httplib module, used to implement HTTP requests, I am able to
construct a useful mechanism for distributed propagation

I have also constructed a library to accompany DProp, named PyDProp.
This library simplifies the construction of cells shared via DProp by
offering a simple API for cell creation. This library may also be used
to construct provenance-aware cells, which share the same basic API
used for non-provenance-aware propagation. By sharing the API for
creating both provenance-aware and non-provenance-aware cells, I am
able to demonstrate the ease with which provenance may be added to
existing applications that use distributed propagation.

\section{The Architecture of DProp}

Although I have outlined a basic protocol for distributed propagation
in Chapter~\ref{ch:design}, that outline simply lays out the
architectural requirements of the protocol itself; there are no
provisions made for the architectural design of applications that
implement the protocol correctly. As long as a program adheres to the
protocol, its implementation may be integrated into the application,
or made to be reused by many programs. DProp has a more flexible
architecture that allows it to be reused by many existing programs.

As described above, DProp uses the Twisted networking stack to
implement the actual HTTP communications. Although it would be
possible to construct a separate propagation stack for each program
that utilized propagation, I have instead chosen to implement DProp
using a client-server architecture. Local client applications may
create cells on the DProp server that may be made available to the
network at large. This design choice separates propagation
functionality from the applications that use it; they do not need to
actually implement distributed propagation and may rely on the DProp
daemon to handle propagation for them. Client applications would then
only be contacted for cell-specific operations, such as cell merges
and updates.

A client application need only be able to communicate with the DProp
daemon through the DBus messaging library, an open-source
inter-process messaging library. Programs may use a common API
enforced by DBus to create cells. By relying on a single daemon for
all propagation, we reduce the number of distinct propagator
implementations, and reduce the number of bugs in propagator networks
that may be caused by an incorrect implementation of the propagation
protocol.

More importantly, this client-server architecture \textit{also} allows
propagators on the same host to run as separate processes, provided
that they can both communicate with the same DBus messaging bus. The
DProp daemon can manage the sharing of a single cell across multiple
processes simply by using the same APIs in different processes. By
using these APIs to merge and update the same cell, two processes may
effectively share a cell as they might share memory.

\begin{table}
\begin{center}
\begin{tabular}[c]{l|p{9cm}}
\hline
\texttt{escapePath(path)} & Escape part of a path to a cell for use with DBus. \\
\texttt{useSSL()} & Returns True if the daemon is hosting using SSL, False otherwise. \\
\texttt{port()} & Returns the port number the DProp daemon is hosting on. \\
\texttt{registerCell(uuid)} & Creates a new cell identified by \texttt{uuid()} if it doesn't exist and returns the UUID. \\
\texttt{registerRemoteCell(url)} & Creates a new uninitialized local copy of the cell at \texttt{url} if it doesn't exist and returns its UUID. \\
\texttt{cellExists(uuid)} & Returns True if a cell with the given UUID already exists, False otherwise. \\
\hline
\end{tabular}
\caption{DBus remote methods available on a DPropMan object.}
\label{tab:dpropman}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}[c]{l|p{10cm}}
\hline
\texttt{escapePath(path)} & Escape part of a path to a cell for use with DBus. \\
\texttt{changeCell(data)} & Change the contents of the cell to \texttt{data} (which should be encoded as a JSON string) and notify local propagators. \\
\texttt{updateCell(data)} & Send a JSON-encoded update message, \texttt{data}, to the merge operation associated with the cell and forward the message to all remote peers. \\
\texttt{data()} & Return the data of the cell encoded as a JSON string.  data() effectively returns the argument of the previous call to changeCell(data). \\
\texttt{url()} & Returns the URL of the cell. \\
\texttt{connectToRemote(url)} & Actually connect to the cell at the remote peer, specified by \texttt{url}, and set it to synchronize with the cell. \\
\hline
\end{tabular}
\caption{DBus remote methods available on a Cell object.}
\label{tab:dpropcell}
\end{center}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}[c]{l|p{8.5cm}}
\hline
\texttt{UpdateSignal(message, peer)} & Sent by the cell when a (local or remote) update has been received by the cell from \texttt{peer}. \\
\texttt{NotifyPropagatorsSignal()} & Sent by the cell to wake up any connected propagators. \\
\hline
\end{tabular}
\caption{DBus signals sent by a Cell object.}
\label{tab:dpropsignal}
\end{center}
\end{table}

DBus is an \textit{object-oriented} messaging system.  This means that
messages in DBus are associated with particular data objects.  These
data objects are usually created by one application, but may be sent
messages from many other client applications.  Shared data objects in
DBus reveal remote methods defined specifically for the type of object
being shared.

The applications that have created data objects on DBus may also
communicate back to client applications through a number of DBus
``signals''.  Signals are special methods associated with a data
object that result in firing call-back methods that may have been
registered to receive the signal in various client applications.

DProp shares two types of objects on DBus: a single \texttt{DPropMan}
object, and a collection of \texttt{Cell} objects. The
\texttt{DPropMan} object represents the state of the DProp daemon
itself. It has methods that test whether a cell exists, as well as
some that create new \texttt{Cell} objects. These methods are outlined
in Table~\ref{tab:dpropman}.

A \texttt{Cell} object represents a single cell copy in a distributed
propagator network, shared with the world at large. Many of the
methods made available on a \texttt{Cell} object relate to updating
and merging the contents of the cell. These methods are listed in
Table~\ref{tab:dpropcell}. Cells also expose several DBus signals to
client applications. The signals associated with each \texttt{Cell}
are used to notify client applications of updates received by the cell
and completed merges.  A complete list of signals is given in
Table~\ref{tab:dpropsignal}.

\begin{figure}
\begin{center}
\includegraphics{dbus.pdf}
\caption{Example communications between a DProp client and server via DBus.}
\label{fig:dbus}
\end{center}
\end{figure}

A simple example of cell creation and updating using DProp is depicted
in Figure~\ref{fig:dbus}. When an application first requests that a
cell be made, the server will permanently instantiate a cell with the
provided UUID if one does not already exist. This cell may then be
used as the recipient of further remote method calls over DBus. Once
the cell has been created, a client may register appropriate local
functions to handle the signals generated by a particular cell. These
include \texttt{UpdateSignal}s generated whenever a local or remote
update message is received.

Locally generated updates may be sent to the cell by using the
\texttt{updateCell} method. When an update is sent locally, the server
will distribute the update to remote cells, as outlined in
Section~\ref{sec:update}, and then signal any locally registered merge
operations by generating an \texttt{UpdateSignal}.

When an \texttt{UpdateSignal} has been generated by the DProp daemon,
all local merge functions that have been registered to the
\texttt{Cell}'s \texttt{UpdateSignal} will be invoked. These merge
functions may then perform computation based on the current cell
state, which may be obtained from the cell using the \texttt{data}
method on the \texttt{Cell} object. They may then properly set the
contents of the cell to the newly merged state by using the
\texttt{changeCell} method.

This second method actually changes the contents of the cell that are
returned by the \texttt{data} method via DBus or a remote GET request
over HTTP. The \texttt{changeCell} method also wakes any local
propagators associated with the cell by generating the DBus signal
\texttt{NotifyPropagatorsSignal}. Local propagators interested in the
cell should be registered to receive this signal and perform any
computation; this may include further calls to \texttt{updateCell} to
send updates to additional cells.

% Resynchronization???

% Solution for temps, etc.: Wrap hemispheres, clip to world definition.

\section{The DProp Daemon}

The DProp daemon handles the synchronization of local cell copies, as
well as handling requests from other copies. It implements both the
HTTP server and client mechanisms necessary to perform the distributed
propagation protocol outlined in Chapter~\ref{ch:design}.

When the DProp daemon starts, it will instantiate an HTTP server on
port 37767 and connect to DBus.  The DProp daemon creates a
\texttt{DPropMan} object at runtime and associates it with the DBus
path \texttt{/DPropMan}. The remote methods of this object may then be
called by any client; clients need only reference the name of the bus
that the object is hosted on, `edu.mit.csail.dig.DPropMan', and the
path of the object, \texttt{/DPropMan}. Any of the methods described
in Table~\ref{tab:dpropman} may be called on the DPropMan object.

When a cell copy is created using the \texttt{registerCell} or
\texttt{registerRemoteCell} method, the cell object gets created at
the path \texttt{/Cells/\{UUID\}}, where it may be called upon to
update or register signals. This cell is also made available on the
HTTP server by assigning it a URL that is named with reference to the
host's name: `http[s]://\{host\}:\{port\}/Cells/\{UUID\}'. The
collection of the peers of the cell is also created below this URL.

Regardless whether a cell is created with \texttt{registerCell} or
\texttt{registerRemoteCell}, the cell that is created is initially
empty. To finish the initial synchronization process with a cell
created by \texttt{registerRemoteCell}, the \texttt{connectToRemote}
method must be called on the cell. We separate cell creation from
initialization of the cell as no merge function is registered with the
cell immediately following the \texttt{registerRemoteCell} call. A
client must register a call-back function with the
\texttt{UpdateSignal} signal of the cell before we may actually
perform any merges or synchronizations; if this is not done, the
contents of the remote cell will not be properly merged when they are
fetched. Likewise, call-backs to \texttt{NotifyPropagatorsSignal} must
be added to ensure that propagators fire.

This separation of cell creation and initialization also helps users
initialize against a remote cell without blocking execution; if this
was not done, a thread might hang while it waits to connect to a
non-existent remote cell. Finally, it allows the DProp client
application to finely control connection to a remote cell.  This
allows a client application to provide fall-back mechanisms should a
cell fail to connect.  For example, it may be able to try alternate
remote URLs or initialize the contents of the cell based on some local
saved state.

\subsection{Serving Cells}

The DProp daemon uses the Twisted framework to serve HTTP
resources. The built-in \texttt{twisted.web} module allows for the
creation of resources simply by sub-classing the
\texttt{twisted.web.Resource} class. We then provide a top-level
resource when the HTTP server is instantiated. We use a
\texttt{DPropManTopLevel} object to represent the top-level resource
containing the \texttt{/Cells} collection. Similarly, a
\texttt{DPropManCells} object represents the collection of cells, a
\texttt{DPropManCell} object represents a single cell, and a
\texttt{DPropManCellPeers} object represents the collection of a
cell's peers.

Each HTTP resource may respond to any number of HTTP methods simply by
defining instance functions on their Python objects with names having the
form \texttt{render\_METHOD(self, request)}. For example, an HTTP GET
method on a cell resource will result in calling the
\texttt{render\_GET(self, request)} method on the corresponding
\texttt{DPropManCell} object. The \texttt{render\_GET} method has been
implemented to check whether an \texttt{If-None-Match} HTTP header has
been provided. If it has, and the value of the header matches the
\texttt{ETag} of the cell's contents, the resource will return an
empty response along with the ``304 Not Modified'' response code to
imply that any caches with that ETag are still valid. Otherwise, the
cell will return the current contents of the cell along with a ``200
OK'' response code and a new \texttt{ETag}.

% Below should be PATCH. Should clarify HTTP behavior better, REST 
% better.  Clarify difference between Cell object and DPropManCell.

When a cell receives a POST request and the \texttt{render\_POST} method
is called, the Python object will confirm that the HTTP
\texttt{Referer} header field has been specified and that the content
of this field is the URL of a cell that is already present in the
cell's peers collection. If the \texttt{Referer} is unrecognized, the
cell will return a ``403 Forbidden'' response code to signify that the
POST was not allowed. Otherwise, the cell will forward the update to
any interested cell merge operations by calling the
\texttt{UpdateSignal} associated with the cell. The cell returns a
``203 Accepted'' response to denote that the submitted POST was
accepted for merging into the cell, even though it may not actually
change its contents.

We may similarly accept a POST on the Peers collection.  The
\texttt{render\_POST} method on the corresponding
\texttt{DPropManCellPeers} object does not check the \texttt{Referer}
however.  It simply adds the URL of the peer provided in the contents
of the POST to the peers collection without doing any validation or
verification of the new peer named in the \texttt{Referer}.

\subsection{Fetching Cells}

The DProp daemon is also in charge of handling the re-synchronization
protocol described in Section~\ref{sec:resync}. This is performed
automatically by running a method to perform this re-synchronization,
\texttt{startSyncThunk}, repeatedly on a timer. When this method
fires, the daemon will attempt to simultaneously re-synchronize the
local cell with each cell copy in the Peers collection. This is done
in a concurrent, multi-threaded manner.

This multi-threaded behavior is necessary to prevent deadlocks that
might be caused when two peers attempt to re-synchronize with each
other at the same time. If the HTTP server handles requests on the
same thread as the HTTP client makes them, responses to any requests
made to the server will not be generated while DProp waits on a
response from the remote server.

Once an HTTP request has been made for a cell, the response may be
treated according to the rules outlined in Section~\ref{sec:resync}.
The cell will fire a local update if there was a loss of
synchronization or do nothing if no re-synchronization is needed.

Updates to a \texttt{Cell}, regardless of whether they were received
from a remote cell copy or a local call to \texttt{updateCell},
ultimately call the \texttt{Cell}'s \texttt{doUpdate} method. This
method, not publicly visible via DBus, is called by both the
\texttt{render\_POST} method of the HTTP server and \texttt{updateCell}
method of the DBus \texttt{Cell} to send an \texttt{UpdateSignal} to
any local merge functions that have been registered to receive it. It
also calls the \texttt{updatePeers} method if the update was sent
locally. This method is used to forward the update to remote
peers.

As mentioned previously, the \texttt{connectToRemote} method may be
called to properly connect the cell to a network of synchronized
cells.  Like \texttt{startSyncThunk}, this method spawns a thread to
initialize the cell from the remote copy.  It will fetch the contents
of the remote cell with an HTTP GET request and call \texttt{doUpdate}
to pass the contents of that cell to the local update function.  The
method then proceeds to merge the peers known to the remote cell into
the local Peers collection and informs these peers of the existence of
the new cell copy.

\section{PyDProp}

The DProp daemon is accompanied by a separate Python library, called
PyDProp, which is designed to interface with the daemon through DBus.
This Python module may be used with any Python code to create and
synchronize remote cells without writing any low-level DBus code.
PyDProp also includes classes that implement the provenance-aware cell
model described in Chapter~\ref{ch:provenance}.

\begin{figure}
\begin{center}
\includegraphics{pydprop-classes.pdf}
\caption{Class hierarchy of PyDProp.}
\label{fig:pydprop-classes}
\end{center}
\end{figure}

\begin{table}
\begin{center}
\begin{tabular}[c]{l|p{9.4cm}}
\hline
\texttt{addNeighbor(propagator)} & Registers the \texttt{function} method of the provided propagator object with the \texttt{NotifyPropagatorsSignal} signal of the cell so that it is called when the cell updates. \\
\texttt{update(data)} & Updates the cell with the JSON-encoded update provided in \texttt{data}. Wraps the \texttt{updateCell} method. \\
\texttt{set(data)} & Sets the cell to the JSON-encoded update provided in \texttt{data}. Wraps the \texttt{changeCell} method. \\
\texttt{data()} & Returns the JSON-encoded data stored in the cell. \\
\texttt{url()} & Returns the URL of the cell. \\
\hline
\end{tabular}
\caption{Methods available on a Cell object in PyDProp.}
\label{tab:cellmethods}
\end{center}
\end{table}

PyDProp provides four concrete classes, including \texttt{LocalCell},
\texttt{RemoteCell}, and the provenance-aware versions of these
classes, \texttt{ProvenanceAwareLocalCell}, and
\texttt{ProvenanceAwareRemoteCell}.  These four classes are
sub-classed from one of two abstract classes \texttt{Cell} and
\texttt{ProvenanceAwareCell}, as illustrated by the class-hierarchy in
Figure~\ref{fig:pydprop-classes}.  The \texttt{LocalCell} classes are
used to represent a locally-created cell which will not be initialized
from a remote cell copy.  The \texttt{RemoteCell} classes, in
contrast, may be initialized from a copy of a cell at another URL.
All of these classes inherit methods from the abstract \texttt{Cell}
class and share the five basic methods of that class, listed in
Table~\ref{tab:cellmethods}.  These five methods may be used to
perform basic cell-related tasks, such as retrieving the cell's
contents and updating a cell, without needing to directly invoke
methods exposed through DBus.

\subsection{The LocalCell and RemoteCell Classes}

The \texttt{LocalCell} and \texttt{RemoteCell} classes are subclasses
of the \texttt{Cell} class that differ only in how they are
initialized.  Both are initialized with two arguments.  The first
argument is the UUID, if the cell is a \texttt{LocalCell}, or the URL,
if a \texttt{RemoteCell}.  The second argument of both constructors is
a merge function that takes three arguments: the Cell object itself,
the update data encoded in JSON, and the peer that sent the update.

The \texttt{LocalCell} object simply registers the cell with the DProp
daemon using the \texttt{registerCell} method of the \texttt{DPropMan}
object on DBus. It then registers the provided merge function with the
\texttt{UpdateSignal} of the \texttt{Cell} created by
\texttt{registerCell}. Instead of calling \texttt{registerCell},
\texttt{RemoteCell} uses the \texttt{registerRemoteCell} method.  It
also calls the \texttt{connectToRemote} method after the merge
function has been registered with the \texttt{UpdateSignal}.

\subsection{Provenance-Aware Cells}

\texttt{ProvenanceAwareLocalCell} and
\texttt{ProvenanceAwareRemoteCell}, the other two subclasses of
\texttt{Cell}, are based on the abstract \texttt{ProvenanceAwareCell}.
Like \texttt{LocalCell} and \texttt{RemoteCell}, these
provenance-aware subclasses differ only in the arguments they take,
although both now take an optional provenance merge function as their
last argument.  Furthermore, \texttt{ProvenanceAwareLocalCell} now
requires three UUIDs, one for each sub-cell, rather than one UUID for
the entire cell.

\begin{table}
\begin{center}
\begin{tabular}[c]{l|p{10cm}}
\hline
\texttt{mainCellMerge} & Performs the default merge (replacement) operation for the main cell. \\
\texttt{provCellMerge} & A wrapper for the provenance merge function given as the first argument \texttt{provMergeFunction} and performs the merge on the provenance cell. \\
\texttt{dataCellMerge} & Like the \texttt{provCellMerge} function, this function wraps the first argument \texttt{mergeFunction} and handles merging of data. \\
\texttt{defaultProvCellMerge} & The default provenance merge function. \\
\texttt{updateProvenance} & Like \texttt{update} on the original Cell class, but specifically updates the provenance cell. \\
\texttt{setProvenance} & Like \texttt{set} on the original Cell class, but specifically sets the provenance cell. \\
\texttt{provenanceData} & Like \texttt{data} on the original Cell class, but specifically fetches the data of the provenance cell. \\
\hline
\end{tabular}
\caption{Methods available on a ProvenanceAwareCell object in PyDProp.}
\label{tab:provcellmethods}
\end{center}
\end{table}

The parent class of these classes, \texttt{ProvenanceAwareCell}, adds
several additional functions to the basic functions provided by the
\texttt{Cell} class. These additional functions are listed in
Table~\ref{tab:provcellmethods}.  Several wrapper methods and default
merge functions are provided to help with merging the individual
sub-cells of provenance-aware cells.  \texttt{ProvenanceAwareCell}
also overrides some of the methods of the \texttt{Cell} type to
account for the differences between the structure of a basic
\texttt{Cell} and a \texttt{ProvenanceAwareCell}.  Despite these
differences, sub-classing \texttt{Cell} still allows us to easily reuse
existing code written to use non-provenance-aware cells, as the basic
five functions of \texttt{Cell} remain functionally the same.

\subsection{Propagators}

Propagators in PyDProp are first-level objects.  These objects are all
members of a class that wraps propagator functions, named
\texttt{Propagator}.  The constructor of a \texttt{Propagator} object
takes three arguments: an identifier for the propagator, a list of
neighboring cells that will wake the propagator when their content
changes, and the propagator function itself.  The constructor
automatically registers the propagator function with the
\texttt{NotifyPropagatorsSignal} of each neighboring cell so that the
propagator will wake up when one of the neighboring cells changes.
The \texttt{Propagator} object also wraps the propagator function
through its instance method \texttt{function()}.

Provenance-aware propagators are constructed similarly to
non-provenance aware propagators.  Rather than using the
\texttt{Propagator} class, provenance-aware propagators use the class
\texttt{ProvenanceAwarePropagator}, which takes an additional argument
following the list of neighbors.  This argument contains the list of
output cells of the propagator.  This ensures that the provenance
sub-cells of each provenance-aware cell that has had its \textit{data
  sub-cell} updated will be updated as well.  It also takes an optional
provenance-propagation function to allow for custom structures of
provenance rather than the one described in
Section~\ref{sec:provenance}.  Otherwise the propagator will provide
one of its own to create the provenance structure described in that
section.

\section{DProp and JSON}

As may be noted in
Tables~\ref{tab:dpropcell}~and~\ref{tab:cellmethods}, the arguments to
the methods of a \texttt{Cell} object in both DBus or PyDProp are
objects encoded as strings using JSON, a data interchange format based
on JavaScript syntax.  This choice is primarily driven by the static
typing of functions exposed through DBus.  As it would be impossible
to store an arbitrary data type in a \texttt{Cell} and retrieve it
using DBus without knowing which of the static types is stored in the
cell, I chose to use a neutral data interchange format, JSON, to
represent the data stored in a cell.

To handle conversion between arbitrary data and JSON, it is necessary
to map arbitrary objects to a JavaScript ``object'' bearing key-value
pairs that map a string to a string, number, array, or other object.
Encoding and decoding the data of a cell in JSON may be handled by
existing JSON code libraries.  However, several special objects used
in distributed propagation and provenance require special handling.
This is why I use a special DProp-specific Python JSON library,
DPropJSON, for both the DProp daemon and the PyDProp library.

DPropJSON operates like the \texttt{json} module provided by Python
2.6, which exposes two methods, \texttt{dumps} and \texttt{loads}, to
encode and decode JSON respectively.  DPropJSON depends on either the
internal \texttt{json} module, if present, or the python-json library
(also known as json-py) for versions of Python earlier than 2.6.

DPropJSON supports two additional data types in JSON.  These data
types, \texttt{URI} and \texttt{Nothing} are encoded as specifically
formatted objects in JSON output.  The \texttt{URI} type may be
identified by the special key-value pair \texttt{\_\_uri\_\_=True}.
It also has a key-value pair which specifies the value of the
\texttt{URI}, \texttt{uri=\textit{value}}.  This type may be used to
represent URLs.

The \texttt{Nothing} type, on the other hand, is simply identified by
the key-value pair \texttt{\_\_nothing\_\_=True}.  The
\texttt{Nothing} type represents the empty value of a \texttt{Cell}
before it has merged any updates; all \texttt{Cell} objects are
initially set to contain a \texttt{Nothing} object.

\begin{table}
\begin{center}
\begin{tabular}[c]{l|p{10cm}}
\hline
Type & Description \\
\hline
\texttt{dpropMainCell} & Data stored in the main sub-cell of a provenance-aware cell, including pointers to the provenance and data sub-cells. \\
\texttt{dpropDataCell} & Data stored in the data sub-cell of a provenance-aware cell, including a pointer to the main sub-cell. \\
\texttt{dpropProvCell} & Data stored in the provenance sub-cell of a provenance-aware cell, including a pointer to the main sub-cell. \\
\texttt{dpropProvenance} & Provenance data pushed by a provenance-aware propagator. \\
\hline
\end{tabular}
\caption{Types of JSON objects used in PyDProp's provenance-aware cells}
\label{tab:jsontypes}
\end{center}
\end{table}

Provenance-aware cells require several additional ``special'' types of
objects.  Although DPropJSON does not handle these objects, the
provenance-aware PyDProp classes automatically work with these objects
in the default merge functions for provenance sub-cells.  Four
additional object types are required for provenance-aware cells, which
are specified in Table~\ref{tab:jsontypes}.  Each of these object
types may be identified by a JSON object that has a key-value pair
\texttt{type=\textit{typename}}.

The \texttt{dpropMainCell} type has two additional key-value pairs,
named \texttt{dataCell} and \texttt{provCell}.  These two key-value
pairs take values that correspond to the UUIDs of the data and
provenance sub-cells of the provenance-aware cell respectively.

The types \texttt{dpropProvCell} and \texttt{dpropDataCell} also have
two additional key-value pairs, \texttt{mainCell} and \texttt{data}.
\texttt{mainCell} is a UUID pointer to the main sub-cell of the
provenance-aware cell.  \texttt{data}, in contrast, is assigned the
actual wrapped value of the cell.

One additional class, \texttt{dpropProvenance}, is used to transmit
provenance through provenance-aware propagators and differentiate a
\texttt{dpropProvCell} from the provenance stored in the cell.  This
class has only one key-value pair, \texttt{data}.  This key
corresponds to the provenance data being forwarded to the destination
provenance sub-cell.

%\subsection{A Sample Program}
