\chapter{Provenance-Aware Propagation}

\label{ch:provenance}

Distributed propagation allows the distribution of a number of
algorithms that would not otherwise be possible within a traditional
distributed system.  However, in distributing computation, we lose the
ability to determine how a particular result is derived.  As
distributed computing is inherently concurrent, there is no explicit
sequence of operations that we may follow backwards in an attempt to
determine the cause of an error.  Furthermore, there is no way to
easily identify any host that may be returning incorrect results.
Distributed systems usually implement some sort of rudimentary
mechanism to track the history of data for this reason.

These data histories, or provenance, provide an interesting use case
for distributed propagator networks; due to the modularity of
propagator networks, support for maintaining provenance may be done
independently of how the networks themselves are implemented.  The
method of provenance handling I describe in this chapter may be
applied not only to the distributed propagator networks described in
Chapter~\ref{ch:design}, but, with appropriate modifications,
non-distributed propagator networks as well.

We may construct these ``provenance-aware propagator networks'',
capable of constructing and maintaining the provenance of data within
them, simply by transforming the structure of the original propagator
network.  We need only add cells and propagators that are designed to
explicitly handle the provenance of the data in the network.  However,
before I outline this transformation, we first must understand what is
meant by the term provenance.

\section{Provenance}

\label{sec:provenance}

For the purposes of constructing a ``provenance-aware propagator
network'', we define provenance to be a collection of records that
details the history and derivation of all data that contributes to our
understanding of a specific resource.  We distinguish this concept of
provenance from what we call a \textit{justification}, which is the
minimal subset of this provenance from which we may derive \textit{the
  current state} of a resource.

An example illustrates this distinction: Suppose we have a fact that
states that the temperature, $T$, is greater than $40^\circ$F.  We may
then combine this fact with another which states that $T$ is greater
than $50^\circ$F.  The combination of these two bounds now means we
have a new bound on $T$, as it must be greater than $50^\circ$F,
rather than $40^\circ$F.  When we combine these two bounds, our
\textit{new} knowledge of the bounds only takes into account the
second fact.  We need not know the first fact ($T > 40^\circ$F) at all
in order to account for our knowledge of $T$.  We thus say that the
\textit{justification} of the value of $T$ is the statement ``$T >
50^\circ$F''.  The first fact, $T > 40^\circ$F, which corroborates our
knowledge, is a part of the \textit{provenance} of $T$, along with $T
> 50^\circ$F, but it is not part of the \textit{justification}.

This dichotomy between the \textit{provenance} and
\textit{justification} of a resource is very similar to the
distinction between ``why- and where-provenance'' outlined by Buneman,
et al.\cite{buneman2001whywhere} However, Buneman distinguishes
between why- and where-provenance within the context of
\textit{structured data}.  Why-provenance corresponds to the
provenance of the data structure itself, while where-provenance
corresponds to the data in the structure.  In contrast, provenance and
justification must be able to detail the history of conceptual
resources rather than actual concrete data structures.  Provenance
concerns itself with the history of the resource as a whole,
effectively mirroring Buneman's why-provenance; justification provides
the support for the fields of the \textit{current} state of the
resource, mirroring Buneman's where-provenance.

We treat the provenance of a fact to be a collection of ``records''
having a partial order that either indicate where and how a piece of
data was stored (``possession records'') or where and how a piece of
data was modified or derived (``derivation records'').  These record
types are depicted in Figure~\ref{fig:provenance-tree} by rounded and
unrounded rectangles, respectively.  Each record includes an
identifier of the record, as well as any additional meta-data, such as
authenticity tokens, the algorithm or application used, or the current
date and time, that might prove useful when auditing the provenance.

\begin{figure}
\begin{center}
\includegraphics{provenance-tree.pdf}
\caption{A possible provenance graph for a temperature range in Celsius.}
\label{fig:provenance-tree}
\end{center}
\end{figure}

Knowledge that we hold may depend on several pieces of data from which
it is derived, as in Figure~\ref{fig:provenance-tree}.  This
collection of provenance may be considered a directed acyclic graph,
where exactly one node, the seed, has an in-degree of 0.  I refer to
this collection of records as a provenance graph.  The seed of the
graph is the most recent provenance record; the parents of each node
(the nodes to which each node points) are records of the data from
which the data corresponding to that node was derived.

% C(n) -> P(n)

