Although computers were invented barely fifty years ago, their enormous value and impact on society has already relegated much of computing discipline into a commodity status. While the pedagogical theories of computing have failed to keep pace with the rapid technological advances, of immense importance, a systematic approach to achieving reliable systems design despite complexity compounding on virtually daily basis, is sorely lacking. The immense array of sub-disciplines of computer science including digital hardware, computer architecture, programming languages, databases, networking, artificial intelligence, software engineering, etc. are rapidly coalescing into a new sub-discipline, labeled as the "service industry."

Although computers were invented in 1945, barely fifty years ago, their enormous value and impact on society has relegated much of computing discipline, fortunately or unfortunately, into a commodity status already. Not only are semiconductor-based computers inherently fast, the unique use of bootstrapping to use computers to design even faster computers has brought us to the precipitous edge of unprecedented computing performance and exceptionally powerful systems. As unintended consequences, while the pedagogical theories of computing have failed to keep pace with the rapid technological advances, of immense importance, a systematic approach to achieving reliable systems design despite complexity compounding on virtually daily basis, is sorely lacking. As a result, systems design is spinning out of control and urgently warrants a new approach to rein it in so that they may serve humanity in a safe and reliable manner. A quick analysis of the evolution of IBM Corporation is highly revealing of the challenges faced by the industry. IBM began its journey as a giant in computer hardware design including the legendary IBM 7044 and then quickly turned into a turn-key systems company with its proprietary operating system in the 1970s. By the late 1970s, the dawn of the VLSI age relegated computer hardware to the level of a commodity and IBM's desire to maintain a high profit margin forced it to turn to software as its core competency. The value of data and its manipulation became a dominant force in the marketplace and IBM emerged as a specialist in database-oriented products. Stiff competition from Oracle and other database vendors, and with the introduction of Microsoft's Access have steadily eroded IBM's cutting edge to the point where IBM is presently being forced to evolve into an entirely new company and a major player in the service industry

The evolution and dominance of service functions in addition to their distinguishing features has been the subject of study for years. Service functions aim to satisfy and facilitate the needs of their customers. In doing so, service providers design the service functions so that the customers feel comfortable and convenient when using them. The evolution of technology and automation has enabled functions like knowledge-intensive man-machine interactions to be flexible and user friendly. In this paper, we discuss a wide range of interconnected topics, emphasizing the multifaceted nature of service functions. These areas include the evolution of service functions and their associated systems and products, as wall as the consequent creation of implicit requirements, the technology transfer process, and the error proneness due to intense and prolonged interaction. We argue that by proper 'humanization and personalization' the service-based interactive systems can be made easy for the customer to use and enjoy personalized services. We introduce an anonymous opinion survey mechanism for encouraging new service industry. We conclude that the existence of a strong interaction between knowledge and technology growths is shown by 'The Kozmetsky Effect' model and consider the methodology to accelerate the convergence of knowledge-technology transfer phases at the Kozmetsky Effect model

Software products never grow old, or fade away. The designs, their patterns and the ideas embodied in them are carried over and over again for a long time. In this presentation we explore the venues of immortalizing the software systems and the intellectual components they are made up of. We argue that such indestructible systems must embody crucial application ideas and functions but also exemplify user oriented architectural forms that personify ease of use, crash free operations, and user maintainable and /or maintenance free within the specified constraints. We approach the issue by recognizing the implicit fact that a software malfunction is a disaster, however small it is. Based on our previous studies in disaster hardening systems, we apply the ideas used in preventing and mitigating disasters to the methods of designing and developing software systems. We show the mutual commonality as well as areas where methods used in one can be carried over effectively into the other.

Summary form only given. We identify the important overlap between the two areas of software development and disaster mitigation. The software change management and maintenance methods can greatly benefit by ideas from disaster technology. The software developed under damage and disaster control techniques would be robust, resilient and long lasting, the virtues eminently needed in the current open-systems software environments. Importing methods and techniques from disaster engineering into software engineering can also help in dealing with the issue of emergent behaviors which are created by unexpected changes that could occur while modifying and maintaining software systems. We are starting to create solid bricks to build great software castles of the future, which are not just beautiful to look at but formidable extruding strength and resilience to support future supercritical and complex applications created in a democratically managed open systems environment. Systems on these principles will be of high quality, easy to use and maintain. They will also be cost effective because of the availability of reusable 'disaster hardened' software bricks (components).

The existing definitions for infrastructure notion do not seem to completely capture its impact, outreach, and the importance of entities it represents. Thorough understanding of the concept is necessary if we are to develop long-lasting adaptive infrastructures, which can handle the continuously increasing service demands and threats. We study the infrastructure notion to understand and clarify its definition, impact, and scope. We take different perspectives for exploring subtle relationships between a system and its infrastructure. We provide various classifications to cope with the inherent complexity of the infrastructure notion. Our emphasis is the information technology infrastructure, its security, and survivability.

Complex systems, services and enterprises are very dependent on computer-communication technology and in particular to their supporting and controlling software systems. This paper describes aspects of software system quality from different points of view. It provides a historical overview of the evolution of software quality and the means and methods used to achieve and enhance it. The traditional software quality models trace their origins to the well-established manufacturing industries. Since quality of a product consists of many attributes, we identify the commonly accepted established entities that conform to our vision of good quality. Notions and meanings of quality vary across disciplines and application domains.

