bluuebunny/crossref_metadata_2025 huggingface dataset:
Concepts and capabilities of a database computer\
Authors: Banerjee Jayanta , Hsiao David K. , Baum Richard I.
Published: July 2002

The concepts and capabilities of a database computer (DBC) are given in this paper. The proposed design overcomes many of the traditional problems of database system software and is one of the first to describe a complete data-secure computer capable of handling large databases.

This paper begins by characterizing the major problems facing today's database system designers. These problems are intrinsically related to the nature of conventional hardware and can only be solved by introducing new architectural concepts. Several such concepts are brought to bear in the later sections of this paper. These architectural principles have a major impact upon the design of the system and so they are discussed in some detail. A key aspect of these principles is that they can be implemented with near-term technology. The rest of the paper is devoted to the functional characteristics and the theory of operation of the DBC. The theory of operation is based on a series of abstract models of the components and data structures employed by the DBC. These models are used to illustrate how the DBC performs access operations, manages data structures and security specifications, and enforces security requirements. Short Algol-like algorithms are used to show how these operations are carried out. This part of the paper concludes with a high-level description of the DBC organization. The actual details of the DBC hardware are quite involved and so their presentation is not the subject of this paper.

A sample database is included in the Appendix to illustrate the working of the security and clustering mechanisms of the DBC.
Analysis of the Address Assignment Problem for Clustered Keys
Authors: Toyoda Junichi , Tezuka Yoshikazu , Kasahara Yoshiro
Published: July 2002

The occurrence pattern of clusterings of keys is analyzed by use of the generating function. Probabilities of occurrences of several clustered patterns are given as the coefficients of generating functions. Moreover, the result when a key-to-address transformation of
aK
+
b
/mod
c
is performed on clustered keys is briefly discussed.
A Formalism for Program Translation
Authors: Slansky J. , Finkelstein M.
Published: July 2002

A formalism for representing sequences or networks of program translations and compiler translations is described. The formalism is shown to be capable of (a) concisely and clearly representing the overall tasks of assemblers and preprocessors, (b) checking for similarities or equivalences among translation networks, and (c) reducing translation networks to smaller entities.
Finite Difference Scheme for a Third Boundary Value Problem
Authors: Zafarullah A.
Published: July 2002

A finite difference scheme for a linear, second-order third boundary value problem in ordinary differential equations is described. The discretization error is found to be
O
(
h
4
).
Computer Interval Arithmetic: Definition and Proof of Correct Implementation
Authors: Good Donald I. , London Ralph L.
Published: July 2002

A definition is given of computer interval arithmetic suitable for implementation on a digital computer. Some computational properties and simplifications are derived. An ALGOL code segment is proved to be a correct implementation of the definition on a specified machine environment.
Waiting Lines and Times in a System with Polling
Authors: Konheim Alan G. , Meister Bernd
Published: July 2002

A communication system consisting of a number of buffered input terminals connected to a computer by a single channel is analyzed. The terminals are polled in sequence and the data is removed from the terminal's buffer. When the buffer has been emptied, the channel, for an interval of randomly determined length, is used for system overhead and/or to transmit data to the terminals. The system then continues with a poll of the next terminal. The stationary distributions of the length of the waiting line and the queueing delay are calculated for the case of identically distributed input processes.
Experimental mathematics: the role of computation in nonlinear science
Authors: Campbell David , Farmer Doyne , Crutchfield Jim , Jen Erica
Published: July 2002

Computers have expanded the range of nonlinear phenomena that can be explored mathematically. An “experimental mathematics facility,” containing both special-purpose dedicated machines and general-purpose mainframes, may someday provide the ideal context for complex nonlinear problems.
The Multics virtual memory
Authors: Bensoussan A. , Clingen C. T. , Daley R. C.
Published: July 2002

As experience with use of on-line operating systems has grown, the need to share information among system users has become increasingly apparent. Many contemporary systems permit some degree of sharing. Usually, sharing is accomplished by allowing several users to share data via input and output of information stored in files kept in secondary storage. Through the use of segmentation, however, Multics provides direct hardware addressing by user and system programs of all information, independent of its physical storage location. Information is stored in segments each of which is potentially sharable and carries its own independent attributes of size and access privilege.

Here, the design and implementation considerations of segmentation and sharing in Multics are first discussed under the assumption that all information resides in a large, segmented main memory. Since the size of main memory on contemporary systems is rather limited, it is then shown how the Multics software achieves the effect of a large segmented main memory through the use of the Honeywell 645 segmentation and paging hardware.
A generalization of AVL trees
Authors: Foster Caxton C.
Published: July 2002

