bluuebunny/crossref_metadata_2025_split huggingface dataset:
Simulating reactive systems by deduction
Authors: Feldman Yishai A. , Schneider Haim 
Published: July 2002

Debugging is one of the main uses of simulation. Localizing bugs or finding the reasons for unclear behavior involves going backwards in time, whereas simulation goes forward in time. Therefore, identifying causes with the aid of most existing simulation tools usually requires repeating the simulation several times, each time with reduced holes in the sieve. An alternative is simulation by deduction, a technique in which the steps in the dynamic behavior of the simulated model are deduced by a reasoning system. A simulation system that uses simulation by deduction can give direct answers to questions about the reasons for the simulation results. By recording the support for its deductions, such a system can answer “why” and “why not” questions about the scenario.Another benefit of simulation by deduction is that it enables symbolic simulation, that is, simulating a scenario given only a partial description of the environment and the simulated model. This allows verifying properties of an evolving design at any stage of the design process, and thus checking the consequences of the design decisions made so far. In order to allow deducing as much as possible from partial information, the axiom system has to be minimalistic, i.e., axioms have to require the minimum amount of knowledge of simulation inputs.These ideas were implemented in a system called SIP, which simulates the behavior of reactive systems. SIP is capable of answering “why,” “why not,” and “what if” questions. It also has a limited capability of dealing with partial knowledge. SIP is based on a reasoning system that is responsible for deducing the effects of the external inputs on the state of the simulated model, and recording the support for its deductions. The logical basis for the deduction of a step in SIP is provided by a minimalistic axiom system for statecharts.Although SIP simulates reactive systems described as statecharts, the principle of simulation by deduction is applicable to other types of systems and descriptions, provided only that they have a well-defined formal semantics.
A meta-environment for generating programming environments
Authors: Klint P. 
Published: July 2002

Over the last decade, considerable progress has been made in solving the problems of automatic generation of programming/development environments, given a formal definition of some programming or specification language. In most cases, research has focused on the functionality and efficiency of the generated environments, and, of course, these aspects will ultimately determine the acceptance of environment generators. However, only marginal attention has been paid to the development process of formal language definitions itself. Assuming that the quality of automatically generated environments will be satisfactory within a few years, the development costs of formal language definitions will then become the next limiting factor determining ultimate success and acceptance of environment generators.In this paper we describe the design and implementation of a meta-environment (a development environment for formal language definitions) based on the formalism ASF + SDF. This meta-environment is currently being implemented as part of the Centaur system and is, at least partly, obtained by applying environment generation techniques to the language definition formalism itself. A central problem is providing fully interactive editing of modular language definitions such that modifications made to the language definition during editing can be translated immediately to modifications in the programming environment generated from the original language definition. Therefore, some of the issues addressed are the treatment of formalisms with user-definable syntax and incremental program generation techniques.
The TickerTAIP parallel RAID architecture
Authors: Cao Pei , Lin Swee Boon , Venkataraman Shivakumar , Wilkes John 
Published: July 2002

Traditional disk arrays have a centralized architecture, with a single controller through which all requests flow. Such a controller is a single point of failure, and its performance limits the maximum number of disks to which the array can scale. We describe TickerTAIP, a parallel architecture for disk arrays that distributes the controller functions across several loosely coupled processors. The result is better scalability, fault tolerance, and flexibility.
This article presents the TickerTAIP architecture and an evaluation of its behavior. We demonstrate the feasibility by a working example, describe a family of distributed algorithms for calculating RAID parity, discuss techniques for establishing request atomicity, sequencing, and recovery, and evaluate the performance of the TickerTAIP design in both absolute terms and by comparison to a centralized RAID implementation. We also analyze the effects of including disk-level request-scheduling algorithms inside the array. We conclude that the Ticker TAIP architectural approach is feasible, useful, and effective.
An algorithm for concurrency control and recovery in replicated distributed databases
Authors: Bernstein Philip A. , Goodman Nathan 
Published: July 2002

In a one-copy distributed database, each data item is stored at exactly one site. In a replicated database, some data items may be stored at multiple sites. The main motivation is improved reliability: by storing important data at multiple sites, the DBS can operate even though some sites have failed.
This paper describes an algorithm for handling replicated data, which allows users to operate on data so long as one copy is “available.” A copy is “available” when (i) its site is up, and (ii) the copy is not out-of-date because of an earlier crash.
The algorithm handles clean, detectable site failures, but not Byzantine failures or network partitions.
From VHDL to efficient and first-time-right designs
Authors: Middelhoek Peter F. A. , Rajan Sreeranga P. 
Published: July 2002

