The problem of elaborating the specification for the submodules of a system is considered.A new method for the construction of submodule specifications is described.If the system is to consist of n submodules and the system as well as (n -1) submodules are specified, then the method described determines the specification of the additional nth submodule.A formula is given which defines the specification of the additional submodule in the general case where module specifications are given in terms of sets of possible execution sequences, and interaction occurs when several modules participate in the execution of an atomic interaction.For the restricted context of finite-state machines, a constructive algorithm for the evaluation of the formula is given.The use of this design method is demonstrated by examples, including a simple communication protocol involving error detection and retransmission.Possible applications in other areas, as well as remaining problems, are indicated.

Abstract This paper is concerned with the problem of defining K multiple paths between pairs of nodes in a network. The treatment presented here is on a theoretical level, although the problem is motivated by a practical scheme for message routing in store‐and‐forward packet switched computer networks. Theorems are presented which offer readily testable sufficient conditions on the topology of a network which guarantee the existence of at least one set of paths under consideration. The proof of this theorem provides a generalized systematic method for constructing these paths if the sufficient conditions are met.

Store-and-forward deadlock in store-and-forward networks may be avoided by forwarding messages from buffer to buffer in accordance with a loop-free directed buffer graph which accommodates all the desired message routes. Schemes for designing such buffer graphs are presented, together with methods for using them to forward the messages in an efficient and deadlock-free manner. These methods can be implemented by a set of counters at each node. Such an implementation increases the efficiency of buffer use, and simplifies jumping between normal lowoverhead operation when deadlock is far and more careful operation when deadlock is near. The proposed deadlock avoidance mechanism works for any network topology and any finite routing algorithm.

This paper describes the construction of loop-free buffer graphs which avoid four types of buffer deadlocks in store-and-forward networks. 1) Progeny deadlock, where original messages spawnother ones, and buffer contention occurs between the original and progeny messages. This occurs when positive or negative acknowledgments are created, e.g., if messages reverse direction after encountering a path failure. 2) Copy-release deadlock, where a message copy is stored at the source node and the buffer is not released until an acknowledgment is received from the destination node. Buffer contention may arise among the original messages, stored copies, and acknowledgments. 3) Pacing deadlock, where a local flow control protocol is used between a network node and attached terminals. Buffer contention may arise between the message flows into and out of the terminal, preventing the transmission of go-ahead commands. 4) Reassembly deadlock, whereby reassembly of packetized messages at the destination node cannot be completed. The solution presented here has the novel features of not requiring preallocation of reassembly buffers before transmission of multiple packets of a multipacket message, and not requiring dedication of buffer space at intermediate nodes for individual messages. These schemes are believed to have modest buffer requirements at each node, and if adequate buffer pools are provided, will incur negligible performance degradations under normal conditions, with overhead increasing under heavy buffer usage when deadlock is near.

Complex protocols are used to coordinate remote activities in computer networks. To insure proper operation, formal techniques of protocol definition and validation have been proposed, and developed to the point that they can be applied to actual protocols. However, much work remains to be done in order to cope with protocols of ever-increasing complexity; in particular, those coordinating the activities of many interacting entities. The characteristics that determine the applicability of the different specification and validation techniques to a protocol will be discussed. We will define the "topology" of a protocol, and treat also protocols that are intended to work in a variety of configurations, as well as configurations which may change in time (i.e. "evolving topologies"). Finally, based on this new general point of view, a short survey of specification and validation techniques will be presented, and the extensions needed to handle complex protocol characteristics will be discussed.

An algorithm for constructing and adaptively maintaining routing tables in communication networks is presented. The algorithm can be employed in message as well as circuit switching networks, uses distributed computation, provides routing tables that are loop-free for each destination at all times, adapts to changes in network flows, and is completely failsafe. The latter means that after arbitrary failures and additions, the network recovers in finite time in the sense of providing routing paths between all physically connected nodes. For each destination, the routes are independently updated by an update cycle triggered by the destination.

We define the class of conjunctive queries in relational data bases, and the generalized join operator on relations. The generalized join plays an important part in answering conjunctive queries, and it can be implemented using matrix multiplication. It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal. The main lemma used to show this is that each conjunctive query has a unique minimal equivalent query (much like minimal finite automata).

This paper presents a coherent method which permits the specification, check out, and implementation of communication protocols. Although this work is mainly directed towards telephone signaling in a programmable environment, the philosophy and most of the tools can be effectively used to handle the most general situations in which two entities interact by any kind of protocol. Since the proposed approach reduces the possibility of errors and inconsistencies, minimizes the programming needed, and improves the documentation and understandability, we believe that this methodology will facilitate the installation or modification of complex trunk protocols and other communication protocols.

A study is presented which permits the formal analysis and synthesis of recoverable computer communication protocols. This study is based on a formal representation of processes by a model of computation, the Petri nets (PN's). The PN model is generalized to include a representation of the possible failures, and then, the concept of "recoverability" is formally defined. A set of necessary and sufficient conditions which a process must satisfy in order to be recoverable is derived. In the PN model, the processes that satisfy these conditions are shown to have some practical limitations. A new model, the time-Petri net (TPN), is introduced to remove these limitations. This new model allows the introduction of constraints in the execution times of its part. As shown in this paper, the TPN appears to be a suitable model for the study of practical recoverable processes. Several practical communication protocols are formally designed and analyzed using this new model, and some interesting properties of these protocols are formally derived.

In Hough [1], Duda and Hart [2], and Griffith [3] procedures were proposed for detecting lines in pictures and in [2] Duda and Hart extended their method for more general algebraic curve, fitting. This correspondence shows how this method can be used to detect any given curve in a specific orientation. The procedure presented here con be easily implemented and can be efficiently implemented in a parallel machine.