A generalization of AVL trees is proposed in which imbalances up to Δ are permitted, where Δ is a small integer. An experiment is performed to compare these trees with standard AVL trees and with balanced trees on the basis of mean retrieval time, of amount of restructuring expected, and on the worst case of retrieval time. It is shown that, by permitting imbalances of up to five units, the retrieval time is increased a small amount while the amount of restructuring required is decreased by a factor of ten.

A few theoretical results are derived, including the correction of an earlier paper, and are duly compared with the experimental data. Reasonably good correspondence is found.
On computing sets of shortest paths in a graph
Authors: Minieka Edward
Published: July 2002

Two algorithms are presented that construct the
k
shortest paths between every pair of vertices in a directed graph. These algorithms generalize the Floyd algorithm and the Dantzig algorithm for finding the shortest path between every pair of vertices in a directed graph.
Ten Mini-Languages: A Study of Topical Issues in Programming Languages
Authors: Ledgard Henry F.
Published: July 2002

The proliferation of programming languages has raised many issues of language design, definition, and implementation. This paper presents a series of ten mini-languages, each of which exposes salient features found in existing programming languages. The value of the mini-languages lies in their brevity of description and the isolation of important linguistic features: in particular, the notions of assignment, transfer of control, functions, parameter passing, type checking, data structures, string manipulation, and input/output. The mini-languages may serve a variety of uses: notably, as a pedagogical tool for teaching programming languages, as a subject of study for the design of programming languages, and as a set of test cases for methods of language implementation or formal definition.
Third Generation Computer Systems
Authors: Denning Peter J.
Published: July 2002

The common features of third generation operating systems are surveyed from a general view, with emphasis on the common abstractions that constitute at least the basis for a “theory” of operating systems. Properties of specific systems are not discussed except where examples are useful. The technical aspects of issues and concepts are stressed, the nontechnical aspects mentioned only briefly. A perfunctory knowledge of third generation systems is presumed.
The
k
-distribution of generalized feedback shift register pseudorandom numbers
Authors: Fushimi M. , Tezuka S.
Published: July 2002

A necessary and sufficient condition is established for the generalized feedback shift register (GFSR) sequence introduced by Lewis and Payne to be k-distributed. Based upon the theorem, a theoretical test for k-distributivity is proposed and performed in a reasonable amount of computer time, even for k = 16 and a high degree of resolution (for which statistical tests are impossible because of the astronomical amount of computer time required). For the special class of GFSR generators considered by Arvillias and Maritsas based on the primitive trinomial D
p
+ D
q
+ 1 with q = an integral power of 2, it is shown that the sequence is k-distributed if and only if the lengths of all subregisters are at least k. The theorem also leads to a simple and efficient method of initializing the GFSR generator so that the sequence to be generated is k-distributed.
Even no data has a value
Authors: Babad Yair M. , Hoffer Jeffrey A.
Published: July 2002

Data that are missing, lost, or incomplete can be very significant in certain situations. Programs and languages need to be able to identify and manage such data effectively.
The weighted median filter
Authors: Brownrigg D. R. K.
Published: July 2002

The median filter is well-known [
1, 2
]. However, if a user wishes to predefine a set of feature types to remove or retain, the median filter does not necessarily satisfy the requirements. A more general filter, called the Weighted Median Filter, of which the median filter is a special case, is described. It enables filters to be designed with a wide variety of properties. Particular cases of filter requirements are discussed and the corresponding filters are derived. The notion of a minimal weighted median filter, of a subclass that act identically, is introduced and discussed. The question of finding the number of distinct ways a class of filters can act is considered and solved for some classes.
The impact of office automation on the organization
Authors: Olson Margrethe H. , Lucas Henry C.
Published: July 2002

Computer technology has recently been applied to the automation of office tasks and procedures. Much of the technology is aimed not at improving the efficiency of current office procedures, but at altering the nature of office work altogether. The development of automated office systems raises a number of issues for the organization. How will this technology be received by organization members? How will it affect the definition of traditional office work? What will be its impact on individuals, work groups, and the structure of the organization? This paper presents a descriptive model and propositions concerning the potential impacts of office automation on the organization and it stresses the need, when implementing automated office systems, to take a broad perspective of their potential positive and negative effects on the organization. The need for further research examining the potential effects of office automation is emphasized.
A practical interprocedural data flow analysis algorithm
Authors: Barth Jeffrey M.
Published: July 2002

