\chapter{Summary}

\label{ch:summary}

\section{Contributions}

% Am I sure I want to keep it as an appendix?

I have discussed and implemented a distributed system based on the
computational paradigm of data propagation in an attempt to provide
distributed solutions to problems with high dimensionality. This
architecture, which I call ``distributed propagation'', achieves
useful computation within a weakly-connected network, making it
comparable to existing distributed computing approaches that also
assume such. I designed this system with the principles of
Representational State Transfer, or REST, in mind, resulting in a
system that is both robust to failure and simple enough to be easily
implemented on multiple platforms.

% Something about RESTAR here?

The development of distributed propagation has also led me to outline
and implement a provenance mechanism for distributed propagator
systems. This mechanism takes advantage of the explicit modularity of
propagator networks and provides for the simple modification of
existing networks to add support for provenance. I have implemented a
library to support the creation of distributed propagator networks
which demonstrates this by implementing fundamentally identical APIs
to construct both traditional and provenance-aware distributed
propagator networks.

\begin{table}
\begin{center}
\begin{tabular}[c]{l|p{11cm}}
Constraint & Benefit \\
\hline
Idempotence & (with associativity) no locking during cell initialization \\
 & no filtering for duplicate updates during re-synchronization \\
Associativity & (with idempotence) no locking during cell initialization \\
 & don't need to save all updates for re-synchronization \\
Commutativity & removes need for global synchronization (timestamps) \\
 & removes timeliness constraint on communications \\
Monotonicity & removes complexity caused by deletion operations \\
 & allows computation of results with partial knowledge \\
\hline
\end{tabular}
\caption{The four constraints on the merge operation and their benefits.}
\label{tab:constraints}
\end{center}
\end{table}

I have also outlined several constraints on the merge operations used
in data propagation; these constraints reduce the complexity of
distributed propagator networks and allow for meaningful distributed
computation. The four constraints and their corresponding benefits are
outlined in Table~\ref{tab:constraints}. Finally, I have also
developed a loose guideline for how data structures may be represented
in propagator networks, either by including data structures in the
cells themselves, or by treating cell URLs as de-facto memory
pointers.

\section{Challenges and Future Work}

\subsection{Propagator Networks \& Garbage Collection}

In this thesis, I have assumed that the collection of all cells in a
propagator network is monotonically increasing. There is no explicit
``deletion'' or ``unregistration'' mechanism for a distributed
cell. Once a cell has been created, it may not be deleted, nor may a
host disclaim any continuing interest in it. There is no mechanism for
garbage collection in a distributed propagator network; this results
in an intractably large propagator network as time progresses.

In practical systems that use distributed propagator networks, it may
be necessary to support non-monotonic actions, such as the deletion or
unregistration of a cell from a given network. In doing so, we may
allow for more efficient allocation of the resources on a host. Rather
than spending effort to re-synchronize or maintain a copy of a cell
that will never be re-used, a host may allocate resources to more
useful computation.

There is a similar need for a mechanism to allow propagator networks
to eventually prune unreachable peers. This would allow networks to
eventually stop making efforts to synchronize a node that no longer
exists.  A implementation of garbage collection within propagator
networks in general will be needed before distributed garbage
collection may be considered.

\subsection{Data Structures and Propagators}

It is not entirely clear that the URL-based distributed data structure
design that I propose in Section~\ref{sec:propastruct} is useful for
more general computation in propagator networks. It may be difficult
to merge two data structures for which only pointers are known. If two
pointers are assigned at the same time to different (shared) cells,
there is no way to determine how to merge these otherwise opaque
pointers. A sensible merge algorithm may need to look at the contents
of each pointer to unify cells that may have been assigned different
UUIDs.

The provenance-aware cells proposed in Section~\ref{sec:provcell} are
not affected by the issue raised above. When a provenance-aware cell
is created, all pointers are allocated to appropriate sub-cells
automatically. This means that any merge operation on the sub-cells of
a provenance-aware cell should never have to merge two distinct
pointer values that are assigned to the same field; the merge
operation may safely ignore the contents of the pointer field other
than ensuring that it remains assigned.

\subsection{Redundancy of Distributed Operations}

One advantage of distributing propagation is that we may
\textit{duplicate} a host as many times as we like and have all
duplicates perform the same computation in parallel.  This would allow
for error-correction and fault-tolerance, as a failure to produce
correct results would be ameliorated by the ability of other hosts to
generate the correct values.

At this point, all such duplication would have to be designed into the
application.  This may be problematic, as the number of duplicate
clients may not be known at run time.  Resolving this issue and
allowing dynamic allocation of redundant computation will require the
resolution of the compound propagator issue described below.

\subsection{Scalability and Practicality Issues}

Although I have tested distributed propagation successfully across a
network, these tests have been limited in scope to only two or three
peers. I have not yet tested larger distributed propagator networks,
and it is unknown whether propagator networks will scale practically;
the amount of re-synchronization communications is likely to result in
flooding the network as the propagator network grows large.  As each
cell re-synchronizes with every other cell that it knows about, and my
distributed propagation model assumes the existence of a clique, the
number of re-synchronization messages per unit time will grow
according to the square of the number of peers.

\subsubsection{Cell Discovery}

Although this thesis has considered discovery of an initial cell copy
to be orthogonal to the problem of distributing propagator networks, a
scalable distributed propagator network will need to be able to
determine what cells exist and where copies are located. A number of
mechanisms may be helpful in moving beyond the assumption of a priori
knowledge passed to the API, which I have assumed in this
thesis. Other mechanisms may include name servers like DNS
\cite{rfc1034,rfc1035} or service-discovery protocols such as DNS-SD
\cite{dnssdDraft} or SSDP (part of the universal plug-and-play
architecture (UPnP) proposed by the UPnP Forum \cite{upnp1_0,upnp1_1}).

