Search

When a crash occurs in a transaction processing system, the database can enter an unacceptable state. To continue the processing, the recovery system has three tasks: 1) verification of the database state for acceptability, 2) restoration of an acceptable database state, and 3) restoration of an acceptable history of transaction processing. Unfortunately these tasks are not trivial and the computational complexity of the algorithms for most of them is either NP-complete or NP- hard. In this paper we discuss the concepts and design issues of a construct called database integrity block (DIB). The implementation of this construct allows for efficient verification of the database state by employing a set of integrity assertions and restoration of transaction history by utilizing any database restoration technique such as audit trail or differential file. This paper presents approximation algorithms for minimizing the costs of evaluation of integrity assertions by modeling the problem as the directed traveling salesman problem, and presents a methodology to compare the costs of audit trail and differential file techniques for database restoration. The applicability of integrity verification research to the problem of multiple-query optimization is also included. [ABSTRACT FROM AUTHOR]

This paper discusses axiomatic and functional models of the semantics of structured programming. The models are presented together with their respective methodologies (or proving program correctness and for denying correct programs. Examples using these methodologies are given. Finally, the models are compared and contrasted. [ABSTRACT FROM AUTHOR]

Backward error recovery (that is, resetting an erroneous state of a system to a previous error-free state) is an important general technique for recovery from faults in a system, especially those faults which were not foreseen. However, the provision of backward error recovery can be complex, particularly if the implementation of the system is ‘multilevel’ and recovery is to be provided at a number of these levels. This paper discusses two distinct categories of multilevel system, and then examines in detail the issues involved in providing backward error recovery in both types of system. [ABSTRACT FROM AUTHOR]

This paper describes the design and implementation of an intelligent tutoring system for the Dijkstra-Gries programming methodology as defined by Cries in "The Science of Programming"[12]. The first part of the paper identifies the requirements of intelligent tutoring systems in general and those of the methodology in particular. It shows the suitability of the Smalltalk environment for developing expandable intelligent systems and the compatibility of Smalltalk's object-oriented paradigm with the Gries methodology's goal/plan approach to programming. We then describe how these requirements are met: an overview of the system's support of the methodology and the modules that enable the system to respond intelligently. As an example, a reusable tutorial part is presented, first from a student's perspective, then from an author's perspective. Finally the results of an evaluation of the system drawn from actual student experience are presented. [ABSTRACT FROM AUTHOR]

A self-stabilizing system is a network of processors, which, when started from an arbitrary (and possibly illegal) initial state, always returns to a legal state in a finite number of steps. This implies that the system can automatically deal with infrequent errors. One issue in designing self-stabilizing algorithms is the number of states required by each machine. This paper presents mutual exclusion algorithms which will be self-stabilizing while only requiring each machine in the network to have two states. The concept of a randomized central demon is also introduced in this paper. The first algorithm is a starting point where no randomization is needed (the randomized central demon is not necessary). The other two algorithms require randomization. The second algorithm builds on the first algorithm and reduces the number of network connections required. Finally, the number of necessary connections is again reduced yielding the final two-state, probabilistic algorithm for an asynchronous, unidirectional ring of processes. [ABSTRACT FROM AUTHOR]

This paper investigates how the use of a new data structure, the codeword, can help improve the performance of quicksort when the records to be sorted are long and the keys are alphanumeric sequences of bytes. The codeword is a compact representation of a key with respect to some codeword generator. It consists of a byte for a character count of "equal" bytes, a byte for the "first nonequal" byte, and a pointer to the record. The paper shows how the ordering of keys is preserved by an adequate choice of the code generator and how this can be applied to the quicksort algorithm. An analysis of the potential savings on various architectures and actual measurements show the improvements that can be attained by using codewords rather than pointers. Architecturally independent parameters, such as the number of bytes to be compared and the number of swaps, architecture-dependent parameters such as caches and their write policies, and compiler optimizations such as in-line expansion and register allocation are considered. [ABSTRACT FROM AUTHOR]

We explain why pre-run-time scheduling is essential if one wishes to guarantee that timing constraints will be satisfied in a large complex hard-real-time system. We examine some of the major concerns in pre-run-time scheduling and consider what formulations of mathematical scheduling problems can be used to address those concerns. This paper provides a guide to the available algorithms. [ABSTRACT FROM AUTHOR]

Diagrams play a central role in software engineering. They are used for specifying design elements such as requirements, concurrent systems, database models and interactive systems. Families of diagrams form visual languages, and creating such diagrams constitutes visual programming. The Visual Programmer's WorkBench (VPW) addresses the rapid synthesis of programming environments for the specification, analysis, and execution of visual programs. A language-based environment for a specific visual language is generated in VPW from a specification of the syntactic structure, the abstract structure, the static semantics and the dynamic semantics of the language. VPW is built around a model of distributed processing based on shared distributed memory. This framework is used both in defining the architecture of the environment and for the execution model of visual languages. The Visual Programmer's WorkBench has been used to experiment with visual programming environments for several visual languages. This paper describes the design of the Visual Programmer's WorkBench and our experience using it to generate a distributed programming environment for a concurrent visual language. [ABSTRACT FROM AUTHOR]

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

This paper contains an exposition of the method of programming with verification conditions. Although this method has much in common with the one discussed by Dijkstra in A Discipline of Programming, it is shown to have the advantage in simplicity and flexibility. The simplicity is the result of the method's being directly based on Floyd's inductive assertions. The method is flexible because of the way in which the program is constructed in two stages. In the first stage, a set of verification conditions is collected which corresponds to a program in "flowgraph" form. In this stage sequencing control is of no concern to the programmer. Control is introduced in the second stage, which consists of automatable applications of translation and optimization rules, resulting in conventional code. Although our method has no use for the sequencing primitives of "structured programming," it is highly secure and systematic. [ABSTRACT FROM AUTHOR]

This paper reports on the initial design and partial implementation of an interactive programming environment to be used by expert programmers. The system is based on three forms of program description: 1) definition of structured data objects, their parts, properties, and relations between them, 2) input-output specification of the behavior of program segments, and 3) a hierarchical representation of the internal structure of programs (plans). The plan representation is of major theoretical interest because it includes not only data flow and control flow relationships between subsegments of a program, but also goal-subgoal, prerequisite, and other logical dependencies between the specifications of the subsegments. Plans are utilized both for describing particular programs and in the compilation of a knowledge base of more abstract knowledge about programming, such as the concept of a loop and various specializations, such as enumeration loops and search loops. We also describe a deductive system which can verify the correctness of plans involving side effects on complex data with structure sharing. [ABSTRACT FROM AUTHOR]