In this article we provide a practical transformational approach to the synthesis of correct synchronous digital hardware designs from high-level specifications. We do this while taking into account the complete life cycle of a design from early prototype to full custom implementation. Besides time-to-market, both flexibility with respect to target architecture and efficiency issues are addressed by the methodology. The utilization of user-selected behavior-preserving transformation steps ensures first-time-right design while exploiting the experience, flexibility, and creativity of the designer.To ensure that design transformations are indeed behavior-preserving a novel mechanized approach to the specification and verification of design transformations on control data flow graphs which is independent of a specific behavioral model or graph size has been developed.As a demonstration of an industrial application we use a video processing algorithm needed for the conversion from a line-interlaced to progressively scanned video format. Both a video signal processor-based prototype implementation as well as a very efficient full custom implementation are developed starting from a single high-level behavioral specification of the algorithm in VHDL. Results are compared with those previously obtained using different tools and methodologies.
Formal verification of complex coherence protocols using symbolic state models
Authors: Pong Fong , Dubois Michel 
Published: July 2002

Directory-based coherence protocols in shared-memory multiprocessors are so complex that verification techniques based on automated procedures are required to establish their correctness. State enumeration approaches are well-suited to the verification of cache protocols but they face the problem of state space explosion, leading to unacceptable verification time and memory consumption even for small system configurations. One way to manage this complexity and make the verification feasible is to map the system model to verify onto a symbolic state model (SSM). Since the number of symbolic states is considerably less than the number of system states, an exhaustive state search becomes possible, even for large-scale sytems and complex protocols.
In this paper, we develop the concepts and notations to verifiy some properties of a directory-based protocol designed for non-FIFO interconnection networks. We compare the verification of the protocol with SSM and with the Stanford Mur φ, a verification tool enumerating system states. We show that SSM is much more efficient in terms of verification time and memory consumption and therefore holds that promise of verifying much more complex protocols. A unique feature of SSM is that it verifies protocols for any system size and therefore provides reliable verification results in one run of the tool.
Propeties of storage hierarchy systems with multiple page sizes and redundant data
Authors: Lam Chat-Yu , Madnick Stuart E. 
Published: July 2002

The need for high performance, highly reliable storage for very large on-line databases, coupled with rapid advances in storage device technology, has made the study of generalized storage hierarchies an important area of research.
This paper analyzes properties of a data storage hierarchy system specifically designed for handling very large on-line databases. To attain high performance and high reliability, the data storage hierarchy makes use of multiple page sizes in different storage levels and maintains multiple copies of the same information across the storage levels. Such a storage hierarchy system is currently being designed as part of the INFOPLEX database computer project. Previous studies of storage hierarchies have primarily focused on virtual memories for program storage and hierarchies with a single page size across all storage levels and/or a single copy of information in the hierarchy.

In the INFOPLEX design, extensions to the least recently used (LRU) algorithm are used to manage the storage levels. The read-through technique is used to initially load a referenced page of the appropriate size into all storage levels above the one in which the page is found. Since each storage level is viewed as an extension of the immediate higher level, an overflow page from level
i
is always placed in level
i
+ 1. Important properties of these algorithms are derived. It is shown that depending on the types of algorithms used and the relative sizes of the storage levels, it is not always possible to guarantee that the contents of a given storage level
i
is always a superset of the contents of its immediate higher storage level
i
- 1. The necessary and sufficient conditions for this property to hold are identified and proved. Furthermore, it is possible that increasing the size of intermediate storage levels may actually increase the number of references to lower storage levels, resulting in reduced performance. Conditions necessary to avoid such an anomaly are also identified and proved.
The entity-relationship model—toward a unified view of data
Authors: Chen Peter Pin-Shan 
Published: July 2002

A data model, called the entity-relationship model, is proposed. This model incorporates some of the important semantic information about the real world. A special diagrammatic technique is introduced as a tool for database design. An example of database design and description using the model and the diagrammatic technique is given. Some implications for data integrity, information retrieval, and data manipulation are discussed.
The entity-relationship model can be used as a basis for unification of different views of data: the network model, the relational model, and the entity set model. Semantic ambiguities in these models are analyzed. Possible ways to derive their views of data from the entity-relationship model are presented.
Application of Parallel Processing to Numerical Weather Prediction
Authors: Carroll A. B. , Wetherald R. T. 
Published: July 2002

