\subsection{Multiple Servers}
\label{sec:future:multiple-servers}

% Sketch of how this would work if we had multiple servers. Everything
% operates essentially the same except that transactions spanning
% multiple block servers would need to appoint one as the coordinator
% and perform a 2-phase commit. Of course, timestamps need to be
% synchornized somehow, e.g. with Lamport clocks or loosely synchronized
% clocks (CLOCC).

% The main complication, perhaps surprisingly, is conflict-freeness of
% read-only transactions. It's not obvious how to guarantee this, or
% even if it's possible at all. The problem is that two-phase commit
% requires a prepare phase in which a transaction has been assigned a
% timestamp but its fate is undecided. While the transaction is in the
% prepare phase on a particular node, that node can't return modified
% blocks for that timestamp because it doesn't know which version to
% send. It needs to block for the transaction to commit or abort, which
% is exactly what we don't want. Could probably work around this by
% using flexibility in transaction timestamps, with the server helping
% pick, but this gets icky real fast.


The protocol described in Section~\ref{sec:algorithm:protocol} assumes
a single, central server; this decision was made to simplify the
protocol and the implementation. With a few modifications, the
protocol can also be used in a more distributed setting. We sketch an
outline of such a modified protocol. For simplicity, we consider an
environment where blocks are statically partitioned between multiple
servers. If all blocks in a transaction are on one server, the
transaction proceeds as before. Otherwise, one server is chosen as a
coordinator, and it executes a two-phase commit protocol.

The client must ensure that messages are processed in timestamp
order. With a single server, and an order-preserving (TCP) connection,
this task is trivial, but with multiple servers it is somewhat
complex. A simple solution is to maintain loosely synchronized clocks
on all machines (using NTP or a similar protocol), then include
timestamps in each message and delay the processing of each message
until its timestamp has been
reached~\cite{adya95:_effic_optim_concur_contr_using}; another
alternative is to explicitly use logical
clocks~\cite{lamport78:_time_clock_and_order_of}.

An open problem is that two-phase commit is necessary for multi-server
consistency, but is at odds with the conflict-freeness of read-only
transactions. Specifically, the problem is that when subordinates are in
\textsc{prepared} state, the fate of the prepared transaction is
unknown; if a read-only transaction attempts to retrieve an affected
block, it must block until the transaction commits or aborts. One
solution is simply to relax the conflict-freeness requirement, but
this is undesirable. An alternative might be to assign transaction
timestamps lazily: rather than having the client choose a timestamp,
it could choose a range of timestamps to send to the server in its
\textsc{get} requests, and the server could choose a timestamp that
avoids blocking on prepared transactions.

\subsection{Generalized Causality}
\label{sec:future:generalized}

% If two applications on different node managers communicate out of
% band (either, for example, through their own network connection, or
% by one person walking from one computer to another), then the
% weakness of global causality becomes observable. While clearly
% nothing practical can be done about a user walking between nodes, it
% is unfortunate that a distributed application wishing to use our
% block store as an infrastructure service cannot better characterize
% its causality needs to the system.

Out-of-band communication between nodes can expose the lack of global
causality in the system.  This could arise either from applications
opening their own network connections, or through external observers
with the ability to observe more than one node in the system.  While
little can be done about external observers except to reduce the
acausality to an acceptable minimum, it is unfortunate that a
distributed application wishing to use a transactional infrastructure
service based on our algorithm cannot better characterize its
causality needs to the infrastructure.  Generalized causality would
permit such characterizations so that applications would not be
limited to the strict dichotomy between local causality and global
acausality.

\subsection{Dynamic Read-Only Timestamps}
\label{sec:future:timestamps}

Our protocol currently assigns read-only transactions a timestamp no
earlier than the GLUB, even if the freshness requirement $\epsilon$ is
much more flexible. In some circumstances, it can be desirable to use
an earlier timestamp for which more cached data is present. Choosing
the best timestamp to maximize cached data availability is a difficult
problem. The timestamp is currently assigned when a transaction
begins; at this time no information is available about what data will
be read.

We could instead assign timestamps lazily, initially beginning with a
window of maximum allowable size (ending at the current time, and
beginning at the timestamp of the freshness requirement or the last
committed read/write transaction). Each successive read would choose
an appropriate version, from the cache if possible, and \emph{narrow}
the window to its intersection with the validity interval of that
version. This allows more flexibility to use cached
versions. Additionally, hints about the read set of the transaction
could be used to make a more informed decision at transaction start
time.

\subsection{Applications}
\label{sec:future:applications}

We would like to evaluate the performance of our system using real
applications in addition to traces. We would like to have some sort of
database workload, perhaps using our system as the bottom layer of
SimpleDB. A transactional file system would also make an interesting
workload; an actual implementation would make it possible to avoid the
NFS caching effects we observed on our trace workloads. A file system
implementation might benefit from expanding the block store interface
to be aware of file metadata, allowing for several optimizations; to
be practical, it would also require a system for inferring
transactions from existing non-transactional application workloads.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "report"
%%% TeX-PDF-mode: t
%%% End: