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]

In his paper "Communicating Sequential Processes," bare suggested the use of the input/output construct and Dijkstra's guarded commands for handling the task of communication and synchronization in distributed systems. bare's proposal was intended for programming general parallel systems; as a result, little consideration was given by Hoare to the question of how his mechanisms could be utilized in the construction of reliable dynamic resource management schemes. In this paper, we examine this problem and propose several simple extensions to bare's constructs that will make the extended Communicating Sequential Processes concept more suitable for the handling of such management schemes. [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]

Parallel computing on interconnected workstations is becoming a viable and attractive proposition due to the rapid growth in speeds of interconnection networks and processors. In the case of workstation clusters, there is always a considerable amount of unused computing capacity available in the network. However, heterogeneity in architectures and operating systems, load variations on machines, variations in machine availability, and failure susceptibility of networks and workstations complicate the situation for the programmer. In this context, new programming paradigms that reduce the burden involved in programming for distribution, load adaptability, heterogeneity, and fault tolerance gain importance. This paper identifies the issues involved in parallel computing on a network of workstations. The Anonymous Remote Computing (ARC) paradigm is proposed to address the issues specific to parallel programming on workstation systems. ARC differs from the conventional communicating process model by treating a program as one single entity consisting of several loosely coupled remote instruction blocks instead of treating it as a collection of processes. The ARC approach results in distribution transparency and heterogeneity transparency. At the same time, it provides fault tolerance and load adaptability to parallel programs on workstations. ARC is developed in a two-tiered architecture consisting of high level language constructs and low level ARC primitives. The paper describes an implementation of the ARC kernel supporting ARC primitives. [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]

A new approach to coordination of cooperating concurrent processes, each capable of error detection and recovery, is presented. Error detection, rollback, and retry in a process are specified by a well-structured language construct called recovery block. Recovery points of processes must be properly coordinated to prevent a disastrous avalanche of process rollbacks. In contrast to the previously studied approaches that require the program designer to coordinate the recovery block structures of interacting processes (thereby coordinating the recovery points of processes), the new approach relieves the program designer of that burden It instead relies upon an intelligent processor system (that runs processes) capable of establishing and discarding the recovery points of interacting processes in a well coordinated manner such that 1) a process never makes two consecutive rollbacks without making a retry between the two, and 2) every process rollback becomes a minimum-distance rollback. Following the discussion of the underlying philosophy of the new approach, basic rules of reducing storage and time overhead in such a processor system are discussed. Throughout this paper examples are drawn from the systems in which processes communicate through monitors. [ABSTRACT FROM AUTHOR]

A number of mechanisms have been created for controlling entity visibility. As with most language concepts in computer science, visibility control mechanisms have been developed in an essentially ad hoc fashion, with no clear indication given by their designers as to how one proposed mechanism relates to another. This paper introduces a formal model for describing and evaluating visibility control mechanisms. The model reflects a general view of visibility in which the concepts of requisition of access and provision of access are distinguished. This model provides a means for characterizing and reasoning about the various properties of visibility control mechanisms. Specifically, a notion of preciseness is defined in this paper. The utility of the model is illustrated by using it to evaluate and compare the relative strengths and weaknesses, with respect to preciseness, of the visibility control mechanisms found in Algo160, Ada, Gypsy, and an approach we have developed, called PLC, that specifically addresses the concerns of visibility control in large software systems. [ABSTRACT FROM AUTHOR]

This paper examines the use of cluster analysis as a tool for system modularization. Several clustering techniques are discussed and used on two medium-size systems and a group of small projects. The small projects are presented because they provide examples (that will fit into a paper) of certain types of phenomena. Data bindings between the routines of the system provide the basis for the bindings. It appears that the clustering of data bindings provides a meaningful view of system modularization. [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]

