Topic: Distributed systems
Here is another post in my series about distributed systems.
This one is about J. Eliot B. Moss's 1981 PhD dissertation on nested transactions.
Moss's dissertation describes a system built using two-phase locking, two-phase commit, and a new deadlock detection algorithm as the mechanism for guaranteeing serializability and progress in the presence of multiple failure modes.
A contrasting approach to implementing nested transactions is to use multi-version timestamping (introduced in David P. Reed's 1978 PhD dissertation, which was mentioned in a previous post).
The multi-version approach is free of deadlock as a result of object timestamping, however it is vulnereable to livelock: slow, long-running transactions retrying repeatedly due to changes committed by quickly running ones. For the same reason, multi-version timestamping does not work well in the presence of a high degree of contention over an object by many transactions. Aspnes et alia's 1988 paper on applying multi-version timestamping to nested transactions provides an extension of Reed's original algorithm that somewhat alleviates this problem.
Nested transactions, while not necessary for many applications, become
critical when nondeterminism, such as the orElse construct
introduced in Harris
et alia's 2005 paper on composable memory transactions and
implemented in the GHC
software transactional memory system (to be discussed in an upcoming
post), is needed.