A new interprocedural data flow analysis algorithm is presented and analyzed. The algorithm associates with each procedure in a program information about which variables may be modified, which may be used, and which are possibly preserved by a call on the procedure, and all of its subcalls. The algorithm is sufficiently powerful to be used on recursive programs and to deal with the sharing of variables which arises through reference parameters. The algorithm is unique in that it can compute all of this information in a single pass, not requiring a prepass to compute calling relationships or sharing patterns. The algorithm is asymptotically optimal in time complexity. It has been implemented and is practical even on programs which are quite large.
Packed scatter tables
Authors: Lyon Gordon
Published: July 2002

Scatter tables for open addressing benefit from recursive entry displacements, cutoffs for unsuccessful searches, and auxiliary cost functions. Compared with conventional methods, the new techniques provide substantially improved tables that resemble exact-solution optimal packings. The displacements are depth-limited approximations to an enumerative (exhaustive) optimization, although packing costs remain linear—
O
(
n
)—with table size
n
. The techniques are primarily suited for important fixed (but possibly quite large) tables for which reference frequencies may be known: op-code tables, spelling dictionaries, access arrays. Introduction of frequency weights further improves retrievals, but the enhancement may degrade cutoffs.
Using synthetic images to register real images with surface models
Authors: Horn Berthold K. P. , Bachman Brett L.
Published: July 2002

A number of image analysis tasks can benefit from registration of the image with a model of the surface being imaged. Automatic navigation using visible light or radar images requires exact alignment of such images with digital terrain models. In addition, automatic classification of terrain, using satellite imagery, requires such alignment to deal correctly with the effects of varying sun angle and surface slope. Even inspection techniques for certain industrial parts may be improved by this means.

We achieve the required alignment by matching the real image with a synthetic image obtained from a surface model and known positions of the light sources. The synthetic image intensity is calculated using the reflectance map, a convenient way of describing surface reflection as a function of surface gradient. We illustrate the technique using LANDSAT images and digital terrain models.
Early experience with Mesa
Authors: Geschke Charles M. , Morris James H. , Satterthwaite Edwin H.
Published: July 2002

The experiences of Mesa's first users—primarily its implementers—are discussed, and some implications for Mesa and similar programming languages are suggested. The specific topics addressed are: module structure and its use in defining abstractions, data-structuring facilities in Mesa, an equivalence algorithm for types and type coercions, the benefits of the type system and why it is breached occasionally, and the difficulty of making the treatment of variant records safe.
An interactive computer graphics approach to surface representation
Authors: Wu Sheng-Chuan , Abel John F. , Greenberg Donald P.
Published: July 2002

An interactive computer graphics method has been developed for the rapid generation of arbitrary shaped three-dimensional surfaces. The method is a synthesis of spline theory and algorithms, an interactive means for man-machine communication, and software for static or dynamic graphics display. The basic technique employed is a modified lofting method in which sectional curves are represented by uniform B-splines and the surface is interpolated between sections by Cardinal splines. Among the features of this method are algorithm, which enable interactive modification of the B-spline representation of the sectional curves. At all stages of the process, the spatial information is graphically displayed to the user. Complex surfaces can be created by the combination of a number of shapes that have been separately generated and automatically joined. The system has been successfully interfaced to a variety of analytical routines for structural, medical and graphical applications.
The optimal approach to recursive programs
Authors: Manna Zohar , Shamir Adi
Published: July 2002

The classical fixedpoint approach toward recursive programs suggests choosing the “least defined fixedpoint” as the most appropriate solution to a recursive program. A new approach is described which introduces an “optimal fixedpoint,” which, in contrast to the least defined fixedpoint, embodies the maximal amount of valuable information embedded in the program. The practical implications of this approach are discussed and techniques for proving properties of optimal fixedpoints are given. The presentation is informal, with emphasis on examples.
Reflections on an operating system design
Authors: Lampson Butler W. , Sturgis Howard E.
Published: July 2002

The main features of a general purpose multiaccess operating system developed for the CDC 6400 at Berkeley are presented, and its good and bad points are discussed as they appear in retrospect. Distinctive features of the design were the use of capabilities for protection, and the organization of the system into a sequence of layers, each building on the facilities provided by earlier ones and protecting itself from the malfunctions of later ones. There were serious problems in maintaining the protection between layers when levels were added to the memory hierarchy; these problems are discussed and a new solution is described.
Recursion analysis for compiler optimization
Authors: Walter Kenneth G.
Published: July 2002

A relatively simple method for the detection of recursive use of procedures is presented for use in compiler optimization. Implementation considerations are discussed, and a modification of the algorithm is given to further improve optimization. This analysis can also be used to determine what possible subset of values could be assumed by variables which can only take on a relatively small discrete set of values. The most common are parameters of variables assuming values of label, procedure, or Pascal's enumerated type.
Some performance tests of “quicksort” and descendants
Authors: Loeser Rudolf
Published: July 2002