This presentation is concerned with digital product evolution, particularly those asociated with consumer needs. We shall consider evolution as the implicit result of change needed for the improvement? and refinement, extension of its functions and performance. Our y-pose is tc study the ruies and concerns that reguiate product innovation and evolution. It is well known that consumer digital products have short life cycles and shelf lives. The market generally has a wide variety of products satisfying the same consumer needs. The pressure on the product designers and manufacturers is to shorten development time, reduce manufacturing costs are refined derivatives of earlier versions, we recognize the creation of product families, where members of a family exhibit the same core functionalities, compatibilities and interoperabilities. We provide several examples of such product families and their impact in the digital product area. The and trying to satisfy the motto, ‘Be first, be right and also be the best’. They naturally need to be paranoid to survive (Andrew Grove). The new products’ architect and the designer, now, have to explore flexible architectures for the whole family of products covering a long period of time, to fit the terrain of different technologies and needs. We shall distinguish the products from the product lines, product generations and the product families. We review models from other disciplines like biology, economics, statistics, physics etc., that have analogical overtones to digital consumer products to lend us insight into the nature of the evolutionary processes We discovered that the life-cycle models of biology lit well with those of products and their families. We show that their properties are self-similar (Mandelbrot). Since product evolution implies improvement we show that the life-cycle phases (transformations) include knowledge gathering, knowledge reuse, knowledge dissemination (transfer) and knowledge creation. We conclude by showing that these steps are implicitly included in the some of the real advanced product development organizations like Sony and Microsoft.

Reverse engineering and reengineering are two major research challenges in the software maintenance process. Reverse engineering is the process of rederiving the specification of a program; and reengineering is the process of modifying an already existing software to add additional functionalities or to correct any malfunction. The difficulty in these tasks are that software development commonly involves many software engineers with implicit assumptions about the behavior of each module. These assumptions are not documented and often leads to inconsistencies in the code. During reverse engineering, such assumptions may not be uncovered. These assumptions usually have complex dependencies, and are the cause of a lot of bugs when the software is reengineered. Many approaches and prototype tools have been developed to address these issues. Reverse engineering and automated program understanding tools have been developed to support the reverse engineering tasks; while various theoretical works on structural program analysis and programs for automated ripple effect analysis have attempted to deal with the reengineering process. These works can be classified into two main types of approaches: those using shallow knowledge or knowledge about the structure of the system and those utilizing deep knowledge or knowledge about the semantics and behavior of the software system. In this paper, we attempt to survey works that have been done under these two broad categories of approaches to deal with the software maintenance tasks, evaluate the strengths and drawbacks of each approach, and attempt to draw a conclusion on the advantages and disadvantages of the two main lines of approaches.

We present a storage management system that has the ability to adapt to the data access characteristics of the application that uses it based on collection and analysis of runtime statistics. This feature is especially useful in the storage management layer of database systems, where applications exhibit relatively predictable access patterns. Adaptive reorganization is performed by the storage management system in a manner that optimizes the access patterns of the system for which it is used. We enhance the log-structured storage system that naturally caters for write optimization, with the addition of a statistics collection mechanism to determine data access patterns of applications. The storage system can serve as a testbed for a variety of statistics analysis and clustering mechanisms. Higher level application-specific data clustering mechanisms can be used to override the storage system's low-level clustering mechanisms. In addition, the analysis techniques and reorganization scheme can be used in other storage systems. Performance results from our prototype show potential response time speedups of up to 83 percent over the basic log-structured file system in the best case, using a combination of storage reorganization and prefetching.

We present a storage management system that has the ability to adapt to the data access characteristics of the application that uses it, based on collection and analysis of runtime statistics. Adaptive reorganization is performed by the storage management system in a manner that optimizes the access patterns of the system for which it is used. Application-specific data clustering mechanisms can also be specified to override the default mechanisms provided by our prototype. Performance results from our prototype show potential read time speedups of over 80% in the best case, using a combination of storage reorganization and prefetching.

We present a partial instantiation theorem prover (INSTANT) which handles sentences in first order logic in clausal or non clausal form. INSTANT uses a variant of the GSAT algorithm for determining the satisfiability of a propositional sentence to increase its speed. The algorithm used in INSTANT can be parallelized with good speedup to improve performance. INSTANT is designed for matching requests for resources with available resources over a network. Environments in which distributed resource location takes place through matching of requests and advertisements include CORBA's Object Trading Service and communication between agents using KIF and KQML.

We propose a class of algorithms which gives best-effort answers to problems in first-order logic given a bound on the resources available for reasoning. The algorithms in this class generate and attempt to solve S/sub 1/ and S/sub 3/ approximations to the input problem, then use the results to determine the most likely solution to the input problem. We show that an algorithm in this class outperforms theorem provers which attempt to solve the problem directly.

Influence diagrams have been used effectively in applied decision analysis to model complex systems, identify probabilistic dependence and characterize the flow of information. We argue that influence diagrams are a natural fit for decision making for software risk analysis. Our approach is very general and can be adapted for various type of software risks. We use software metrics collected at various stages of software development. The metrics data is analyzed by an influence diagram to identify the sources of errors and predict future risk items like reliability, complexity, schedule, or non-reusability.

