Search

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]

Software productivity has been steadily increasing over the past 30 years, but not enough to close the gap between the demands placed on the software industry and what the state of the practice can deliver [22], [39]; nothing short of an order of magnitude increase in productivity will extricate the software industry from its perennial crisis [39], 1671. Several decades of intensive research in software engineering and artificial intelligence left few alternatives but software reuse as the (only) realistic approach to bring about the gains of productivity and quality that the software industry needs. In this paper, we discuss the implications of reuse on the production, with an emphasis on the technical challenges. Software reuse involves building software that is reusable by design and building with reusable software. Software reuse includes reusing both the products of previous software projects and the processes deployed to produce them, leading to a wide spectrum of reuse approaches, from the building blocks (reusing products) approach, on one hand, to the generative or reusable processor (reusing processes), on the other 1681. We discuss the implication of such approaches on the organization, control, and method of software development and discuss proposed models for their economic analysis. Software reuse benefits from methodologies and tools to: 1) build more readily reusable software and 2) locate, evaluate, and tailor reusable software, the last being critical for the building blocks approach. Both sets of issues are discussed in this paper, with a focus on application generators and OO development for the first and a thorough discussion of retrieval techniques for software components, component composition (or bottom-up design), and transformational systems for the second. We conclude by highlighting areas that, in our opinion, are worthy of further investigation. [ABSTRACT FROM AUTHOR]

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]

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 describes a new method, called mutant unification, for high-performance software testing. The method is aimed at supporting program mutation on parallel machines based on the Single Instruction Multiple Data stream (SIMD) paradigm. Several parameters that affect the performance of unification have been identified and their effect on the time to completion of a mutation test cycle and speedup has been studied. Program mutation analysis provides an effective means for determining the reliability of large software systems. It also provides a systematic method for measuring the adequacy of test data. However, it is likely that testing large software systems using mutation is computation bound and prohibitive on traditional sequential machines. Current implementations of mutation tools are unacceptably slow and are only suitable for testing relatively small programs. The unification method reported in this paper provides a practical alternative to the current approaches. It also opens up a new application domain for SIMD machines. [ABSTRACT FROM AUTHOR]

There are two main contributions of this paper. First, this paper introduces the concept of a processor working set (pws) as a single value parameter for characterizing the parallel program behavior. Through detailed experimental studies of different algorithms on a transputer-based multiprocessor machine, it is shown that the pws is indeed a robust measure for characterizing the workload of a multiprocessor system. Small deviations in the performance of algorithms arising due to communication overhead are captured in this parameter. The second contribution of this paper relates to the study of static processor allocation strategies. It is shown that processor allocation strategies based on the pws provide significantly better throughput-delay characteristics. The robustness of pws is further demonstrated by showing that allocation policies that allocate processors more than the pws are inferior in performance to those that never allocate more than the pws—even at a moderately low load. Based on the results, a simple static allocation policy that allocates the pws at low load and adaptively fragments at high load to one processor per job is proposed. This allocation strategy is shown to possess the best throughput-delay characteristic over a wide range of loads. [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]

Problem orientation is gaining interest as a way of approaching the development of software intensive systems, and yet, a significant example that explores its use is missing from the literature. In this paper, we present the basic elements of Problem Oriented Software Engineering (POSE), which aims at bringing both nonformal and formal aspects of software development together in a single framework. We provide an example of a detailed and systematic POSE development of a software problem: that of designing the controller for a package router. The problem is drawn from the literature, but the analysis presented here is new. The aim of the example is twofold: to illustrate the main aspects of POSE and how it supports software engineering design and to demonstrate how a nontrivial problem can be dealt with by the approach. [ABSTRACT FROM AUTHOR]

