This paper addresses the problem of finding safe paths through a network, some of whose nodes may be faulty. By a safe path we mean one between two nodes that does not contain any faulty node. The kinds of faults that concern us are not limited to those that may cause a failure of a node or link, but include those that may cause a node to distort messages in arbitrary ways. Furthermore, we want a distributed algorithm to allow the network itself to discover suitable paths without depending on a central controller for the analysis. More broadly, we assume that each node has only local knowledge of the network structure.

Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system.This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city.Communicating only by messenger, the generals must agree upon a common battle plan.However, one or more of them may be traitors who will try to confuse the others.The problem is to find an algorithm to ensure that the loyal generals will reach agreement.It is shown that, using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals.With unforgeable written messages, the problem is solvable for any number of generals and possible traitors.Applications of the solutions to reliable computer systems are then discussed.

The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to each other nonfaulty processor. Nonfaulty processors always communicate honestly, whereas faulty processors may lie. The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each nonfaulty processor to infer a value for each other processor. The value inferred for a nonfaulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other nonfaulty processor. It is shown that the problem is solvable for, and only for, n ≥ 3 m + 1, where m is the number of faulty processors and n is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary n ≥ m ≥ 0. This weaker assumption can be approximated in practice using cryptographic methods.

A laboratory system for studying the design of knowledge-based systems to support a manager in the development and execution of operational plans is described. The system, called ACS.1 for Automated Command Support, operates in the simulated environment of a naval air squadron, but the techniques used are believed applicable to a wide spectrum of environments requiring the planning of operations, the administration and monitoring of approved plans, and the retrospectrive analysis of completed operations. The development of ACS.1 has shown that the concept is feasible and has included the development of programming techniques to support it. The design of ACS.1 is predicated on the importance of system flexibility. This quality is considered essential to permit incremental growth of the system, to facilitate its adaptation to a changing environment or to new requirements, and to enable the manager to intervene in exceptional situations. Much of the design of ACS.1 was chosen to provide flexibility. As viewed from the top level, ACS.1 is highly modular, with coordination being achieved through a process of negotiation carried on via messages. The manager can intervene in this process in a central switching unit called the message handler. He can, for example, direct that certain messages be rerouted to new modules or to the terminal. This is a useful capability, facilitating the orderly incremental growth of the system, as well as permitting alteration of the system's behavior in preplanned ways to meet particular needs.

The inversion of nonsingular matrices is considered. A method is developed which starts with an arbitrary partitioning of the given matrix. The separate submatrices are grouped into sets determined by the nonzero entries of some appropriate group, G , of permutation matrices. The group structure of G then establishes a sequence of operations on these sets of submatrices from which the corresponding representation of the inverse is obtained. Whether the method described is to be preferred to, say, Gauss's algorithm will depend on the capabilities that are required by other parts of the algorithm that is to be implemented in the special-purpose parallel computer. The basic speed, measured by the count of parallel multiplications and divisions, is comparable to that obtained with Gauss's algorithm and is slightly better under certain conditions. The principal difference is that this method uses primarily matrix multiplication, whereas Gauss's algorithm uses primarily row combinations. When the special-purpose computer under design must supply this capability anyway, the method developed here should be considered. Application of the process is limited to matrices for which we can set up a partitioning such that we can guarantee, a priori, that certain of the submatrices are nonsingular. Hence the method is not useful for arbitrary nonsingular matrices. However, it can be applied to certain important classes of matrices, notably those that are “dominated by the diagonal.” Noise covariance matrices are of this type; therefore the method can be applied to them. The inversion of a noise covariance matrix is required in some problems of optimal prediction and control. It is for applications of this sort that the method seems particularly attractive.

AnSTRACT.The organization of a special purpose processor for computing the Fourier transform of a data set of N = 2 ~ complex numbers is considered.A limited amount of parallel computation facility is assumed, and organizations are sought that make efficient use of the available parallel capacity and can use memories of limited speed and therefore of relatively low cost.The proposed organization not only accomplishes this but also can be programmed, without loss of speed, to deliver the computed spectra in proper order.In addition, it is adapted to the handling of very large data bases on a continuous production basis, where the rate of flow of data is too great for serial processing.

A modified version of the Fast Fourier Transform is developed and described. This version is well adapted for use in a special-purpose computer designed for the purpose. It is shown that only three operators are needed. One operator replaces successive pairs of data points by their sums and differences. The second operator performs a fixed permutation which is an ideal shuffle of the data. The third operator permits the multiplication of a selected subset of the data by a common complex multiplier. If, as seems reasonable, the slowest operation is the complex multiplications required, then, for reasonably sized date sets—e.g. 512 complex numbers—parallelization by the method developed should allow an increase of speed over the serial use of the Fast Fourier Transform by about two orders of magnitude. It is suggested that a machine to realize the speed improvement indicated is quite feasible. The analysis is based on the use of the Kronecker product of matrices. It is suggested that this form is of general use in the development and classification of various modifications and extensions of the algorithm.

Two general methods of matrix inversion, Gauss's algorithm and the method of bordering, are analyzed from the viewpoint of their adaptability for parallel computation. The analysis is not based on any specific type of parallel processor; its purpose is rather to see if parallel capabilities could be used effectively in matrix inversion. It is shown that both methods are indeed able to make effective use of parallel capability. With reasonable assumptions on the parallelism that is available, the speeds of the two methods are roughly comparable. The two methods, however, make use of different kinds of parallelism. To implement Gauss's algorithm we would like to have (a) parallel transfer capability for n numbers, if the matrix is n X n , (b) the capability for parallel multiplication of the accessed numbers by a common multiplier, and (c) parallel additive read-in capability. For the method of bordering, we need, primarily, the capability of forming the Euclidean inner product of two n -dimensional real vectors. The latter seems somewhat harder to implement, but, because it is an operation that is fundamental to linear algebra in general, it is one that might be made available for other purposes. If so, then the method of bordering becomes of interest.