Search

Comments on the articles in the "IEEE Transactions on Software Engineering" were given. The periodical has an established, published scope which is subject to change as the file develops. Part of the review process is to state whether the paper meets the criteria. The scope should be limited to papers of interest to the software engineering community. However, besides mainstream software engineering topics, it could include the software engineering of various applications.

The interpretations of logical expressions found in most introductory textbooks are not suitable for use in software engineering applications because they do not deal with partial functions. More advanced papers and texts deal with partial functions in a variety of complex ways. This paper proposes a very simple change to the classic interpretation of predicate expressions, one that defines their value for all values of all variables, yet is almost identical to the standard definitions. It then illustrates the application of this interpretation in software documentation. [ABSTRACT FROM AUTHOR]

In this paper we: 1) discuss the need for quantitatively reproducible experiments in the study of top-down design; 2) propose the design and writing of tutorial papers as a suitably general and in- expensive vehicle; 3) suggest the software science parameters as appropriate metrics; 4) report two experiments validating the use of these metrics on outlines and prose; and 5) demonstrate that the experiments tended toward the same optimal modularity. The last point appears to offer a quantitative approach to the estimation of the total length or volume (and the mental effort required to produce it) from an early stage of the top-down design process. If results of these experiments are validated elsewhere, then they will provide basic guidelines for the design process. [ABSTRACT FROM AUTHOR]

The use of icons is effective for attaining higher man-machine interaction in programming from the viewpoints of both universality and efficiency. In this paper, the authors propose a new framework for icon management and an iconic programming based on it. In the framework, icons represent real objects or the concepts already established in a target application environment, whereas icons representing functions are not provided. A function is represented by a combination of two different icons. Each icon can take an active or a passive role against the other. The role sharing is determined dynamically depending on the environment in which the icons are activated; The framework for icon management mentioned above, which is quite object-oriented, is first proposed, and then an iconic programming system named HI-VISUAL is presented on the basis of the framework. Programming in HI-VISUAL and implementational issues of the system prototype, now in actual operation in our laboratory environment, are extensively discussed. [ABSTRACT FROM AUTHOR]

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]

Web engineering is a new research line in software engineering that covers the definition of processes, techniques, and models suitable tot Web environments in order to guarantee the quality of results. The research community is working in this area and, as a very recent line, they are assuming the Model-Driven paradigm to support and solve some classic problems detected in Web developments. However, there is a lack in Web requirements treatment. This paper presents a general vision of Navigational Development Techniques (NDT), which is an approach to deal with requirements in Web systems. It is based on conclusions obtained in several comparative studies and it tries to fill some gaps detected by the research community. This paper presents its scope, its most important contributions, and offers a global vision of its associated tool: NDT-Tool. Furthermore, it analyzes how Web Engineering can be applied in the enterprise environment. NDT is being applied in real projects and has been adopted by several companies as a requirements methodology. The approach offers a Web requirements solution based on a Model-Driven paradigm that follows the most accepted tendencies by Web engineering. [ABSTRACT FROM AUTHOR]

Association is one of the key concepts in UML that is intensively used in conceptual modeling. Unfortunately, in spite of the fact that this concept is very old and is inherited from other successful modeling techniques, a fully unambiguous understanding of it, especially in correlation with other newer concepts connected with association ends, such as uniqueness, still does not exist. This paper describes a problem with one widely assumed interpretation of the uniqueness of association ends, the restrictive interpretation, and proposes an alternative, the intentional interpretation. Instead of restricting the association from having duplicate links, uniqueness' of an association end in the intentional interpretation modifies the way in which the association end maps an object of the opposite class to a collection of objects of the class at that association end. If the association end is unique, the collection is a set obtained by projecting the collection of all linked objects, in that sense, the uniqueness of an association end modifies the view to the objects at that end, but does not constrain the underlying object structure. This paper demonstrates how the intentional interpretation improves expressiveness of the modeling language and has some other interesting advantages. Finally, this paper gives a completely formal definition of the concepts of association and association ends, along with the related notions of uniqueness, ordering, and multiplicity. The semantics of the UML actions on associations are also defined formally. [ABSTRACT FROM AUTHOR]

Experimental research in computer science is a relatively new, yet fast developing area. It is encouraging to that there is substantial research going on in this important area. A study on experimental evaluation of a reusability-oriented parallel programming environment is given. There is a significant amount of experimental research in the area of computer dependability.