The development of appropriate test oasis is an important issue for conformance testing of protocol implementations and other reactive software systems. A number of methods are known for the development of a test suite based on a specification given in the form of a finite state machine. In practice, the system requirements evolve throughout the lifetime of the system and the specifications are modified incrementally. In this paper, we adapt tour well-known test derivation methods, namely, the HIS, W, Wp, and UlOv methods, for generating tests that would test only the modified parts of an evolving specification. Some application examples and experimental results are provided. These results show significant gains when using incremental testing in comparison with complete testing, especially when the modified part represents less than 20 percent of the whole specification. [ABSTRACT FROM AUTHOR]

Although the benefits of requirements traceability are widely recognized, the actual practice of maintaining a traceability scheme is not always entirely successful. The traceability infrastructure underlying a software system tends to erode over its lifetime, as time-pressured practitioners fail to consistently maintain links and update impacted artifacts each time a change occurs, even with the support of automated systems. This paper proposes a new method of traceability based upon event-notification and is applicable even in a heterogeneous and globally distributed development environment. Traceable artifacts are no longer tightly coupled but are linked through an event service, which creates an environment in which change is handled more efficiently, and artifacts and their related links are maintained in a restorable state. The method also supports enhanced project management for the process of updating and maintaining the system artifacts. [ABSTRACT FROM AUTHOR]

This paper describes a multiview characterization of concurrent software and systems suitable for displaying and analyzing performance information. The views draw from well-known descriptions, and are compatible with established techniques and tools such as execution graphs, Petri Nets, State-Charts, structured design or object-oriented design, and various models for performance. The views are connected by means of a "Core model" and are used together to extract information relating to system integration, such as interprocess overheads, and the delay behavior of separate software components in complex systems. The integration of the views in the Core assists by converting results in one view (such as scheduling delay for resources) to parameters in another (such as delays along a path). The ultimate goal of the views is to support designers in making tradeoffs which involve performance, and to provide early assessment of the performance potential of software designs. [ABSTRACT FROM AUTHOR]

Software bottlenecks are performance constraints caused by slow execution of a software task. In typical client-server systems a client task must wait in a blocked state for the server task to respond to its requests, so a saturated server will slow down all its clients. A Rendezvous Network generalizes this relationship to multiple layers of servers with send-and-wait interactions (rendezvous), a two-phase model of task behavior, and to a unified model for hardware and software contention. Software bottlenecks have different symptoms, different behavior when the system is altered, and a different cure from the conventional bottlenecks seen in queueing network models of computer systems, caused by hardware limits. The differences are due to the "push-back" effect of the rendezvous, which spreads the saturation of a server to its clients. The paper describes software bottlenecks by examples, gives a definition, shows how they can be located and alleviated, and gives a method for estimating the performance benefit to be obtained. Ultimately, if all the software bottlenecks can be removed, the performance limit will be due to a conventional hardware bottleneck. [ABSTRACT FROM AUTHOR]

This paper discusses general requirements for architecture definition languages, and describes the syntax and semantics of the subset of the Rapide language that is designed to satisfy these requirements. Rapide is a concurrent event-based simulation language for defining and simulating the behavior of system architectures. Rapide is intended for modelling the architectures of concurrent and distributed systems, both hardware and software. In order to represent the behavior of distributed systems in as much detail as possible, Rapide is designed to make the greatest possible use of event-based modelling by producing causal event simulations. When a Rapide model is executed it produces a simulation that shows not only the events that make up the model's behavior, and their timestamps, but also which events caused other events, and which events happened independently. The architecture definition features of Rapide are described here: event patterns, interfaces, architectures and event pattern mappings. The use of these features to build causal event models of both static and dynamic architectures is illustrated by a series of simple examples from both software and hardware. Also we give a detailed example of the use of event pattern mappings to define the relationship between two architectures at different levels of abstraction. Finally, we discuss briefly how Rapide is related to other event-based languages. [ABSTRACT FROM AUTHOR]

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

