Search

This paper illustrates an application of the system entity structure, a frame-like knowledge representation scheme, to the design of local area networks. An entity structure for a data link layer protocol that unifies many possibilities from the literature is introduced. The main concepts of our design methodology are illustrated using this example entity structure, and the underlying simulation environment is briefly discussed. The methodology aims to facilitate evaluation of a wide family of design alternatives and component combinations. [ABSTRACT FROM AUTHOR]

This paper illustrates an application of the system entity structure, a frame-like knowledge representation scheme, to the design of local area networks. An entity structure for a data link layer protocol that unifies many possibilities from the literature is introduced. The main concepts of our design methodology are illustrated using this example entity structure, and the underlying simulation environment is briefly discussed. The methodology aims to facilitate evaluation of a wide family of design alternatives and component combinations. [ABSTRACT FROM AUTHOR]

The IC* project is an effort to create an environment for the design, specification, and development of complex systems such as communication protocols, parallel machines, and distributed systems. The basis of this work is the IC* model of parallel computation. In this model, a system is specified by a set of invariant expressions which describe its behavior in time. The novel features of the model include temporal and structural constraints, inherent parallelism, explicit modeling of time, nondeterministic evolution, and dynamic activation. The project also includes the construction of a parallel computer specifically designed to support the model of computation. The model of computation, the status of the project, and the user environment are the content of this paper. [ABSTRACT FROM AUTHOR]

In today's distributed computing environment, the coordination of concurrent processes and the coordination of resource sharing are of critical importance. Consequently, much effort has been focused on the modeling of problems of coordination and concurrency. In this paper we describe a software environment (SPANNER) for the specification and analysis of such problems. In the SPANNER environment, one can formally produce a specification of a distributed computing problem, and then verify its "correctness" through reachability analysis and simulation. SPANNER is based on a finite state machine model called the selection/resolution model. We illustrate the capabilities of SPANNER by specifying and analyzing two classical coordination problems: 1) the dining philosophers; and 2) Dijkstra's concurrent programming problem. In addition to discussing these specific problems, our intention is also to focus on some of the more recently implemented capabilities of the SPANNER system such as process types and cluster variables. [ABSTRACT FROM AUTHOR]

Computations of distributed systems are extremely difficult to specify and verify using traditional techniques because the systems are inherently concurrent, asynchronous, and nondeterministic. Furthermore, computing nodes in a distributed system may be highly independent of each other, and the entire system may lack an accurate global clock. In this paper, we develop an event-based model to specify formally the behavior (the external view) and the structure (the internal view) of distributed systems. Both control-related and data-related properties of distributed systems are specified using two fundamental relationships among events: the "precedes" relation, representing time order; and the "enables" relations, representing causality. No assumption about the existence of a global clock is made in the specifications. The specification technique has a rather wide range of applications. Examples from different classes of distributed systems, include communication systems, process control systems, and a distributed prime number generator, are used to demonstrate the power of the technique. The correctness of a design can be proved before implementation by checking the consistency between the behavior specification and the structure specification of a system. Both safety and liveness properties can be specified and verified. Furthermore, since the specification technique defines the orthogonal properties of a system separately, each of them can then be verified independently. Thus, the proof technique avoids the exponential state-explosion problem found in state-machine specification techniques. [ABSTRACT FROM AUTHOR]

Distributed applications written in Hermes typically consist of a large number of sequential processes. The use of a hierarchy of process clusters can facilitate the debugging of such applications. Ideally, such a hierarchy should be derived automatically. This paper discusses two approaches to automatic process clustering, one analyzing runtime information with a statistical approach and one utilizing additional semantic information. Tools realizing these approaches were developed and a quantitative measure to evaluate process clusters is proposed. The results obtained under both approaches are compared, and indicate that the additional semantic information improves the cluster hierarchies derived. We demonstrate the value of automatic process clustering with an example. It is shown how appropriate process clusters reduce the complexity of the understanding process, facilitating program maintenance activities such as debugging. [ABSTRACT FROM AUTHOR]

The hypergeometric distribution model has been proposed for estimating the number of faults initially resident in a program at the beginning of test/debugging process. However, the parameter values of the hypergeometric distribution necessary for making the estimation were previously determined by the three-dimensional exhaustive search and therefore much time was needed to get the numerical result. In this paper, six ways to estimate parameters of the hypergeometric distribution are investigated and their accuracies are examined comparatively. It is demonstrated that the least-squares sum method is the best one among those we tried and can be well applied to real test/debug data for estimating the number of faults still resident in a program after test/debugging. By this method the estimation time can be reduced greatly. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of assigning the modules of a distributed program to the processors of a distributed system. The goal of such an assignment is to minimize the total execution and communication costs. A computational model of a distributed program, containing probabilistic branches and loops, is described using a directed graph whose edges represent precedence relations between modules. Efficient algorithms based on shortest path methods are presented to determine the optimum assignment on a distributed system containing N heterogeneous processors. [ABSTRACT FROM AUTHOR]

A formal semantics of a prototyping language for hard real-time systems, PSDL, is given. PSDL provides a data flow notation augmented by application-orientation timing and control constraints to describe a system as a hierarchy of networks of processing units communicating via data streams. The semantics of PSDL is defined in terms of algebraic high-level Petri nets. This formalism combines algebraic specifications of abstract data types with process and concurrency concepts of Petri nets. Its data abstraction facilities are used to define the meaning of PSDL data types, while high-level Petri nets serve to model the casual and timing behavior of a system. The net model exposes potential concurrency of computation and makes all synchronization needs implied by timing and control constraints explicit and precise. Time is treated as state of clocks, and clocks are modeled as ordinary system components. The net semantics provides the basis for applying analysis techniques and semantic tools available for high-level Petri nets. [ABSTRACT FROM AUTHOR]

We report our experience in developing a simulator, called Véda. Véda is a software tool to support designers in protocol modeling and validation. It is basically oriented towards the rapid prototyping of distributed algorithms, and has been available for more than two years. Algorithms are described using an ISO formal description technique, called Estelle. We first give an external view of Véda, and particularly how one can describe service properties and tracing, using a specific feature of Véda, called observation. Then, the development of Véda and its internal structure is presented, emphasizing the use of Prolog as a software engineering tool. Typical uses of Véda that have been made in the relatively large community of its users are sketched. We conclude with a critical analysis of the main features of Véda and how they may have contributed to its success. [ABSTRACT FROM AUTHOR]

A model for representing and analyzing the design of a distributed software system is presented. The model is based on a modified form of Petri net, and enables one to represent both the structure and the behavior of a distributed software system at a desired level of design. Behavioral properties of the design representation can be verified by translating the modified Petri net into an equivalent ordinary Petri net and then analyzing that resulting Petri net. The model emphasizes the unified representation of control and data flows, partially ordered software components, hierarchical component structure, abstract data types, data objects, local control, and distributed system state. At any design level, the distributed software system is viewed as a collection of software components. Software components are externally described in terms of their input and output control states, abstract data types, data objects, and a set of control and data transfer specifications. They are interconnected through the shared control states and through the shared data objects. A system component can be viewed internally as a collection of subcomponents, local control states, local abstract data types, and local data objects. [ABSTRACT FROM AUTHOR]