Recent years have witnessed the rapid growth of mobile computing environments. One of the major concerns in such environments is security, specially in the context of wireless communications. We describe some of the important issues which need to be addressed in designing a security scheme for mobile communications. These include autonomy of communicating entities, mobility of the users, limitations of the hardware, etc. We describe a scheme which addresses the above issues, and provides a correct and efficient mechanism to establish secure communications. Our scheme provides authentication of the communicating entities, location privacy, and secure messaging.>

The software industry is increasingly working towards the goal of software reuse. The use of metrics to assess software modules has long been advocated by the US Army. A combination of these two trends should make it possible for a software developer to predict the metrics of the composite software system given the metrics of the component software modules. It should also enable the developer to make an appropriate choice among many possible modules available in the software repository. The paper presents an approach to solve the above two problems. The metrics suite used is an extension of the US Army STEP metrics, the approach is simulation based, and its theoretical validation is provided from approximation theory.>

DOMINO is a software maintenance tool that assist software developers to understand and modify software systems. DOMINO supports facilities for the definition and maintenance of software objects created at each software development stage, from requirements analysis to implementation; finding information about various software objects and their relationships; automating the computation of ripple effects caused by a modification; and tracing an implemented object back to its corresponding specification and vice versa. The underlying technique used in DOMINO is based on the loose hierarchical truth maintenance system, a derivative of De Kleer's assumption-based TMS. This paper provides an outline of the DOMINO system, its conceptual model, its architecture, the software objects supported by DOMINO, and the representations used to characterize software objects and the relations between them.>

We present RiskExpert, an expert system tool that can be used by management for analyzing metrics data and predicting fixture results based on past trends and expert knowledge. The expert advice generated by RiskExpert from metric data analysis can greatly aid in reducing various risks involved in a software project life cycle, such as cost overruns and schedule delays. RiskExpert also allows the manager to pose questions on expected results for hypothetical projects that can be dynamically created, enabling him to pose What If? questions and analyze the results if he had done things a different way.>

In this paper, we characterize the performance of parallel file transfers using the Zebra striped network file system by means of distributed discrete-event simulation model which uses a variation of the conservative timestamping-technique. The simulator is a powerful tool that can be adapted to model related systems such as multiprocessors and distributed shared memories. Preliminary simulation results confirm the results in published literature. Experiences with building the distributed simulator are also discussed.

We have built a distributed discrete-event simulator called Empathy. This paper describes some aspects of the Empathy simulation algorithm. Optimistic simulation incurs enormous memory overhead. In this paper, we propose an algorithm for optimistic simulation that is based on the concept of local conservative control for commitment of events. This algorithm reduces the memory overhead by an average of 30% and reduces the aggregate computational time for simulation by up to 25%.>

The authors present the techniques and architecture of a knowledge-based support system currently under development for risk analysis in software generation and reuse processes. They describe the main components and their relationships. Another tool that supports risk reduction is for consistency management. This tool analyzes the effects of changes and repairs.

Optimistic distributed discrete-event simulation incurs significant memory overhead because it stores state vectors with each processed but uncommitted message. The authors propose an application-independent scheme that substantially reduces this overhead, while also improving the simulation performance. Global control in optimistic simulation is replaced by local conservative control, and the concept of hierarchical layers of commitment of messages is introduced. The memory overheads imposed by Time Warp are reduced, and the performance of the Time Warp algorithm is improved. These two objects are achieved by ensuring that the state of the system as a whole is not impeded by the slowness of a few logical processes.>

Exploration is made of how methods of truth maintenance may be applied in the engineering of integrated, dynamic systems. In the life of a large system, it is not possible to foresee every significant event which may affect the behavior of the system. Truth maintenance techniques may prove useful in the production and maintenance of these large systems. A discussion is presented of how it is the decision making aspects of a system which change. Both the information on which the authors base their decisions and strategies for decision making change. Truth maintenance is discussed with respect to preserving the models of specifications and the models of programs.>

Deals with the specifications for the development of an expert tool for the automatic optical detection and recognition of the connectivity among devices in digital electronic circuits and the understanding of the circuits functionality. In particular, the proposed tool, called ANTISTROFEAS, uses expert knowledge recognizing and understanding electronic circuits without the use of their associated database. The ANTISTROFEAS tool will use classical picture processing methods in combination with heuristics and knowledge acquisition schemes. The expert tool proposed is used for understanding of 'unknown' electronic circuits, or where the complexity of the circuit is too great, so that any human searching effort requires long time for reliable results.>

Software engineering (SE) needs to make substantial breakthroughs in many different areas to allow order of magnitude improvements in software development times, software quality, and system cost. Artificial intelligence (AI) is uniquely positioned to help the SE research community in many of these areas, and we examine issues in AI for SE research. Given the fuzzy definition of AI, we provide a list of AI techniques to identify how much AI there is in specific AI for SE research. We recommend using the divide and conquer approach for SE automation and provide criteria for dividing the SE problems. We provide a vision of the future CASE environment, a knowledge and database management system at the center in a client-server architecture, and argue that it constitutes an ideal test-bed for research in AI for SE. We recommend an AI for SE research approach that includes dividing the problem up, using protocol analysis, implementing on a realistic CASE environment, and evaluating in industrial settings. We give criteria to evaluate applications of AI to SE including generality, scalability, and combinability. We conclude that AI will help SE to make slow and steady progress, but that it constitutes no silver bullet.