% Something about the duplication of the same propagator host for 
% backups.

\subsubsection{Compound Propagators in Distributed Propagator Networks}

As distributed cells must be assigned a UUID identity \textit{before}
they may be connected to propagators or remote cell copies, there is
no mechanism to create a cell on a remote host and spawn a given
propagator attached to it. This makes it difficult to dynamically
negotiate or delegate tasks in a distributed application. This also
makes it impossible to create distributed compound propagators, one of
the more compelling elements of propagator networks. Although we may
instantiate \textit{local} propagators when a cell receives data, we
may not dynamically assign tasks to remote hosts by providing a
propagator and cell.

It may be possible to create such dynamic propagator networks by
treating propagators as first-class objects that may be stored in a
cell. We might then be able to distribute propagator and cell
descriptions to remote nodes so that they may be instantiated for
further processing. Allowing arbitrary code execution does raise
security concerns, so any mechanism for compound propagation within
distributed propagator networks will need to be carefully crafted to
eliminate issues that arise due to allowing the dynamic construction
of distributed propagator networks.

\subsection{Security}

I have outlined several approaches to security in
Sections~\ref{sec:security}~and~\ref{sec:provaudit}. However, my
implementation, DProp, and its accompanying library, PyDProp,
currently do not implement them. As such, the security implementations
proposed in this paper should be studied to ensure that data remains
secure and that effective access control is possible in this system.
Improved encryption may be had by implementing propagation with a new
protocol that allows for cell-based security mechanisms.

SSL may also suffer scalability issues.  As my proposed SSL
implementation of security depends on knowledge of certificates, the
number of certificates that must be ``known'' by a user of distributed
propagation may be high in a large distributed system.  Unified
authentication systems such as Kerberos may be more appropriate within
larger networks than SSL, allowing greater scalability and larger
propagator networks.

\subsection{Representational State Refinement}

Strictly speaking, the combination of propagation and REST I have set
out in Chapter~\ref{ch:design} does not strictly adhere to several of
the underlying principles of REST.  Although it nominally adheres to
the five primary constraints of REST, distributed propagation does not
follow some of the underlying tenets of hypertextuality and resource
management that a true RESTful architecture provides.  In particular,
distributed propagation does not generally concern itself with the
creation or deletion of resources; most, if not all, actions on cells
are done solely through the GET and POST operations.

Nevertheless, it seems inappropriate to simply abandon a RESTful model
for distributed computation.  Distributed propagation does make
effective use of resource retrieval and update, and actually places a
more meaningful constraint on the meaning of ``update'' implied by the
POST operation.  Updates within a distributed propagator network may
only be used to ``refine'' a resource, rather than allowing any
arbitrary modification.

As completely disposing of REST would be inappropriate, I propose that
the work presented here is not so much that of ``Representational
State \textit{Transfer}'' but of ``Representational State
\textit{Refinement}'', or RESTAR.  This architectural style
essentially synthesizes the principles of propagation and resource
management into a single model.  Rather than simply providing for the
underlying CRUD operations of creation, reading, updating, and
deletion, RESTAR supposes the replacement of the nondescript update
operation with a ``refinement'' operation which selectively updates
the resource by refining partial knowledge of the resource.

\subsection{Which HTTP Method? POST vs. PUT vs. PATCH}

One critical aspect of constraining ourselves to a new REST-based
model is the correct choice of HTTP method for conveying updates to
remote cell copies.  Although I have modeled propagation of updates
through the use of the POST method, we must be careful that this is
the correct HTTP method to use.  The effective semantics of a POST are
vague; POST is stated to be a non-idempotent method that is to be used
to effectively create a new ``subordinate'' of the resource to which
the POST request is sent. \cite{rfc2616} However, this is commonly
interpreted in practice to allow for the modification of the resource
itself, and this is how I use it in this paper.

Unlike POST, PUT is specified to be idempotent.  Although this might
seem to be preferable, PUT is much more strongly associated with the
semantics of ``creating'' or ``replacing'' an object at the URL
provided in the request.  As distributed propagation never actually
creates cells, and updates cannot simply ``replace'' the old content
of the cell without abandoning the monotonicity constraint on the
merge operation, PUT may not be used for distributed propagation.

The PATCH method of HTTP \cite{rfc5789} carries more appropriate
semantics, in that it allows a set of changes to be applied to the
resource to which a PATCH request is sent.  However, PATCH is still
specified to be non-idempotent.  Distributed propagation explicitly
requires idempotency, so this would require an implicit additional
restriction on the PATCH operation.

Unfortunately, while the PATCH method would thus be the most
appropriate method to implement distributed propagation, some HTTP
implementations may not be able to support this relatively new method.
The Twisted library and Python's \texttt{httplib} module, which I have
used to construct my implementation, DProp (See
Appendix~\ref{ch:dprop}), do allow the PATCH method, and I plan to
revise DProp to support the PATCH method in a future release.

\section{Conclusion}

Distributed propagation provides a useful alternate mechanism for
distributed computation that does not rely on simply distributing the
data across the system for identical processing. This will provide for
a larger number of computations that may be distributed, and perhaps
allow for a greater number of applications for distributed computing.
As the power of individual computers begins to reach a plateau without
making use of concurrent processing, it will become ever more
important to construct systems to make use of a larger number of hosts
and processors and to move away from sequential processing.

By providing a mechanism for the distributed \textit{refinement} of
resources, distributed propagation and related applications may
provide a means to develop more push-based, data-driven algorithms
over a network and on the world wide web.  As interest in other
push-driven web application technologies like Comet and Web Sockets
grows, distributed propagation may provide a meaningful development
model for those applications that do not wish to abandon the
resource-based architecture style of REST.