A method for formal description of programming principles is presented in this paper. Programming principles, such as sequential search can be defined and proven even in the absence of an application. We represent a principle as a program scheme which has partially interpreted functions in it. The functions must obey certain input constraints. Use of these ideas in program proving is illustrated with examples. [ABSTRACT FROM AUTHOR]

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

Database systems that can efficiently manage complex objects are increasingly needed in many different fields, Such as office automation, knowledge processing, CAD/CAM, CASE, etc. A hit of recent complex object database systems support the concepts of object identity and object identifier. Following an object identifier to access the referenced object is called navigation operation and is an essential operation in dealing with complex objects. Navigation operation is a difficult operation to implement efficiently since every navigation operation inherently causes one disk access operation. This paper proposes a scheme to notably. accelerate the navigation operation among a sea of complex objects, by increasing the effective number of objects in one disk page. The main concept of the presented technique is threefold. The first idea is to store a cached value within a complex object that is referencing another complex object. The second is that when the referenced object, is to be updated the update propagation is delayed until the time when the cached value is referenced. The third is to utilize a hashed table on main memory to efficiently validate the consistency between the cached values and the original values. [ABSTRACT FROM AUTHOR]

Communicating real-time state machines (CRSM's) are a new, complete, and executable notation for specifying concurrent real-time systems including the monitored and controlled physical environment. They are essentially state machines that communicate synchronously in a manner much like the input-output in Hoare's CSP. In addition, CRSM's have a novel and small set of facilities for describing timing properties and accessing real time. The paper defines the CRSM language, gives many examples of its use in requirements specification, outlines an algorithm for executing or simulating CRSM's, introduces some techniques for reasoning about the specifications, and discusses some open problems and issues. [ABSTRACT FROM AUTHOR]

We present a simple method for normalizing the control-flow of programs to facilitate program transformations, program analysis, and automatic parallelization. While previous methods result in programs whose control ftowgraphs are reducible, programs normalized by this technique satisfy a stronger condition than reducibility and are therefore simpler in their syntax and structure than with previous methods. In particular, all control-flow cycles are normalized into single-entry, single- exit while loops and all goto's are eliminated. Furthermore, the method avoids problems of code replication that are characteristic of node-splitting techniques. This restructuring obviates the control dependence graph, since afterwards control dependence relations are manifest in the syntax tree of the program. In this paper we present transformations that effect this normalization, and study the complexity of the method. [ABSTRACT FROM AUTHOR]

A state constraint is a new programming construct designed to restrict the domain of definition of a program. It can be used to decompose a program pathwise, i.e., to divide the program into subprograms along the control How, as opposed to divide the program across the control flow when the program is decomposed into functions and procedures. As a result one can now construct and manipulate a program consisting of one or more execution paths of another program. This paper describes the idea involved, examines the properties of state constraints, establishes a formal basis for pathwise decomposition, and discusses their utilities in program simplification, testing, and verification. [ABSTRACT FROM AUTHOR]

This paper presents syntax for an integrated Entity Relationship (E-R) programming language. We envision this syntax being used to extend a general purpose programming language such as Cobol, PL/1, Pascal, or C to provide facilities for working with E-R data. We start by discussing the problems that arise in providing data manipulation facilities by embedding a query language in a general purpose programming language and argue that an integrated approach is superior. We than state the requirements for such a language followed by a syntax. The syntax provides data manipulation capabilities for the E-R model in which entity sets are assumed to be mutually disjoint and each entity set has a unique, perhaps multiattribute, key. The syntax also covers the extended entity relationship (E-E-R) model which allows relationships between relationships. In an integrated language, database objects are automatically brought into main memory when they are referred to. To keep track of these objects and their references a run-time environment must be provided and bound to the user program. We discuss the design of this run time environment in some detail. If the E-R model is restricted to binary relationships between entity types and without attributes then the syntax can be considerably simplified. We discuss this syntax which has been implemented in a language called ERLANG (12). Finally, we discuss briefly some implementation considerations as well as a simple facility for defining an E-R database. [ABSTRACT FROM AUTHOR]

A distributed system is an interconnected network of computing elements or nodes, each of which has its own storage. A distributed program is a collection of processes which execute asynchronously, possibly in different nodes of a distributed system, and they communicate with each other in order to realize a common goal. In such an environment, a group of processes may sometimes get involved in a communication deadlock. This is a situation in which each member process of the group is waiting for some member to communicate with it, but no member is attempting communication with it. In this paper, we present an algorithm for detecting such communication deadlocks. The algorithm is distributed, i.e., processes detect deadlocks during the course of their communication, without the aid of a central controller. The detection scheme does not presume any a priori structure among processes, and detection is made "on the fly" without freezing normal activities. The scheme does not require any storage whose size is determined by the size of the network, and hence is suitable also for an environment where processes are created dynamically. [ABSTRACT FROM AUTHOR]

A loosely coupled multiprocessor system contains multiple processors which have their own local memories. To balance the load among multiple processors is of fundamental importance in enhancing the performance of such a multiple processor system. Probabilistic load balancing in a heterogeneous multiple processor system with many job classes is considered in this study. The load balancing scheme is formulated as a nonlinear programming problem with linear constraints. An optimal probabilistic load balancing algorithm is proposed to solve this nonlinear programming problem. The proposed load balancing method is proven globally optimum in the sense that it results in a minimum overall average job response time on a probabilistic basis. [ABSTRACT FROM AUTHOR]

The problem of proving whether or not a loop computes a given function is investigated. We consider loops which have a certain ‘closure’ property and derive necessary and sufficient conditions for such a loop to compute a given function. It is argued that closure is a fundamental concept in program proving. Extensions of the basic result to proofs involving relations other than functional relations, which typically arise in nondeterministic loops, are explored. Several applications of these results are given, particularly in showing that certain classes of programs may be directly proven (their loop invariants generated) given only their input-output relationships. Implications of these results are discussed. [ABSTRACT FROM AUTHOR]

An approach to specification of requirements and verification of design for real-time systems is presented. A system is defined by a conventional mathematical model for a dynamic system where application specific states denote functions of real time. Specifications are formulas in duration calculus, a real-time interval logic, where predicates define durations of states. Requirements define safety and functionality constraints on the system or a component. A top-level design is given by a control law: a predicate that defines an automaton controlling the transition between phases of operation. Each phase maintains certain relations among the system states; this is analogous to the control functions known from conventional control theory. The top-level design is decomposed into an architecture for a distributed system with specifications for sensor, actuator, and program components. Programs control the distributed computation through synchronous events. Sensors and actuators relate events with system states. Verification is a deduction showing that a design implies requirements. [ABSTRACT FROM AUTHOR]

A global state of a distributed transaction system is consistent if no transactions are in progress. A global checkpoint is a transaction which must view a globally consistent system state for correct operation. We present an algorithm for adding global checkpoint transactions to an arbitrary distributed transaction system. The algorithm is nonintrusive in the sense that checkpoint transactions do not interfere with ordinary transactions in progress; however, the checkpoint transactions still produce meaningful results. [ABSTRACT FROM AUTHOR]

A study of several of the proof of correctness methods is presented. In particular, the form of induction used is explored in detail. A relational semantic model (or programming languages is introduced and its relation to predicate transformers is explored. A rather elementary viewpoint is taken in order to expose, as simply as possible, (he basic differences of the methods and the underlying principles involved. These results were obtained by attempting to thoroughly understand the "subgoal induction" method, [ABSTRACT FROM AUTHOR]

Synchronous and asynchronous operation of software systems are defined. It is argued that certifying the correct operation of a system in the synchronous mode is significantly simpler than in the asynchronous mode. A series of compile-time and run-time restrictions for systems constructed in Concurrent Pascal are presented which assure equivalent operation in the synchronous and asynchronous modes. [ABSTRACT FROM AUTHOR]

An approach to automating the selection of implementations for the data representations used in a program is presented. Formalisms are developed for specifying data representations and implementation structures. Using these formalisms, algorithms are presented which will recognize the use in a program of known data representations (e.g., stacks, queues, lists, arrays, etc.) so that alternative implementations can be retrieved from a library and which will, for those representations not recognized, generate alternative implementations with a wide range of space-time tradeoffs. Experience with using these algorithms indicates they are reasonably successful, although there are several problems that must be solved before automatic implementation selection systems will be practical. [ABSTRACT FROM AUTHOR]