Conventional expert systems based on a single flat knowledge base have fared well in solving a narrow range of problems. Their architectures, however, do not extend to large applications like automated factories, which require multidisciplinary knowledge and are geographically distributed. To solve multidisciplinary problems, a knowledge-based system must be able to: reason about the need for cooperation, understand global knowledge to locate relevant expert systems and select appropriate cooperation plans. Cooperations models to characterize three essential decisions in the cooperation process are proposed. A computational method is devised to decide if an expert system has enough knowledge to solve a given problem or if it needs to consult with other expert systems. The use of a yellow-pages technique to represent global knowledge and to select appropriate cooperation plans is proposed. The approach lets expert systems autonomously resolve the three fundamental decisions in cooperation at run time, in contrast to contemporary approaches in which the decisions are made at design time by the programmers.>

A system for analyzing program structures is described. The system extracts relational information from C programs according to a conceptual model and stores the information in a database. It is shown how several interesting software tasks can be performed by using the relational views. These tasks include generation of graphical views, subsystem extraction, program layering, dead code elimination and binding analysis.>

The evolution support environment (ESE) system, which provides a framework for capturing and making available semantic information about software components of an evolving software system, is described. The goal in the design of the ESE system was to provide integrated support for management of software architecture configuration, life-cycle configuration, and version control. Software architecture configuration management allows tracking of interconnections among software components that make up a system. Life-cycle management allows traceability among specifications, design, code, and test cases during software development. Adding version control allows specific versions of software objects and their associated objects, such as specifications and test cases, to be retrieved. The authors' experience with the use of the system is discussed.>

Neural networks have traditionally been applied to recognition problems, and most learning algorithms are tailored to those problems. The authors discuss the requirements of learning for generalization, which is NP-complete and cannot be approached by traditional methods based on gradient descent. They present a stochastic learning algorithm based on simulated annealing in weight space. The convergence properties and feasibility of the algorithm are verified.>

An adaptive hierarchical routing protocol based on the extension of the new Arpanet scheme is proposed and its simulated performance is presented. The protocol can adapt to rapidly changing environments and works for arbitrarily large networks. A number of existing schemes as well as the proposed scheme are simulated under many different environments and clustering structures. The proposed protocol is found to be superior to the other protocols tested in many different types of network traffic and topological configurations. The results indicate that intercluster links must be reliable, because (1) the failure of these links can significantly degrade the routing performance, even though the protocol does not degrade as badly as the existing scheme and (2) hierarchical routing protocols usually prefer small clusters, which means that there will be many intercluster links. The tradeoff between two conflicting performance criteria, response speed and communication overhead, is shown.>

The authors provide an overview of the current research and development directions in knowledge and data engineering. They classify research problems and approaches in this area and discuss future trends. Research on knowledge and data engineering is examined with respect to programmability and representation, design tradeoffs, algorithms and control, and emerging technologies. Future challenges are considered with respect to software and hardware architecture and system design. The paper serves as an introduction to this first issue of a new quarter.>

Designing concurrent systems has been shown to be difficult due to state explosion problems. A synthesis technique using Petri nets is proposed to tackle the problem. A set of rules has been proposed to guide designers incrementally expanding Petri nets under design while maintaining the logical correctness. These rules cover the semantics of concurrency, exclusiveness, cyclicity, and interactions.>

The authors present a procedure for computing the cycle time of concurrent systems modeled by a restricted class of Petri nets, i.e. decision-free and safe persistent nets. The procedure is based on formulating the cycle time computation as a minimal cost-to-time ratio cycle problem. The result is an efficient algorithm with a computational complexity of O(n/sup 3/log/sub 2/ n). By using an example with a stochastic counterpart, it is shown that the results are consistent with those obtained by more complex Markov analysis.>

Running simulations in a distributed manner by decentralizing the advancement of clock potentially allows significant speedup. However, because time may not advance at the same rate in the target system and the testbed system, deadlocks that do not occur in the target system can occur during distributed simulation. Previous approaches to deadlock resolution incur either high computation overhead through centralized coordination or high communication overhead through a fully distributed solution. Hierarchical decentralized algorithms that take advantage of the locality of these deadlocks are presented. Overheads associated with time advancement are computed analytically, so that appropriate clustering policies can be designed.>

Installing an update in an indexed database of size N takes O(log N) disk accesses, because of a root-leaf path traversal. If the installing of updates is deferred for a while, until a certain number n of them have been collected, substantial savings can be obtained. Two efficient algorithms for performing such grouped updates are presented and analyzed. The conditions on n are derived for which these algorithms perform better than straightforward update installation. A technique called model scaling, which is borrowed from the domain of fluid mechanics, is used to show how small simulations can be used for the accurate modeling of real-life environments. Some experimental results are presented to validate the analysis as well as justify the assumptions made.>

Genesis is a software-engineering-based programming environment geared to support big software projects. The authors first discuss a reusability-driven development methodology that advocates software development based on reusability considerations. Then, they discuss the tools and techniques provided in Genesis to support this methodology. Techniques are suggested for improving the retrievability, composability, and understandability of software resources. Retrievability is improved by use of ESL (entity specification language) for tying resources through attributes and relations. Composability is improved through a mechanism called functional composition that provides considerably more generality than Unix pipes for composing programs. Understandability is improved by the use of program abstractors.>