Detailed performance evaluations are presented for six ACM algorithms:
quicksort
(No. 64),
Shellsort
(No. 201),
stringsort
(No. 207), “
TREESORT3
” (No. 245),
quickersort
(No. 271), and
qsort
(No. 402). Algorithms 271 and 402 are refinements of algorithm 64, and all three are discussed in some detail. The evidence given here demonstrates that
qsort
(No. 402) requires many more comparisons than its author claims. Of all these algorithms,
quickersort
requires the fewest comparisons to sort random arrays.
Ancient Babylonian algorithms
Authors: Knuth Donald E.
Published: July 2002

The early origins of mathematics are discussed, emphasizing those aspects which seem to be of greatest interest from the standpoint of computer science. A number of old Babylonian tablets, many of which have never before been translated into English, are quoted.
Levels of language for portable software
Authors: Brown P. J.
Published: July 2002

An increasing amount of software is being implemented in a portable form. A popular way of accomplishing this is to encode the software in a specially designed machine-independent language and then to map this language, often using a macro processor, into the assembly language of each desired object machine. The design of the machine-independent language is the key factor in this operation. This paper discusses the relative merits of pitching this language at a high level or a low level, and presents some comparative results.
Reducing the retrieval time of scatter storage techniques
Authors: Brent Richard P.
Published: July 2002

A new method for entering and retrieving information in a hash table is described. The method is intended to be efficient if most entries are looked up several times. The expected number of probes to look up an entry, predicted theoretically and verified by Monte Carlo experiments, is considerably less than for other comparable methods if the table is nearly full. An example of a possible Fortran implementation is given.
Syntax-directed documentation for PL360
Authors: Mills Harlan D.
Published: July 2002

The language PL360, together with its phrase structure grammar, is used as a concrete basis for illustrating an idea called syntax-directed documentation. This idea is: (1) to use the phrase structure of a program to define the structure of a formal documentation for that program; (2) to use the syntactic types and identifiers in the resulting structure to trigger the automatic formation of questions to the programmer, whose answers will become part of that documentation; and (3) to provide automatic storage and retrieval facilities so that other programmers who want to understand or modify the program can access the resulting documentation, which is cross-indexed in various ways by syntactic types and objects. A small PL360 program, already found in the literature, is worked out as an example.
Canonical structure in attribute based file organization
Authors: Wong Eugene , Chiang T. C.
Published: July 2002

A new file structure for attribute based retrieval is proposed in this paper. It allows queries involving arbitrary Boolean functions of the attribute-value pairs to be processed without taking intersections of lists. The structure is highly dependent on the way in which the file is to be used and is uniquely determined by the specification of the allowed queries. Thus, for example, the structure for retrieval on the basis of ranges of values on a given attribute would be very different from one where only retrieval on the basis of a single value is permitted.

The file organization being proposed is based on the atoms of a Boolean algebra generated by the queries. The desirable properties claimed for this structure are proved, and file maintenance questions are discussed.
An algorithm for generating root locus diagrams
Authors: Krall Allan M. , Fornaro Robert
Published: July 2002

A technique for using a digital computer to draw both ordinary and time-lag root locus diagrams is described. Ordinary diagrams are drawn much faster and more accurately than ever before. Time-lag diagrams, which had been impossible to obtain, are drawn with the same speed and accuracy as ordinary diagrams.
Synchronization in a parallel-accessed data base
Authors: Shoshani A. , Bernstein A. J.
Published: July 2002

The following problem is considered: Given a data base which can be manipulated simultaneously by more than one process, what are the rules for synchronization which will maximize the amount of parallel activity allowed. It is assumed that the data base can be represented as a graph. An example of such a data base is a hierarchy of directories for an on-line file system. Methods for synchronization of processes are examined; their validity is discussed and their performance compared.
Scientific Applications: BRAD
Authors: Ophir D. , Rankowitz S. , Shepherd B. J. , Spinrad R. J.
Published: July 2002

A multiconsole computer display system has been designed that provides very rich displays at low unit cost. Each BRAD (Brookhaven RAster Display) console can plot tens of thousands of points, or up to 4000 characters at 30 frames per second. After an initial display system investment of $50,000, each display, with teletype, cost less than $3,000.

The technique employed is that of programmatically generating a binary image of the desired display in a computer. The image is written on a rotating drum memory. Independent read heads continuously display the picture, which is generated by swept horizontal lines. A standard TV monitor serves as the display device.

The technique has two drawbacks. A computer must compute any image to be displayed. Also, the “pointing” interaction is more difficult. This is because the pointing function gives only the coordinates of the point on the screen. The inverse of the map generation process is required to calculate the coordinates at the input space.
The simulation of time sharing systems
Authors: Nielsen Norman R.
Published: July 2002

