Functional semantics of programs with exceptions

Linguistic mechanisms for exception handling facilitate the production of reliable software and play an important role in fault tolerant computing. This paper describes the functional semantics of a Pascal-like language which supports exception handling and data abstraction. A program with exceptions is considered as having a standard semantics, as well as an exceptional semantics for each exception that may be signaled during its execution. Standard functional semantics methods provide rules to obtain the function representing the standard semantics. In this paper, we provide rules to determine the functions representing the exceptional semantics. We also describe a method for specifying and verifying the correctness of implementation of data types with exceptions.     

Functional refinement and nested objects for object-oriented design

An extended object-oriented design methodology is proposed which incorporates a top-down, stepwise refinement approach in a coherent fashion. The extended object-oriented design methodology also includes a phase of progressive object refinement to support the nesting of objects, which would allow entities in real life that are composed of subentities to be modeled. A design example is included, and experiences encountered using this methodology in a course are described     

Synthesizing implementations of abstract data types from axiomatic specifications

This paper describes a system for automatically generating an implementation of an abstract data type from its axiomatic specifications. Such a system can be useful for rapid prototyping and for detecting inconsistencies in the specifications by testing the generated implementation. In the generated Implementation, an instance of the data type is represented by its state. An operation on the data type is implemented by a collection of functions — a function for each of the axioms specified for the operation, and a function for the operation that determines, depending on the state of the instance(s) on which the operation is being performed, which of the axioms of the operation is applicable. The system is developed on a Sun-3 workstation running Unix. It is written in C and generates the implementation of the abstract data type in C.     

Learning context-free grammar rules from a set of program

The grammar of a programming language is important because it is used in developing program analysis and modification tools. Sometimes programs are written in dialects-minor variations of standard languages. Normally, grammars of standard languages are available but grammars of dialects may not be available. A technique for reverse engineering context-free grammar rules is presented. The proposed technique infers rules from a given set of programs and an approximate grammar is generated using an iterative approach with backtracking. The correctness of the approach, is explained and a set of optimisations proposed to make the approach more efficient. The approach and the optimisations are experimentally verified on a set of programming languages.     

A formal framework for on-line software version change

The usual way of installing a new version of a software system is to shut down the running program and then install the new version. This necessitates a sometimes unacceptable delay during which service is denied to the users of the software. An online software replacement system replaces parts of the software while it is in execution, thus eliminating the shutdown. While a number of implementations of online version change systems have been described in the literature, little investigation has been done on its theoretical aspects. We describe a formal framework for studying online software version change. We give a general definition of validity of an online change, show that it is in general undecidable and then develop sufficient conditions for ensuring validity for a procedural language     

Optimum control limits for employing statistical process control in software process

There is increasing interest in using control charts for monitoring and improving software processes, particularly quality control processes like reviews and testing. In a control chart, control limits are established for attributes and, if any point falls outside the limits, it is assumed to be due to special causes that need to be identified and eliminated. If the control limits are too tight, they may raise too many "false alarms" and, if they are too wide, they may miss special situations. Optimal control limits will try to minimize the cost of these errors. In this paper, we develop a cost model for employing control charts for software processes using optimum control limits which can be determined. Our applications of the model suggest that, for quality control processes like inspection, optimum control limits may be tighter than those commonly used in manufacturing. We have also implemented this model as a Web service that can be used for determining optimum control limits.     

Coding-based replication schemes for distributed systems

Data is often replicated in distributed systems to improve availability and performance. This replication is expensive in terms of disk storage since the existing schemes generally require full files to be stored at each site. In this paper, we present schemes which significantly reduce the storage requirements in replication based systems. These schemes use the coding method suggested by Rabin to store replicated data. The first scheme that we present is a modification of the simple voting algorithm and its quorum requirements. We then show how some of the extensions of the voting algorithm can also be modified to get storage efficient schemes for managing such replication. We evaluate the availability offered by these schemes and show that the storage space required to achieve certain availability are significantly lower than the conventional schemes with full file replication. Since coding is used, these schemes also provide a high degree of data security     

On fault tolerance in manufacturing systems

The physical and control structure of manufacturing systems is described, and a hierarchical model for supporting fault tolerance is proposed. The main advantage of the model is that it allows different fault tolerance and recovery techniques to be used in different segments of the network. To help in the choice of specific techniques in particular network segments, a set of metrics to evaluate fault tolerance techniques is presented along with preliminary ideas about integrating the different techniques. Design issues in applying the model to a given manufacturing system are discussed     

Resilient objects in broadband networks

An object is said to be resilient if operations on the object can be performed even if some nodes of the network fail. To support resiliency, copies of the objects are stored on different nodes, and access to different copies is coordinated. The properties of broadcast networks are utilized to devise a distributed scheme for implementing resilient objects. All the copies of an object are equivalent. If an operation is requested on an object, the operation is performed on all the copies of the object. No special mechanisms are needed if some copies are not available due to node failures, as long as there is at least one active node that has a copy of the object and the network does not get partitioned. Simulation results indicate that the number of messages needed to perform an operation increases slowly and the response time for performing an operation decreases as the number of copies increases     

Fault tolerant processes

A process is said to be fault tolerant if the system provides proper service despite the failure of the process. For supporting fault-tolerant processes, measures have to be provided to recover messages lost due to the failure. One approach for recovering messages is to use message-logging techniques. In this paper, we present a model for message-logging based schemes to support fault-tolerant processes and develop conditions for proper message recovery in asynchronous systems. We show that requiring messages to be recovered in the same order as they were received before failure is a stricter requirement than necessary. We then propose a distributed scheme to support fault-tolerant processes that can also handle multiple process failures.Pankaj Jalote received the Bachelor of Technology degree in electrical engineering from the Indian Institute of Technology, Kanpur, India, in 1980, the M.S. degree in computer science from Pennsylvania State University, University Park, in 1982, and the Ph.D. degree in computer science from the University of Illinois at Urbana-Champaign in 1985. From August 1985 to July 1989 he was an Assistant Professor in the Department of Computer Science at the University of Maryland, College Park. Currently he is an Assistant Professor in the Department of Computer Science and Engineering at IIT Kanpur, India. His research interests include fault-tolerant computing, distributed systems, and software engineering.This work was supported in parts by the NSF grant DCI-8610337