In order to effectively optimize complex programs built in a layered or recursive fashion (possibly from reused general components), the programmer has a critical need for performance information connected directly to the design decisions and other optimization opportunities present in the code. Call path refinement profiles are novel tools for guiding the optimization of such programs, that: 1) provide detailed performance information about arbitrarily nested (direct or indirect) function call sequences, and 2) focus the user's attention on performance bottlenecks by limiting and aggregating the information presented. This paper discusses the motivation for such profiles, describes in detail their implementation in the CPPROF profiler, and relates them to previous profilers, showing how most widely available profilers can be expressed simply and efficiently in terms of call path refinements. [ABSTRACT FROM AUTHOR]

Effective management of the software development process requires that management be able to estimate total development effort and cost. One of the fundamental problems associated with effort and cost estimation is the a priori estimation of software size. Function point analysis has emerged over the last decade as a popular tool for this task Following its use over this time, however, a number of criticisms of the method have emerged. These criticisms relate to the way in which function counts are calculated and the impact of the processing complexity adjustment on the function point count. SPQR/20 function points among others are claimed to overcome some of these criticisms. This paper compares the SPQR/20 function point method to traditional function point analysis as a measure of software size in an empirical study of MIS environments. In a study of 64 projects in one organization it was found that both methods would appear equally satisfactory. However consistent use of one method should occur since the individual counts differ considerably. [ABSTRACT FROM AUTHOR]

We explore the use of software transformations for software evolution. Meaning-preserving program transformations have been widely used for program development from a fixed initial specification. We consider a wider class of transformations to support development in which the specification evolves, rather than being fixed in advance. We present a new and general classification of transformations based on their effect on system interfaces, externally observable behavior, and abstraction level of a system description. This classification is used to rearrange chronological derivation sequences containing meaning-changing transformations into lattices containing only meaning-preserving transformations. This paper describes a process model for software evolution, utilizing prototyping techniques, and shows how this class of transformations can be used to support such a process. A set of examples illustrates our ideas. Software tool support and directions for future research are discussed. [ABSTRACT FROM AUTHOR]

This paper presents an environment and a methodology for the design and rapid prototyping of data-intensive software applications; i.e., applications which perform substantial retrieval and update activity on persistent data. In the proposed approach, the application is formally specified using Logres, a database language which combines object-oriented data modeling and rule-based programming. These specifications are translated into Algres, an extended relational algebra, thus yielding a rapid executable prototype. Finally, Algres programs embedded into a conventional programming language interface may be converted to conventional programs operating on a commercial relational system. This methodology helps automate the conversion from declarative requirements to imperative code, performing several tasks fully automatically and reducing the probability of human errors, while integrity constraints and application specifications are expressed in a declarative language, at a very high level of abstraction. [ABSTRACT FROM AUTHOR]

This paper describes the knowledge representation and reasoning strategies in an automatic program synthesis architecture called ELF. ELF synthesizes CAD tools that automatically mute wires in VLSI circuits. The design space ELF confronts requires it to understand various physical technologies, to select an appropriate procedure-level decomposition, to choose algorithms and data structures, to manage any interdependencies, and to generate efficient code. ELF manages the design space using a variety of knowledge sources, including domain-specific knowledge. The manner in which knowledge is used determines the representation method of choice. For example, ELF uses languages to describe knowledge that is subject to modification, rules for cause-and-effect knowledge, and graphs and templates to capture knowledge interdependencies. We illustrate the effectiveness of our ideas via a tour through the synthesis steps for a specific routing tool, and a brief discussion of the performance of the resulting synthetic router as measured against an industrial tool. [ABSTRACT FROM AUTHOR]

The paper proposes a comprehensive framework for representing and using nonfunctional requirements during the development process. The framework consists of five basic components which provide for the representation of nonfunctional requirements in terms of interrelated goals. Such goals can be refined through refinement methods and can be evaluated in order to determine the degree to which a set of nonfunctional requirements is supported by a particular design. Evidence for the power of the framework is provided through the study of accuracy and performance requirements for information systems. [ABSTRACT FROM AUTHOR]

