Search

Recent advances in technology have made the construction of general-purpose systems out of many small independent microprocessors feasible. One of the issues concerning distributed systems is the question of appropriate language constructs for the handling of communication and synchronization. In his paper, "Communicating sequential processes," Hoare has suggested the use of the input and output constructs and Dijkstra's guarded commands to handle these two issues. This paper examines Hoare's concepts in greater detail by concentrating on the following two issues: 1) allowing both input and output commands to appear in guards, 2) simple abstract implementation of the input and output constructs. In the process of examining these two issues we develop a framework for the design of appropriate communication and synchronization facilities for distributed systems. [ABSTRACT FROM AUTHOR]

A new approach for checkpointing and rollback recovery in a distributed computing system using a common time base is proposed in this paper. First, a common time base is established in the system using a hardware clock synchronization algorithm. This common time base is coupled with the idea of pseudo-recovery points to develop a checkpointing algorithm that has the following advantages: 1) reduced wait for commitment for establishing recovery lines, 2) fewer messages to be exchanged, and 3) less memory requirement. These advantages are assessed quantitatively by developing a probabilistic model. [ABSTRACT FROM AUTHOR]

Basic error recovery problems between interacting processes are first discussed and the desirability of having separate recovery mechanisms for cooperation and competition is demonstrated. The paper then concentrates on recovery mechanisms for processes competing for the use of the shared resources of a computer system. Appropriate programming language features are developed based on the class and inner features of SIMULA, and on the structuring concepts of recovery blocks and monitors. [ABSTRACT FROM AUTHOR]

RELAY is a model of faults and failures that defines failure conditions, which describe test data for which execution will guarantee that a fault originates erroneous behavior that also transfers through computations and information flow until a failure is revealed. This model of fault detection provides a framework within which other testing criteria's capabilities can be evaluated. In this paper, we analyze three test data selection criteria that attempt to detect faults in six fault classes. This analysis shows that none of these criteria is capable of guaranteeing detection for these fault classes and points out two major weaknesses of these criteria. The first weakness is that the criteria do not consider the potential unsatisfiability of their rules; each criterion includes rules that are sufficient to cause potential failures for some fault classes, yet when such rules are unsatisfiable, many faults may remain undetected. Their second weakness is failure to integrate their proposed rules; although a criterion may cause a subexpression to take on an erroneous value, there is no effort made to guarantee that the intermediate values cause observable, erroneous behavior. This paper shows how the RELAY model overcomes these weaknesses. [ABSTRACT FROM AUTHOR]

This paper examines several relations between software testing criteria, exploring whether for each relation R and each pair of criteria, C1 and C2, R(C1, C2) guarantees that C1 is better at detecting faults than C2 according to various probabilistic measures of fault-detecting ability. It is shown that the fact that C1 subsumes C2 does not guarantee that C1 is better at detecting faults. Relations that strengthen the subsumption relation and that have more bearing on fault-detecting ability are introduced. [ABSTRACT FROM AUTHOR]

A basic requirement for communication in a heterogeneous computing environment is a standard external data representation. Abstract Syntax Notation One (ASN.1) has been widely used in international standard specifications; its transfer-syntax, the Basic Encoding Rules (BER), is used as the external data representation. This paper presents a HER implementation called the ED library. The ED library includes a number of encoding and decoding routines that may be used as primitive functions to compose encoders and decoders for arbitrarily complicated ASN.1 data-types. Based on the ED library, an ASN.1-C compiler, called CASN1, is designed and implemented to free the protocol implementors from the arduous work of translating protocol-defined data-types and constructing their encoders and decoders. Given an ASN.1 protocol specification, CASNI automatically translates the input ASN.1 modules into C and generates the BER encoders and decoders for the protocol defined data-types. This paper discusses the CASN1 design principles, user interface, and some example applications. The performance of the ED library and generated CASN1 code is also measured and discussed. [ABSTRACT FROM AUTHOR]

In the area of software development, data processing management often focuses more on coding techniques and system architecture than on how to manage the development. In recent years, "structured programming" and "structured analysis" have received more attention than the techniques software managers employ to manage. Moreover, these coding and architectural considerations are often advanced as the key to a smooth running, well managed project. This paper documents a philosophy for software development and the tools used to support it. Those management techniques deal with quantifying such abstract terms as "productivity," "performance," and "progress," and with measuring these quantities and applying management controls to maximize them. The paper also documents the application of these techniques on a major software development effort. [ABSTRACT FROM AUTHOR]

