This report deals with the problems associated with building a reliable Distributed Computer System (DCS), able to survive node crashes and communication problems. A DCS is modeled as a set of nodes which communicate only by sending messages over an (abstract) communication network. Each node is made of a processor and some memory. There are two kinds of memory: permanent and volatile. It is assumed that permanent memory never fails, and that its state is not affected by node crashes. Techniques for building one such memory are outlined. For the communication subsystem, the only assumption is that any two nodes may send messages to each other, but no direct connection is assumed. The communication subsystem may fail, in the sense that a message may be lost, duplicated, and arbitrarily delayed.
The concept of transaction is the basis of the entire presentation. A transaction is taken as the equivalent of an atomic action, i.e., an action which appears to take place in an indivisible manner. A transaction must show failure atomicity, in the sense that either it happens in entirety or not at all. Transactions are said to manipulate objects. Read and Write are the only primitive actions performed on objects.
A system must satisfy consistency constraints. Transactions are the units of consistency since, by definition, execution of a transaction in isolation leaves the system in a consistent state (if it was in a consistent state before transaction execution). Parallel execution of transactions may lead to an inconsistent state. It is well known that consistency is preserved when the parallel execution of a group of transactions is equivalent to some serial schedule of those transactions.
The author chooses locking to achieve transaction serialization. Locks provide serialization on an object-by-object basis. The classical two-phase locking protocol is therefore brought in. This protocol is then modified so as to allow object restoration in the face of node crashes. The new protocol works by saving sufficient object’s state information, when a transaction acquires a write lock for a given object. All locks are released at the same time, when the transaction either commits or aborts. The two-phase commit protocol [1] is then presented to deal with transaction commit/abort in a distributed system.
The arguments summarized above form the content of the first three chapters. I must say that these chapters make a very clear picture of the subject matter; they could be taken as a sort of reference manual.
Nested transactions come into play in the fourth chapter. To understand what nested transactions (also called subtransactions) are, consider a transaction as the action corresponding to the execution of “transaction routine.” It is likely that a transaction corresponds to the execution of several “subtransaction routines.” Execution of these routines may be sequential, but it is conceivable that they are run concurrently, so as to provide concurrency within the original transaction. These threads of execution are naturally called subtransactions. Subtransactions must synchronize with each other, within the microcosm of synchronization given by the whole transaction, in the same way as whole transactions synchronize with each other.
As a result, we have a top-level transaction which is composed of a certain number of nested (sub)transactions. The argument may be iterated and a hierarchy can be admitted. This leads to a subtransaction tree, having its root in the top-level transaction. (At this point, the terminological distinction between transaction and subtransactions becomes irrelevent).
Synchronizing nested transaction needs some extensions to the locking algorithm, because the locks acquired by a subtransaction cannot be released until the top-level transaction commits itself. Therefore, parent transactions inherit the committing child’s locks. Extensions are also needed to the state restoration algorithm.
The author’s DCS model assumes that each object exists entirely at a single node, and that no object duplication is allowed. This assumption has significant impact on overall system operation: it makes object handling a pure local fact. With the further assumption that only leaf transactions (in the nested transaction tree) may manipulate objects, the concern is limited to the effects of local transactions. Though limiting, these assumptions should be reasonable for most practical cases; besides they make for a very clean design.
The author makes the claim that the concept of subtransaction may be useful in several ways. The argument goes as follows. If a subtransaction is considered as a full-fledged transaction within the microcosm of its parent transaction, then its failure may not affect the outcome of other transactions. In a distributed system, a transaction will be broken in a number of subtransactions running at different nodes. It is conceivable that in case of failure of some subtransactions, only those that failed should be retried. In other words, only the nodes at which (sub)transactions failed need to intervene in transaction redoing. As the author puts it: “If the independent failure property of subtransactions is coupled with appropriately timed writes to permanent storage . . . ., then we might be able to raise the limiting probability of success from zero to one.”
To coordinate system activity, each node has a Transaction Manager (TM). The node where a (sub)transaction is created is called the “home node” of that transaction; the associated TM is called the transaction manager of that transaction. A transaction’s TM is the only transaction manager that can move the transaction through its state transitions towards commitment or abortion. The bulk of the work deals with the construction of a protocol able to resist communication failures, transaction aborts, and node crashes.
To drive transactions at completion, TM’s exchange messages with each other. There is a long list of possible message types: commit and abort notices; prepare, prepared, complete and completed messages; queries (on transaction states) and responses. Of course a transaction is completed only when the top level transaction completes. In practical cases this may entail transmission of a great number of messages between TMs. It’s hard to say how long a transaction may last. Performance aspects are not addressed. My impression is that if performance is an issue, then application of this methodology should be carefully evaluated.
However, this objection is irrelevant. The state-of-the-art requires a better understanding of DCS behavior, much more than addressing performance issues. In this light, the author’s attention is on reliability, on guaranteeing system progress, and on avoiding system deadlocks.
The remaining part of the book is dedicated to the examination of related work, the discussion of accomplishment, and the indications for further research.
My evaluation is that the author has made a successful step towards the unification of several concepts that were previously known, by compounding them in a consistent manner and improving them for application to DCS. Original solutions to some intricate problems have been presented. Another quality is that the scope of the work goes much beyond the field of Data Base Management Systems, addressing general purpose programming problems. Examination of ongoing projects and an updated extended bibliography make the book very appropriate also for beginners (in distributed systems). I would recommend it even to the experienced reader.
Now for some criticisms. Intent on being very accurate, the author gets quite boring in several parts. Algorithms are usually presented in a descriptive manner. After two or three uniformly written pages, I often found myself thinking of something else other than what I was reading. Some more schematization (i.e., use of a pseudo-programming language) to explain the subject matter would certainly have helped. I had a great sense of relief when I encountered a piece of program. Unfortunately, such schematizations were very few. Also, the typographical aspect of the report is not the most attractive one. Some figures are not numbered, and state diagrams have no indication of conditions triggering state changes. Often they are obvious, but sometimes they are necessary.
