Search

A computer aid for the specification and analysis of computer communication protocols has been developed over a period of 7 years by the Telecom Australia Research Laboratories. It is based on a formal specification technique called Numerical Petri Nets. The computer aid, known as PROTEAN (PROTocol Emulation and Analysis), provides both graphical (color) and textual interfaces to the protocol designer. Numerical Petri Net (NPN) specifications may be created, stored, appended to other NPNs, structured, edited, listed, displayed, and analyzed. Interactive simulation, exhaustive reachability analysis, and several directed graph analysis facilities are provided. Reachability graphs can be automatically laid out and displayed. PROTEAN determines liveness (dead code, deadlocks, and livelocks) from the reachability graph and its strongly connected components. Language analysis, involving the automatic reduction of reachability graphs to language graphs, can be used to study sequences of key system events. This allows a protocol to be compared with its service specification. Elementary cycles of graphs can be generated, allowing interesting cycles to be highlighted on reachability and language graphs. Facilities are provided for debugging the specification, once a problem with the protocol has been discovered. They allow sequences of events, which lead to the undesired behavior, to be traced. The paper commences with a comparison of specification languages, concentrating on extended finite state machines and high-level Petri nets. NPNs and PROTEAN's facilities are then described and illustrated with a simple example. The application of PROTEAN to complex examples is mentioned briefly. A discussion of the approach, its limitations and future work is presented in the context of other developments reported in the literature. Work towards a comprehensive Protocol Engineering Workstation is also discussed. [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]

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]