The properties of a capability-based protection mechanism to be incorporated in a language for concurrent programming axe presented. The protection mechanism is that abstractly characterized in terms of a protection model; the components of the protection mechanism, that is, the objects, subjects, and protection rules which govern the accessing to the objects by the subjects, are defined. The paper then concentrates on appropriate programming language features to specify how the protection mechanism may be embedded in an object-oriented programming language which allows an abstract data-type definition. In particular, it is shown how the protection rules can be implemented in the language so that a completely static access control to objects is obtained. [ABSTRACT FROM AUTHOR]

This paper describes Cola, an object-oriented command language for Hydra; Hydra is a capability-based operating system that runs on C.mmp, a tightly coupled multiprocessor. The two primary aspects of Cola, that it is a command language for Hydra, and that it is based on the object paradigm, are examined. Cola was designed to effect a correspondence between capabilities in Hydra and objects that are supported by the language. Cola is based on Smalltalk in that it uses message-passing as a control structure to allow syntactic freedom in the expression of commands to the system. Cola objects are arranged in a hierarchy, and the message-passing mechanism was designed to exploit this structure by automatically forwarding an unanswered message up the hierarchy. Two ramifications of this mechanism, automatic inheritance and shadowing, are discussed. An evaluation of the design decisions is also given. [ABSTRACT FROM AUTHOR]

This paper, which was initially prepared to accompany a series of lectures given at the 1978 NATO International Summer School on Program Construction, is primarily tutorial in nature. It begins by discussing in a general setting the role of type abstraction and the need for formal specifications of type abstractions. It then proceeds to examine in some detail two approaches to the construction of such specifications: that proposed by Hone in his 1972 paper "Proofs of Correctness of Data Representations," and the author's own version of algebraic specifications. The Hoare approach is presented via a discussion of its embodiment in the programming language Euclid. The discussion of the algebraic approach includes material abstracted from earlier papers as well as some new material that has yet to appear. This new material deals with parameterized types and the specification of restrictions. The paper concludes with a brief discussion of the relative merits of the two approaches to type abstraction. [ABSTRACT FROM AUTHOR]

This editorial discusses selected articles about software management that appear in the July 1978 issue of "IEEE Transactions on Software Engineering". The manuscript was inspired by a series of seminars on software management organized by the American Institute of Aeronautics and Astronautics which addressed software management from the viewpoint of the U.S. Defense Department. The first paper manifests the theme of the seminar, that is the Department of Defense is launching a major effort to bring the management of software development under better control. Starting with this global view of the problem, the succeeding papers examine software management from the more restrictive viewpoints of the system developer within the framework of a major procurement agency, the program manager responsible for a system containing an embedded computer resource, and finally the system implementer who gambles his system expertise in an attempt to successfully develop a system on schedule and profit.

It is desirable to have Distributed Database Management System whose behavior and control is as identical as possible to that used in signel site database management systems. Preserving the autonomy of sites which join a DDBMS network is essential to the peace of mind of its managers and users, and more technically, is essential in an environment where sites and communication lines fail. Redundant copies in a distributed system provide locality of reference for reads and the potential for parallel processing.

The Pareto principle is often used to describe how faults in large software systems are distributed over modules. A recent paper by Andersson and Runeson again confirmed the Pareto principle of fault distribution. In this paper, we show that the distribution of software faults can be more precisely described as the Weibull distribution. [ABSTRACT FROM AUTHOR]

This paper proposes a new lower bound on the number of processors and finish time for the problem of scheduling precedence graphs with communication costs. An algorithm (ETF) has been proposed by Hwang [1] for scheduling precedence graphs In systems with interprocessor communication limes. In this paper the notion of the earliest starting time of a task is formulated for the context of lower bounds. A lower bound on the completion time is proposed. A task delay which does not increase the earliest completion time of a schedule is defined. Each task can then be scheduled within a time interval without affecting the lower bound performance on the finish time. This leads to definition of a new lower bound on the number of processors required to process the task graph. A derivation of the minimum time increase over the earliest completion time is also proposed for the case of smaller number of processors. Finally the paper proposes a lower bound on the minimum number of interprocessor communication links required to achieve optimum performance. Evaluation has been carried out by using a set of 360 small graphs. The bound on the finish time deviates at most by 5% from the optimum solution in 96% of the cases and performs well with respect to the minimum number of processors and communication links. [ABSTRACT FROM AUTHOR]