This editorial discusses selected papers submitted during the Third International Conference on Software Engineering held in Atlanta, Georgia in May 1978. The international congress, attended by members of the academe and the computer industry, aimed to define the emerging importance of computer software engineering. The first paper refers to how the computer industry provides solutions to everyday challenges with the use of computers. Here, customers express their views on the purpose of computers, leading computer software developers to consider user requirements. The second paper focuses on the activity of design. It discusses a modeling scheme where large programs can be built out of incomplete parts. Design activities are followed by testing, the focus of the third manuscript. A comprehensive study of the two basic approaches to program testing is discussed. The last paper considers programs in operation, the last phase of the computer software development.

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]

This paper is concerned with the problem of ensuring the integrity of database systems that are accessed concurrently by a number of independent asynchronously running transactions. It is assumed that the database system is partitioned into small units that are referred to as the database entities. The relation between the entities is represented by a directed acyclic graph in which the vertices correspond to the database entities and the arcs correspond to certain access rights. We develop a family of non-two-phase locking protocols for such systems that will be shown to ensure serializability and deadlock-freedom. This family is sufficiently general to encompass all the previously developed non-two-phase locking protocols as well as a number of new protocols. One of these new protocols that seems to be particularly useful is also presented in this paper. [ABSTRACT FROM AUTHOR]

Conventional database design techniques rely heavily on the designer's skill and experience, which are neither efficient nor effective for large, realistic design problems. A computer design aid can help by storing many design parameters and performing simple pre- processing before design decisions are made. In this paper, we report on the development of such a system. The system is based on a data model called the Functional Data Model (FDM), and on a transaction (or process) model which is specified via the Transaction Specification Language (TASL). FDM is used to define data entities and the relationships between them. TASL is used to capture application processing intent and performance parameters that are relevant to the database design. Logical database design involves two major steps. First, local (or application) views are modeled using FDM and TASL. Second, in order to achieve an integrated database design, these local views are combined and transformed to produce a global conceptual view (schema). This paper describes FDM and TASL; in addition, a set of operations for integrating and transforming local views is presented. A unique feature of these transformations is that they apply to TASL processes as well as FDM schema Finally, an algorithm is given for view integration. This algorithm, along with heuristics and some user-supplied subset assertions, enables the database design system to automatically identify and filter out redundancies. [ABSTRACT FROM AUTHOR]

DIRECT is a multiprocessor database machine designed and implemented at the University of Wisconsin. This paper describes our experiences with the implementation of DIRECT. We start with a brief overview of the original machine proposal and how it differs from what was actually implemented. We then describe the structure of the DIRECT software. This includes software on host computers that interfaces with the database machine; software on the back-end controller of DIRECT; and software executed by the query processors. In addition to describing the structure of the software we will attempt to motivate and justify its design and implementation. We also discuss a number of implementation issues (e.g., debugging of the code across several machines). We conclude the paper with a list of the "lessons" we have learned from this experience. [ABSTRACT FROM AUTHOR]

It is becoming increasingly important that communication protocols be formally specified and verified. This paper describes a particular approach—the state transition model—using a collection of mechanically supported specification and verification tools incorporated in a running system called AFFIRM. Although developed for the specification of abstract data types and the verification of their properties, the formalism embodied in AFFIRM can also express the concepts underlying state transition machines. Such models easily express most of the events occurring in protocol systems, including those of the users, their agent processes, and the communication channels. The paper reviews the basic concepts of state transition models and the AFFIRM formalism and methodology and describes their union. A detailed example, the alternating bit protocol, illustrates various properties of interest for specification and verification. Other examples explored using this formalism are briefly described and the accumulated experience is discussed. [ABSTRACT FROM AUTHOR]

In database management systems and operating systems, transactions are used as units of consistency, serializability, recovery, and for deadlock control. Normally, the transactions for each of these systems are considered independently. In this paper we describe nested transactions where the transactions from one system interact with the transactions from another system. Such nested transactions can expect to become more important with the introduction of network operating systems and heterogeneous distributed database systems. Nested transactions raise additional problems for the desirability of enforcement of serializability, for the prevention and detection of deadlock, and for the consistent system state recovery from hardware and software crashes. This paper directly addresses the deadlock problems of nested transactions. In particular, we define a transaction controller (IC) that is responsible for maintaining exclusive and restricted shared access to a specific set of resources in what we call its transaction control domain (TCD). TC's are said to interact if a transaction in one controller can initiate a transaction in another controller. Three approaches to the deadlock problem of interacting TC's are described. In the first approach, TC's are tightly coupled in that they need to share transaction identifiers, resource identifiers, and use a common deadlock control mechanism. In the second approach, TC's obey protocols which ensure that if deadlock does occur it will be completely contained in one TCD. In the final approach, we resort to the currently used techniques of a timeout mechanism between interacting mutually suspicious TC's. [ABSTRACT FROM AUTHOR]

