The store-and-forward deadlock problem in packet switching networks is considered. Most of the previous work addressed this issue using reserved buffers, and most algorithms, with the exception of that given by J. Blazewicz et al. (1987) (the BBG algorithm), use more reserved buffers than necessary, implying that each node does not have the maximum flexibility in message routing. It is shown that the BBG deadlock prevention algorithm can generate an unbounded number of backtracked messages. A deadlock detection and resolution algorithm that allows a minimum number of buffers to be reserved and minimizes the number of backtracked messages at the end of each detection and resolution is presented. It is shown that in the worst case, only O( mod E mod ) backtracked messages can be generated as a result of this algorithm, and that each backtracked message is backtracked only one hop.>

Resolving a deadlock in a computer system involves choosing processes to terminate or roll back so that the deadlock is eliminated. It is widely known that the problem of finding the minimum number of processes to abort is NP-complete. Two polynomial-time heuristics to resolve deadlocks, the edge cycle method and a method based on enumerating the cycles in the wait-for-graph, are discussed. Simulation results are presented that show these heuristics perform better than several previously reported heuristics.>

The problem of conducting a global survey in faulty networks is studied. The global survey problem (GSP) can be considered as an extension of that of network broadcasting. It is shown that the time complexity lower bound for the GSP is Omega ( mod V mod ) and the message complexity is Omega min( mod V mod ,k) mod V where k is the number of links failed. While there is a straightforward protocol to achieve the time complexity lower bounds, the design of message-optimal protocols is rather complex. This work provides such a protocol.>

The problem of nonpreemptively scheduling a set of m partially ordered tasks on n identical processors subject to interprocessor communication delays is studied in an effort to minimize the makespan. A new heuristic, called Earliest Task First (ETF), is designed and analyzed. It is shown that the makespan $\omega _{{\text{ETF}}} $ generated by ETF always satisfies $\omega _{{\text{ETF}}} \leqq ({{2 - 1} / n})\omega _{{\text{opt}}}^{(i)} + C$, where $\omega _{{\text{opt}}}^{(i)} $ is the optimal makespan without considering communication delays and C is the communication requirements over some immediate predecessor-immediate successor pairs along one chain. An algorithm is also provided to calculate C. The time complexity of Algorithm ETF is $O(nm^2 )$.

The speedup issue is reexamined for message-passing multiprocessors and computer networks in which interprocessor communication overhead is considered undesirable but significant. A unified model of speedup ) is developed for analyzing the system in terms of communication overhead, scheduling, and the application algorithm. The model can be used to assess quantitatively the impact on overall system performance of the interprocessor communication overhead and its interaction with different scheduling methods. Whereas most authors treat speedup as a measure of improved algorithms or improved systems, the presented model integrates the effects of these factors and of scheduling. Two concepts, hidden overhead and efficiency loss, are introduced to clarify the effect of the scheduling factor. The concepts are illustrated using two scheduling methods designed for use in systems with significant communication overhead.>

A description is given of a Petri-net-based methodology for modeling and evaluation of pipelined processing of concurrent database queries in an integrated data network (IDN). An extended Petri-net model is presented and used to model two key approaches to concurrent database query processing in the IDN, namely, pipelined and data-flow-based execution of queries and intermediate data sharing among concurrent queries. Database operations are categorized, and the models for the data flow and control flow in them are presented. A general-purpose Petri-net simulator has been developed using event-driven programming techniques and used to simulate the execution of the Petri-net models of some test queries. The results validate the results of a previous analytical evaluation in which the advantages of pipeline and intermediate data sharing were established. Since all the essential details of query processing in the IDN have been simulated, the results of this simulation study are believed to present closely the workings of the actual system.>

This paper presents a detailed analysis of a sampling approach used in the partitioning of a data file for the parallel balanced tree sort in a local area network or a multiprocessor environment. The average overall time complexity for sorting N data on a k processor system is derived. The performance of the parallel sorting rests upon how evenly the file can be partitioned into k ordered subfiles. A data partition scheme by sampling is proposed and analyzed. Formulas for computing the optimal sampling size are obtained. The results also show the computational improvement of the sorting as a function of k and the sampling overhead. The performance of the sampling method is studied and found to be approaching the absolute optimal in some cases.

The future data systems are likely to be integrated data networks (IDNs) consisting of a mix of general-purpose computer systems and special-purpose functional processors that are produced by different vendors and have quite different computational power and database management capabilities. Data stored in these networks need to be integrated and shared by the network users. It is important to have a query processing strategy in this type of network that can take advantage of the diverse functional capabilities of the component systems and the parallel processing potential of the network. In this paper, we present a query processing strategy which combines three known techniques: 1) query decomposition, 2) pipelined and data-flow processing of queries, and 3) intermediate result sharing among concurrent queries. The strategies for controlling and managing query and data pipelines are presented. Algorithms for the pipelined execution of the relational join operation are also described. Selected results of the evaluation of the query processing strategy, pipeline control strategies, and parallel algorithms are presented.

A classification method for parallel sorting architectures is presented for comparison of existing designs. Some common drawbacks of these parallel sorters are noted: in general, they are limited by their data accessing mechanism, their hardware utilization is low, and their sorting speed is in some sense independent of the number of sorting elements used in the architecture. In this paper we present a detailed design and analysis of distributor based sorters (parallel balanced tree sorters) which can sort lists whose size is proportional to the memory space available and whose speed is proportional to the number of sorting elements used.

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.