It is generally accepted that object-based systems provide a simple and elegant paradigm for general-purpose programming that meshes well with data models. Such systems are characterized by three core concepts: object, class, and message. As a consequence we are able to define object types with operations, to structure objects according to their properties, and to have objects that share properties. All these features make them suitable to serve as a basis for the next generation computing systems. However, they have been criticized for the lack of declarative semantics which is an essential feature for knowledge-based applications. For this purpose we propose the framework of logic-oriented object bases, i.e. databases that are constructed based on object model and augmented by mathematical logic. Adopting logic as a formal means for knowledge representation, we have developed both algorithmic and knowledge-based approaches to relate objects, to evaluate declarative queries that involve high level concepts, and to schedule declarative update requests such that changes to objects can be made consistently.

Petri net is a powerful model for analyzing communication protocols because they share many common properties. Currently, protocol analysis suffers the state explosion problem especially for error-recoverable protocols and multi-party protocols. Protocol synthesis relieves this problem by generating new and complicated protocols from simple subsets of the protocol models. Reduction analysis provides theoretical ground for correct synthesis or expansion. Thus, reduction is a very important research area. In this paper, we present a general Petri net reduction algorithm that reduces the number of states while preserving all desirable and undesirable properties. To the best of our knowledge, this is the first general Petri net reduction algorithm for protocol analysis. We first present and extend Dong's [DON 83] definition of WBMs to include more subnets as WBMs. To render the reductions automated, a new concept of simple well-behaved modules (SWBMs) is introduced. Recursively performing reductions of SWBMs, complicated WBMs can be reduced. A main program is written to implement this recursive procedure. The problem is then reduced to finding conditions for SWBMs. We do this by progressing from simpler SWBMs to more complicated ones, i.e., from single-arc ones to multi-arcs ones. Finally, we demonstrate the usefulness of this algorithm by applying it to the state exploration in protocol synthesis. Other applications such as error detection, performance evaluation, and software engineering will be discussed in future.

We have developed a correct, general, and efficient procedure of synthesizing two-party error-recoverable protocols for noisy channels where messages could be lost, corrupted, and/or missequenced. The state explosion problem has been tackled by synthesizing the error-recoverable protocol (ERP) from its noiseless local entity model using certain rules. This reduction arises from the approaches of local modeling and elaboration. We expect that these two approaches will also play a major role in tackling the complexity problems in designing multi-party protocols. Measures of efficiency and functionality improvements have been discussed.

In this correspondence, we study the problem of finding optimal reconfiguration strategies for a class of reconfigurable fault- tolerant computer systems in which there is no repair in failed components. The problem of finding optimal reconfiguration strategies consists of determining, for each failed state of the system, the operational state into which the system should reconfigure itself. We presented a stochastic model for the above class of reconfigurable computer systems. Based on this model, we construct a polynomial-time algorithm for finding optimal reconfiguration strategies.

It is asserted that ad-hoc programming techniques do not work in the development of big software systems. The programs faced in developing large software include starting from fuzzy and incomplete requirements; enforcing a methodology on the developers; coordinating multiple programmers and managers; achieving desired reliability and performance in the system; managing a multitude of resources in a meaningful way; and completing the system within a limited time frame. The authors examine some of the trends in requirement specification; life cycle modeling; programming environments; design tools; and other software engineering areas for tackling the above problems. The authors suggest several phase-independent and phase-dependent techniques for programming in the large. It is shown how research in automatic programming, knowledge-based systems, metrics, and programming environments can make a significant difference in the ability to develop large systems.

In the past, a number of methods have been proposed to model and validate communication protocols that have already been designed. However, design criteria and design aids are still lacking for designing correct protocols. The objective of developing automated protocol synthesizers is to provide a systematic way of designing new communication protocols such that their correctness can be ensured.

In this paper, we show that the simple file allocation problem in computer science is isomorphic to the single commodity warehouse location problem in operations research. In simple file allocation, costs due to query and update accesses and storage are considered. Design requirements such as reliability, availability, and delay are not taken into account. Due to this isomorphism, many techniques which have been developed for the warehouse location problem can be applied to solve the simple file allocation problem. Furthermore, there are techniques and conditions developed for one problem which match closely with techniques and conditions developed for the other problem. Based on a combined set of conditions developed in computer science and operations research, a heuristic for file allocation is presented.

In distributed databases, deadlocks may occur due to conflicts in data file lockings A system is in a deadlock if and only if there is a directed cycle in its demand graph. However, due to the inherent communication delay in a distributed system, it is not easy to construct a consistent demand graph for a distributed system. In this paper, three deadlock detection protocols are discussed. The first protocol uses two communication phases. The second protocol uses a single communication phase. Based on the second protocol, a one-phase hierarchical deadlock detection protocol is developed.

It is essential to assess the reliability of digital computer systems used for critical real-time control applications (e.g., nuclear power plant safety control systems). This involves the assessment of the design correctness of the combined hardware/software system as well as the reliability of the hardware. In this paper we survey methods of determining the design correctness of systems as applied to computer programs.

In this paper an optimal algorithm for scheduling requests on interleaved memories is presented. With this algorithm the average completion time for servicing a finite set of randomly generated requests is proved to be minimum. Performance of this algorithm for nonrandom requests has not been proved. However, it is compared with alternate algorithms using simulations. A pipelined processor is used as an example for the generation of nonrandom requests to the memories. Nonetheless, the source could have been a vector processor or a multiprocessor system. Two alternative organizations are investigated, one with a common set of fixed size buffers to store conflicting requests and one with individual fixed size buffers for each module. These two organizations are shown to be equivalent as far as the average utilization and waiting cycles are concerned. An intelligent scheduler determines the order of initiation of the memory modules. An alternative design with separate instruction and data modules is investigated. It is found that separation gains very little in performance because of the unequal rates of access to the instruction and the data modules. The basic assumptions for the analysis are that the dependency effects are ignored and the request rate is very high so that any empty buffers can be filled immediately. The degradation in memory utilization due to dependency effects is studied in a separate paper in this issue.