We explain why pre-run-time scheduling is essential if one wishes to guarantee that timing constraints will be satisfied in a large complex hard-real-time system. We examine some of the major concerns in pre-run-time scheduling and consider what formulations of mathematical scheduling problems can be used to address those concerns. This paper provides a guide to the available algorithms. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of the dependability validation of fault-tolerant computing systems and more specifically the validation of the fault-tolerance mechanisms. The presented approach is based on the use of fault-injection at the physical level on a hardware/software prototype of the considered system. The place of this approach in a validation directed design process, as well as its place with respect to related works on fault-injection, is clearly identified. The major requirements and problems related to the development and application of a validation methodology based on fault injection are presented and discussed. Emphasis is put on the definition, analysis, and use of the experimental dependability measures that can be obtained. The proposed methodology has been implemented through the realization of a general pin-level fault injection tool (MESSALINE) and its usefulness is demonstrated by the application of MESSALINE to the experimental validation of two systems: 1) a subsystem of a centralized computerized inerlocking system for railway control applications and 2) a distributed system corresponding to the current implementation of the dependable communication system of the ESPRIT Delta-4 Project. [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]

This paper presents a recognition procedure for parallel tasks in the user program written in a conventional programming language. To establish our program model, it describes the parallelism of the program in terms of a process flow graph in which the relationships among processes are of predecessors and successors. And finally it presents a parallel processing scheme which realizes automatically the recognition of parallel tasks and schedules these tasks for parallel execution. [ABSTRACT FROM AUTHOR]

We are concerned with languages in which the programmer has explicit control over the referencing environment of a name. Several modern programming languages, including Ada, Euclid, Mesa, and Modula, implement these control capabilities. This paper describes a simple technique which uses the traditional concepts of a hashed symbol table and lexical level to solve many of the symbol table implementation problems associated with explicit scope control. The primary advantage of this technique is that a single symbol table abstraction can be used to simply and efficiently solve most problems in scope control. [ABSTRACT FROM AUTHOR]

An approach to proving parallel programs correct is presented. The steps are 1) model the parallel program, 2) prove partial correctness (proper synchronization), and 3) prove the absence of deadlock, livelock, and infinite loops. The parallel program model is based on Keller's model. The main contributions of the paper are techniques for proving the absence of deadlock and livelock. A connection is made between Keller's work and Dijkstra's work with serial non-deterministic programs. It is shown how a variant function may be used to prove finite termination, even if the variant function is not strictly decreasing, and how finite termination can be used to prove the absence of livelock. Handling of the finite delay assumption is also discussed. The illustrative examples include one which occurred in a commercial environment and a classic synchronization problem solved without the aid of special synchronization primitives. [ABSTRACT FROM AUTHOR]

A major portion of the problems associated with software development might be blamed on the lack of appropriate tools to aid in the planning and testing phases of software projects. As one step towards solving this problem, this paper presents a model to estimate the number of bugs remaining in a system at the beginning of the testing and integration phases of development. The model, based on software science metrics, was tested using data currently available in the literature. Extensions to the model are also presented which can be used to obtain such estimates as the expected amount of personnel and computer time required for project validation. [ABSTRACT FROM AUTHOR]

This paper contains an exposition of the method of programming with verification conditions. Although this method has much in common with the one discussed by Dijkstra in A Discipline of Programming, it is shown to have the advantage in simplicity and flexibility. The simplicity is the result of the method's being directly based on Floyd's inductive assertions. The method is flexible because of the way in which the program is constructed in two stages. In the first stage, a set of verification conditions is collected which corresponds to a program in "flowgraph" form. In this stage sequencing control is of no concern to the programmer. Control is introduced in the second stage, which consists of automatable applications of translation and optimization rules, resulting in conventional code. Although our method has no use for the sequencing primitives of "structured programming," it is highly secure and systematic. [ABSTRACT FROM AUTHOR]

