\chapter{Related Work}

\label{ch:related}

\section{Distributed Cells and Replicated Databases}

The work on distributed propagation described in
Chapter~\ref{ch:design} builds upon a significant amount of work in
the field of replicated databases.  Although cells are not as complex
as databases, the replication and propagation of updates are analogous
to the replication and propagation of queries in a synchronized,
replicated database.  Replicated database systems adhere to a
different set of constraints than distributed propagator networks;
these may include requiring the serialization of operations and
support for non-monotonic operations, such as row deletion.
Nevertheless, database update propagation mechanisms provide a useful
baseline against which this system may be compared.

Grapevine \cite{birrell1982grapevine} offers a mechanism for database
replication that relies on message forwarding, much like distributed
propagator networks.  Although this system is similar to that of
distributed propagation, Grapevine treats messaging and databases as
two distinct subsystems of its architecture.  Both messaging and
distributed databases depend on each other to carry out their duties.
Unlike distributed propagation, Grapevine assumes that the network on
which it is operating is strongly-connected and that all nodes are
always reachable.  Distributed propagation's re-synchronization
operation ensures that cells will globally converge even if a peer is
temporarily disconnected from the network, which Grapevine is unable
to do.

Just as distributed propagation forwards updates to copies of a
cell, Grapevine propagates database changes to clones of that
database.  This propagation mechanism does not provide any guarantees
about timely convergence.  Although my mechanism for distributed
propagation also provides no timeliness guarantees, it explicitly
maintains a clique to attempt to provide timeliness; Grapevine makes
no attempt to provide anything beyond eventual convergence.  Grapevine
also does not specify a re-synchronization process following a node
failure or failed message reception.  Although the authors describe a
``nightly'' cloning operation designed to resolve inconsistencies, the
operation is not clearly defined and does not explicitly make use of
caching or other structures.

The Bayou system \cite{terry1995bayou} stands in contrast to
Grapevine, and adheres to a constraint of weak-connectivity in the
network, much as distributed propagation does.  Unlike distributed
propagation, Bayou constrains itself to the use of a strict
client-server model when controlling information; only one host
controls a canonical version of the database.  This design choice is enforced
by Bayou so as to guarantee eventual serializability of updates made
to a database.

These ``canonical'' representations of a database are not compatible
with the decentralization of distributed propagator networks.  In
contrast to the decentralized, peer-to-peer model used for distributed
propagation, Bayou implements a centralized system that makes
reorderable ``soft'' writes to a database before ``locking'' them into
a canonical order.  In addition, Bayou, like Grapevine, offers a
method to delete information from the database, and thus attempts to
satisfy a constraint of non-monotonicity.  Distributed propagation
instead uses monotonicity as a constraint and does not need to
implement this feature of Bayou or Grapevine.

The update propagation algorithm proposed by Singhal
\cite{singhal1990updatetransport} also resembles the method of
distributed data propagation described in Section~\ref{sec:resync}.
Singhal does not assume the existence of a weakly-connected network,
however.  This renders Singhal's approach unsuitable for the
weakly-connected distributed computing applications we desire to
create using distributed propagation.  Singhal's approach also
resembles Bayou in that it attempts to enforce a serialization
constraint on the operations performed, which is not necessary for
propagation due to propagation's explicit associativity and
commutativity constraints.

\section{Decentralized REST}

As mentioned in Section~\ref{sec:netarch}, DProp utilizes REST in a
decentralized manner.  Rather than strictly adhering to a
client-server architecture, DProp attempts to apply a peer-to-peer
network overlay on top of traditional client-server communications.
The work of Khare and Taylor in developing their ARRESTED architecture
provides a useful comparison to our approach of constructing
peer-to-peer communications with RESTful
constraints. \cite{khare2004arrested}

Although many of the principles of ARRESTED are similar to the
principles behind my proposal for distributed propagation, ARRESTED
also suggests several features that have been designed to adhere to
constraints that distributed propagation does not have.  ARRESTED
explicitly includes estimation, locking, and routing in their
decentralized REST architecture.  These operations are unnecessary for
distributed propagation due to its monotonicity constraint.

Furthermore, there is no need to ensure reception of a message in a
distributed propagator network, as the cell re-synchronization
mechanism, combined with the existing constraints of associativity and
commutativity ensure that a repeated attempt to merge an update will
not change the final contents of the cell.  Similarly, propagator
networks do not have a particular need to estimate the current
contents of the cell based on previous updates.  Although such a
mechanism could be constructed with propagators, there is no implicit
need to estimate, as timeliness is not a virtue in distributed
propagator networks.  We need only guarantee eventuality.