The purpose of this study is to illustrate the application of a parallel network processing computing system to an important class of problems in hydrodynamics. The computing system selected for this study is a prototype of the SOLOMON parallel processing system (cited as SOLOMON II) which was developed at the Westinghouse Defense and Space Center, Baltimore, Maryland.Emphasis is placed on the problem of numerical weather prediction mainly because of the large data storage and manipulation required, plus the extensive numerical analysis that is involved. The mathematical basis for numerical weather forecasting lies in the principles of conservation of mass, momentum, and energy. From these principles, research meteorologists have devised equations which express the physical laws governing the atmosphere. These basic equations are nonlinear partial differential equations and are well suited for solution by the SOLOMON II system. The computational method is to replace the region of interest by a grid system and replace the continuous equations by their finite difference approximations. In this representation, the programmer can take maximum advantage of mode control, neighboring connections, variable geometry, and simultaneous operation of a network of processing elements.Another topic discussed is the numerical solution of elliptic partial differential equations by the parallel processing network. It is felt by the authors that a parallel processing system of this type will offer a significant increase in computational speed over that of a sequentially organized computing system in the field of fluid dynamics as well as in other scientific fields.
Toward a Theory of Enumerations
Authors: Young Paul R. 
Published: July 2002

An attempt is made to show that there is much work in pure recursion theory which implicitly treats computational complexity of algorithmic devices which enumerate sets. The emphasis is on obtaining results which are independent of the particular model one uses for the enumeration technique and which can be obtained easily from known results and known proofs in pure recursion theory.
First, it is shown that it is usually impossible to define operators on sets by examining the structure of the enumerating devices unless the same operator can be defined merely by examining the behavior of the devices. However, an example is given of an operator which can be defined by examining the structure but which cannot be obtained merely by examining the behavior.
Next, an example is given of a set which cannot be enumerated quickly because there is no way of quickly obtaining large parts of it (perhaps with extraneous elements). By way of contrast, sets are constructed whose elements can be obtained rapidly in conjunction with the enumeration of a second set, but which themselves cannot be enumerated rapidly because there is no easy way to eliminate the members of the second set.
Finally, it is shown how some of the elementary parts of the Hartmanis-Stearns theory can be obtained in a general setting.
Scan conversion algorithms for a cell organized raster display
Authors: Barrett R. C. , Jordan B. W. 
Published: July 2002

Raster scan computer graphics with “real time” character generators have previously been limited to alphanumeric characters. A display has been described which extends the capabilities of this organization to include general graphics.
Two fundamentally different scan conversion algorithms which have been developed to support this display are presented. One is most suitable to noninteractive applications and the other to interactive applications. The algorithms were implemented in Fortran on the CDC6400 computer. Results obtained from the implementations show that the noninteractive algorithms can significantly reduce display file storage requirements at little cost in execution time over that of a conventional raster display. The interactive algorithm can improve response time and reduce storage requirements.
Experimental personalized array translator system
Authors: Hellerman H. 
Published: July 2002

A system designed for intimate man-machine interaction in a general-purpose problem-solving environment is experimentally operational. The system utilizes an array-oriented symbolic source language containing powerful statement types. These include numeric, Boolean, relational and selection operators on operands which can be entire arrays. The system also permits simple specification of test and argument arrays in single statements.
The completely symbolic operating system includes display and entry of program and data. Sequence control is aided by an interrupt switch which allows the user to interact with the program during execution. In addition to normal stored program sequencing, the system provides trace options and the ability to enter any statement for immediate execution.
Present implementation of the system is with an interpretive translator on an IBM 1620 computer.
Charcoal sketching: returning control to the artist
Authors: Bleser Teresa W. , Sibert John L. , McGee J. Patrick 
Published: July 2002