We may define an ``additive-union'' operation over two provenance
graphs so that we may join them in a meaningful manner.  This
additive-union operation serves as the basis for our cell merge
operation for provenance-aware cells.  Throughout this thesis, when we
refer to taking the union of, or adding two provenance graphs, we
refer to this operation.

The additive-union operation may be defined mathematically.  We define
a provenance graph $P$ to be the tuple $(N, A(n), s)$, where $N$ is
the set of all nodes in the graph, the relation $A(n)$ gives the set of
parents of a given node $n$, and $s$ is the seed of $N$.  We may then
define a new graph, $P^\prime$ to be the additive-union of two other
graphs, $P_1 \uplus P_2$, which has the same seed, $s_1$, as $P_1$.
This may be defined as follows:

\begin{equation}
P_1 \uplus P_2=(N_1 \cup N_2, A^\prime(n), s_1)
\end{equation}

Here, we define $A^\prime(n)$ to be:

\begin{equation}
A^\prime(n)=
\begin{cases}
A_1(n) & \text{if } n \in N_1 - N_2 - \{s_1\} \\
A_2(n) & \text{if } n \in N_2 - N_1 \\
A_1(n) \cup A_2(n) & \text{if } n \in N_1 \cap N_2 \\
A_1(r_1) \cup \{s_2\} & \text{if } (n = s_1) \wedge s_1 \neq s_2 \\
A_1(r_1) & \text{if } (n = s_1) \wedge s_1 = s_2 \\
\emptyset & \text{if } n \notin N_1 \cup N_2 
\end{cases}
\end{equation}

Note that, in order to maintain the acyclic nature of the provenance
graph, the ancestors of a node in the graph $P_1$, $A_1^+(n)$, must
not contain any of the descendents of that node in $P_2$.  That is,
the following must hold:

\begin{gather*}
\forall n \in (N_1 \cap N_2)\, \{n^\prime | n \in A_1^+(n^\prime)\} \cap A_2^+(n) = \emptyset \\
\forall n \in (N_1 \cap N_2)\, \{n^\prime | n \in A_2^+(n^\prime)\} \cap A_1^+(n) = \emptyset \\
s_1 \notin N_2 \vee s_1 = s_2
\end{gather*}

% TODO: A conclusion?

\section{Data Structures on a Distributed Propagator Network}

\label{sec:propastruct}

How can we actually store provenance in a propagator network?
Although some na\"{\i}ve methods may seem obvious, they may not
actually be the best choice overall.  In order to better understand
this, we must first examine how we may represent data structures in a
distributed propagator network, as the association of data with
provenance relies on having a data structure that relates the two.

Although distributed propagator networks are well-suited to handle
synchronizing small amounts of data, larger amounts of structured data
are more difficult to process in a distributed propagator network.
Memory pointers, a traditional tool used to construct large and
complex data structures, are not feasible in a distributed system.
Pointers usually have meaning only when they are expressed in relation
to a specific memory address space.  A pointer within one program
rarely has any meaning in another program, as virtual memory usually
ensures that the address space of each program is independent of all
others.  Similarly, a pointer on one machine has no meaning on another
machine, as they usually do not share any memory, and may not even
share the same computer architecture.

Even though we may not simply share a memory pointer with another
computer and expect the other computer to do computation on that data,
the design of distributed propagator networks offers a na\"{\i}ve
solution: as there may exist copies of the same cell that are
synchronized between two hosts in a distributed propagator network, it
is possible to use memory pointers that are relative to the address
space of the \textit{cell itself}, as this address space may be
synchronized.

Unfortunately, this approach to sharing memory pointers is unfeasible,
as all data would need to be stored in the same cell for the pointers
to have any context; the address space that would be used for pointers
is unique to that cell alone.  If any global inconsistency arose
between copies of the cell, it would be necessary to transfer the
entire contents of the cell as the contents of an update during a
re-synchronization.  This may result in excessive bandwidth
consumption if the amount of data stored in a cell is large.

The use of UUIDs to identify cells in a distributed propagator network
suggests an alternative approach that may serve us better.  Rather
than relying on memory pointers relative to a single cell, we might be
able to use UUIDs to point to other cells containing additional data.
We would only need to replace traditional pointers with URL pointers
to construct useful data structures in a distributed propagator
network.  Allocated memory normally identified by distinct pointers
would be replaced with distinct cells identified by appropriate UUIDs.