This paper proposes a control-oriented Algol-like nonprocedural language called Condor. Automatic controller theory, in company with computer science, underlies many industrial fields. Sequential control is especially important. So far, sequential-controller description methods have by and large been limited to graphic ones, which are unreadable in the case of large controllers. A higher-level linguistic approach has been considered unlikely. This paper proposes a language widely suitable for controller architecture description. A controller, in its nature, consists of many subsystems which work in a parallel manner, interacting with one another. This paper deems that a basic component is not a process, but a response. A controller is considered to be a responding system in which every reactor works together, having a relation and communication to one another. A Condor program is a role assignment list for the reactors; it is Algol-like and nonprocedural. All the statements work at all times, interacting with one another. Besides, a controller has some kinds of tree structures: one is that of information-collecting subsystems, another is that of information-distributing subsystems, and a third is that of the hierarchical construction of the controller system. On the other hand a language also has some kinds of tree structures. It is natural to express the free structures of a controller by the free structures of a language through graph-theoretic isomorphism. We can properly call Condor a spatial programming language. Condor is a language of a new kind. This paper will bring new progress into both the programming language theory and automatic- control engineering. For the readers unfamiliar with automatic control, this paper includes elementary explanations. [ABSTRACT FROM AUTHOR]

This paper concerns new techniques for making requirements specifications precise, concise, unambiguous, and easy to check for completeness and consistency. The techniques are well-suited for complex real-time software systems; they were developed to document the requirements of existing flight software for the Navy's A-7 aircraft. The paper outlines the information that belongs in a requirements document and discusses the objectives behind the techniques. Each technique is described and illustrated with examples from the A-7 document. The purpose of the paper is to introduce the A-7 document as a model of a disciplined approach to requirements specification; the document is available to anyone who wishes to see a fully worked-out example of the approach. [ABSTRACT FROM AUTHOR]

This paper describes weapon system software life cycle management from a contractor perspective. Four procurement strategies—each requiring two or more contracts—are examined and their impact on the contractor and the software process are described. [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]

Structured analysis (SA) combines blueprint-like graphic language with the nouns and verbs of any other language to provide a hierarchic, top-down, gradual exposition of detail in the form of an SA model. The things and happenings of a subject are expressed in a data decomposition and an activity decomposition, both of which employ the same graphic building block, the SA box, to represent a part of a whole. SA arrows, representing input, output, control, and mechanism, express the relation of each part to the whole. The paper describes the rationalization behind some 40 features of the SA language, and shows how they enable rigorous communication which results from disciplined, recursive application of the SA maxim: "Everything worth saying about anything worth saying something about must be expressed in six or fewer pieces." [ABSTRACT FROM AUTHOR]

Presents a reply to an article on a method for representing data items of unlimited length in computer memory.

High cohesion is a desirable property of software as it positively impacts understanding, reuse, and maintenance. Currently proposed measures for cohesion in Object-Oriented (OO) software reflect particular interpretations of cohesion and capture different aspects of it. Existing approaches are largely based on using the structural information from the source code, such as attribute references, in methods to measure cohesion. This paper proposes a new measure for the cohesion of classes in OO software systems based on the analysis of the unstructured information embedded in the source code, such as comments and identifiers. The measure, named the Conceptual Cohesion of Classes (C3), is inspired by the mechanisms used to measure textual coherence in cognitive psychology and computational linguistics. This paper presents the principles and the technology that stand behind the C3 measure. A large case study on three open source software systems is presented which compares the new measure with an extensive set of existing metrics and uses them to construct models that predict software faults. The case study shows that the novel measure captures different aspects of class cohesion compared to any of the existing cohesion measures. In addition, combining C3 with existing structural cohesion metrics proves to be a better predictor of faulty classes when compared to different combinations of structural cohesion metrics. [ABSTRACT FROM AUTHOR]