The development of new large scale time-sharing systems has raised a number of problems for computation center management. Not only is it necessary to develop an appropriate hardware configuration for these systems, but appropriate software adjustments must be made. Unfortunately, these systems often do not respond to changes in the manner that intuition would suggest, and there are few guides to assist in the analysis of performance characteristics. The development of a comprehensive simulation model to assist in the investigation of these questions is described in this paper. The resulting model has a general purpose design and can be used to study a variety of time-sharing systems. It can also be used to assist in the design and development of new time-sharing algorithms or techniques. For the sake of efficiency and greater applicability, the model was implemented in a limited FORTRAN subset that is compatible with most FORTRAN IV compilers. The use of the simulation is demonstrated by a study of the IBM 360/67 time-sharing system.
A case study in programming for parallel-processors
Authors: Rosenfeld Jack L.
Published: July 2002

An affirmative partial answer is provided to the question of whether it is possible to program parallel-processor computing systems to efficiently decrease execution time for useful problems. Parallel-processor systems are multiprocessor systems in which several of the processors can simultaneously execute separate tasks of a single job, thus cooperating to decrease the solution time of a computational problem. The processors have independent instruction counters, meaning that each processor executes its own task program relatively independently of the other processors. Communication between cooperating processors is by means of data in storage shared by all processors.

A program for the determination of the distribution of current in an electrical network was written for a parallel-processor computing system, and execution of this program was simulated. The data gathered from simulation runs demonstrate the efficient solution of this problem, typical of a large class of important problems. It is shown that, with proper programming, solution time when

N
P

processors are applied approaches 1/

N
P

times the solution time for a single processor, while improper programming can actually lead to an increase of solution time with the number of processors. Storage interference and other measures of performance are discussed. Stability of the method of solution was also investigated.
GEORGE 3—A general purpose time sharing and operating system
Authors: Oestreicher M. D. , Bailey M. J. , Strauss J. I.
Published: July 2002

An Operating System is described which will run on a wide variety of configurations of the I.C.T. 1900, and can handle a large number of online console users while at the same time running several offline (background) jobs. The system is not oriented towards either mode and can be either a batch processing system (such as the ATLAS Supervisor, IBSYS, or GECOS), or a multiaccess system (resembling, to the user, CTSS or MULTICS), or both simultaneously, depending on the installation, which can adjust the Schedulers.

Both online users and offline jobs use a common Command Language. The system includes a Multilevel device-independent File Store.
Some effects of the 6600 computer on language structures
Authors: Allard R. W. , Wolf K. A. , Zemlin R. A.
Published: July 2002

The problem of compiling efficient 6600 codes prompted the development of an intermediate language reflecting the structure of the machine, that is more easily manipulated in improving object program efficiency. The subject of this paper is the intermediate language and methods of manipulating it.

Compilations of a series of arithmetic statements are discussed. It is assumed that all functions and exponentials have been removed from these statements, and replaced by simple variables. For purposes of simplicity the treatment of subscripts is ignored.

A simplified 6600 structure is presented to illustrate the compiling method. Several assumptions are made for purposes of simplification, although there are cases in which the assumptions are violated in the actual machine.
Evolution of the meta-assembly program
Authors: Ferguson David E.
Published: July 2002

A generalized assembler called a “meta-assembler” is described. The meta-assembler is defined and factors which contributed to its evolution are presented. How a meta-assembler is made to function as an assembly program is described. Finally, the implication of meta-assemblers on compiler design is discussed.
PM, a system for polynomial manipulation
Authors: Collins G. E.
Published: July 2002

PM is an IBM 7094 program system for formal manipulation of polynomials in any number of variables, with integral coefficients unrestricted in size. Some of the formal opeartions which can be performed by the system are sums, differences, products, quotients, derivatives, substitutions and greatest common divisors. PM is based on the REFCO III list processing system, which is described and compared with the LISP and SLIP systems. The PM subroutines for arithmetic of large integers are described as constituting an independently useful subsystem. PM is compared with the ALPAK system in several respects, including the choices of canonical forms for polynomials. A new algorithm for polynomial greatest common divisor calculation is mentioned, and examples are included to illustrate its superiority.
Automatic abstracting and indexing—survey and recommendations
Authors: Edmundson H. P. , Wyllys R. E.
Published: July 2002

