Nested Transactions

Here is another post in my series about distributed systems.

This one is about J. Eliot B. Moss's 1985 PhD dissertation on nested transactions, Nested Transactions: An Approach to Reliable Distributed Computing, published by the MIT Press. In it, Moss explains the design of his distributed transaction system supporting nested transactions.

Although Moss's is not the first distributed system to support nested transactions, the dissertations introduces the novel mechanism of two-phase locking and deadlock detection as the mechanism for guaranteeing serializability as a correctness condition.

A contrasting approach to implementing nested transactions is to use multi-version timestamping (introduced in David P. Reed's 1978 PhD dissertation, mentioned in a previous post). This 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 strictly necessary for many systems, 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.