We gain a number of benefits by adopting this approach to pointers in
distributed data structures.  As mentioned above, this approach
facilitates the synchronization of large data structures by dividing
them into smaller, more tractable chunks.  We also may reduce the
number of propagators that must be notified when a data structure
changes; we only need to attach propagators to the parts of the data
structure they may be interested in.  For example, if a propagator is
only interested in the first element of a linked list, it need not be
notified to perform computation when any of the other elements of the
linked list change.  By separating the linked list into separate
cells, the propagator will only need to be a neighbor of the cell
containing the first element of that list.

%\section{Provenance and Justifications}
%
%Throughout this entire section, we use the word ``provenance'' when
%referring to the history of a particular piece of data.  It is
%important to note that when we refer to such, however, we refer to the
%\textit{maximal} set of ancestors of a particular cell's data.  This
%is in contrast to what we call the ``justification'' of a cell, which
%is the \textit{minimal} set of ancestors necessary to create a given
%result.
%
%For example, a cell that has received and merged two updates, ``$T >
%40^\circ$F'' and ``$T > 50^\circ$F'', would have provenance consisting
%of \textit{both} updates, as they both were sent as updates and merged
%into the cell.  However, the \textit{justification} might simply
%include the latter statement, as it supersedes the former statement.

\section{Modifying Existing Propagator Networks for Provenance}

\begin{figure}
\begin{center}
\includegraphics[width=15cm]{cell-indirection.pdf}
\caption{Making a simple propagator network provenance-aware.}
\label{fig:cell-indirection}
\end{center}
\end{figure}

As mentioned previously, the process of adding support for provenance
in propagator networks, making them ``provenance-aware'', requires a
simple transformation of existing propagator networks.  In practice,
we add provenance by simply introducing ``another level of
indirection''.  We combine basic propagators and cells to construct
more complex compound-propagators and cell-clusters that will be our
new ``provenance-aware'' propagators and cells.
Figure~\ref{fig:cell-indirection} illustrates this transformation from
a ``simple'' propagator network at top to the corresponding
provenance-aware version at the bottom.

A na\"{\i}ve approach often used to associate provenance with data is
to simply wrap the data together with the provenance in a single
object.  The wrapper object may cryptographically seal the data to the
provenance so that the provenance may not be removed.  It may also be
unwrapped as needed to allow access to the underlying data so that it
may be handled by operations that are unable to handle provenance.
Although we could simply store provenance-wrapped data in our cells
instead of the data itself, this is inefficient.  Data and provenance
may need to be separated to allow for independent modification of the
data and provenance.  Such independent modification is particularly
needed within propagator networks, where additional sources of
evidence may corroborate data (adding to the provenance) without
actually changing the data itself.

As an example, suppose we constructed a cell that contained the
maximum and minimum temperatures ever observed in Boston.  It is not
very likely that an update containing today's temperatures will
actually change the contents of the cell, as these temperatures are
unlikely to be that far from the mean.  Even so, it is necessary to
include the provenance of today's temperatures in the provenance of
the maximum and minimum temperatures, so that an audit would be able
to confirm that the maximum and minimum temperatures were selected
from a dataset that included today's temperatures.\footnote{Note that
  we again differentiate our \textit{provenance} of these temperatures
  from the \textit{justification} of these temperatures, which would
  presumably come from the actual temperature readings that provided
  the maximum and minimum.}

The separation of provenance and data also allows us to treat their
security separately as well.  In some cases, such as when dealing with
classified data, it may be necessary to restrict access to the data
itself, while permitting auditor access to its provenance.  Other use
cases may require the opposite behavior, such as when an organization
wishes to protect a whistle-blower's identity. \cite{braun2006provsec}
If we were to treat provenance and data as distinct entities, it is
possible to set up separate access control mechanisms for the data and
the provenance.

\subsection{Provenance-Aware Cells}

\label{sec:provcell}

To maintain this separation of data and provenance, I introduce the
concept of ``provenance-aware cells'', which are a transformation of
the cells in the traditional propagator network.  Instead of using a
single cell to represent data, a provenance-aware cell is actually a
group of three cells, the \textit{master}, \textit{data}, and
\textit{provenance} ``sub-cells.''  These three sub-cells work together
to associate data and provenance by maintaining UUID pointers between
the sub-cells.  However, separating these cells in this manner still
allows them to change independently from one another.  In practice, we
treat a provenance-aware cell as a distributed data structure, as
described in Section~\ref{sec:propastruct}.