In preparation for the widespread use of automatic scanners which will read documents and transmit their contents to other machines for analysis, this report presents a new concept in automatic analysis: the relative-frequency approach to measuring the significance of words, word groups, and sentences. The relative-frequency approach is discussed in detail, as is its application to problems of automatic indexing and automatic abstracting. Included in the report is a summary of automatic analysis studies published as of the date of writing. Conclusions are drawn that point toward more sophisticated mathematical and linguistic techniques for the solution of problems of automatic analysis.
Termination proofs for logic programs with tabling
Authors: Verbaeten Sofie , Schreye Danny De , Sagonas Konstantinos
Published: July 2002

Tabled evaluation is receiving increasing attention in the logic programming community. It avoids many of the shortcomings of SLD execution and provides a more flexible and often considerably more efficient execution mechanism for logic programs. In particular, tabled execution terminates more often than execution based on SLD-resolution. In this article, we introduce two notions of universal termination of logic programming with tabling: quasi-termination and (the stronger notion of) LG-termination. We present sufficient conditions for these two notions of termination, namely quasi-acceptability and LG-acceptability, and we show that these conditions are also necessary in case the selection of tabled predicates meets certain natural criteria. Starting from these conditions, we develop modular termination proofs, i.e., proofs capable of combining termination proofs of separate programs to obtain termination proofs of combined programs. Finally, in the presence of mode information, we state sufficient conditions which form the basis for automatically proving termination in a constraint-based way.
A general approach to dynamic packet routing with bounded buffers
Authors: Broder Andrei Z. , Frieze Alan M. , Upfal Eli
Published: July 2002

We prove a sufficient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of static routing. We show that certain high probability and worst case bounds on the quasi-static (finite past) performance of a routing algorithm imply bounds on the performance of the dynamic version of that algorithm. Our technique is particularly useful in analyzing routing on networks with bounded buffers where complicated dependices make standard queuing techniques inapplicable.

We present several applications of our approach. In all cases we start from a known static algorithm, and modify it to fit our framework. In particular we give the first dynamic algorithms for routing on a butterfly or two-dimensional mesh with bounded buffers. Both the injection rate for which the algorithm is stable, and the expected time a packet spends in the system are optimal up to constant factors. Our approach is also applicable to the recently introduced adversarial input model.
Toward automating the software-development cycle
Authors: Frenkel Karen A.
Published: July 2002

Knowledge-intensive rather than labor-intensive processes are being advanced to spur programming productivity.
Real-time protocol analysis for detecting link-state routing protocol attacks
Authors: Chang Ho-Yen , Wu S. Felix , Jou Y. Frank
Published: July 2002

A real-time knowledge-based network intrusion-detection model for a link-state routing protocol is presented for the
OSPF
protocol. This model includes three layers: a
data process layer
to parse packets and dispatch data; and
event abstractor
to abstract predefined real-time events for the link-state routing protocol; and an
extended timed finite state machine
to express the real-time behavior of the protocol engine and to detect intrusions by pattern matching. The timed FSM, called the
JiNao Finite State Machine
(JFSM) is extended from the conventional FSM with timed states, multiple timers, and time constraints on state transitions. The JFSM is implemented as a generator that can create and FSM by constructing the configuration file only. The results show that this approach is very effective for detecting real-time intrusions. Our approach can be extended for use in other network protocol intrusion-detection systems, especially for those with known attacks.
A hierarchical boundary model for solid object representation
Authors: De Floriani Leila , Falcidieno Bianca
Published: July 2002

A new hierarchical model for solid object representation is described. This model, called a
hierarchical face adjacency hypergraph
(HFAH), is based on a relational description of the object boundary, called a
face adjacency hypergraph
(FAH), which considers faces as the primary topological entities defining the object boundary. The HFAH consists of a hierarchy of FAHs describing the decomposition of the boundary of an object into form features. In this paper the HFAH is described together with its internal encoding structure. Two basic transformations, called
refinement
and
abstraction
, are defined on the hierarchical model; these allow effective and efficient modifications of the hierarchical boundary model.
Physical database design for relational databases
Authors: Finkelstein S. , Schkolnick M. , Tiberio P.
Published: July 2002