This paper summarizes our experience in the Programmer's Apprentice project in applying knowledge representation and automated reasoning to support software development. We describe a system, called Cake, that comprises seven layers of knowledge representation and reasoning facilities: truth maintenance, Boolean constraint propagation, equality, types, algebra, frames, and Plan Calculus. We also include sessions with two experimental software development tools implemented using Cake: the Requirements Apprentice and the Debugging Assistant. [ABSTRACT FROM AUTHOR]

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

The performance of transaction processing systems with two-phase locking (2PL) can be degraded by transaction blocking due to lock conflicts and aborts to resolve deadlocks. This paper develops a straightforward analytic solution method, which takes into account the variability of transaction size (the number of lock requests), an issue which has been ignored in most earlier studies. We first obtain analytic expressions for the probability of lock conflict, probability of deadlock, and the waiting time per lock conflict. We then develop a family of noniterative analytic solutions to evaluate the overall system performance by considering the expansion in transaction response time due to transaction blocking. The accuracy of these solutions is verified by validation against simulation results. We also introduce a new measure for the degree of lock contention, which is a product of the mean number of lock conflicts per transaction and the mean waiting time per lock conflict (when blocked by an active transaction). It is shown that the variability in transaction size results in an increase in both measures as compared to fixed-size transactions of comparable size. It follows that performance studies of 2PL which ignore the variability in transaction size underestimate the effect of lock contention on system performance. We also provide a solution method for the case when the processing times of transaction steps are different. The solution method is used in the analysis of the two-phase transaction processing method, according to which a transaction is first executed without requesting any locks, prefetching data (from disk) for the second execution phase with locking. In high lock contention environments, this approach may result in a significant improvement in performance compared to 2PL, which is due to the reduction in lock-holding time, since no disk 10 is required in the second phase of the execution, but this is achieved at the cost of additional CPU processing due to repeated execution. [ABSTRACT FROM AUTHOR]

Data structure diagrams are two-dimensional figures made up of lines that aim to pictorially indicate the interrelationships of the elements of a data structure. This paper collects the various rules and factors of aesthetics that go into the way we draw data structure diagrams. We formulate the various subjective factors into computable objectives and numeric parameters. These are distilled from a large number of data structure drawings as found in various textbooks. We reveal that the rules used have not reached a level of acceptance compared to the relevant rules in engineering graphics. We also outline the internal architecture of a (sub)system that we are building that helps draw data structure diagrams. [ABSTRACT FROM AUTHOR]

While the benefits of modular software development are widely acknowledged, there is little agreement as to what constitutes a good module interface. Computational complexity techniques allow us to evaluate algorithm time and space costs but offer no guidance in the design of the interface to an implementation. Yet, interface design decisions often have a critical effect on the development and maintenance costs of large software systems. In this paper we present criteria that have led us to simple, elegant interfaces. These criteria have been developed and refined through repeated practical application. We present the criteria in detail and illustrate their use with concrete examples. [ABSTRACT FROM AUTHOR]

