On Optimistic Methods for Concurrency Control
by H.T. Kung and John T. Robinson
Transactions on Database Systems, vol 6 no 2, 1981.

This paper has as its premise that serializability through two-phase
locking constrains concurrency more than is needed in most databases.
It recommends, instead, that applications optimistically proceed without
locks until they are ready to commit, then "check" that they did not
conflict with another transaction.  If a transaction did conflict, they
rely on transaction abort and atomicity to "recover" from the conflicts
and then restart the transaction.

This paper is "the" paper justifying the notion of optimistic execution.

A couple of notes on language -- what we call serializability, they call
serial equivalence -- what we call consistency, they call integrity.

Lock-based serializability reduces concurrency, adds lock overhead (mutual
exclusion is usually built on lower level, more exclusive, centralized
mechanisms), may allow/increase deadlock risks.  But in many systems the
real probability of conflict is very low, because real sharing is rare,
so the "benefit" of the lock overhead and reduced concurrency is not
large.

An optimistic method assumes that conflict will not happen, runs a faster
algorithm based on that assumption, and pays an expensive recovery process
in case the assumption is wrong.  If the recovery process is automated (ie.,
transaction abort and restart), then this strategy is not only a performance 
improvement, it is also a software coding simplification technique.

Returning to serializability, a set of concurrent transactions are 
serializable if an ordering exists such that the database is transformed
from the original state to the final state through intermediate states
that agree with the intermediate states of this serial ordering.   We
shall delay choosing this ordering as long as possible in these optimistic
schemes.  While we do not restrict transactions with two-phase locking, we
do assume two phases, database reading following by database writing (we
can use private scratch to delay the database writes til all work is complete).

What matters is the state a transaction sees and the transforms it applies.
The criteria for an ordering (transaction numbering) in which transaction i
proceeds transaction j is the satisfaction of ONE of the following:
1) T(i) completes all writes before T(j) starts reading [no concurrency]
2) the writes of T(i) do not intersect with the reads of T(j) and T(i)
completes its writes before T(j) starts its writes [no read-before-write 
conflicts]
3) the writes of T(i) do not intersect with the reads or writes of T(j) and
T(i) completes its reads before T(j) completes its reads [no sharing]

So the optimistic mechanisms explicitly record read and write sets and test
intersections.

They offer two mechanisms.  The first, serial ordering, checks for the first 
two conditions, defines a critical section around the validation and all 
writes, and as a results is not useful for disk based databases.  The second,
parallel validation, checks for all three conditions, defines a critical 
section only around the definition of which transactions are concurrent and 
their sets, then validates and writes.  

The idea behind the second mechanism is that the critical section at the end 
of the read phase establishes this transaction in a "race" to determine 
which of the transactions which have finished their reads will be the first
to finish its writes and be "next" in the serial ordering.

Optimistic algorithms are MUCH harder to understand than lock-based solutions
and implementers still tend to prefer two-phase locking.  But when their is
enough concurrent work, and conflicts are rare (lots of data) then optimistic
methods will be much more scalable.  Database designers simply make transactions
big enough that there aren't that many concurrent transactions and the
scalability advantage is not compelling -- my opinion.