bluuebunny/crossref_metadata_2025 huggingface dataset:
Board-level multiterminal net routing for FPGA-based logic emulation
Authors: Mak Wai-Kei , Wong D. F.
Published: July 2002

We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System [Varghese et al. 1993] and the Enterprise Emulation System [Maliniak 1992] manufactured by Quickturn Design Systems. Optimal algorithms have been proposed for the case where all nets are two-terminal nets [Chan and Schlag 1993; Mak and Wong 1995]. We show how multiterminal nets can be handled by decomposition into two-terminal nets. We show that the multiterminal net decomposition problem can be modeled as a bounded-degree hypergraph-to-graph transformation problem where hyperedges are transformed to spanning trees. A network flow-based algorithm that solves both problems is proposed. It determines if there is a feasible decomposition and gives one whenever such a decomposition exists.
Sparsification—a technique for speeding up dynamic graph algorithms
Authors: Eppstein David , Galil Zvi , Italiano Giuseppe F. , Nissenzweig Amnon
Published: July 2002

We provide data strutures that maintain a graph as edges are inserted and deleted, and keep track of the following properties with the following times: minimum spanning forests, graph connectivity, graph 2-edge connectivity, and bipartiteness in time
O
(
n
1/2
) per change; 3-edge connectivity, in time
O
(
n
2/3
) per change; 4-edge connectivity, in time
O
(
n
α(
n
)) per change;
k
-edge connectivity for constant
k
, in time
O
(
n
log
n
) per change;2-vertex connectivity, and 3-vertex connectivity, in the
O
(
n
) per change; and 4-vertex connectivity, in time
O
(
n
α(
n
)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms.

All our algorithms are based on a new technique that transforms an algorithm for sparse graphs into one that will work on any graph, which we call
sparsification.
Performance evaluation of the Orca shared-object system
Authors: Bal Henri E. , Bhoedjang Raoul , Hofman Rutger , Jacobs Ceriel , Langendoen Koen , Rühl Tim , Kaashoek M. Frans
Published: July 2002

Orca is a portable, object-based distributed shared memory (DSM) system. This article studies and evaluates the design choices made in the Orca system and compares Orca with other DSMs. The article gives a quantitative analysis of Orca's coherence protocol (based on write-updates with function shipping), the totally ordered group communication protocol, the strategy for object placement, and the all-software, user-space architecture. Performance measurements for 10 parallel applications illustrate the trade-offs made in the design of Orca and show that essentially the right design decisions have been made. A write-update protocol with function shipping is effective for Orca, especially since it is used in combination with techniques that avoid replicating objects that have a low read/write ratio. The overhead of totally ordered group communication on application performance is low. The Orca system is able to make near-optimal decisions for object placement and replication. In addition, the article compares the performance of Orca with that of a page-based DSM (TreadMarks) and another object-based DSM (CRL). It also analyzes the communication overhead of the DSMs for several applications. All performance measurements are done on a 32-node Pentium Pro cluster with Myrinet and Fast Ethernet networks. The results show that Orca programs send fewer messages and less data than the TreadMarks and CRL programs and obtain better speedups.
The tea-leaf reader algorithm: an efficient implementation of CRC-16 and CRC-32
Authors: Griffiths Georgia , Stones G. Carlyle
Published: July 2002

The tea-leaf reader CRC algorithms are error-detection algorithms that use a look-ahead table to increase execution speed.
Optimal clock synchronization
Authors: Srikanth T. K. , Toueg Sam
Published: July 2002

We present a simple, efficient, and unified solution to the problems of synchronizing, initializing, and integrating clocks for systems with different types of failures: crash, omission, and arbitrary failures with and without message authentication. This is the first known solution that achieves optimal accuracy—the accuracy of synchronized clocks (with respect to real time) is as good as that specified for the underlying hardware clocks. The solution is also optimal with respect to the number of faulty processes that can be tolerated to achieve this accuracy.
The equalizing impact of a group support system on status differentials
Authors: Tan Bernard C. Y. , Wei Kwok-kee , Watson Richard T.
Published: July 2002

This study investigates the impact of the electronic communication capability of a group support system (GSS) on status differentials in small groups. A laboratory experiment was used to answer the research questions. Three support levels were studied: manual, face-to-face GSS, and dispersed GSS. Two task types were examined: intellective and preference. Five dependent variables reflecting different aspects of status differentials were measured: status influence, sustained influence, residual disagreement, perceived influence, and decision confidence. The results show that manual groups had higher status influence, sustained influence, and decision confidence, but lower residual disagreement than face-to-face GSS and dispersed GSS groups. Preference task groups also produced higher status influence and sustained influence, but lower residual disagreement compared to intellective task groups. In addition, manual groups working on the preference task reported higher perceived influence than face-to-face GSS and dispersed GSS groups working on the same task. These findings suggest that when groups are engaged in activities for which status differentials are undesirable, a GSS can be used in both face-to-face and dispersed settings to dampen status differentials. Moreover, when a task amplifies status differentials, the use of a GSS tends to produce corresponding stronger dampening effects.
Bimodal multicast
Authors: Birman Kenneth P. , Hayden Mark , Ozkasap Oznur , Xiao Zhen , Budiu Mihai , Minsky Yaron
Published: July 2002

There are many methods for making a multicast protocol “reliable.” At one end of the spectrum, a reliable multicast protocol might offer tomicity guarantees, such as all-or-nothing delivery, delivery ordering, and perhaps additional properties such as virtually synchronous addressing. At the other are protocols that use local repair to overcome transient packet loss in the network, offering “best effort” reliability. Yet none of this prior work has treated stability of multicast delivery as a basic reliability property, such as might be needed in an internet radio, television, or conferencing application. This article looks at reliability with a new goal: development of a multicast protocol which is reliable in a sense that can be rigorously quantified and includes throughput stability guarantees. We characterize this new protocol as a “bimodal multicast” in reference to its reliability model, which corresponds to a family of bimodal probability distributions. Here, we introduce the protocol, provide a theoretical analysis of its behavior, review experimental results, and discuss some candidate applications. These confirm that bimodal multicast is reliable, scalable, and that the protocol provides remarkably stable delivery throughput.
Using semantic knowledge for transaction processing in a distributed database
Authors: Garcia-Molina Hector
Published: July 2002

This paper investigates how the semantic knowledge of an application can be used in a distributed database to process transactions efficiently and to avoid some of the delays associated with failures. The main idea is to allow nonserializable schedules which preserve consistency and which are acceptable to the system users. To produce such schedules, the transaction processing mechanism receives semantic information from the users in the form of transaction semantic types, a division of transactions into steps, compatibility sets, and countersteps. Using these notions, we propose a mechanism which allows users to exploit their semantic knowledge in an organized fashion. The strengths and weaknesses of this approach are discussed.
Minimum cost selection of secondary indexes for formatted files
Authors: Anderson Henry D. , Berra P. Bruce
Published: July 2002

Secondary indexes are often used in database management systems for secondary key retrieval. Although their use can improve retrieval time significantly, the cost of index maintenance and storage increases the overhead of the file processing application. The optimal set of indexed secondary keys for a particular application depends on a number of application dependent factors. In this paper a cost function is developed for the evaluation of candidate indexing choices and applied to the optimization of index selection. Factors accounted for include file size, the relative rates of retrieval and maintenance and the distribution of retrieval and maintenance over the candidate keys, index structure, and system charging rates. Among the results demonstrated are the increased effectiveness of secondary indexes for large files, the effect of the relative rates of retrieval and maintenance, the greater cost of allowing for arbitrarily formulated queries, and the impact on cost of the use of different index structures.
Preservation of unambiguity and inherent ambiguity in context-free languages
Authors: Ginsburg Seymour , Ullian Joseph
Published: July 2002

Various elementary operations are studied to find whether they preserve on ambiguity and inherent ambiguity of language (“language” means “context-free language”) The following results are established:

If
L
is an unambiguous language and
S
is a generalized sequential machine, then (a)
S
(
L
) is an unambiguous language if
S
is one-to-one on
L
, and (b)
S
-1
(
L
) is an unambiguous language.

Inherent ambiguity is preserved by every generalized sequential machine which is one-to-one on the set of all words.

The product (either left or right) of a language and a word preserves both unambiguity and inherent ambiguity.

Neither unambiguity nor inherent ambiguity is preserved by any of the following language preserving operations: (a) one state complete sequential machine; (b) product by a two-element set; (c)
Init
(
L
) = [
u
≠ dur in
L
for some
v
]; (d)
Subw
(
L
) = [
w
≠ durr in
L
for some
u
,
v
].
New Methods in Automatic Extracting
Authors: Edmundson H. P.
Published: July 2002

This paper describes new methods of automatically extracting documents for screening purposes, i.e. the computer selection of sentences having the greatest potential for conveying to the reader the substance of the document. While previous work has focused on one component of sentence significance, namely, the presence of high-frequency content words (key words), the methods described here also treat three additional components: pragmatic words (cue words); title and heading words; and structural indicators (sentence location).

The research has resulted in an operating system and a research methodology. The extracting system is parameterized to control and vary the influence of the above four components. The research methodology includes procedures for the compilation of the required dictionaries, the setting of the control parameters, and the comparative evaluation of the automatic extracts with manually produced extracts. The results indicate that the three newly proposed components dominate the frequency component in the production of better extracts.
A Search Procedure for Hamilton Paths and Circuits
Authors: Rubin Frank
Published: July 2002

A search procedure is given which will determine whether Hamilton paths or circuits exist in a given graph, and will find one or all of them. A combined procedure is given for both directed and undirected graphs. The search consists of creating partial paths and making deductions which determine whether each partial path is a section of any Hamilton path whatever, and which direct the extension of the partial paths.
Temporal sequence learning and data reduction for anomaly detection
Authors: Lane Terran , Brodley Carla E.
Published: July 2002

The anomaly-detection problem can be formulated as one of learning to characterize the behaviors of an individual, system, or network in terms of temporal sequences of discrete data. We present an approach on the basis of instance-based learning (IBL) techniques. To cast the anomaly-detection task in an IBL framework, we employ an approach that transforms temporal sequences of discrete, unordered observations into a metric space via a similarity measure that encodes intra-attribute dependencies. Classification boundaries are selected from an
a posteriori
characterization of valid user behaviors, coupled with a domain heuristic. An empirical evaluation of the approach on user command data demonstrates that we can accurately differentiate the profiled user from alternative users when the available features encode sufficient information. Furthermore, we demonstrate that the system detects anomalous conditions
quickly
— an important quality for reducing potential damage by a malicious user. We present several techniques for reducing data storage requirements of the user profile, including instance-selection methods and clustering. As empirical evaluation shows that a new greedy clustering algorithm reduces the size of the user model by 70%, with only a small loss in accuracy.
System-level power optimization
Authors: Benini Luca , Micheli Giovanni de
Published: July 2002

This tutorial surveys design methods for energy-efficient system-level design. We consider electronic sytems consisting of a hardware platform and software layers. We consider the three major constituents of hardware that consume energy, namely computation, communication, and storage units, and we review methods of reducing their energy consumption. We also study models for analyzing the energy cost of software, and methods for energy-efficient software design and compilation.
This survery is organized around three main phases of a system design: conceptualization and modeling design and implementation, and runtime management. For each phase, we review recent techniques for energy-efficient design of both hardware and software.
Scale and performance in a distributed file system
Authors: Howard John H. , Kazar Michael L. , Menees Sherri G. , Nichols David A. , Satyanarayanan M. , Sidebotham Robert N. , West Michael J.
Published: July 2002

The Andrew File System is a location-transparent distributed tile system that will eventually span more than 5000 workstations at Carnegie Mellon University. Large scale affects performance and complicates system operation. In this paper we present observations of a prototype implementation, motivate changes in the areas of cache validation, server process structure, name translation, and low-level storage representation, and quantitatively demonstrate Andrews ability to scale gracefully. We establish the importance of whole-file transfer and caching in Andrew by comparing its performance with that of Sun Microsystems NFS tile system. We also show how the aggregation of files into volumes improves the operability of the system.
The early years of logic programming
Authors: Kowalski Robert A.
Published: July 2002

This firsthand recollection of those early days of logic programming traces the shared influences and inspirations that connected Edinburgh, Scotland, and Marseilles, France.
The TWA reservation system
Authors: Gifford David , Spector Alfred
Published: July 2002

Where can you find a solid, forthright overview of the computer systems and management behind airline reservations? NASA's space shuttle? Or any of the multitude of other large computer systems that support important projects or national activities? It's hard, sometimes impossible: partly because the people who worked on such systems often do not have the time to write about their experiences: and partly because many professional journalists who interview these people do not have the technical background to ferret out answers to the fundamental design questions addressed in these systems.
Sorting on a mesh-connected parallel computer
Authors: Thompson C. D. , Kung H. T.
Published: July 2002

Two algorithms are presented for sorting n
2
elements on an n × n mesh-connected processor array that require O (n) routing and comparison steps. The best previous algoritmhm takes time O(n log n). The algorithms of this paper are shown to be optimal in time within small constant factors. Extensions to higher-dimensional arrays are also given.
A model for verification of data security in operating systems
Authors: Popek Gerald J. , Farber David A.
Published: July 2002

Program verification applied to kernel architectures forms a promising method for providing uncircumventably secure, shared computer systems. A precise definition of data security is developed here in terms of a general model for operating systems. This model is suitable as a basis for verifying many of those properties of an operating system which are necessary to assure reliable enforcement of security. The application of this approach to the UCLA secure operating system is also discussed.
Game interpretation of the deadlock avoidance problem
Authors: Devillers R.
Published: July 2002

The deadlock avoidance problem may be defined informally as the determination, from some a priori information about the processes, resources, operating system, etc., of the “safe situations” which may be realized without endangering the smooth running of the system. When each process specifies its future needs by a flowchart of need-defined steps, a global approach to the phenomenon and its interpretation as a game between the operating system and the processes allows formalization of risk and safety concepts. The bipartite graph representation of this game may then be used to construct explicitly the set of safe states and to study their properties.
Optimal reorganization of distributed space disk files
Authors: Maruyama K. , Smith S. E.
Published: July 2002

In most database organizations, the cost of accessing the database will increase due to structural changes caused by updates and insertions. By reorganizing the database, the access costs can be reduced. A basic problem is to establish the proper tradeoff between performance, storage costs, and reorganization costs. This paper considers the optimum points at which to reorganize a database. A disk file organization which allows for distributed free space is described. A cost function describing the excess costs due to physical disorganization is defined, and this function is minimized to obtain the optimum reorganization points. Numerical examples based on the characteristics of existing disk storage devices are given.
An improved program-synthesizing algorithm and its correctness
Authors: Lee R. C. T. , Waldinger R. J. , Chang C. L.
Published: July 2002

An improved program-synthesizing algorithm based on the algorithm proposed by Waldinger and Lee in 1969 is given. In the old algorithm, the program-synthesizing problem is translated into a theorem-proving problem, and a program is obtained by analyzing a proof. For the improved algorithm, the analysis is not necessary, and a program is obtained as soon as the proof is completed. This is achieved by using a modified variable tracing mechanism invented by Green in 1969. The correctness of the improved algorithm is also proved; i.e. the program thus obtained always satisfies the specification.
Scheduling independent tasks to reduce mean finishing time
Authors: Bruno J. , Coffman E. G. , Sethi R.
Published: July 2002

Sequencing to minimize mean finishing time (or mean time in system) is not only desirable to the user, but it also tends to minimize at each point in time the storage required to hold incomplete tasks. In this paper a deterministic model of independent tasks is introduced and new results are derived which extend and generalize the algorithms known for minimizing mean finishing time. In addition to presenting and analyzing new algorithms it is shown that the most general mean-finishing-time problem for independent tasks is polynomial complete, and hence unlikely to admit of a non-enumerative solution.
Exception handling
Authors: Goodenough John B.
Published: July 2002

This paper defines exception conditions, discusses the requirements exception handling language features must satisfy, and proposes some new language features for dealing with exceptions in an orderly and reliable way. The proposed language features serve to highlight exception handling issues by showing how deficiencies in current approaches can be remedied.
The nucleus of a multiprogramming system
Authors: Hansen Per Brinch
Published: July 2002

This paper describes the philosophy and structure of a multi-programming system that can be extended with a hierarchy of operating systems to suit diverse requirements of program scheduling and resource allocation. The system nucleus simulates an environment in which program execution and input/output are handled uniformly as parallel, cooperating processes. A fundamental set of primitives allows the dynamic creation and control of a hierarchy of processes as well as the communication among them.
Automatic parsing for content analysis
Authors: Damerau Frederick J.
Published: July 2002

Although automatic syntactic and semantic analysis is not yet possible for all of an unrestricted natural language text, some applications, of which content analysis is one, do not have such a stringent coverage requirement. Preliminary studies show that the Harvard Syntactic Analyzer can produce correct and unambiguous identification of the subject and object of certain verbs for approximately half of the relevant occurences. This provides a degree of coverage for content analysis variables which compares favorably to manual methods, in which only a sample of the total available text is normally processed.
Object code optimization
Authors: Lowry Edward S. , Medlock C. W.
Published: July 2002

Methods of analyzing the control flow and data flow of programs during compilation are applied to transforming the program to improve object time efficiency. Dominance relationships, indicating which statements are necessarily executed before others, are used to do global common expression elimination and loop identification. Implementation of these and other optimizations in OS/360 FORTRAN H are described.
An algorithm for hidden line elimination
Authors: Galimberti R.
Published: July 2002

The algorithm presented causes the elimination of hidden lines in the representation of a perspective view of concave and convex plane-faced objects on the picture plane. All the edges of the objects are considered sequentially, and all planes which hide every point of an edge are found.

The computing time increases roughly as the square of the number of edges. The algorithm takes advantage of a reduced number of concave points and automatically recognizes if only one object with no concave points is considered. In this last case, the result is obtained in a much simpler way.
A note on reliable full-duplex transmission over half-duplex links
Authors: Bartlett K. A. , Scantlebury R. A. , Wilkinson P. T.
Published: July 2002

A simple procedure for achieving reliable full-duplex transmission over half-duplex links is proposed. The scheme is compared with another of the same type, which has recently been described in the literature. Finally, some comments are made on another group of related transmission procedures which have been shown to be unreliable under some circumstances.
Remark on Romberg quadrature
Authors: Krasun A. M. , Prager W.
Published: July 2002

A modified form of Romberg quadrature is described, which is less sensitive to the accumulation of rounding errors than the customary one.
A imaginary number system
Authors: Knuth Donald E.
Published: July 2002

For centuries the decimal number system reigned supreme, except, perhaps, among the Mayan Indians, until the advent of digital computers brought the binary and octal systems into the limelight. This paper introduces another number system which may prove useful for manipulating complex numbers on machines.
An efficient I/O interface for optical disks
Authors: Vitter Jeffrey S.
Published: July 2002

We introduce the notion of an I/O interface for optical digital (write-once) disks, which is quite different from earlier research. The purpose of an I/O interface is to allow existing operating systems and application programs that use magnetic disks to use optical disks instead, with minimal change. We define what it means for an I/O interface to be disk-efficient. We demonstrate a practical disk- efficient I/O interface and show that its I/O performance in many cases is optimum, up to a constant factor, among all disk-efficient interfaces. The interface is most effective for applications that are not update-intensive. An additional capability is a built-in history mechanism that provides software support for accessing previous versions of records. Even if not implemented, the I/O interface can be used as a programming tool to develop efficient special purpose applications for use with optical disks.
Tools for navigating large social cyberspaces
Authors: Smith Marc
Published: July 2002

The Netscan project helps online participants form cooperative relationships by offering a better sense of the other players involved.
Inferring sequences produced by pseudo-random number generators
Authors: Boyar Joan
Published: July 2002

In this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators. The generators considered are all of the form

X
n

= Σ
k
j-l
α
j
φ
j
(
X
o
,
X
l
, . . .,

X
n-l

) (mod
m
). In each case, we assume that the functions φ
j
are known and polynomial time computable, but that the coefficients aj and the modulus
m
are unknown. Using this general method, specific examples of generators having this form, the linear congruential method, linear congruences with
n
terms in the recurrence, and quadratic congruences are shown to be cryptographically insecure.
On understanding types, data abstraction, and polymorphism
Authors: Cardelli Luca , Wegner Peter
Published: July 2002

Our objective is to understand the notion of
type
in programming languages, present a model of typed, polymorphic programming languages that reflects recent research in type theory, and examine the relevance of recent research to the design of practical programming languages.

Object-oriented languages provide both a framework and a motivation for exploring the interaction among the concepts of type, data abstraction, and polymorphism, since they extend the notion of type to data abstraction and since type inheritance is an important form of polymorphism. We develop a λ-calculus-based model for type systems that allows us to explore these interactions in a simple setting, unencumbered by complexities of production programming languages.

The evolution of languages from untyped universes to monomorphic and then polymorphic type systems is reviewed. Mechanisms for polymorphism such as overloading, coercion, subtyping, and parameterization are examined. A unifying framework for polymorphic type systems is developed in terms of the typed λ-calculus augmented to include binding of types by quantification as well as binding of values by abstraction.

The typed λ-calculus is augmented by universal quantification to model generic functions with type parameters, existential quantification and packaging (information hiding) to model abstract data types, and bounded quantification to model subtypes and type inheritance. In this way we obtain a simple and precise characterization of a powerful type system that includes abstract data types, parametric polymorphism, and multiple inheritance in a single consistent framework. The mechanisms for type checking for the augmented λ-calculus are discussed.

The augmented typed λ-calculus is used as a programming language for a variety of illustrative examples. We christen this language Fun because fun instead of λ is the functional abstraction keyword and because it is pleasant to deal with.

Fun is mathematically simple and can serve as a basis for the design and implementation of real programming languages with type facilities that are more powerful and expressive than those of existing programming languages. In particular, it provides a basis for the design of strongly typed object-oriented languages.
A distributed mutual exclusion algorithm
Authors: Suzuki Ichiro , Kasami Tadao
Published: July 2002

A distributed algorithm is presented that realizes mutual exclusion among
N
nodes in a computer network. The algorithm requires at most
N
message exchanges for one mutual exclusion invocation. Accordingly, the delay to invoke mutual exclusion is smaller than in an algorithm of Ricart and Agrawala, which requires 2*(
N
- 1) message exchanges per invocation. A drawback of the algorithm is that the sequence numbers contained in the messages are unbounded. It is shown that this problem can be overcome by slightly increasing the number of message exchanges.
Ray tracing generalized cylinders
Authors: Bronsvoort Willem F. , Klok Fopke
Published: July 2002

An algorithm is presented for ray tracing generalized cylinders, that is, objects defined by sweeping a two-dimensional contour along a three-dimensional trajectory. The contour can be any 'well-behaved' curve in the sense that it is continuous, and that the points where the tangent is horizontal or vertical can be determined, the trajectory can be any spline curve. First a definition is given of generalized cylinders in terms of the Frenet frame of the trajectory. Then the main problem in ray tracing these objects, the computation of the intersection points with a ray, is reduced to the problem of intersecting two two-dimensional curves. This problem is solved by a subdivision algorithm. The three-dimensional normal at the intersection point closest to the eye point, necessary to perform shading, is obtained by transforming the two-dimensional normal at the corresponding intersection point of the two two-dimensional curves. In this way it is possible to obtain highly realistic images for a very broad class of objects.
Type theories and object-oriented programmimg
Authors: Danforth Scott , Tomlinson Chris
Published: July 2002

Object-oriented programming is becoming a popular approach to the construction of complex software systems. Benefits of object orientation include support for modular design, code sharing, and extensibility. In order to make the most of these advantages, a type theory for objects and their interactions should be developed to aid checking and controlled derivation of programs and to support early binding of code bodies for efficiency. As a step in this direction, this paper surveys a number of existing type theories and examines the manner and extent to which these theories are able to represent the ideas found in object-oriented programming. Of primary interest are the models provided by type theories for abstract data types and inheritance, and the major portion of this paper is devoted to these topics. Code fragments illustrative of the various approaches are provided and discussed. The introduction provides an overview of object-oriented programming and types in programming languages; the summary provides a comparative evaluation of the reviewed typing systems, along with suggestions for future work.
Types and persistence in database programming languages
Authors: Atkinson Malcolm P. , Buneman O. Peter
Published: July 2002

Traditionally, the interface between a programming language and a database has either been through a set of relatively low-level subroutine calls, or it has required some form of embedding of one language in another. Recently, the necessity of integrating database and programming language techniques has received some long-overdue recognition. In response, a number of attempts have been made to construct programming languages with completely integrated database management systems. These languages, which we term
database programming languages
, are the subject of this review.

The design of these languages is still in its infancy, and the purpose of writing this review is to identify the areas in which further research is required. In particular, we focus on the problems of providing a uniform type system and mechanisms for data to persist. Of particular importance in solving these problems are issues of polymorphism, type inheritance, object identity, and the choice of structures to represent sets of similar values. Our conclusion is that there are areas of programming language research—modules, polymorphism, persistence, and inheritance—that must be developed and applied to achieve the goal of a useful and consistent database programming language. Other research areas of equal importance, such as implementation, transaction handling, and concurrency, are not examined here in any detail.
The design of a relational database system with abstract data types for domains
Authors: Osborn Sylvia L. , Heaven T. E.
Published: July 2002

An extension to the relational model is described in which domains can he arbitrarily defined as abstract data types. Operations on these data types include primitive operations, aggregates, and transformations. It is shown that these operations make the query language complete in the sense of Chandra and Harel. The system has been designed in such a way that new data types and their operations can be defined with a minimal amount of interaction with the database management system.
Efficient distributed event-driven simulations of multiple-loop networks
Authors: Lubachevsky B. D.
Published: July 2002

Simulating asynchronous multiple-loop networks is commonly considered a difficult task for parallel programming. Two examples of asynchronous multiple-loop networks are presented in this article: a stylized queuing system and an Ising model. In both cases, the network is an n × n grid on a torus and includes at least an order of n
2
feedback loops. A new distributed simulation algorithm is demonstrated on these two examples. The algorithm combines three elements: (1) the bounded lag restriction; (2) minimum propagation delays; and (3) the so-called opaque periods. We prove that if N processing elements (PEs) execute the algorithm in parallel and the simulated system exhibits sufficient density of events, then, on average, processing one event would require
O
(log
N
) instructions of one PE. Experiments on a shared memory MIMD bus computer (Sequent's Balance) and on a SIMD computer (Connection Machine) show speed-ups greater than 16 on 25 PEs of a Balance and greater than1900 on 2
14
PEs of a Connection Machine.
The Escrow transactional method
Authors: O'Neil Patrick E.
Published: July 2002

A method is presented for permitting record updates by long-lived transactions without forbidding simultaneous access by other users to records modified. Earlier methods presented separately by Gawlick and Reuter are comparable but concentrate on “hot-spot” situations, where even short transactions cannot lock frequently accessed fields without causing bottlenecks. The Escrow Method offered here is designed to support nonblocking record updates by transactions that are “long lived” and thus require long periods to complete. Recoverability of intermediate results prior to commit thus becomes a design goal, so that updates as of a given time can be guaranteed against memory or media failure while still retaining the prerogative to abort. This guarantee basically completes phase one of a two-phase commit, and several advantages result: (1) As with Gawlick's and Reuter's methods, high-concurrency items in the database will not act as a bottleneck; (2) transaction commit of different updates can be performed asynchronously, allowing natural distributed transactions; indeed, distributed transactions in the presence of delayed messages or occasional line disconnection become feasible in a way that we argue will tie up minimal resources for the purpose intended; and (3) it becomes natural to allow for human interaction in the middle of a transaction without loss of concurrent access or any special difficulty for the application programmer. The Escrow Method, like Gawlick's Fast Path and Reuter's Method, requires the database system to be an “expert” about the type of transactional updates performed, most commonly updates involving incremental changes to aggregate quantities. However, the Escrow Method is extendable to other types of updates.
Hard examples for resolution
Authors: Urquhart Alasdair
Published: July 2002

Exponential lower bounds are proved for the length-of-resolution refutations of sets of disjunctions constructed from expander graphs, using the method of Tseitin. Since these sets of clauses encode biconditionals, they have short (polynomial-length) refutations in a standard axiomatic formulation of propositional calculus.
Software complexity measurement
Authors: Kearney Joseph P. , Sedlmeyer Robert L. , Thompson William B. , Gray Michael A. , Adler Michael A.
Published: July 2002

Inappropriate use of software complexity measures can have large, damaging effects by rewarding poor programming practices and demoralizing good programmers. Software complexity measures must be critically evaluated to determine the ways in which they can best be used.
Resourceful systems for fault tolerance, reliability, and safety
Authors: Abbott Russell J.
Published: July 2002

Above all, it is vital to recognize that completely guaranteed behavior is impossible and that there are inherent risks in relying on computer systems in critical environments. The unforeseen consequences are often the most disastrous [Neumann 1986].

Section 1 of this survey reviews the current state of the art of system reliability, safety, and fault tolerance. The emphasis is on the contribution of software to these areas. Section 2 reviews current approaches to software fault tolerance. It discusses why some of the assumptions underlying hardware fault tolerance do not hold for software. It argues that the current software fault tolerance techniques are more accurately thought of as delayed debugging than as fault tolerance. It goes on to show that in providing both backtracking and executable specifications, logic programming offers most of the tools currently used in software fault tolerance. Section 3 presents a generalization of the recovery block approach to software fault tolerance, called
resourceful systems
. Systems are resourceful if they are able to determine whether they have achieved their goals or, if not, to develop and carry out alternate plans. Section 3 develops an approach to designing resourceful systems based upon a functionally rich architecture and an explicit goal orientation.
Disk arm movement in anticipation of future requests
Authors: King Richard P.
Published: July 2002

When a disk drive's access arm is idle, it may not be at the ideal location. In anticipation of future requests, movement to some other location may be advantageous. The effectiveness of anticipatory disk arm movement is explored. Various operating conditions are considered, and the reduction in seek distances and request response times is determined for them. Suppose that successive requests are independent and uniformly distributed. By bringing the arm to the middle of its range of motion when it is idle, the expected seek distance can be reduced by 25 percent. Nonlinearity in time versus distance can whittle that 25 percent reduction down to a 13 percent reduction in seek time. Nonuniformity in request location, nonPoisson arrival processes, and high arrival rates can whittle the reduction down to nothing. However, techniques are discussed that maximize those savings that are still possible under those circumstances. Various systems with multiple arms are analyzed. Usually, it is best to spread out the arms over the disk area. The both arms should be brought to the middle.
GIBBERELLIN BIOSYNTHESIS: Enzymes, Genes and Their Regulation
Authors: Hedden Peter , Kamiya Yuji
Published: July 2002

▪ Abstract  The recent impressive progress in research on gibberellin (GA) biosynthesis has resulted primarily from cloning of genes encoding biosynthetic enzymes and studies with GA-deficient and GA-insensitive mutants. Highlights include the cloning of ent-copalyl diphosphate synthase and ent-kaurene synthase (formally ent-kaurene synthases A and B) and the demonstration that the former is targeted to the plastid; the finding that the Dwarf-3 gene of maize encodes a cytochrome P450, although of unknown function; and the cloning of GA 20-oxidase and 3β-hydroxylase genes. The availability of cDNA and genomic clones for these enzymes is enabling the mechanisms by which GA concentrations are regulated by environmental and endogenous factors to be studied at the molecular level. For example, it has been shown that transcript levels for GA 20-oxidase and 3β-hydroxylase are subject to feedback regulation by GA action and, in the case of the GA 20-oxidase, are regulated by light. Also discussed is other new information, particularly from mutants, that has added to our understanding of the biosynthetic pathway, the enzymes, and their regulation and tissue localization.
GENETICS OF ANGIOSPERM SHOOT APICAL MERISTEM DEVELOPMENT
Authors: Evans Matthew M. S. , Barton M. Kathryn
Published: July 2002

▪ Abstract  Recent progress has been made in the genetic dissection of angiosperm shoot apical meristem (SAM) structure and function. Genes required for proper SAM development have been identified in a variety of species through the isolation of mutants. In addition, genes with expression patterns indicating they play a role in SAM function have been identified molecularly. The processes of SAM formation, self-renewal, and pattern formation within the SAM are examined with an emphasis on the contributions of recent classical and molecular genetic experiments to our understanding of this basic problem in plant developmental biology.
CRYSTALLOGRAPHIC STRUCTURES OF THE HAMMERHEAD RIBOZYME: Relationship to Ribozyme Folding and Catalysis
Authors: Wedekind Joseph E. , McKay David B.
Published: July 2002

▪ Abstract  The hammerhead ribozyme is a small catalytic RNA that cleaves a target phosphodiester bond in a reaction dependent on divalent metal ions. Crystal structures of the hammerhead reveal the tertiary fold of an enzymatic “ground state” of the molecule; however, they do not clarify the catalytic mechanism of the ribozyme, presumably because a significant conformational rearrangement is required to reach an enzymatic transition state. The structural domains seen in the hammerhead can be related to sequence or structural motifs in transfer and ribosomal RNAs, suggesting that they represent tertiary building blocks that will be found in large, complex RNAs.
MULTIPROTEIN-DNA COMPLEXES IN TRANSCRIPTIONAL REGULATION
Authors: Wolberger Cynthia
Published: July 2002

▪ Abstract  Transcription in eukaryotes is frequently regulated by a mechanism termed combinatorial control, whereby several different proteins must bind DNA in concert to achieve appropriate regulation of the downstream gene. X-ray crystallographic studies of multiprotein complexes bound to DNA have been carried out to investigate the molecular determinants of complex assembly and DNA binding. This work has provided important insights into the specific protein-protein and protein-DNA interactions that govern the assembly of multiprotein regulatory complexes. The results of these studies are reviewed here, and the general insights into the mechanism of combinatorial gene regulation are discussed.
NMR Probes of Molecular Dynamics: Overview and Comparison with Other Techniques
Authors: Palmer III Arthur G.
Published: July 2002

▪ Abstract  NMR spin relaxation spectroscopy is a powerful approach for characterizing intramolecular and overall rotational motions in proteins. This review describes experimental methods for measuring laboratory frame spin relaxation rate constants by high-resolution solution-state NMR spectroscopy, together with theoretical approaches for interpreting spin relaxation data in order to quantify protein conformational dynamics on picosecond-nanosecond time scales. Recent applications of these techniques to proteins are surveyed, and investigations of the contribution of conformational chain entropy to protein function are highlighted. Insights into the dynamical properties of proteins obtained from NMR spin relaxation spectroscopy are compared with results derived from other experimental and theoretical techniques.
ISOFORM SORTING AND THE CREATION OF INTRACELLULAR COMPARTMENTS
Authors: Gunning Peter , Weinberger Ron , Jeffrey Peter , Hardeman Edna
Published: July 2002

▪ Abstract  The generation of isoforms via gene duplication and alternative splicing has been a valuable evolutionary tool for the creation of biological diversity. In addition to the formation of molecules with related but different functional characteristics, it is now apparent that isoforms can be segregated into different intracellular sites within the same cell. Sorting has been observed in a wide range of genes, including those encoding structural molecules, receptors, channels, enzymes, and signaling molecules. This results in the creation of intracellular compartments that (a) can be independently controlled and (b) have different functional properties. The sorting mechanisms are likely to operate at the level of both proteins and mRNAs. Isoform sorting may be an important consequence of the evolution of isoforms and is likely to have contributed to the diversity of functional properties within groups of isoforms.
Secretory Protein Trafficking and Organelle Dynamics in Living Cells
Authors: Lippincott-Schwartz Jennifer , Roberts Theresa H. , Hirschberg Koret
Published: July 2002

▪ Abstract  Green fluorescent protein chimerae acting as reporters for protein localization and trafficking within the secretory membrane system of living cells have been used in a wide variety of applications, including time-lapse imaging, double-labeling, energy transfer, quantitation, and photobleaching experiments. Results from this work are clarifying the steps involved in the formation, translocation, and fusion of transport intermediates; the organization and biogenesis of organelles; and the mechanisms of protein retention, sorting, and recycling in the secretory pathway. In so doing, they are broadening our thinking about the temporal and spatial relationships among secretory organelles and the membrane trafficking pathways that operate between them.
Physics of Partially Saturated Porous Media: Residual Saturation and Seismic-Wave Propagation
Authors: Li Xun , Zhong Lirong , Pyrak-Nolte Laura J
Published: July 2002

▪ Abstract  In this paper, we present a review of seismic-wave propagation in fluid-saturated and partially saturated porous media. Seismic-wave velocity and attenuation are affected by the degree of saturation and the spatial distribution of fluids within the medium. Attenuation mechanisms include local and global flow as well as energy loss caused by scattering. We also present results from acoustic tomography of unconsolidated porous media with residual paraffin saturation. The acoustic attenuation was found to be sensitive to the grain- and subgrain-scale (microscale) distribution of residual saturation; in other words, the residual saturation behaves like soft cement that locally stiffens grain contacts and creates heterogeneity that results in scattering. The effect of microscale phenomena on multigrain scale (macroscale) measurements of seismic-wave attenuation and velocity cannot be ignored.