The performance of a hardware/software system is a function of both the deterministic properties of the computation being performed and the probabilistic properties of the information sequence being processed. This paper develops the idea of a computational cost which can be used to measure system performance and shows how this cost can be related to the structure of the system and the information processed by the system. Different ways in which this cost can be used to study system performance are presented. [ABSTRACT FROM AUTHOR]

In Concurrent Pascal, the syntactic and semantic definition of the language prevents the inadvertent definition of a program that might violate the integrity of a shared data object. However, the language also does not allow the dynamic allocation of reusable resources among processes, and this restriction seems unnecessarily stringent. This paper proposes the addition to Concurrent Pascal of a new type of program component, to be called a resource manager. By this means, dynamic resource allocation can be accomplished both safely and efficiently. The notion that a process holds access Fights to a resource is generalized to the notion that it holds capability rights, but the capability to actually make use of a resource is granted dynamically. The anonymity of dynamically allocatable resources is also guaranteed. [ABSTRACT FROM AUTHOR]

Most current approaches to mechanical program verification transform a program and its specifications into first-order formulas and try to prove these formulas valid. Since the first-order predicate calculus is not decidable, such approaches are inherently limited. This paper proposes an alternative approach to program verification: correctness proofs are constructively established by proof justifications written in an algorithmic notation. These proof justifications are written as part of the program, along with the executable code and correctness specifications. A notation is presented in which code, specifications, and justifications are interwoven. For example, if a program contains a specification ∃x P(x), the program also contains a justification that exhibits the particular value of x that makes P true. Analogously, justifications may be used to state how universally quantified formulas are to be instantiated when they are used as hypotheses. Programs so justified may be verified by proving quantifier-free formulas. Additional classes of justifications serve related ends. Formally, justifications reduce correctness to a decidable theory. Informally, justifications establish the connection between the executable code and correctness specifications, documenting the reasoning on which the correctness is based. [ABSTRACT FROM AUTHOR]

This paper describes a series of psychological experiments used to test a new data base query language. The intent is to make psychological testing of a language part of the design and development process. By testing a language while it is still under development, features that require changing can be identified and the changes made. The experiments, which used college students as subjects, investigated: 1) overall "learnabiity" of the language, 2) "learnabiity" of individual features of the language, and 3) the types and frequencies of errors made. Recommended changes to the particular language and the basis for those recommendations are described. In addition, errors made by experimental subjects during the testing are then analyzed from the point of view of possible causes. Based on this analysis, a preliminary model of query writing and two possible indices of query complexity are suggested. [ABSTRACT FROM AUTHOR]

This paper describes a methodology for the generation of software requirements for large, real-time unmanned weapons systems. It describes what needs to be done, how to evaluate the intermediate products, and how to use automated aids to improve the quality of the product. An example is provided to illustrate the methodology steps and their products and the benefits. The results of some experimental applications are summarized. [ABSTRACT FROM AUTHOR]

This paper presents the formalism of Production Systems and investigates its application to define the syntax and translation of programming languages. Several properties appear well-suited to this task: 1) the formalism can be used to specify exactly the syntax of a computer language, including context-sensitive requirements; 2) the specification of the context-sensitive requirements on syntax can be isolated from the context-free requirements; 3) the same formalism can be used to specify more general structural properties, including the translation of one language into another. The notation has been developed with readability as a prime design issue. The following examples are given: 1) a specification of the syntax of a small but difficult subset of PL/I; 2) a specification of the rules for translating lambda-calculus expressions into normal form. [ABSTRACT FROM AUTHOR]

To provide continuity of operations in automated systems, there is a need to develop techniques that can make them reliable. Many systems such as used in space programs, air traffic control, nuclear plant monitors, ballistic missile defense and other demand robust operation. There is a need for research effort in the investigation of algorithms and system structures that make error/failure detection, reconfiguration, recovery and restart of a system feasible with the least amount of interruptions. A distributed system consists of a set of computers located in different sites connected by means of communications network.