Background: Traditional paint programs can be criticized on the grounds that they provide fewer degrees of freedom than conventional artistic media. Mouse or tablet input devices usually provide only (x, y) spatial information. Thus most paint programs allow continuous control of the path of a stroke, but render it with a single “brush shape” of fixed size and orientation and use menus, either stationary or appearing, for such tasks as changing “brush” shapes. This produces two distinct discontinuities for the artist. First is a physical discontinuity: stopping the act of drawing and making a brush selection using a different physical device, or using the same device to point at a menu selection. A second discontinuity is the cognitive one involved with deciphering the menu contents and making a selection. Although the second may be minimized by using iconic menus, these interruptions of the drawing act make it difficult or impossible for the artist to maintain the kind of continuous control over his or her medium that is required.
A particular example of this level of control is the continuous and immediate control that an artist maintains when sketching with a piece of charcoal or a pencil. By manipulating the implement, the artist can change the shape of its contact point with the drawing surface. By changes in pressure exerted with the implement against the surface, it is possible to control both the darkness (value) and width (weight) of the line. All of these factors are controlled by the artist in real time and with continuous feedback.
Both Greene [2] and Strassman [4] have presented methods for capturing more of the artist's “gesture” in the rendered stroke. However, Greene's technique depends on a special-purpose input device and Strassman's does not work in real time. Hill [3] describes a two-handed paintbrush with the off hand controlling a valuator that varies the 'brush width. The technique described here represents another way to provide such control to the user of an interactive paint program. It uses off-the-shelf hardware, is easy to implement, and works in real time. As a single-handed technique, it takes advantage of the artist's skill with existing media.
The Alpine file system
Authors: Brown M. R. , Kolling K. N. , Taft E. A. 
Published: July 2002

Alpine is a file system that supports atomic transactions and is designed to operate as a service on a computer network. Alpine's primary purpose is to store files that represent databases. An important secondary goal is to store ordinary files representing documents, program modules, and the like.
Unlike other file servers described in the literature, Alpine uses a log-based technique to implement atomic file update. Another unusual aspect of Alpine is that it performs all communication via a general-purpose remote procedure call facility. Both of these decisions have worked out well. This paper describes Alpine's design and implementation, and evaluates the system in light of our experience to date.
Alpine is written in Cedar, a strongly typed modular programming language that includes garbage-collected storage. We report on using the Cedar language and programming environment to develop Alpine.
Query processing techniques in the summary-table-by-example database query language
Authors: Özsoyoğlu Gultekin , Matos Victor , Özsoyoğlu Meral 
Published: July 2002

Summary-Table-by-Example (STBE) is a graphical language suitable for statistical database applications. STBE queries have a hierarchical subquery structure and manipulate summary tables and relations with set-valued attributes.
The hierarchical arrangement of STBE queries naturally implies a tuple-by-tuple subquery evaluation strategy (similar to the nested loops join implementation technique) which may not be the best query processing strategy. In this paper we discuss the query processing techniques used in STBE. We first convert an STBE query into an “extended” relational algebra (ERA) expression. Two transformations are introduced to remove the hierarchical arrangement of subqueries so that query optimization is possible. To solve the “empty partition” problem of aggregate function evaluation, directional join (one-sided outer-join) is utilized. We give the algebraic properties of the ERA operators to obtain an “improved” ERA expression. Finally we briefly discuss the generation of alternative implementations of a given ERA expression.
STBE is implemented in a prototype statistical database management system. We discuss the STBE-related features of the implemented system.
A transient hypergraph-based model for data access
Authors: Watters Carolyn , Shepherd Michael A. 
Published: July 2002

Two major methods of accessing data in current database systems are querying and browsing. The more traditional query method returns an answer set that may consist of data values (DBMS), items containing the answer (full text), or items referring the user to items containing the answer (bibliographic). Browsing within a database, as best exemplified by hypertext systems, consists of viewing a database item and linking to related items on the basis of some attribute or attribute value.A model of data access has been developed that supports both query and browse access methods. The model is based on hypergraph representation of data instances. The hyperedges and nodes are manipulated through a set of operators to compose new nodes and to instantiate new links dynamically, resulting in transient hypergraphs. These transient hypergraphs are virtual structures created in response to user queries, and lasting only as long as the query session. The model provides a framework for general data access that accommodates user-directed browsing and querying, as well as traditional models of information and data retrieval, such as the Boolean, vector space, and probabilistic models. Finally, the relational database model is shown to provide a reasonable platform for the implementation of this transient hypergraph-based model of data access.
New techniques for best-match retrieval
Authors: Shasha Dennis , Wang Tsong-Li 
Published: July 2002

A scheme to answer best-match queries from a file containing a collection of objects is described. A best-match query is to find the objects in the file that are closest (according to some (dis)similarity measure) to a given target.
Previous work [5, 331] suggests that one can reduce the number of comparisons required to achieve the desired results using the triangle inequality, starting with a data structure for the file that reflects some precomputed intrafile distances. We generalize the technique to allow the optimum use of any given set of precomputed intrafile distances. Some empirical results are presented which illustrate the effectiveness of our scheme, and its performance relative to previous algorithms.