This paper describes the concepts used in the implementation of DBDSGN, an experimental physical design tool for relational databases developed at the IBM San Jose Research Laboratory. Given a workload for System R (consisting of a set of SQL statements and their execution frequencies), DBDSGN suggests physical configurations for efficient performance. Each configuration consists of a set of indices and an ordering for each table. Workload statements are evaluated only for atomic configurations of indices, which have only one index per table. Costs for any configuration can be obtained from those of the atomic configurations. DBDSGN uses information supplied by the System R optimizer both to determine which columns might be worth indexing and to obtain estimates of the cost of executing statements in different configurations. The tool finds efficient solutions to the index-selection problem; if we assume the cost estimates supplied by the optimizer are the actual execution costs, it finds the optimal solution. Optionally, heuristics can be used to reduce execution time. The approach taken by DBDSGN in solving the index-selection problem for multiple-table statements significantly reduces the complexity of the problem. DBDSGN's principles were used in the Relational Design Tool (RDT), an IBM product based on DBDSGN, which performs design for SQL/DS, a relational system based on System R. System R actually uses DBDSGN's suggested solutions as the tool expects because cost estimates and other necessary information can be obtained from System R using a new SQL statement, the EXPLAIN statement. This illustrates how a system can export a model of its internal assumptions and behavior so that other systems (such as tools) can share this model.
Secure virtual enclaves
Authors: Shands Deborah , Jacobs Jay , Yee Richard , Sebes E. John
Published: July 2002

The Secure Virtual Enclaves (SVE) collaboration infrastructure allows multiple organizations to share their distributed application objects, while respecting organizational autonomy over local resources. The infrastructure is transparent to applications, which may be accessed via a web server, or may be based on Java or Microsoft's DCOM. The SVE infrastructure is implemented in middleware, with no modifications to COTS operating systems or network protocols. The system enables dynamic updates to security policies to support changes in both coalition membership and participants' perception of risks. While the prototype demonstrates fine-grained access control for secure collaborative computing, we have identified significant issues that remain to be addressed, particularly in the area of policy development, before such collaboration will be convenient. The SVE infrastructure offers a platform and conceptual basis for further exploration of these issues and experimentation with new solutions.
Some problems with the notion of context-aware computing
Authors: Erickson Thomas
Published: July 2002

Ask not for whom the cell phone tolls.
The SecureRing group communication system
Authors: Kihlstrom Kim Potter , Moser L. E. , Melliar-Smith P. M.
Published: July 2002

Secure reliable group communication protocols can facilitate the development of survivable distributed systems that are able to remain correct and reliable despite intrusions that cause some nodes to behave in an arbitrary or malicious manner. However, the development of such protocols is itself difficult, and prior systems have exhibited high overheads, primarily due to the cost of digital signatures. The SecureRing group communication system provides secure, reliable, totally-ordered message delivery and group membership services despite the malicious corruption of a constant fraction of the processors within the system. The network is assumed not to partition, and persistent communication faults are handled as processor faults. The SecureRing message delivery protocol makes use of message digests in a signed token to allow a single digital signature to cover multiple messages, and to avoid the need for multiple rounds of message exchange in normal operation. While these techniques mean that messages are not authenticated in real time, they enable the SecureRing protocols to achieve high throughput and reasonable latency.
Configurable development processes
Authors: Cameron John
Published: July 2002

Keeping the focus on what is being produced.
Social translucence
Authors: Erickson Thomas , Halverson Christine , Kellogg Wendy A. , Laff Mark , Wolf Tracee
Published: July 2002

Making social cues visible and persistent helps online groups govern their activities.
A model for predicting and evaluating computer resource consumption
Authors: Ahituv Niv , Igbaria Magid
Published: July 2002

Evaluation and prediction of computer resource consumption can aid in the determination of computer selection and configuration planning as well as in the usefulness and maintenance of existing systems. The model presented can be used in a "What If" mode to make these determinations.
The polynomial-time hierarchy and sparse oracles
Authors: Balcázar Jose L. , Book Ronald V. , Schöning Uwe
Published: July 2002

Questions about the polynomial-time hierarchy are studied. In particular, the questions, “Does the polynomial-time hierarchy collapse?” and “Is the union of the hierarchy equal to PSPACE?” are considered, along with others comparing the union of the hierarchy with certain probabilistic classes. In each case it is shown that the answer is “yes” if and only if
for every
sparse set
S
, the answer is “yes” when the classes are relativized to
S
if and only if
there exists
a sparse set
S
such that the answer is “yes” when the classes are relativized to
S
. Thus, in each case the question is answered if it is answered for any arbitrary sparse oracle set.

Long and Selman first proved that the polynomial-time hierarchy collapses if and only if for every sparse set
S
, the hierarchy relative to
S
collapses. This result is re-proved here by a different technique.
Fixed versus variable order Runge-Kutta
Authors: Shampine L. F. , Baca L. S.
Published: July 2002

Popular codes for the numerical solution of nonstiff ordinary differential equations (ODEs) are based on a (fixed order) Runge-Kutta method, a variable order Adams method, or an extrapolation method. Extrapolation can be viewed as a variable order Runge-Kutta method. It is plausible that variation of order could lead to a much more efficient Runge-Kutta code, but numerical comparisons have been contradictory.