Increased realism in software engineering experiments is often promoted as an important means of increasing generalizability and industrial relevance. In this context, artificiality, e.g., the use of constructed tasks in place of realistic tasks, is seen as a threat. In this paper, we examine the opposite view that deliberately introduced artificial design elements may increase knowledge gain and enhance both generalizability and relevance. In the first part of this paper, we identify and evaluate arguments and examples in favor of and against deliberately introducing artificiality into software engineering experiments. We find that there are good arguments in favor of deliberately introducing artificial design elements to 1) isolate basic mechanisms, 2) establish the existence of phenomena, 3) enable generalization from particularly unfavorable to more favorable conditions (persistence of phenomena), and 4) relate experiments to theory. In the second part of this paper, we summarize a content analysis of articles that report software engineering experiments published over a 10-year period from 1993 to 2002. The analysis reveals a striving for realism and external validity, but little awareness of for what and when various degrees of artificiality and realism are appropriate. Furthermore, much of the focus on realism seems to be based on a narrow understanding of the nature of generalization. We conclude that an increased awareness and deliberation as to when and for what purposes both artificial and realistic design elements are applied is valuable for better knowledge gain and quality in empirical software engineering experiments. We also conclude that time spent on studies that have obvious threats to validity that are due to artificiality might be better spent on studies that investigate research questions for which artificiality is a strength rather than a weakness. However, arguments in favor of artificial design elements should not be used to justify studies that are badly designed or that have research questions of low relevance. [ABSTRACT FROM AUTHOR]

Cache memory is used in almost all computer systems today to bridge the ever increasing speed gap between the processor and main memory. However, its use in multitasking computer systems introduces additional preemption delay due to the reloading of memory blocks that are replaced during preemption. This cache-related preemption delay poses a serious problem in real-time computing systems where predictability is of utmost importance. In this paper, we propose an enhanced technique for analyzing and thus bounding the cache-related preemption delay in fixed-priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache-related preemption delay. Second, the technique considers the phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache-related preemption delay. This paper also compares the proposed technique with previous techniques using randomly generated task sets. The results show that the improvement on the worst-case response time prediction by the proposed technique over previous techniques ranges between 5 percent and 18 percent depending on the cache refill time when the task set utilization is 0.6. The results also show that as the cache refill time increases, the improvement increases, which indicates that accurate prediction of cache-related preemption delay by the proposed technique becomes increasingly important if the current trend of widening speed gap between the processor and main memory continues. [ABSTRACT FROM AUTHOR]

The dearth of published empirical data on major industrial systems has been one of the reasons that software engineering has failed to establish a proper scientific basis. In this paper, we hope to provide a small contribution to the body of empirical knowledge. We describe a number of results from a quantitative study of faults and failures in two releases of a major commercial system. We tested a range of basic software engineering hypotheses relating to: The Pareto principle of distribution of faults and failures; the use of early fault data to predict later fault and failure data; metrics for fault prediction; and benchmarking fault data. For example, we found strong evidence that a small number of modules contain most of the faults discovered in prerelease testing and that a very small number of modules contain most of the faults discovered in operation. However, in neither case is this explained by the size or complexity of the modules. We found no evidence to support previous claims relating module size to fault density nor did we find evidence that popular complexity metrics are good predictors of either fault-prone or failure-prone modules. We confirmed that the number of faults discovered in prerelease testing is an order of magnitude greater than the number discovered in 12 months of operational use. We also discovered fairly stable numbers of faults discovered at corresponding testing phases. Our most surprising and important result was strong evidence of a counter-intuitive relationship between pre- and postrelease faults: Those modules which are the most fault-prone prerelease are among the least fault-prone postrelease, while conversely, the modules which are most fault-prone postrelease are among the least fault-prone prerelease. This observation has serious ramifications for the commonly used fault density measure. Not only is it misleading to use it as a surrogate quality measure, but, its previous extensive use in metrics studies is shown to be flawed. Our results provide data-points in building up an empirical picture of the software development process. However, even the strong results we have observed are not generally valid as software engineering laws because they fail to take account of basic explanatory data, notably testing effort and operational usage. After all, a module which has not been tested or used will reveal no faults, irrespective of its size, complexity, or any other factor. [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]