Software size estimation has been the object of a lot of research in the software engineering community due to the need of reliable size estimates in the utilization of existing software project cost estimation models. This paper discusses the strengths and weaknesses of existing size estimation techniques, considers the nature of software size estimation, and presents a software size estimation model which has the potential for providing more accurate size estimates than existing methods. The proposed method takes advantage of a characteristic of object-oriented systems, the natural correspondence between specification and implementation, in order to enable users to come up with better size estimates at early stages of the software development cycle. Through a statistical approach the method also provides a confidence interval for the derived size estimates. The relation between the presented software sizing model and project cost estimation has also been considered. [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 describes a computer-aided software development process design. This is a computerized intelligent tool designed to aid managers of software development projects in planning, managing, and controlling the development process of medium to large scale software projects. The application of this computerized tool should help reduce the uncertainties involved in the budget, personnel, and schedule planning of software development projects. A dynamic model for the software development and maintenance life cycle process is described here. This dynamic process is composed of a number of time-varying, interacting developmental phases. Each developmental phase is characterized both by its intended functions and by the requirements for personnel, budget, and schedules. System dynamics is used to model and simulate the dynamic process of soft- ware development. The model is implemented as the software life cycle simulator (SLICS). [ABSTRACT FROM AUTHOR]

While validation of user requirements has become an important goal for information system designers, very little empirical research has been done in this area. Many methodologies have been presented as the best procedures for achieving user validation of design. This paper looks at four of these methodologies in four different experimental settings. In the four experiments the following treatments were examined: HIPO versus system flowcharts, DFD versus narrative, DFD versus Warnier-Orr diagrams, and DFD versus HIPO. The main result of all four experiments was that choice of design methodology had no effect on the level of user understanding of system requirements. [ABSTRACT FROM AUTHOR]

In systems which contain graphical user interfaces, one of the most difficult tasks facing the system implementer is translating graphical inputs into the concepts and structures appropriate to the application. Conversely, the process of translating application structures into graphical images can be equally difficult. Almost all applications using interactive computer graphics contain important structures and concepts which are deeper than the geometries used to display them to the user. One of the major tasks of the system implementer is to cause the user interface to reflect this deeper structure accurately so that it may be directly manipulated by the user. Currently, there are few tools to aid the system implementer in this task. This paper will describe a new tool, the Higgens user interface management system, which can automate much of this task for a wide class of systems using interactive computer graphics. By using new graphical techniques along with new techniques for incremental attribute evaluation, the Higgens system is able to generate graphical user interfaces automatically from a high-level interface specification. These specifications are primarily nonprocedural in nature. They describe how graphical images can be automatically derived and updated based on application entities, and how graphical inputs can be translated back into terms which are appropriate to the application. Since these things can be done automatically by the system based on a high-level specification, much of the difficulty of creating graphical interfaces can be eliminated. [ABSTRACT FROM AUTHOR]

This paper presents a new interactive synthesis algorithm to construct two communicating finite-state machines (protocols), which exchange message over two unidirectional FIFO channels when the function of the protocol has been given. The synthesis algorithm first constructs the global state transition graph (GSTG) of a protocol to be synthesized and then produces the protocol. It is based on a set of production rules and a set of deadlock avoidance rules, which guarantee that complete reception and deadlock freeness capabilities are provided in the interacting processes. This synthesis algorithm prevents a designer from creating unspecified reception and nonexecutable transition, avoids the occurrence of deadlocks, monitors for the presence of buffer overflow, although it does not help the designer synthesize a protocol to achieve some particular functionality. [ABSTRACT FROM AUTHOR]

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

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

The conformance testing of MAP-specified protocol implementations is a complex activity. This paper describes major components of the MAP 2.1 Conformance Test System. A comparison between protocol conformance testing and program testing sets the context. Background on the scope and process of dynamic conformance testing is provided. The architecture of the Test System is presented, first in terms of the developing ISO framework, and then in terms of run-time components. Several specific tools which comprise the Test System are described. These tools include test engines, a high-level control tool, monitoring and analysis tools, and document handling tools. Benefits and limitations of the test tools are examined. Conclusions and suggestions for future efforts are provided. [ABSTRACT FROM AUTHOR]

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

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

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]

RTAG is a language based on an attribute grammar notation for specifying protocols. Its main design goals are: 1) to support concise and easily understood expression of complex real-world protocols, and 2) to serve as the basis of a portable software system for automated protocol implementation. This paper summarizes the RTAG language, gives examples of its use, sketches the algorithms used in generating implementations from these specifications, and describes a UNIX®-based automated implementation system for RTAG. [ABSTRACT FROM AUTHOR]

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