In this correspondence we have presented a technique to find the degradation in memory and buffer utilization due to dependencies of accesses issued by a pipelined computer. When a dependency occurs, the request stream to the memory is interrupted and the utilization of the memory decreases. The dependency is then resolved in the pipelined computer. New requests are generated and the utilization gradually builds up to a maximum. The delay between the time a dependency occurs and the time the dependency is resolved depends highly on the method used in the pipelined computer to resolve the dependency. Hence, the evaluations of a specific computer is too restrictive in scope. A general organization of a pipelined computer is proposed. We evaluate the degradation in memory utilization due to dependencies using a Markovian model. This is validated against a detailed simulation model. The analysis is based on the memory configuration (Organization I) and simulation results with no dependencies that are presented in a separate paper in this issue.

This paper discusses the necessity of a good methodology for the development of reliable software, especialy with respect to the final software validation and testing activities. A formal specification development and validation methodology is proposed. This methodology has been applied to the development and validation of a pilot software, incorporating typical features of critical software for nuclear power plant safety protection. The main features of the approach indude the use of a formal specification language and the independent development of two sets of specifications. Analyses on the specifications consists of three-parts: validation against the functional requirements consistency and integrity of the specifications, and dual specification comparison based on a high-level symbolic execution technique. Dual design, implementation, and testing are performed. Automated tools to facilitate the validation and testing activities are developed to support the methodology. These includes the symbolic executor and test data generator/dual program monitor system. The experiences of applying the methodology to the pilot software are discussed, and the impact on the quality of the software is assessed.

This paper is concerned with the formal specification of program modules which control access to resources shared among concurrent proceses. The concept of state space is defined for such program modules and the formal specification is given in terms of a program module invariant and input-output assertions defined on the state space. Examples are provided to ilustrate the construction of sDecifications with this approach.

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

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

Fault-tolerant programs contain redundancy to provide tolerance for residual program errors and hardware faults during task execution. The concept of parallel execution of fault-tolerant programs, i.e., overlapping main-stream computation with redundant computation related to validation and recovery, was developed in [8]. A memory scheme, referred to as “duplex memory”, was also designed to realize the full potential of parallel execution. Although the duplex memory sketched in [8] is valid, it suffers from high storage and time overhead. This paper presents an improved version of duplex memory and shows its optimality in terms of storage overhead for parallel execution. A scheme for mapping logical addresses of variables to physical memory locations is also discussed.

In this paper, we design some simple schemes for a variety of searches, each of which may be performed in one complete memory cycle using bit-memory logic primarily. The searches we study include the basic equality search, the threshold searches (both greater than and less than searches), and most importantly, the greatest value and the least value searches. For each kind of search, we present both the algorithm suitable for our needs and the logic circuit of the memory cell required by the algorithm. Based on the basic search schemes, an algorithm for ordered retrieval is developed. A comparison for ordered retrieval schemes is then made between the proposed scheme and the previous algorithms. It is found that this algorithm outperforms all the other algorithms compared, particularly in the resolution of multiple responses. Finally, issues relating to LSI implementation, manufacturing defects, modular expansion, and extension to associative sequential memories are discussed.

-Real-time optimization of the overall performance of a large computer system or network such as an air-traffic control system or teleprocessing network inherently requires the introduction of adaptive control into selected control functions or sets of control functions. Such adaptive control is necessitated by the high variance of the available resource inventory and the workload resource demands within the system environment. Global management of the resulting multiloop control system becomes the responsibility of the operating system. Investigated aspects of this evolutionary extension of the operating system called the dynamically adaptive operating system (DAOS) include the general methodology and the real-time modeling and estimation of resource demands. The methodology specifies the general identification, decision, and modification processes required for an adaptive operating system. Support of such processes could be attractively provided by a peripheral or miniprocessor. The problem of estimating resource service times both with and without partial service times is explored and statistical models possessing utility for real-time modeling are developed. In particular, a dynamically partitioned second moment model (DPSMM) is described. The feasibility of such models is established with respect to a General Principle of Locality. Selected simulation results are presented to evaluate selected developments with respect to an adaptive central processing unit (CPU) scheduling discipline.

This paper provides a brief overview of significant developments in computer science and engineering education with discussions on curriculum development, continuing education, and certification. Forecasts of industry needs in the 1980's for computer professionals are included, together with the trends in curriculum developments that may auger.

Recent advances in multiprogramming have been concentrated on multiprocessor systems. But overlap in operations is also permissible in uniprocessor systems in which the processor instruction execution and input–output operations are handled by separate units. By maximizing the processor and input–output overlap, a program can be executed faster while the system utilization is highly improved.