The paper deals with the performance analysis of parallel algorithms and systems. For these, numerical solution methods quickly show their limits because of the enormous state-space growth. The proposed methodology and software tool (LISPACK, an acronym for List-manipulation Parallel-modeling Package) uses string manipulation, lumping, and recursive elimination as a means for the definition of the large Markovian process, its restructuring and efficient solution. Initially, the enormous stage space is conveniently collapsed and the large transition matrix is reduced. Subsequently, the reduced matrix is recursively block banded, and an efficient recursive, symbolic Gauss elimination is applied. No relevant costs are incurred for the state-space collapsing and restructuring, nor for the matrix block banding. The analysis of a typical parallel system and algorithm model is developed as a case study, to discuss the features of the method. The paper has two contributions. The first, symbolic-approach methodology, is proposed for the performance analysis of parallel algorithms and systems. Second, a tool is introduced that exploits the capabilities of the symbolic approach in the solution of parallel models, where the numerical techniques reveal their limits. [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]

In this paper, the author describes a security property for trusted multilevel systems, restrictiveness, which restricts the inferences a user can make about sensitive information. This property is a hookup property, or composable, meaning that a collection of secure restrictive systems when hooked together form a secure restrictive composite system. The author argues that the inference control and composability of restrictiveness make it an attractive choice for a security policy on trusted systems and processes. [ABSTRACT FROM AUTHOR]

Numerous algorithms for computationally intensive tasks have been developed by researchers that are suitable for execution on hypercube multiprocessors. One characteristic of many of these algorithms is that they are extremely structured and are tuned for the highest performance to execute on hypercube architectures. In this paper, we have looked at parallel algorithm design from a different perspective. In many cases, it may be possible to redesign the parallel algorithms using software techniques so as to provide a low-cost on-line scheme for hardware error detection without any hardware modifications. This approach is called Algorithm-based error detection. In the past, we have applied algorithm-based techniques for on-line error detection on the hypercube and have reported some preliminary results of one specific implementation on some applications. In this paper, we provide an in-depth study of the various issues and tradeoffs available in Algorithm-based error detection, as well as a general methodology for evaluating the schemes. We have illustrated the approach on an extremely useful computation in the field of numerical linear algebra: QR factorization. We have implemented and investigated numerous ways of applying algorithm-based error detection using different system-level encoding strategies for QIZ factorization. Different schemes have been observed to result in varying error coverages and time overheads. We have reported the results of our studies performed on a 16 processor Intel iPSC-2/D4/MX hypercube multiprocessor. [ABSTRACT FROM AUTHOR]

The effectiveness of all known recovery mechanisms is greatly reduced in the presence of multiple latent faults. The presence of multiple latent faults increases the possibility of multiple errors, which could result in coverage failure. In this paper, we present experimental evidence indicating workload effects on the duration of fault latency. A synthetic workload generator is used to vary the workload, and a hardware fault injector is applied to inject transient faults of varying durations. This method allows us to derive the distribution of fault latency duration. Experimental results were obtained from the fault-tolerant multiprocessor (FTMP) at the NASA Airlab. [ABSTRACT FROM AUTHOR]

In this paper, we have investigated the efficient evaluation of branch-and-bound algorithms in a system with a two-level memory hierarchy. An efficient implementation depends on the disparities in the numbers of subproblems expanded between the depth-first and best-first searches as well as the relative speeds of the main and secondary memories. A best-first search should be used when it expands a much smaller number of subproblems than that of a depth-first search, and the secondary memory is relatively fast. In contrast, a depth-first search should be used when the number of expanded subproblems is close to that of a best-first search. The choice is not as clear for cases in between. The Iterative Deepening A* (IDA*) algorithm has been shown to be asymptotically optimal in space, time, and cost. However, for the conditions that we have assumed, 1DM does not result in the optimal space-time tradeoff for minimizing the completion time. In this paper, we study the space-time tradeoff by proposing and analyzing two strategies: a specialized virtual-memory system that matches the architectural design with the characteristics of the existing algorithm, and a modified branch-and-bound algorithm that can be tuned to the characteristic of the problem and the architecture. The latter strategy illustrates that designing a better algorithm is sometimes more effective than tuning the architecture alone. Guidelines have also been developed to select appropriate a priori values for the parameters of the modified B&B algorithm. [ABSTRACT FROM AUTHOR]

