The performance of two distributed checkpointing and recovery algorithms, the synchronous checkpointing algorithm (SA) and the independent checkpointing algorithm (ICA), is evaluated. The performance is based on a detailed implementation of algorithms published earlier in the C language. A benchmark that simulates a variety of application requirements and considers variations in the number of processes running on one or more machines, size of processes to be checkpointed, size of control messages, and frequency of message exchanges for normal processing is used to conduct the experiments. Measurements are made for the elapsed time and the CPU time to run a single instance of the checkpoint or rollback. The experiments are repeated for various combinations of concurrent checkpoint and rollback executions. The messages needed for synchronization are computed. It is found that the time that a process spends in processing control messages contributes significantly to the elapsed time in both algorithms. Elapsed times for recovery for both algorithms are found to be comparable when the number of checkpoints is small.>

Concurrent checkpointing and recovery using a concurrent transaction processing model which consists of four types of atomic operation and five types of conflict is developed. Each checkpoint/rollback transaction is executed by multiple processes in the system. They can be executed concurrently. It is shown that the consistency of recovery lines and rollback lines established by checkpoint transactions and rollback transactions can be achieved by enforcing serializability on the corresponding transactions. There are two advantages in using a transaction model for concurrent checkpointing and recovery: (1) it is easier to find algorithms to solve a transaction processing problem; and (2) based on this model, related issues of the two corresponding problems can be thought of uniformly. This model clarifies the concepts of concurrent checkpointing and recovery, and brings more ideas for designing algorithms.>

A checkpoint/rollback algorithm is presented for multiple processes in a distributed system that uses message passing for communication. Each process in the system can initiate the algorithm autonomously. If only one instance of the algorithm is being executed, the algorithm will force the minimal number of additional processes other than the initiator to make checkpoints (or roll back). The contributions of this research are as follows: (1) the concurrent execution of the algorithm for different global checkpointing instances and rollback instances initiated by several processes is allowed. Deadlocks or livelocks among different global checkpointing instances and rollback instances will not occur; (2) the algorithm is resilient to multiple process failures, and handles network partitioning in a pessimistic way, and (3) the algorithm does not require that messages be received in the order in which they are sent.>

The authors propose a formal definition of the two-phase locking class derived from the semantic description of the two-phase locking protocol, and prove that this definition is equivalent to that given by C.H. Papadimitriou (1979). They present: (1) a precise definition of the two phase locking; (2) a clarification of the occurrence and the order of all events such as lock points, unlock points, read operations, and write operations of conflicting transactions; and (3) by relaxing some conditions in the given definition, the derivation of a new class called restricted-non-two-phase locking (RN2PL), which is a superset of the class two-phase locking (2PL) but a subset of the class D-serializable (DSR) given by Papadimitriou.>

We propose multidimensional timestamp protocols for concurrency control in database systems where each transaction is assigned a timestamp vector containing multiple elements. The timestamp vectors for two transactions can be equal if timestamp elements are assigned the same values. The serializability order among the transactions is determined by a topological sort of the corresponding timestamp vectors. The timestamp in our protocols is assigned dynamically and is not just based on the starting/finishing time as in conservative and optimistic timestamp methods. The concurrency control can be enforced based on more precise dependency information derived dynamically from the operations of the transactions. Several classes of logs have been identified based on the degree of concurrency or the number of logs accepted by a concurrency controller. The class recognized by our protocols is within D-serializable (DSR), and is different from all previously known classes such as two phase locking (2PL), strictly serializable (SSR), timestamp ordering (TO), which have been defined in literature. The protocols have been analyzed to study the complexity of recognition of logs. We briefly discuss the implementation of the concurrency control algorithm for the new class, and give a timestamp vector processing mechanism. The extension of the protocols for nested transaction and distributed database models has also been included.

We propose multidimensional timestamp protocols where each transaction has a timestamp vector of multiple elements. The timestamp vectors need not be distinct but do define a partial order. The serializability order among the transactions is determined by any topological sort of their timestamp vectors. The timestamp in our protocols is constructed dynamically, not just based on the starting/finishing time as in conservative and optimistic timestamp methods, and thus the concurrency control can be enforced based on more precise dependency information derived from the operations of the transactions. Several classes of logs have been identified based on the degree of concurrency which represents the number of logs accepted by a concurrency controller [12]. The class for our protocols is different from any previously known classes such as two phase locking (2PL), D-serializable (DSR), strictly serializable (SSR), timestamp ordering (TO), which have been defined in [5, 9, 12, 13]. If the dimension of the timestamp vector is one, then our protocols recognize the class timestamp ordering (TO). We will briefly discuss the implementation of the concurrency control algorithm for the new class.