A modified, priority-based probe algorithm for deadlock detection and resolution in distributed database system is presented. Various examples are used to show that the original priority-based algorithm, presented by M.K. Sinha and N. Natarajan (1985), either fails to detect deadlocks or reports deadlocks that do not exist in many situations. A modified algorithm that eliminates these problems is proposed. The algorithm has been tested through simulation and appears to be errorfree. The performance of the modified algorithm is briefly discussed.>

A line inadvertently omitted from a section of the pseudocode in the above paper (see ibid., vol.15, no.1, p.10-17, 1989) is provided. The correct reading of the section is given in full.>

The authors use a mean value model for data contention and a piecewise linear model for resource contention. To show the usefulness of this methodology, they compare three different optimistic concurrency control protocols for a centralized system. The authors derive a closed-form expression for the transaction throughput as a function of workload parameters and the resource-access-time parameters. The resource-access-time parameters can be derived using a simple analytical model. The closed-form expressions are very useful as a quick evaluation of different protocols and to gain insight about protocol performance over a wide range of model parameters. They also yield a simple asymptotic analysis of the optimistic concurrency control protocols. The authors apply the methodology to predict the performance of a testbed database system.>

A queuing network model for analyzing the performance of a distributed database testbed system with a transaction workload is developed. The model includes the effects of the concurrency control protocol (two-phase locking with distributed deadlock detection), the transaction recovery protocol (write-ahead logging of before-images), and the commit protocol (centralized two-phase commit) used in the testbed system. The queuing model differs from previous analytical models in three major aspects. First, it is a model for a distributed transaction processing system. Second, it is more general and integrated than previous analytical models. Finally, it reflects a functioning distributed database testbed system and is validated against performance measurements.>

A queueing network model to analyze the performance of a distributed database testbed system is developed and validated against empirical measurements. The model includes the effects of the concurrency control protocol (two-phase locking with distributed deadlock detection), the transaction recovery protocol (write-ahead-logging of before-images), and the commit protocol (centralized two-phase commit) used in the testbed system. The queueing model differs from previous analytical models in three major aspects. First, it is a model for a distributed transaction processing system. Second, it is more general and integrated than previous analytical models. Finally, it reflects a functioning distributed database testbed system and is validated against performance measurements.

In this paper we discuss the issues involved in debugging a provide distributed computing system. We describe the major differences between debugging a distributed system and debugging a sequential program. We suggest a methodology for distributed debugging, and we propose various tools or aids.

Multiuser transaction processing and database systems commonly use well-formed, two-phase locking to maintain data consistency. The preliminary results presented here represent the first step of an experimental investigation of the impact of different locking schemes on transaction performance. Tests were performed using a simplified but functionally complete testbed system. The transaction throughput rates for three different locking policies (file level locking, page level locking, and mixed level locking) are compared as a function of the lock mode (exclusive or share) and the file size for a small centralized database application. The experimental results for this environment show that the choice of locking policy and lock mode can have a significant impact on transaction throughput performance. The tests also demonstrate the sensitivity of the conclusions to the choice of workload and system characteristics.

Queueing models for a simple heterogeneous multiple processor system are presented, analyzed, and compared. Each model is distinguished by a job routing strategy which is designed to reduce the average job turnaround time by balancing the total load among the processors. In each case an arriving job is routed by a job dispatcher to one of m parallel processors. The job routing strategies are divided into two classes: deterministic and nondeterministic. The nondeterministic policies are described by state independent branching probabilities. For the deterministic policies, the next processor is chosen to minimize or maximize the expected value of a performance related criterion function.

Improved exact and approximate algorithms for the n-job two-machine mean finishing time flow-shop problem, n/2JF/P, are presented While other researchers have used a variety of approximate methods to generate suboptimal solutions and branch-and-bound algorithms to generate exact solutmns to sequencing problems, thin work demonstrates the computatmnal effectiveness of couphng the two methods to generate solutmns with a guaranteed accuracy.The computational reqmrements of exact, approximate, and guaranteed accuracy algorithms are compared expemmentally on a set of test problems ranging in size from 10 to 50 jobs The approach is readily apphcable to other sequencing problems

The problem of scheduling tasks on a system of independent identical processors is discussed and the performance of a suboptimal method is evaluated. The computation is modeled by an acyclic directed graph G(T,<), where node set T represents the set of tasks to be completed and edge set < defines the precedence between tasks. The objective is to minimize the finishing time of the computation graph. Known theoretical results are reviewed and a general branch-and-bound algorithm for finding optimal solutions is presented. The schedules produced by a simple critical path priority method are shown to be near optimal for randomly generated computation graphs.

Branch-and-bound implicit enumeration algorithms for permutation problems (discrete optimization problems where the set of feasible solutions is the permutation group S n ) are characterized in terms of a sextuple ( B p S,E,D,L,U ), where (1) B p is the branching rule for permutation problems, (2) S is the next node selection rule, (3) E is the set of node elimination rules, (4) D is the node dominance function, (5) L is the node lower-bound cost function, and (6) U is an upper-bound solution cost. A general algorithm based on this characterization is presented and the dependence of the computational requirements on the choice of algorithm parameters, S, E, D, L, and U is investigated theoretically. The results verify some intuitive notions but disprove others.