The paper presents a probabilistic performance analysis of a deadlock detection algorithm in distributed systems. Although there has been extensive study on deadlock detection algorithms in distributed systems, little attention has been paid to the study of the performance of these algorithms. Most work on performance study has been achieved through simulation but not through an analytic model. Min (1990), to the best of our knowledge, made the sole attempt to evaluate the performance of distributed deadlock detection algorithms analytically. Being different from Min's, our analytic approach takes the time-dependent behavior of each process into consideration rather than simply taking the mean-value estimation. Furthermore, the relation among the times when deadlocked processes become blocked is studied, which enhances the accuracy of the analysis. We measure performance metrics such as duration of deadlock, the number of algorithm invocations, and the mean waiting time of a blocked process. It is shown that the analytic estimates are nearly consistent with simulation results.

We propose a multidatabase transaction management scheme using the flexible transaction model. In our approach, global subtransactions can be committed unilaterally at local sites before the global commit. Since such executions may not guarantee the traditional atomicity requirement of global transactions, a new correctness criterion is proposed. We also present a semantics-based concurrency control scheme and a commit protocol which ensure the proposed correctness criterion without requiring local DBMSs to provide prepare-to-commit operations.

We propose a distributed deadlock detection algorithm which detects cycles made of back edges in a distributed search tree. Our algorithm detects the deadlocks in which the initiator of the algorithm is directly or indirectly involved, while most of the proposed deadlock detection algorithms only detect the cycles in which the initiator is directly involved. Our algorithm is a reduced version of the one proposed previously, which resolves all deadlocks reachable from the initiator in a single execution by propagating the probe messages to the nodes in the search tree and having each node resolve deadlocks in its subtree with collected information on dependency between its subtree nodes. Our algorithm substantially reduces the message overhead of the previous algorithm. We compare the performance of our algorithm with others through extensive simulation. It is found that our algorithm detects deadlocks as fast as the previous algorithm with much fewer messages. The simulation results show that our algorithm outperforms other algorithms considerably in major performance measures.

This paper presents a checkpointing recovery scheme which effectively copes with media failures in distributed database systems, under the two-phase locking policy. Our scheme utilizes both the current database area and the checkpoint area, so that the transactions whose effects are to be included in the checkpoint and the ones whose effects are to be excluded from the checkpoint can separately reflect their effects. Hence, the check pointing process under our scheme is executed concurrently with normal transactions, without aborting or delaying any of them. Unlike the existing schemes, each data item needs to be read at most once for checkpointing without the maintenance of the before-images of the data items.>

This paper analyzes a load-balancing scheme, called All-Sharing Load Balancing (ASLB), which evenly distributes the load of the system among all nodes on a CSMA/CD local area network in a collision-free manner for each load-balancing activity. A novel analytical model is presented to evaluate performance of the ASLB scheme and its effect on the normal communication message transmission and vice versa. The evaluation also takes into account the tradeoff between system response time and message delay. Our analysis shows that ASLB can achieve good performance in both system response time and message transmission delay. Our analysis techniques are applicable to various distributed algorithms involved with interprocess coordination.

A large-scale distributed computing system architecture for the area-wide real-time traffic control system (ARTC) of J.L. Kim et al. (1992) is presented. In the ARTC system, signal controllers coordinate with each other through the communications network to achieve real-time adaptive traffic control. For reliable service, the ARTC system is designed to be fault-tolerant at the I/O component, processor, and network levels. A modular system architecture that enables the ARTC signal controllers to support fault-tolerant design strategies is proposed. A flexible cost-effective networking strategy is presented to support different level network redundancy. In order to estimate the expected service quality of the ARTC control system and to study the reliability effects of signal controller failure rate, the repair efficiency, and the degree of system redundancy, an analytical model is developed.>

The authors present an efficient synchronized checkpointing protocol that exploits the dependency relation between processes in distributed systems. In this protocol, a process takes a checkpoint when it knows that all processes on which it computationally depends took their checkpoints, hence the process need not always wait for the decision made by the checkpointing coordinator as in the conventional synchronized protocols. As a result, the checkpointing coordination time is substantially reduced and the possibility of total abort of the checkpointing coordination is reduced.>

The authors present an efficient software application of a distributed system for area-wide traffic control. This system, called area-wide real-time traffic control (ARTC), can provide orderly movement of traffic, shorten average vehicle delay, prevent congestion, and improve road utilization. The signal controllers in ARTC, which are microcomputers, are interconnected through a computer network. By exchanging traffic flow information among the signal controllers, ARTC provides a novel concept in traffic control by using the computer network. Simulation results of the ARTC prototype control algorithm are presented. The results show substantial improvement over an optimized fixer time control. The signal controllers and the computer network were designed to support real-time communication requirements and a sufficient level of fault tolerance.>

A protocol for dynamic load balancing in distributed systems on the CSMA/CD local area network is presented. Using the protocol, the workload is evenly distributed throughout the system when load-balancing activity is triggered, and effective load distribution is accomplished through transmission of load-balancing messages in a collision-free manner. Analytical and simulation results are presented to show the efficiency of the protocol.>

The authors present an election protocol that does not assume an underlying ring structure and that tolerates failures, including lost messages and network partitioning, during the execution of the protocol itself. The major problem to be solved is that when nodes cannot communicate with one another or messages are lost, a conflict in resolving the election will often arise. In the authors' approach, the conflict is detected by the cohorts (noncandidate participants in the election). Related election protocols are discussed, and the system model is described together with assumptions about the communication subsystem. The protocol and the lost-message situations are then examined.>