In this paper, we present an extension to Kerry Raymond's tree based distributed mutual exclusion algorithm to make it fault tolerant. The algorithm uses a spanning tree of a computer network. With N nodes in the network the number of messages exchanged per critical section entry is typically O(log N). The novelty of the algorithm lies in each node holding information only about its immediate neighbors in the spanning tree. We basically present a protocol to make the algorithm tolerant to single node/link failure and associated network partition. This protocol assumes that the graph of the underlying network is biconnected. Basically we attempt reconfiguration of the tree after isolating the failed components. With this enhancement a significant number of cases in which the algorithm would have halted due to lack of communication paths, can be effectively handled by utilizing alternative communication paths now available, thus continuing to provide the mutual exclusion service.

Architectural level design and synthesis requires a versatile library support system. Such a system must have provisions for organizing abstract models in a hierarchical manner as well as retrieval and storage of components in an object-oriented manner. Common relations between models can then be captured and different library models substituted and reused within the environment. An example of the capabilities of the library system for DASE is also provided.>

For distributed problem solving systems, there is a need to define knowledge at two levels, one external to the agents and the other internal to the agents. External knowledge is required to achieve cooperation among agents and global convergence of the problem solving process, whereas internal knowledge is required to solve the sub-problems assigned to the agents. External knowledge specifies the role of each agent and its relationship with other agents in the system. Internal knowledge specifies knowledge structure and the problem solving process within each agent. DKRL is an object-oriented language for describing distributed blackboard systems. In DKRL a problem solving system is described as a collection of distributed intelligent, autonomous agents (modelled as objects), cooperating to solve the problem. An agent consists of a knowledge base, a behaviour part, a local controller, a monitor, and a communication controller. DKRL has characteristics of a dynamic nature, i.e. the agents can be created dynamically and the relationship among them also changes dynamically. An agent in DKRL’s computational model cannot be activated by more than one message at the same time and uses a virtual synchrony environment for message transmission among agents. This model combines the advantages of remote procedure calls with those of asynchronous message passing. DKRL allows object-oriented programming techniques to be used for system development and facilitates the development by allowing one-to-one mapping between the objects in the knowledge model and the knowledge base of the agent. In this paper, we give an overview of the distributed blackboard paradigm for which DKRL was developed as well as the design considerations. We also propose and formally describe the underlying models of DKRL and explain how concurrency is exploited by DKRL. We conclude with the current status of and preliminary experience with DKRL in using it for the development of a gate assignment problem.

A framework for system level synthesis is presented, and a suitable language, DSL, for capturing design specifications and generating control graphs amiable to synthesis is proposed. The three stages in the synthesis process-design specification, intermediate representation, and synthesis-are examined in detail. A rough version of the language is used to model a simple system.>

An algorithm with worst case time complexity O(log/sup 2/N) in two dimensions and O(m/sup 1/2/log N) in three dimensions with N input points and m as the number of tetrahedra in triangulation is given. Its AT/sup 2/ VLSI complexity on Thompson's logarithmic delay model, (1983) is O(N/sup 2/log/sup 6/N) in two dimensions and O(m/sup 2/Nlog/sup 4/ N) in three dimensions.>

In this paper we describe two interconnection networks for parallel processing, namely the orthogonal trees network and the orthogonal tree cycles (OTN and OTC). Both networks are suitable for VISI implementation and have been analyzed using Thompson's model of VLSI. While the OTN and OTC have time performances similar to fast networks such as the perfect shuffle network (PSN), the cube comnected cycles (CCC), etc., they have substantially better area * time2 performances for a number of matrix and graph problems. For instance, the connected components and a minimal spanning tree of an undirected N-vertex graph can be found in 0(log4 N) time on the OTC with an area * time2 performance of 0(N2 log8 N) and 0(N2 log9 N) respectively. This is asymptoticaly much better than the performances of the CCC, PSN and Mesh. The OTC and OTN can be looked upon as general purpose parallel processors since a number of other problems such as sorting and DFT can be solved on them with an area * time2 performance matching that of other networks. Finally, programming the OTN and OTC is simple and they are also amenable to pipelining a series of problems.

We present a language RACHNA, which in our opinion, can form the basis of a CAD system. In RACHNA various hardware features like - asynchronism, parallelism, pipelining, timing and delays etc. can be described in a procedural frame-work. A number of control constructs have been provided, which can be suitably nested. It allows a designer to include structural information also, giving him a better control over the final hardware realization. A design can be evolved in a top-down manner by defining subsystems as Processes, Modules and Functions. RACHNA is associated with an interpreted graph model, which defines its semantics and is useful for simulation and logic synthesis.

Some comments are offered on the number of I/O terminals p of the Q-universal logic modules (ULM) [2]. An equation is given in this note which will determine minimum number of I/O terminals for all n.

In this correspondence a new representation of a sequential machine (without output) is given which enables the determination of all incompatible pairs without any intermediate step(s). The method is programmable, is much faster, and requires less memory than existing methods.