This paper presents the results of analyzing several defect models using data collected from two large commercial projects. Traditional models typically use either program metrics (i.e., measurements from software products) or testing time or combinations of these as independent variables. The limitations of such models have been well-documented. For example, program metrics are difficult to compute for those products that consist of code modified from previous versions. Another example is that testing time is not available at the beginning of the testing phase. The models considered in this paper all use the number of defects detected in the earlier phases of the development process as the independent variable. This number can be used to predict the number of defects to detected later, even in modified software products. We have found a very strong correlation between the number of earlier defects and that of later ones. Using this relationship, we constructed a mathematical model which may be used to estimate the number of defects remaining in software. This defect model may also be used to guide software developers in evaluating the effectiveness of the software development and testing processes. [ABSTRACT FROM AUTHOR]

Precise abstract software specification is achievable by using formal specification languages. However, nontrivial specifications are inordinately difficult to read and write. This paper summarizes the trace specification language and presents the trace specification methodology: a set of heuristics designed to make the reading and writing of complex specifications manageable. Also described is a technique for constructing formal, executable models from specifications written using the methodology. These models are useful as proofs of specification consistency and as executable prototypes. Fully worked examples of the methodology and the model building technique are included. [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]

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]

The two phase locking protocol for serializability in concurrent transaction processing is simile to comprehend but is difficult to formalize. The definition of the two phase locking class given by Papadimitriou assumes certain facts about the transaction model, which are not obvious to the reader, and dues not clarify the occurrence of events in the log of database accesses. In this paper, we propose a formal definition of the two phase locking class derived from the semantic description of the two phase locking protocol, and prove that this definition is equivalent to that given by Papadimitriou. The contributions of the paper are as follows. 1) A precise definition of the two phase locking. 2) A clarification of the occurrence and the order of all events such as lock points, unlock points, read operations, and write operations of conflicting transactions. 3) By relaxing some conditions in the new definition, we derive a new class called restricted-non-two-phase locking (RN2PL) which is a superset. of the class two-phase locking (2PL) but a subset of the class D-serializable (DSR) given by Papadimitriou. [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]

The mathematics of product-form queueing networks has traditionally dealt with the "analysis" of computer systems. That is, the system is assumed to be given and the question of how it performs is answered. In this paper the opposite process of system "synthesis" is dealt with: i.e., we answer the question of what the system topology and parameters should be in order to achieve a given performance objective. Possible research and industry applications range from the hierarchical top-down design of software systems to the management and design of computer installations. [ABSTRACT FROM AUTHOR]