Limiting the extent of error propagation when faults occur and localizing the subsequent error recovery are common concerns in the design of fault tolerant parallel processing systems. Both activities are made easier if the designer associates fault tolerance mechanisms with the underlying atomic actions of the system. With this in mind, this paper has investigated two methods for the identification of atomic actions in parallel processing systems described using CSP. Explicit trace evaluation forms the basis of the first algorithm, which enables a designer to analyze interprocess communications and thereby locate atomic action boundaries in a hierarchical fashion. The second method takes CS? descriptions of the parallel processes and uses structural arguments to infer the atomic action boundaries. This method avoids the difficulties involved with producing full trace sets, but does incur the penalty of a more complex algorithm. [ABSTRACT FROM AUTHOR]

A key index of the performance of a rule-based pro- gram used in real-time monitoring and control is its response time, defined by the longest program execution time before a fixed point of the program is reached from a start state. Previous work in computing the response-time bounds for rule-based programs effectively assumes that all rules take the same amount of firing time, It is also assumed that if two rules are enabled, then either one of them may be scheduled first for firing. These assumptions can result in loose bounds, especially in the case programmers choose to impose a priority structure on the set of rules. In this paper, we remove the uniform-firing-cost assumption and discuss how to get tighter bounds by taking rule-priority information into account. We show that the rule-suppression relation we previously introduced can be extended to incorporate rule-priority information. A bound-derivation algorithm for programs whose potential-trigger relations satisfy an acyclicity condition is presented, followed by its correctness proof and an analysis example. [ABSTRACT FROM AUTHOR]

This paper presents four optimization models to demonstrate that the optimization of software reliability within the available resources can be accomplished. The models help us find the optimal software system structure while considering basic information on reliability and cost of modules. Each model is applicable to a distinct situation. All four models maximize reliability while ensuring that expenditures remain within budget. [ABSTRACT FROM AUTHOR]

Fault injection has been used to evaluate the dependability of computer systems, but most fault-injection studies concentrate on the final impact of faults on the system with an emphasis on fault latency and coverage issues. What realty happens after a fault is injected and how a fault propagates in a software system are not well understood. This paper presents a fault injection and monitoring environment (FINE) as a tool to study fault propagation in the UNIX kernel. FINE injects hardware-induced software errors and software faults into the UNIX kernel and traces the execution flow and key variables of the kernel. It consists of a fault injector, a software monitor, a workload generator, a controller, and several analysis utilities. Experiments on SunOS 4.1.2 are conducted by applying FINE to investigate fault propagation and to evaluate the impact of various types of faults. Fault propagation models are built for both hardware and software faults. Transient Markov reward analysis is performed based on the models to evaluate the loss of performance due to an injected fault. Experimental results show that memory faults and software faults usually have a very long latency while bus faults and CPU faults tend to crash the system immediately. About half of the detected errors are data faults, which are detected when the system tries to access an unauthorized memory location. Only about 8% of faults propagate to other UNIX subsystems. Markov reward analysis shows that the performance loss incurred by bus faults and CPU faults is much higher than that incurred by software and memory faults. Among software faults, the impact of pointer faults is higher than that of nonpointer faults. [ABSTRACT FROM AUTHOR]

Applying equal testing and verification effort to all parts of a software system is not very efficient, especially when resources are limited and scheduling is tight. Therefore, one needs to be able to differentiate low/high fault frequency components so that testing/verification effort can be concentrated where needed. Such a strategy is expected to detect more faults and thus improve the resulting reliability of the overall system. This paper presents the Optimized Set Reduction approach for constructing such models, intended to fulfill specific software-engineering needs. Our approach to classification is to measure the software system and build multivariate stochastic models for predicting high-risk system components. We present experimental results obtained by classifying Ada components into two classes: is or is not likely to generate faults during system and acceptance test. Also, we evaluate the accuracy of the model and the insights it provides into the error-making process. [ABSTRACT FROM AUTHOR]

The programming tradeoffs between structure-oriented and clause-oriented operations on data structures in Prolog are limited in current implementations of Prolog, because the assertion of clauses that include uninstantiated variables destroys any binding between these variables and those with which they are unified in the execution of the program. In this paper, we propose new built-in predicates for Prolog that allow us to assert predicate variable pointers, which are constants, rather than uninstantiated variables. We show: 1) the possible performance benefits of clause-oriented implementations of data structures over equivalent structure-oriented versions, 2) the logical implications of the proposed built-in predicates, and 3) their practical significance by integrating them in C-Prolog, and evaluating the two different implementations of the symbol table dictionary in Warren's Pseudo-Pascal Compiler example. [ABSTRACT FROM AUTHOR]