The UUID of the \textit{master sub-cell} ((a) in
Figure~\ref{fig:cell-indirection}) provides a general identifier for
the collection of the three sub-cells as a whole.  This cell contains
pointers to the data and provenance sub-cells.  It may also contain
additional meta-data that might apply to the entire provenance-aware
cell.  Although a complete discussion of how such meta-data would be
used is outside the scope of this thesis, such meta-data might assist
with use cases that require authentication of the provenance by
providing a pointer to the public key of the cell's owner.

Depending on the meta-data stored, the master sub-cell usually will not
need a proper merge operation, as its contents normally will not
change.  Since we are likely to know the meta-data of the
provenance-aware cell when it is being created, we may use simple
assignment as a merge operation when the contents of the cell are
empty.  Otherwise the merge operation may be a simple null operation.

The \textit{data sub-cell} ((b) in Figure~\ref{fig:cell-indirection})
contains the data of the provenance-aware cell in a simple wrapper
that adds a pointer back to the master sub-cell.  The merge operation
on this sub-cell would be constructed from the original merge operation
of the non-provenance-aware cell and a stub operation that would add
the wrapper containing the pointer to the master sub-cell.  This would
ensure that the actual data of the sub-cell was the only data in the
sub-cell that changed.

The \textit{provenance sub-cell} ((c) in
Figure~\ref{fig:cell-indirection}) is similar to the data sub-cell: its
data would consist of the provenance of the provenance-aware cell
wrapped together with a pointer to the master sub-cell.  The merge
operation of the provenance sub-cell would be similar to that of the
data sub-cell.  It combines the basic merge operation used for the
format of provenance that is stored in the cell with a stub that would
add the pointer to the master sub-cell.

In practice, I implement a basic provenance merge operation that
constructs the model of provenance described in
Section~\ref{sec:provenance} by taking the union or addition of the
provenance as needed, depending on the form of the update.  For
example, if the cell was modified by a provenance-aware propagator,
the associated update to the provenance sub-cell will contain the
entire provenance of the source cell, which will be \textit{added} to
the local provenance.  During re-synchronization, however, the update
will contain a \textit{copy} of the local provenance.  In this case,
we would take the \textit{union} of the two provenance structures.

%As provenance may be represented in a graph format, with the sources of
%data coming from many different sources (such as in the
%maximum/minimum temperature case, which may use many thousands of days
%of temperatures to construct its value), we must actually be able to
%unify and add to the set of provenance graphs at each step in the
%default operation.  Other provenance traces may require some other
%merge operation, which we also allow, but such must still be aware of
%the loose wrapper around the data.

Unlike normal cells in a propagator network, the three sub-cells of a
provenance-aware cell are not initially in a true empty state.
Instead, they are initialized such that the contents of the
provenance-aware cell as a whole may be considered to be empty.  By
this, I mean that the data and provenance cells are effectively empty.
Although the pointer back to the master cell is specified, the actual
data wrapped with them would be treated as an empty cell by the merge
operation.

Separating provenance and data in this way gains us an additional
benefit in a propagator network: we may construct and maintain
provenance only at those points in the propagator network where we
desire it.  We would effectively treat the propagator network between
such cells as a single compound-propagator which has then been
augmented to be provenance-aware.

For example, a number of basic arithmetic propagators may be used to
convert a temperature between the Fahrenheit and Celsius temperature
scales.  Although we could track the provenance of the values through
each arithmetic operation, there is little knowledge gained from doing
so.  Useful knowledge is only obtained following complete conversion
between the two scales.  Instead of adding a provenance-aware
propagator and cell for each operation, we need only use a simple
propagator network between the two data cells and forward the
provenance directly to the provenance-aware cell at the other end of
the propagator network.  This effectively ``bypasses'' the
computational operations where we do not need to maintain provenance.

\subsection{Provenance-Aware Propagators}

Modification of a propagator to become provenance-aware requires the
addition of a simple propagator that will read the contents of a
input's provenance sub-cell and then forward its contents as an update
to the output's provenance sub-cell for merging ((d) in
Figure~\ref{fig:cell-indirection}).  This propagator would also modify
the input provenance to add a record for the particular propagator
(and possibly one for the output cell as well, if its merge
operation does not add one already).

This propagator is only triggered when an update has been sent to the
output's data sub-cell by the primary propagator.  The added propagator
effectively becomes a switch, allowing provenance updates to be
forwarded only after the primary propagator has sent an update.  As
propagators may have multiple inputs and outputs, there must be one
provenance switch-propagator for each pair of input and output cells
in the original propagator.  This ensures that the provenance of all
input cells will only be forwarded to output cells that have actually
received an update.