In this paper, we shall derive two formulas for the average number of buckets to be examined over all possible partial match queries for Cartesian product flies and random files, respectively. The superiority of the Cartesian product file is established. A new multikey file, called a partition file, is introduced. It is shown that both Cartesian product files and random files are special cases of partition files. [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 lack of comprehensive planning prior to the initiation of a software development project is a very pervasive failing. This paper walks through a sample software development plan discussing the various areas that a software development manager should ad dress in preparing his project's plan. Various considerations and suggestions are presented for each of the management subject areas. How the user/customer can use the developer's plan to aid in monitoring of his software's evolution is also presented. Detailed planning of a software development project is necessary to the successful completion of the project. [ABSTRACT FROM AUTHOR]

The formalism of temporal logic has been suggested to be an appropriate tool for expressing the semantics of concurrent programs. This paper is concerned with the application of temporal logic to the specification of factors affecting the synchronization of concurrent processes. Towards this end, we first introduce a model for synchronization and axiomatize its behavior. SYSL, a very high-level language for specifying synchronization properties, is then described. It is designed using the primitives of temporal logic and features constructs to express properties that affect synchronization in a fairly natural and modular fashion. Since the statements in the language have intuitive interpretations, specifications are humanly readable. In addition, since they possess appropriate formal semantics, unambiguous specifications result. [ABSTRACT FROM AUTHOR]

This paper discusses the goals and methods of the Toolpack project and in this context discusses the architecture and design of the software system being produced as the focus of the project. Toolpack is presented as an experimental activity in which a large software tool environment is being created for the purpose of general distribution and then careful study and analysis. The paper begins by explaining the motivation for building integrated tool sets. It then proceeds to explain the basic requirements that an integrated system of tools must satisfy in order to be successful and to remain useful both in practice and as an experimental object. The paper then summarizes the tool capabilities that will be incorporated into the environment. It then goes on to present a careful description of the actual architecture of the Toolpack integrated tool system. Finally the Toolpack project experimental plan is presented, and future plans and directions are summarized. [ABSTRACT FROM AUTHOR]

One of the most important problems faced by software developers and users is the prediction of the size of a programming system and its development effort. As an alternative to "size," one might deal with a measure of the "function" that the software is to perform. Albrecht [1] has developed a methodology to estimate the amount of the "function" the software is to perform, in terms of the data it is to use (absorb) and to generate (produce). The "function" is quantified as "function points," essentially, a weighted sum of the numbers of "inputs," "outputs," master files," and "inquiries" provided to, or generated by, the software. This paper demonstrates the equivalence between Albrecht's external input/output data flow representative of a program (the "function points" metric) and Halstead's [2] "software science" or "software linguistics" model of a program as well as the "soft content" variation of Halstead's model suggested by Gaffney [7]. Further, the high degree of correlation between "function points" and the eventual "SLOC" (source lines of code) of the program, and between "function points" and the work-effort required to develop the code, is demonstrated. The "function point" measure is thought to be more useful than "SLOC" as a prediction of work effort because "function points" are relatively easily estimated from a statement of basic requirements for a program early in the development cycle. The strong degree of equivalency between "function points" and "SLOC" shown in the paper suggests a two-step work-effort validation procedure, first using "function points" to estimate "SLOC," and then using "SLOC" to estimate the work-effort. This approach would pro- vide validation of application development work plans and work-effort estimates early in the development cycle. The approach would also more effectively use the existing base of knowledge on producing "SLOC" until a similar base is developed for "function points." The paper assumes that the reader is familiar with the fundamental theory of "software science" measurements and the practice of validating estimates of work-effort to design and implement software applications (programs). If not, a review of [1] -[3] is suggested. [ABSTRACT FROM AUTHOR]

This paper proposes a model or paradigm for the development of parallel algorithms, gives an example of the proposed paradigm, and displays algorithms developed by application of the technique. The algorithm for the merge of two ordered fists developed through application of this technique is thought to be original. The paradigm proposed is to create composite unit operations which combine data movement between data structures with a conventional operation such as compare or add. The composite operation constructed for this study is based upon partitioning the data elements into two linear lists. Exchange of data between adjacent elements in each list are then combined with compares and adds to complete the composite operations. This composite operation can be implemented on at least the following computational architectures. 1) SIMD with all processors sharing a common memory. 2) SIMD with local memories and a linear interconnection (circular pipeline or ring network of processors). 3) Vector processor with common memory, such as a CDC CYBER 205 or a Cray Research CRAY-1. The algorithms developed all have the property of linear speed-up with the number of processing elements. The algorithms developed include sorting, merging, selection among sets, set interconnection, set difference, subset testing, and string matching. [ABSTRACT FROM AUTHOR]

A decision procedure to determine when computer software should be released is described. This procedure is based upon the cost- benefit for the entire company that has developed the software. This differs from the common practice of only minimizing the repair costs for the data processing division. Decision rules are given to determine it what time the system should be released based upon the results of testing the software. Necessary and sufficient conditions are identified which determine when the system should be released (immediately, before the deadline, at the deadline, or after the deadline). No assumptions are made about the relationship between any of the model's parameters. The model can be used whether the software was developed by a first or second party. The case where future costs are discounted is also considered. [ABSTRACT FROM AUTHOR]

This paper describes our experience specifying, implementing, and validating a record-oriented text editor similar to one discussed in [7]. Algebraic axioms served as the specification notation; and the implementation was tested with a compiler-based system that uses the axioms to test implementations with a finite collection of test cases. Formal specifications were sometimes difficult to produce, but helped reveal errors during unit testing. Thorough exercising of the implementations by the specifications resulted in few errors persisting until integration. [ABSTRACT FROM AUTHOR]

The concept of abstract syntax is commonly applied to the formal specification of programming language semantics and is also useful in the broader context of software design. This paper proposes a scheme for the representation of abstract syntax specifications in the form of easily understood charts. The structuring primitives considered are those of scalar enumeration, heterogeneous aggregation, homogeneous lists and sets, disjunction, and partial functions. Secondarily, a related system of charts for depicting particular objects with a given structure is proposed. Examples are given to illustrate the use of these diagrammatic notations in the contexts of language description and software design and documentation. [ABSTRACT FROM AUTHOR]