Software validation through testing will continue to be a very important tool for ensuring correctness of large scale software systems. Automation of testing tools can greatly enhance their power and reduce testing cost. In this paper, techniques for automated test data generation are discussed. Given a program graph, a set of paths are identified to satisfy some given testing criteria. When a path or a program segment is specified, symbolic execution is used for generating input constraints which define a set of inputs for executing this path or segment. Problems encountered in symbolic execution are discussed. A new approach for resolving array reference ambiguities and a procedure for generating test inputs satisfying input constraints are proposed. References to arrays are recorded in a table. during symbolic execution and ambiguities are resolved when test data are generated to evaluate the subscript expressions. The implementation of a test data generator for Fortran programs incorporating these techniques is also described.

There is an increasing use of error detectors and correctors in computer subsystems, such as parity detectors in memory modules and residue checkers in arithmetic units. Their fault tolerant characteristics are studied through the model of detector redundant systems. Their reliabilities and availabilities are analyzed and compared with those which do not have any such error detectors. The design of fault isolating and reconfiguring networks used in the implementation of such systems are developed.

In the past few years, research has been actively carried out in an attempt to improve the quality and reliability of large-scale software systems. Although progress has been made on the formal proof of program correctness, proving large-scale software systems correct by formal proof is still many years away. Automated software tools have been found to be valuable in improving software reliability and attacking the high cost of software systems. This paper attempts to describe some main features of automated software tools and some software evaluation systems that are currently available.

The usefulness of software monitors in testing large programs is discussed. Several types of testing strategies based on the use of monitors are surveyed. Since there is a computational overhead involved in employing monitors, attempts are made to minimize the number of monitors employed. This optimisation problem is formulated and analyzed in graph theoretic terms. Implementation aspects are considered through both discussion and examples.

Current architecture for microprogrammable machines vary widely. In order to avoid the applicability of the testing technique to a particular machine example, hardware, microware and microprograms are represented in a general fashion. This representation will account for a composite of features common to a large variety of contemporary machines. Such a general description seems to be absolutely necessary, when a comparison of two microprograms executing on different machines has to be made. After defining the model, correctness and equivalence of loopfree microprograms will be defined. The testing techniques are then developed. In the Appendix are shown two examples of straight line microprograms (for simplicity), to which the developed model is applied.

A high-level language, SIMPL (Single Identity MicroProgramming), for horizontal microprogramming has been developed. This language allows the SIMPL compiler to easily detect concurrent microoperations and to optimize their intricate timing and concurrency for generating highly parallel and efficient object microprograms in horizontal formats. This unique feature accrues from the single assignment concept for multiprocessing languages that was adapted to the design of SIMPL.

This is a refreshingly clear introductory text on computer organization for undergraduates with very little previous background in computers. The clarity of exposition makes it useful for self-reading. The author admirably succeeds in his stated purpose which is "to introduce the student to the most primitive actions of a computer and then show how the primitive actions can be put together to construct most of the complex actions that computers regularly perform."

With the developments of parallel computer systems, the techniques for the recognition and representation of parallel task streams in a job (program) have become important to enhance the system performance.

With a view to the computational speed, it is obviously advantageous to perform the frequently used arithmetic operations in the hardware rather than in software, especially in scientifically oriented real-time applications. Here we present two optimal square-rooting algorithms for hardware implementation which utilize high-speed-multiplication of sophisticated scientific computers and no division. One of them is the well-known one, titled here as Algorithm N, which was derived on the mathematical basis of NEWTON iteration scheme;, while the other is a new algorithm, titled as Algorithm G, derived on the basis of Normalization Technique. Algorithm G is compared with Algorithm N in various aspects since Algorithm N has been believed so far to be the most efficient among this class of algorithms. Both possess the property of quadratic convergence, an important property as far as speed is concerned. However, Algorithm G turns out to be faster with no more hardware than Algorithm N, since it requires less time for each iteration, analogous to the higher speed of Goldschmidt' s division algorithm over original NEWTON iteration scheme for division. It is shown that the higher speed of Algorithm G purposed purely for hardware implementation is primarily due to the inherent parallelism which makes full use of characteristics of hardware implementation. Furthermore, in case where Goldschmidt" s division algorithm is implemented as in IBM 91/360, Algorithm G has more advantages because of possibility to share most of the required hardware with division unit including one for initial approximation. Therefore, it is believed that at present Algorithm G has the most promising advantages for hardware implementation.

Reliability is an important aspect of any system. On-line diagnosis, parity check coding, triple modular redundancy, and other methods have been used to improve the reliability of computing systems. In this paper another aspect of reliable computing systems is explored. The problem is that of recovering error-free information when an error is detected at some stage in the processing of a program. If an error or fault is detected while a program is being processed and if it cannot be corrected immediately, it may be necessary to run the entire program again. The time spent in rerunning the program may be substantial and in some real time applications critical. Recovery time can be reduced by saving states of the program (all the information stored in registers, primary and secondary storage, etc.) at intervals, as the processing continues. If an error is detected the program is restarted from its most recently saved state. However, a price is paid in saving a state in the form of time spent storing all the relevant information in secondary storage. Hence it is expensive to save the state of the program too often. Not saving any state of the program may cause an unacceptably large recovery time. The problem that we solve is the following. Determine the optimum points at which the state of the program should be stored to recover after any malfunction.

The overhead involved in the real-time multiprocessor execution of parallel-processable segments of a sequential program is investigated. The execution follows a preprocessing phase in which the source program is analyzed and the parallel-processable segments are recognized. A number of representations of a parallel-processable program are possible. A table representation is used, and a technique is developed to efficiently interpret this table in a system in which a number of identical processors share a common memory.