This paper shows how design time testing may be used in conjunction with formal specification. Emphasis is placed upon the benefits of using an executable specification language OBJ, a design controlled by requirements specification and adherence to the "regularity" and "uniformity" hypotheses in dynamic validation. Such an approach offers positive benefits by providing early design validation and a controlled, disciplined design process. [ABSTRACT FROM AUTHOR]

A distributed system is an interconnected network of computing elements or nodes, each of which has its own storage. A distributed program is a collection of processes which execute asynchronously, possibly in different nodes of a distributed system, and they communicate with each other in order to realize a common goal. In such an environment, a group of processes may sometimes get involved in a communication deadlock. This is a situation in which each member process of the group is waiting for some member to communicate with it, but no member is attempting communication with it. In this paper, we present an algorithm for detecting such communication deadlocks. The algorithm is distributed, i.e., processes detect deadlocks during the course of their communication, without the aid of a central controller. The detection scheme does not presume any a priori structure among processes, and detection is made "on the fly" without freezing normal activities. The scheme does not require any storage whose size is determined by the size of the network, and hence is suitable also for an environment where processes are created dynamically. [ABSTRACT FROM AUTHOR]

In this paper we discuss the issues involved in debugging a distributed computing system. We describe the major differences between debugging a distributed system and debugging a sequential program. We suggest a methodology for distributed debugging, and we propose various tools or aids. [ABSTRACT FROM AUTHOR]

Some analysis techniques for real-time asynchronous concurrent systems are presented. In order to model clearly the synchronization involved in these systems, an extended timed Petri net model is used, The system to be studied is first modeled by a Petri net. Based on the Petri net model, a system is classified into either: 1) a consistent system; or 2) an inconsistent system. Most real-world systems fall into the run class which is further subclassified into i) decision-free systems; ii) safe persistent systems; and iii) general systems. Procedures for predicting and verifying the system performance of all three types are presented. It is found that the computational complexity involved increases in the same order as they are listed above. [ABSTRACT FROM AUTHOR]

We present a new approach to the control of versions of software and other hierarchically structured entities. Any part of a system, from the smallest component to a complete system, may exist in different versions. The set of all possible versions under the refinement relation forms a partial order (in fact, a lattice). The fact that version V approximates version V' in this order means that V is relevant to V' in this sense: when constructing version V' of a system, we can sometimes use version V of a component if nothing more appropriate is available. More precisely, a particular version of an entire system is formed by combining the most relevant existing versions of the various components of the system. We call this the variant structure principle; it makes precise the idea that components of a given version of the system can be inherited by more refined versions of the system. We give an algebraic version language which allows histories (numbered series), subversions (or variants), and joins. In particular, the join operation is simply the lattice least upper bound. The join operation, together with the variant structure principle, provide a systematic framework for recombining divergent variants. We demonstrate the utility of this approach through LEMUR, a programming environment for modular C programs, which was developed using itself. Finally, we show how this notion of versions is related to the possible world semantics of intentional logic. [ABSTRACT FROM AUTHOR]

A group-select operation has been defined for relational algebra. This operation is found to lie useful for efficiently reducing expressions of nonprocedural relational languages that permit natural quantifiers; Conceptually, the operation first partitions a relation into blocks of tuples that have the same value for an attribute Or attribute concatenation. It then extracts each block for which a specified number of tuples meet a specified condition. The quantity of tuples for the operation is specified by means of a natural quantifier. Performance of the group-select operation will be poor with conventional file processing, making the operation more suitable for use with a database machine with an associative memory. [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]

Real-time systems often have very high reliability requirements and are therefore prime candidates for the inclusion of fault tolerance techniques. In order to provide tolerance to software faults, some form of state restoration is usually advocated as a means of recovery. State restoration can be expensive and the cost is exacerbated for systems which utilize concurrent processes. The concurrency present in most real-time systems and the further difficulties introduced by timing constraints suggest that providing tolerance for software faults may be inordinately expensive or complex. We believe that this need not be the case, and propose a straightforward pragmatic approach to software fault tolerance which is believed to be applicable to many real-time systems. The approach takes advantage of the structure of real-time systems to simplify error recovery, and a classification scheme for errors is introduced. Responses to each type of error are proposed which allow service to be maintained. [ABSTRACT FROM AUTHOR]