% What principles?

\section{Distributed Provenance}

There are a number of different approaches to the integration of
provenance in a system.  Many of these approaches are domain-specific,
such as for file systems \cite{sar2005lineagefs} or web services
\cite{szomszor2003ws}.  Our approach is a more holistic one,
demonstrating the viability of provenance collection and maintenance
in a general-purpose computing architecture and the easy modification
of existing software to add support for provenance.  There are many
similarities between my proposed system and more general approaches to
the inclusion of provenance in service-oriented architectures, such as
those proposed by Moreau, et al. \cite{moreau2008provenance}

In Moreau, et al's work, an architecture for provenance handling is
proposed with the aim of achieving many of the same goals of
provenance-aware propagators.  This includes the automatic
documentation of processes with what Moreau calls
\textit{p-assertions}, which are functionally similar to the
possession and modification records we use in our provenance model in
Chapter~\ref{ch:provenance}.  Moreau addresses the problem of querying
constructed provenance, instead of focusing on the construction and
maintenance of provenance, with which we are concerned.  Furthermore,
Moreau assumes that general-purpose provenance, such as the
\textit{purpose} of an action, may be collected within their system.
While this is certainly possible within provenance-aware propagator
networks, we make no explicit claims about how such potentially
subjective provenance traces are handled.

The Matrioshka system proposed by da Cruz, et
al. \cite{dacruz2008provenanceservices} also attempts to provide
provenance in distributed workflows much as provenance-aware
propagation does.  Unlike the provenance system described here,
Matrioshka relies on a centralized provenance store rather than
distributing the provenance with the data to which it applies.  The
system also assumes that logging functionality already exists in a
distributed application.  This makes Matrioshka more brittle than
provenance-aware propagation; provenance-aware propagation does not
require any intermediate steps to generate logs or store provenance,
as provenance is generated and stored along with the data it pertains
to.  Provenance-aware propagation also allows for existing
applications to be retrofitted as provenance-aware applications, which
da Cruz does not demonstrate with Matrioshka.

The work of Altintas, et al \cite{altintas2006kepler} in extending
the Kepler Scientific Workflow System is perhaps the most similar
effort to integrate provenance in existing distributed systems.
Altintas makes use of the underlying flexibility of Kepler to add a
provenance framework, much as I do with distributed propagation.  This
framework simply acts as part of the Kepler system, constructing and
tracing the provenance of events that operate within it, and it may be
easily added to existing programs that use Kepler.

This system does not port itself well to the propagation paradigm, due
to propagation's inherent decentralization.  Kepler appears to rely
instead on a client-server model of computation.  This allows the
server to additionally track provenance.  Although we could create a
provenance host that would trace the activity of all cells in a manner
similar to that of Kepler, this is not scalable.  A large enough
propagator network would effectively drown any host listening to all
updates while trying to construct the provenance of data within the
network.  This defeats the purpose of adopting distributed
computation.

In many respects, provenance-aware propagator networks complement
Munroe, et al's PrIMe system \cite{munroe2006prime}.  Rather than
providing an explicit mechanism for the inclusion of provenance in
existing systems, PrIMe is a \textit{software design methodology} that
may be used to construct provenance-aware applications by taking
provenance into account during the design process.  As a software
design methodology, PrIMe differs greatly from my proposal, being a
more concrete implementation of a provenance-aware processing system.
PrIMe does not specify a particular \textit{implementation} of
provenance, but merely helps developers consider implementing
provenance in systems that require it.  Provenance-aware propagation
may offer an opportunity to facilitate design processes that use PrIMe
by reducing the work necessary to retrofit existing systems with
provenance capabilities.

As mentioned in Section~\ref{sec:provaudit}, it is possible to extend
provenance in a provenance-aware propagator network to include
provenance integrity mechanisms by building on the approach set forth
by Hasan, et al. \cite{hasan2009picasso} Hasan applies a provenance
integrity mechanism to construct a provenance-aware file system.  In
contrast, provenance-aware propagation is a more general mechanism
for provenance construction that can be used to construct distributed
file systems, as well as many other applications.  I thus expand on
Hasan's approach to general purpose computation.