Some basic ideas and practices in the area of microdiagnostics are surveyed, and these are molded into a theoretical framework that could help the design of microprogrammed computers, as well as the development of test procedures for fault detection and location. The basic architectural variations as seen in the current microprogrammed computers and their relationship to microdiagnostics are discussed.

This paper describes a set of techniques that can be used to optimally schedule a sequence of interrelated computational tasks on a multiprocessor computer system. Using a directed graph model to represent a computational process, two basic problems are solved here. First, given a set of computational tasks and the relationships between them, the tasks are scheduled such that the total execution time is minimized, and the minimum number of processors required to realize this schedule is obtained. The second problem is of a more general nature. Given k processors, the tasks are scheduled such that execution time is again minimized. Consideration is given to tasks of equal and unequal duration, and task preemption is not allowed.

With the increasing availability of high-speed multiplication units in large computers it is attractive to develop an iterative procedure to compute division and square root, using multiplication as the primary operation. In this paper, we present three new methods of performing square rooting rapidly which utilize multiplication and no division. Each algorithm is considered for convergence rate, efficiency, and implementation. The most typical and efficient one of the already-known algorithms which utilizes multiplication, here called the N algorithm, is introduced for the purpose of comparison with the new algorithms. The effect and importance of the initial approximation is considered. (One of the algorithms, here called the G algorithm, is described in detail with the emphasis on its high efficiency.)

This paper describes the Fortran parallel task recognizer and the directed graph model upon which it is based. The recognizer is itself a Fortran program. As input the recognizer accepts source programs written in Fortran; as output the recognizer generates a set of tables which communicate to the operating system information regarding the parallel processability of source program tasks. The recognizer has been used to analyze several programs in an attempt to determine what characteristics render a program "suitable" for parallel processing. Timing studies have shown that the detailed recognizer analysis consumes a large amount of time in an attempt to answer the suitability question. For a suitable production-type program this analysis time can be distributed over the lifetime of the program. In those cases where the source program is not suitable for parallel processing, however, this analysis represents a wasted investment of valuable system resources. To circumvent this, a heuristic procedure has been developed which introduces little overhead and provides a preliminary answer to the suitability question based solely on the nature and number of source program statements. If the preliminary analysis suggests a favorable potential for the source program, then the program is subjected to the detailed analysis of the recognizer.

With increased use of microprogramming in present computer systems, the need arises to automate the checking and optimization of microcode. This paper reviews the optimization objectives, characterizes microprogranis, and discusses the machine structure. A translator from machine code to microcode appears feasible and is described. Some compiler techniques are reviewed and adapted to improve microprograms by studying operational interaction. Microprogram characteristics permit additional methods to reduce the computation effort. The techniques are integrated into a scheme implemented for optimizing a simulated machine.

Fault tolerance has become an important design parameter of fourth generation computing systems. A brief overview of significant accomplishments in fault detection and location, reliability modeling, analysis and architecture, and some comments on software aspects of reliable computation are provided. A few promising areas for future investigation are described.

In this paper we develop methods of segmenting a large system into smaller subsystems so that the letter can be diagnosed in parallel. Two basic techniques called serial segmentation and parallel segmentation are introduced. Furthermore, an algorithm is developed for the purpose of reducing the complexity and the size of the large subsystem.

The efficient organization of a very large file to facilitate search and retrieval operations is an important but very complex problem. In this paper we consider the case of a large file in which the frequency of use of its component subfiles are known. We develop the organization of the file so that the average number of entries to locate individual items in it by means of binary search is minimized. The algorithm iteratively partitions the file into "saturated" subfiles, and with each successive iteration the average number of entries to locate an item is reduced until no more improvement is possible. Next, we extend the method to solve the realistic problem of designing an optimal memory hierarchy to hold the file in a computer system. The sizes of various memory components and location of various items of the frequency-dependent file are determined so that the average time to locate an item (over the totality of items) in the memory hierarchy is minimized for a given total cost of the memory system. A number of examples are given to elucidate the methods. Also, the characteristics and results of a Fortran implementation of the algorithms on the CDC 6600 are described.

In previous papers [3]–[5] the authors considered the application of graph theory to represent and analyze a computer system. From such analysis of the graph (thus the system), we have shown that faults can be detected and located by means of strategically placed test points within the system.

The optimization of memory hierarchy involves the selection of types and sizes of memory devices such that the average access time to an information block is a minimum for a particular cost constraint. It is assumed that the frequency of usage of the information is known a priori. In this paper the optimization theory for a single task or program is reviewed and it is extended to a general case in multiprogramming when a number of tasks are executed concurrently. Another important extension treats the case when memories are available only in indivisible modules. Comparisons with conventional methods of solution as well as computational experience on the multiprogrammed and modular cases are given.

Signal flow graph methods are applied to the problem of counting the number of allowable code words for certain classes of prefixed comma-free codes. This method can be applied whenever the distance between the prefix and otherA-tuples in the code word is a prescribed function of the position of theA-tuple. Such codes can have desirable synchronization properties without leading to very small code word sets.

Discrete sequential systems, such as sampled data systems, discrete Markov processes, linear shift register generators, computer programs, sequential code generators, and prefixed comma-free codes, can be represented and studied in a uniform manner by directed graphs and their generating functions. In this paper the properties of the generating functions are examined from certain connectivity considerations of these graphs.