Some properties of a program data flow can be used to guide program testing. The presented approach aims to exercise use-definition chains that appear in the, program. Two such data oriented testing strategies are proposed; the first involves checking liveness of every definition of a variable at the point(s) of its possible use; the second deals with liveness of vectors of variables treated as arguments to an instruction or program block. Reliability of these strategies is discussed with respect to a program containing an error. [ABSTRACT FROM AUTHOR]

A language for defining sequential file structures, characterized as nested sequences of records having in common certain keys and types, is presented. "Input schemata" are defined as program skeletons that contain all the necessary control structure to process a specified file. A method for obtaining an input schema from the corresponding file structure definition is given. The method is based on attributed grammars, and has been implemented in the programming language PROLOG. This constitutes a formalization of some aspects of the data-directed program design method of Jackson and Warnier. Examples of applications of this method to business data processing problems such as file updating and report generation are given. [ABSTRACT FROM AUTHOR]

A formal model for atomic commit protocols for a distributed database system is introduced. The model is used to prove existence results about resilient protocols for site failures that do not partition the network and then for partitioned networks. For site failures, a pessimistic recovery technique, called independent recovery, is introduced and the class of failures for which resilient protocols exist is identified. For partitioned networks, two cases are studied: the pessimistic case in which messages are lost, and the optimistic case in which no messages are lost. In all cases, fundamental limitations on the resiliency of protocols are derived. [ABSTRACT FROM AUTHOR]

-c_A language-independent syntax-directed pretty printer has been implemented as the first step towards building a language-independent syntax-directed editor. The syntax-directed pretty printer works in two phases: the grammar processing phase and the program processing phase. In the grammar processing stage, a grammar which contains a context-free grammar and information for the parser and pretty printer is processed and all files needed by the second phase are written. With these files, the syntax-directed pretty printer works for the language of the grammar. The syntax-directed editor would use the same grammar processing phase to construct the files needed to make it work for a specific language. In the program processing phase, programs in the language of the grammar are parsed and parse trees are built If syntax errors are found, error messages are produced and error recovery is done. The parse trees are pretty printed according to the pretty printer specifications given in the grammar, resulting in well-indented, syntactically clear programs. [ABSTRACT FROM AUTHOR]

The feasibility of using macros to compile a lines, assembly language is well established. A cross assembler has been implemented, via macros, for an assembly language, SCRAM, which embodies high-level language features such as user-controlled symbol scope and nested DO and IF/THEN/ELSE control structures. Difficulties arose in implementation primarily from the inconvenience of managing assembly-tune data. It is demonstrated herein that indirect referencing of assembly-time variables can be used in a two-pass macro assembler to solve these problems. Scope control may be accomplished by limiting the range of internally generated symbols (indexed through user-declared symbols) which may be accessed at any time. Saving and restoring the current control structure environment to an arbitrary depth of nesting is possible by implementing an assembly-time stack using indirectly referenced variables. [ABSTRACT FROM AUTHOR]

A global state of a distributed transaction system is consistent if no transactions are in progress. A global checkpoint is a transaction which must view a globally consistent system state for correct operation. We present an algorithm for adding global checkpoint transactions to an arbitrary distributed transaction system. The algorithm is nonintrusive in the sense that checkpoint transactions do not interfere with ordinary transactions in progress; however, the checkpoint transactions still produce meaningful results. [ABSTRACT FROM AUTHOR]

A construct is proposed for parallel programming, called soma (software machine). A so,na is a sequential process that can communicate with other somas by exchanging messages via mailboxes. The soma construct is well suited for implementation on conventional as well as on distributed computer architectures, the main characteristic of the latter being the absence of a common store. In addition to a description of the soma construct, a rationale is given for its communication characteristics and a comparison is made with related proposals. Three illustrative examples are given: updating a sequential file (with concurrent operation of the input, update, and output activities), the general producer/consumer problem, and the computation of a critical path in a PERT graph. [ABSTRACT FROM AUTHOR]