Iterative-deepening searches mimic a breadth-first node expansion with a series of depth-first searches that operate with successively extended search horizons. They have been proposed as a simple way to reduce the space complexity of best-first searches like A* from exponential to linear in the search depth. But there is more to iterative-deepening than just a reduction of storage space. As the authors show, the search efficiency can be greatly improved by exploiting previously gained node information. The information management techniques considered here owe much to their counterparts from the domain of two-player games, namely the use of fast-execution memory functions to guide the search. The authors' methods not only save node expansions, but are also faster and easier to implement than previous proposals.>

Abstract Although both shared memory and loosely coupled parallel computing systems are now common, many still do not offer an easy way to design, implement, and test parallel algorithms. Our system provides software tools that make possible a variety of connection structures between processes. These structures are said to form a 'Network Multi‐Processor', which is implemented on a local area network of heterogeneous UNIX‐based timesharing computers, plus a set of processor boards dedicated to an application so that accurate timing measurements can be made. We explain how these tools have been used both to aid parallel algorithm development and to explore the properties of different computer interconnection methods.

The design issues affecting a parallel implementation of the alpha-beta search algorithm are discussed with emphasis on a tree decomposition scheme that is intended for use on well ordered trees. In particular, the principal variation splitting method has been implemented, and experimental results are presented which show how such refinements as progressive deepening, narrow window searching, and the use of memory tables affect the performance of multiprocessor based chess playing programs. When dealing with parallel processing systems, communication delays are perhaps the greatest source of lost time. Therefore, an implementation of our tree decomposition based algorithm is presented, one that operates with a modest amount of message passing within a network of processors. Since our system has low search overhead, the principal basis for comparison is the communication overhead, which in turn is shown to have two components.

Abstract Experience with a technique for compiling subsets of the procedural elements of AlgolW programs is described. The method does not require modifications to the compiler, but does presume the existence of a random access file system. Complete management of the user's source and object files is provided by supplementary directory and environment files. Because of its nature, the basic method should be equally applicable to other block‐structured languages, such as Pascal, which also require recompilation of the whole program whenever a small change is made.

Abstract Details of a computer‐computer communication facility are presented. The primary feature of the system is the use of a single terminal to monitor and control processes on different machines simultaneously, working together on the solution of a common problem. Experience with an application, error handling and maintenance of synchronization are described.

Recovery under a wide spectrum of system mal functions is considered in a distributed database environment. Knowledge of the nature of all the processes that access the data is effectively used to design system recovery protocols for different classes of transactions. A policy for optimal check pointing is derived through the use of a simple model, and an audit trail maintenance policy is outlined. The "domino effect" is modeled, and a rollback algorithm is developed.

A graph-theoretic model is used to represent the process interactions in DDBMS. From this model a general deadlock detection algorithm is derived, with the important feature of significantly reducing the communication requirements that usually follow the invocation of a deadlock detection mechanism. The idea of "on-line" detection of deadlocks in DDBMS is introduced, and an effective algorithm is presented which detects deadlocks without further delay, at the time of making the data resource allocation decision at the concerned installation. Problems and drawbacks involved in earlier attempts to handle deadlocks in distributed DBMS are provided. Several highlights of our proposals are emphasized, and further possibilities of research are identified.

Abstract The development of basic support software for a graphics facility requires extensive programming effort, which is sometimes duplicated when the facility is made available from other languages. This paper explores an alternative, which has the advantages that only a single software package need be built for use by a variety of host languages, and no modification is necessary to their compilers. Fortran, PL/I and Algol W are the example hosts used in the feasibility studies, but the approach can be extended.

The study of minicomputer systems in a laboratory environment has been considered by both Electrical Engineering [1], and Computer Science [2] departments. In a summary of the COSINE Committee report on Digital Laboratories, Booth [1] points out that since minicomputers are becoming an integral part of many industrial systems, it is mandatory that students be made aware of the principles of such systems. Further, Booth suggests that the best way to accomplish this is in a projects-oriented laboratory environment. We certainly agree with his statement that “A successfully completed project thus gives the student a sense of accomplishment that is hard to duplicate in any other educational situation.”