In a two-processor distributed computer network, prior research showed that a maximum flow algorithm can be used to find optimal program-module-to-processor assignments to maximize the performance of distributed programs. This paper examines the sequence of optimal assignments found as the load on one processor is held fixed and the load on the other is varied. For every program module M there exists a critical load factor fM such that when the load on the processor with variable load is below fM, M is assigned to that processor by an optimal assignment, and is otherwise assigned to the other processor. This characteristic opens the possibility of doing optimal dynamic assignments in real-time. [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 have noticed two problems with viewing a process as a sequence of events: The first problem is the complete loss of information about potential intra-process concurrency for both sequential and distributed computations, and partial loss of information about potential inter-process concurrency for distributed computations. The second problem is that the resulting reasoning framework does not lend itself to refinement (from sequential computing or a given set of distributed processes) to a preferable set of distributed processes. We argue that it is more natural to view a computation, either distributed or sequential, as a partially ordered set of events. Doing so leads to a view, called passive-space and time view, which we propose in this paper. In the proposed view, a point in space is a passive entity which does not order events that occur at it, and the order is determined by the interaction among the events. We define a relation, "Affects", between pairs of events, which captures the partial order on events. To aid users of the relation "Affects" in developing algorithms, we define vector clocks, that are global logical clocks, so that the relation "Affects", and hence all potential concurrency, between events can be identified from their timestamps assigned. Since this research is motivated by the need to solve practical problems, we define passive-space and time view such that a user has control, in two ways, over the costs involved. First, a process designer may choose any granularity of events and choose any mechanism for determining partial order among events on the process. Second, a user may choose a vector clock such that the extent of potential intra-process concurrency identified depends on the costs associated with the identification. We give vector clocks which trade cost incurred and concurrency identification. We compare the proposed view with the space and time view. Finally, we give a scheme for reducing the cost of communicating timestamps. [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]

In a recent paper by Fayolle, Mitrani, and Iasnogorodski [2], some general multidimensional integral equations were derived in order to solve for the mean response time of each of several classes in a queue whose service discipline was weighted processor sharing. The arrival processes were Poisson. The weighting means that each job within a class k is given an amount of processing proportional to the priority weight gk associated with that class. For exponential service times, the general equations were solved. In this note, a simple observation allows use of the exponential solution directly for the case of hyperexponential servers. As a result, it is possible to state the following. • Characterization of a server in terms of its mean and coefficient of variation is not sufficient to predict even the mean response time for a class using weighted processor sharing. In unweighted or egalitarian processor sharing, only the mean is sufficient. • The Kleinrock conservation law [4] does not hold for nonexponential servers. Fayolle et al. [2] had showed that it did hold for exponential servers. [ABSTRACT FROM AUTHOR]

This paper shows that graph traversal techniques have fundamental differences between serial and distributed computations in their behaviors, computational complexities, and effects on the design of graph algorithms. It has three major parts. Section 1 describes the computational environment for the design and description of distributed graph algorithms in terms of an architectural model for message exchanges. The computational complexity is measured in terms of the number of messages transmitted. Section II presents several distributed algorithms for the pure traversal, depth-first search, and breadth-first search techniques. Their complexities are also given. Through these descriptions are brought out some of the intrinsic differences in the behaviors and complexities of the fundamental traversal techniques between a serial and a distributed computation environment. Section III gives the distributed version of the Ford and Fulkerson algorithm for the maximum flow problem by means of depth-first search, the largest-augmentation search and breadth-first search. The complexities of these methods are found to be 0(f*¦A¦), 0((1 + logM/(M-1)f*)¦V¦¦A¦) and 0(¦V¦6), respectively, where f* is the maximum flow value of the problem, M is the maximum number of arcs in a cut, ¦V¦ is the number of vertices, and ¦A¦ is the number of arcs. Lastly, it is shown that the largest augmentation search may be a better method than the other two. This is contrary to the known results in serial computation. [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]

In this paper a new method for analyzing complex queueing networks is proposed: the isolation method. As an example, we study packet switching networks with finite buffer size at each node. [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]

Recent advances in languages, software design methodologies, and architecture have prompted the development of improved compile-time methods for analyzing the effects of procedure calls, pointer references, and array accesses. Such sophistication, however, generally implies that compilers and programming environments will experience a corresponding increase in the volume, of analysis information, which may be difficult to use efficiently. In this paper, we consider the practical accommodation of such information. Our results show how to engineer a compiler such that its optimization phase takes time proportional to the benefit, rather than the size, of such information. [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]

The fault exposure ratio K is an important factor that controls the per-fault hazard rate, and hence the effectiveness of testing of software. The paper examines the variations of K with fault density which declines with testing time. Because faults get harder to find, K should decline if testing is strictly random. However, it is shown that at lower fault densities K tends to increase; we explain this by using a hypothesis: real testing is more efficient than strictly random testing especially at the end of the test phase. Data sets from several different projects (in USA and Japan) are analyzed. If we combine the two factors, e.g., shift in the detectability profile and the nonrandomness of testing, then the analysis leads us to the logarithmic model which is known to have superior predictive capability. [ABSTRACT FROM AUTHOR]

This paper considers the problem of accurately modeling the software fault-tolerance technique based on recovery blocks. Models of such systems have been criticized for their assumptions of independence. Analysis of some systems have considered the correlation between software modules. This correlation may be due to a portion of the functional specification that is common to all software modules or due to the inherent hardness of some problems. We consider three types of dependence which can be captured using measurements. We consider correlation between software modules for a single input, correlation between successive acceptance tests on correct module outputs and incorrect module outputs, and correlation between subsequent inputs. The technique we use is quite general and can be applied to other types of correlation. In accounting for dependence, we use the intensity distribution introduced by Eckhardt and Lee. We consider a new method of generating the intensity distribution which is based on the pairwise correlation between modules. This method provides us with a pessimistic result and a probability-based approximation. We contrast this method with the assumption of independent modules as well as the use of the beta-binomial density which was introduced by Nicola and Goyal. For the purpose of obtaining numerical results, we use stochastic reward nets (SRN's) that incorporate all of the above dependencies and then use a modeling tool called Stochastic Petri Net Package (SPNP). [ABSTRACT FROM AUTHOR]

The goal of software inspection and test is to reduce the expected cost of software failure over the life of a product. This paper extends the use of defect triggers, the events that cause defects to be discovered, to help evaluate the effectiveness of inspections and test scenarios. In the case of inspections, the defect trigger is defined as a set of values that associate the skills of the inspector with the discovered defect. Similarly, for test scenarios, the defect trigger values embody the deferring strategies being used in creating these scenarios. The usefulness of triggers in evaluating the effectiveness of software inspections and tests is demonstrated by evaluating the inspection and test activities of some software products. These evaluations are used to point to both deficiencies in inspection and test strategies and to progress made in improving such strategies. The trigger distribution of the entire inspection or test series may then be used to highlight areas for further investigation, with the aim of improving the design, implementation, and test processes. [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]