% Lots of related work exists, and it is boring. I read it all so you
% don't have to.

% The long history of multiversion concurrency control, starting with
% Reed in 78. Snapshot isolation. Other work on exploiting read-only
% transactions, but most of it is about avoiding locking, or other more
% complex things. Not really interested in caching like we are. Barbara
% and Rodrigo proposed this idea.

% Weak consistency things are vaguely related in spirit, but not
% really. They are confusing and not really all that interesting. This
% is a different kind of weak consistency where anomalies exist only in
% the distributed setting, and we can argue they are insignificant.

\paragraph{Multiversion concurrency control.}

The general concept of multiversion concurrency control has a long
history, dating back to Reed's work in
1978~\cite{reed78:_namin_and_synch_in_decen_comput_system,reed83:_implem_atomic_action_decen_data}. Many
variations on its use have been proposed for use in both centralized
and distributed database
systems~\cite{bernstein81:_concur_contr_in_distr_datab_system}. Multiversion
concurrency is used most commonly in the form of snapshot isolation
(also a weakened consistency model, as described below), which is
implemented in several popular commercial databases. The benefit of
multiversion concurrency is that having multiple versions of the same
data object makes it possible to perform some operations without
locking. The exact degree to which locks can be avoided depends on the
specific protocol; variants range from multiversion two-phase
locking, where both read and write locks are used, to optimistic
timestamp-ordering, with no locks at
all~\cite{bernstein87:_concur_contr_and_recov_in_datab_system}.

\paragraph{Optimistic concurrency control.}
Multiversion concurrency control is frequently combined with
\emph{optimistic} concurrency
control~\cite{kung81:_optim_method_for_concur_contr}, making it
possible to avoid locks entirely by aborting and retrying if a
conflict occurs. Our work uses optimistic concurrency control in
essentially its standard form for read/write transactions. The use of
a single server greatly simplifies validation and ordering in our
optimistic concurrency control; a protocol like
CLOCC~\cite{adya95:_effic_optim_concur_contr_using} would be required
for the multiple-server case. Though our mechanism for optimizing
read-only actions could also be combined with a locking protocol for
read/write transactions, we have chosen an optimistic protocol instead
because previous work has shown that optimistic concurrency control
provides a performance benefit in distributed
systems~\cite{liskov99:_provid_persis_objec_in_distr_system}.

\paragraph{Weak consistency.}

Many proposals for isolation levels less than full serializability
exist~\cite{gray77:_granul_of_locks_and_degrees,ansi92:_datab_languag_sql,berenson95:_critiq_of_ansi_sql_isolat_level,adya00:_gener_isolat_level_defin,adya99:_weak_consis}. The
ANSI~SQL standard~\cite{ansi92:_datab_languag_sql} defines three such
isolation levels, and many databases default to one of these. Snapshot
isolation~\cite{berenson95:_critiq_of_ansi_sql_isolat_level} is also
used by many databases. Snapshot isolation ensures that each
transaction reads from a consistent snapshot of the database, but is
not fully serializable because it suffers from an anomaly known as
\emph{write skew} because it only detects conflicts between the write
sets of two transactions, not read/write conflicts. Our handling of
read-only transactions could be viewed as snapshot isolation, albeit
perhaps on a less-than-current snapshot, but we avoid write skew by
tracking both the read and write sets of read/write transactions.

The plethora of work attempting to categorize these weak consistency
models attests to their complexity: for example,
\cite{adya00:_gener_isolat_level_defin} is a critique of the
definitions in \cite{berenson95:_critiq_of_ansi_sql_isolat_level},
which is itself a critique of the definitions in the SQL
standard~\cite{ansi92:_datab_languag_sql}. It is similarly difficult
to reason about the cases in which such consistency is sufficient. For
example, snapshot isolation is generally considered ``almost''
serializable (to the extent that it is the highest level of isolation
offered by many databases). Many workloads, such as the TPC-C
benchmark, do indeed execute serializably under snapshot isolation;
however, verifying that this is the case requires non-trivial
analysis~\cite{fekete05:_makin_snaps_isolat_serial}.

Our work is similar in spirit to these forms of weak consistency,
having the same goal of improving performance by allowing some
anomalies. However, motivated by the difficulty in reasoning about
non-serializable execution levels, we relaxed the \emph{causality}
requirements instead of consistency. As a result, our protocol is not
directly comparable to other weak consistency schemes; the only
anomalies that can be observed are ones in which different, but still
transactionally consistent, states are observed on two different
nodes.

\paragraph{Read-only transaction optimization.}

A number of optimizations that take advantage of read-only
transactions have been proposed. Garcia-Molina and Wiederhold defined
consistency and currency requirements for read-only transactions, and
introduced the concept of \emph{insularity} to determine when a
transaction can be executed locally on one node of a distributed
database~\cite{garcia-molina82:_read_only_trans_in_distr_datab}. Our
processing of read-only transactions is similar to the algorithms they
propose, but our use of optimistic concurrency control for read/write
transactions leads to some important differences.  Other work
(\emph{e.g.}~\cite{weihl85:_distr_version_manag_for_read_only_action,wu93:_dynam_finit_version})
has considered how to minimize the number of versions that need to be
retained in order to optimize read-only transactions, but it is
generally focused on avoiding locking rather than taking advantage of
cached data in a distributed system.

C-Store~\cite{stonebraker05:_c_store} applies the same concept in a
different environment, running read-only queries in a data warehouse
on an old version using snapshot isolation.

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

% LocalWords:  serializability serializable SQL