Managing software engineering projects requires an ability to comprehend and balance the technological, economic, and social bases through which large software systems are developed. It requires people who can formulate strategies for developing systems in the presence of ill-defined requirements, new computing technologies, and recurring dilemmas with existing computing arrangements. This necessarily assumes skill in acquiring adequate computing resources, controlling projects, coordinating development schedules, and employing and directing competent staff. It also requires people who can organize the process for developing and evolving software products with locally available resources. Managing software engineering projects is as much a job of social interaction as it is one of technical direction. This paper examines the social arrangements that a soft- ware manager must deal with in developing and using new computing systems, evaluating the appropriateness of software engineering tools or techniques, directing the evolution of a system through its life cycle, organizing and staffing software engineering projects, and assessing the distributed costs and benefits of local software engineering practices. The purpose is to underscore the role of social analysis of software engineering practices as a cornerstone in understanding what it takes to productively manage software projects. [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]

A family of syntactic complexity metrics is defined that generates several metrics commonly occurring in the literature. The paper uses the family to answer some questions about the relationship of these metrics to error-proneness and to each other. Two derived metrics are applied; slope which measures the relative skills of programmers at handling a given level of complexity and r square which is indirectly related to the consistency of performance of the programmer or team. The study suggests that individual differences have a large effect on the significance of results where many individuals are used. When an individual is isolated, better results are obtainable. The metrics can also be used to differentiate between projects on which a methodology was used and those on which it was not. [ABSTRACT FROM AUTHOR]

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

Testing has long been in need of mathematical underpinnings to explain its value as well as its limitations. This paper develops and applies a mathematical framework that 1) unifies previous work on the subject, 2) provides a mechanism for comparing the power of methods of testing programs based on the degree to which the methods approximate program verification, and 3) provides a reasonable and useful interpretation of the notion that successful tests increase one's confidence in the program's correctness. Applications of the framework include confirmation of a number of common assumptions about practical testing methods. Among the assumptions confirmed is the need for generating tests from specifications as well as programs. On the other hand, a careful formal analysis of the usual assumptions surrounding mutation analysis shows that the "competent programmer hypothesis" does not suffice to ensure the claimed high reliability of mutation testing. Hardware testing is shown to fit into the framework as well, and a brief consideration of it shows how the practical differences between it and software testing arise. [ABSTRACT FROM AUTHOR]

A fundamental step in the software design process is the selection of a refinement (implementation) for a data abstraction. This step traditionally involves investigating the expected performance of a system under different refinements of an abstraction and then selecting a single alternative which minimizes some performance cost metric. In this paper we reformulate this design step to allow different refinements of the same data abstraction within a computation. This reformulation reflects the fact that the implementation appropriate for a data abstraction is dependent on the behavior exhibited by the objects of the abstraction. Since this behavior can vary among the objects of a computation, a single refinement is often inappropriate. Accordingly, three frameworks are presented for understanding and representing variations in the behavior of objects and, thus, the potential for multiple implementations. The three frameworks are based upon: 1) a static partitioning of objects into disjoint implementation classes; 2) static partitioning of classes into implementation regions; and 3) dynamic partitioning of classes into implementation regions. These frameworks and analytic tools useful in investigating expected performance under multiple implementations are described in detail. [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 article presents information on articles published in September 1999 issue of the journal "IEEE Transactions on Software Engineering." Computer systems are used to perform many critical tasks, including guiding aircraft, scheduling railroads, assisting in surgery, controlling nuclear reactors, performing financial transactions and supporting military command and control. Although the study of these properties evolved as separate disciples, they have in common the fact that a user must have a high degree of confidence in the service that the system delivers. The first research paper in this issue of the journal considers the problem of electing a leader in a distributed system that may become partitioned. Since the partitions will not be able to communicate with each other, it is necessary to elect a leader for each partition. The second research paper addresses the problem of developing an accurate fault model that can be used to evaluate the dependability of a system. The third paper presents an approach to the quantitative evaluation of the security of operational systems.

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.

There will be a rotation of editors of the periodical "IEEE Transactions on Software Engineering." The periodical is receiving about 25 papers a month, not counting special issue papers. Upon receipt of a paper, the goal is to have the acknowledgment letter to the author and the paper to the editor within five working days.