We reconcile previous comparisons by exposing differences in testing methodology and incompatibilities of the implementations tested. An experimental Runge-Kutta code is compared to a state-of-the-art extrapolation code. With some qualifications, the extrapolation code shows no advantage. Extrapolation does not appear to be a particularly effective way to vary the order of Runge-Kutta methods. Although an acceptable way to solve nonstiff problems, our tests raise the question as to whether there is any point in pursuing it as a separate method.
4.2BSD and 4.3BSD as examples of the UNIX system
Authors: Quarterman John S. , Silberschatz Abraham , Peterson James L.
Published: July 2002

This paper presents an in-depth examination of the 4.2 Berkeley Software Distribution, Virtual VAX-11 Version (4.2BSD), which is a version of the UNIX Time-Sharing System. There are notes throughout on 4.3BSD, the forthcoming system from the University of California at Berkeley. We trace the historical development of the UNIX system from its conception in 1969 until today, and describe the design principles that have guided this development. We then present the internal data structures and algorithms used by the kernel to support the user interface. In particular, we describe process management, memory management, the file system, the I/O system, and communications. These are treated in as much detail as the UNIX licenses will allow. We conclude with a brief description of the user interface and a set of bibliographic notes.
Countable nondeterminism and random assignment
Authors: Apt K. R. , Plotkin G. D.
Published: July 2002

Four semantics for a small programming language involving unbounded (but countable) nondeterminism are provided. These comprise an operational semantics, two state transformation semantics based on the Egli-Milner and Smyth orders, respectively, and a weakest precondition semantics. Their equivalence is proved. A Hoare-like proof system for total correctness is also introduced and its soundness and completeness in an appropriate sense are shown. Finally, the recursion theoretic complexity of the notions introduced is studied. Admission of countable nondeterminism results in a lack of continuity of various semantic functions, and this is shown to be necessary for any semantics satisfying appropriate conditions. In proofs of total correctness, one resorts to the use of (countable) ordinals, and it is shown that all recursive ordinals are needed.
Partitioned signature files: design issues and performance evaluation
Authors: Lee Dik Lun , Leng Chun-Wu
Published: July 2002

A signature file acts as a filtering mechanism to reduce the amount of text that needs to be searched for a query. Unfortunately, the signature file itself must be exhaustively searched, resulting in degraded performance for a large file size. We propose to use a deterministic algorithm to divide a signature file into partitions, each of which contains signatures with the same “key.” The signature keys in a partition can be extracted and represented as the partition's key. The search can then be confined to the subset of partitions whose keys match the query key. Our main concern here is to study methods for obtaining the keys and their performance in terms of their ability to reduce the search space.

Owing to the reduction of search space, partitioning a signature file has a direct benefit in a sequential search (single-processor) environment. In a parallel environment, search can be conducted in parallel effectively by allocating one or more partitions to a processor. Partitioning the signature tile with a deterministic method (as opposed to a random partitioning scheme) provides intraquery parallelism as well as interquery parallelism.

In this paper, we outline the criteria for evaluating partitioning schemes. Three algorithms are described and studied. An analytical study of the performance of the algorithms is provided and the results are verified with simulation.
Using a relational system on Wall Street: the good, the bad, the ugly, and the ideal
Authors: Rozen Steve , Shasha Dennis
Published: July 2002

Developers of a Wall Street financial application were able to exploit a relational DBMS to advantage for some data management tasks (the good). For others, the relational system was not helpful (the bad), or could be pressed into service only by means of major or minor contortions (the ugly). The authors identify database constructs that would have simplified developing the application (the ideal).
The coordinated use of five performance evaluation methodologies
Authors: Anderson Gordon E.
Published: July 2002

Information system design can be influenced and ultimate performance parameters accurately forecast through the coordinated use of five performance analysis tools. The complementary methodology is used to first predict and then validate system performance throughout its life cycle.
Debugging concurrent programs
Authors: McDowell Charles E. , Helmbold David P.
Published: July 2002

The main problems associated with debugging concurrent programs are increased complexity, the "probe effect," nonrepeatability, and the lack of a synchronized global clock. The probe effect refers to the fact that any attempt to observe the behavior of a distributed system may change the behavior of that system. For some parallel programs, different executions with the same data will result in different results even without any attempt to observe the behavior. Even when the behavior can be observed, in many systems the lack of a synchronized global clock makes the results of the observation difficult to interpret. This paper discusses these and other problems related to debugging concurrent programs and presents a survey of current techniques used in debugging concurrent programs. Systems using three general techniques are described: traditional or breakpoint style debuggers, event monitoring systems, and static analysis systems. In addition, techniques for limiting, organizing, and displaying a large amount of data produced by the debugging systems are discussed.