Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 16 of 16
Full-Text Articles in Physical Sciences and Mathematics
A Tight Upper Bound On The Benefits Of Replication And Consistency Control Protocols, Donald B. Johnson, Larry Raab
A Tight Upper Bound On The Benefits Of Replication And Consistency Control Protocols, Donald B. Johnson, Larry Raab
Computer Science Technical Reports
We present an upper bound on the performance provided by a protocol guaranteeing mutually exclusive access to a replicated resource in a network subject to component failure and subsequent partitioning. The bound is presented in terms of the performance of a single resource in the same network. The bound is tight and is the first such bound known to us. Since mutual exclusion is one of the requirements for maintaining the consistency of a database object, this bound provides an upper limit on the availability provided by any database consistency control protocol, including those employing dynamic data relocation and replication. …
Robot Pedagogics: The Adaptation, Analysis, And Computer Control Of A Model Manipulator, Edward T. Hammerand, Chung You Ho
Robot Pedagogics: The Adaptation, Analysis, And Computer Control Of A Model Manipulator, Edward T. Hammerand, Chung You Ho
Computer Science Technical Reports
The subject of robotics is addressed by many different fields, among them computer science, electrical engineering, and mechanical engineering. This work is an attempt to bring together all of these aspects from the perspective of a computer science background. Different techniques are considered and reconciled with one another in the analytical area, while detail and explanation are added in all areas that were not previously available. In addition, geometrical interpretations arc presented for concepts that have heretofore been presented only in the form of equations.
A Direct Access Method Using A Neural Network Model, John William Meyer, George Winston Zobrist
A Direct Access Method Using A Neural Network Model, John William Meyer, George Winston Zobrist
Computer Science Technical Reports
One of the concerns in computer science involves optimizing usage of machines to make them more efficient and cost effective. One item of particular concern is the use of secondary storage devices, devices that store data other than in the main memory of the computer to which it is attached. The times for searching for data on these devices consistently proves to be a contributing factor in inefficient computer usage.
One data access method that avoids searching when possible is the hashing method. A function is defined to return the record number of a record based on its key field. …
Input Data Pattern Encoding For Neural Net Algorithms, Hyeoncheol Kim, George Winston Zobrist
Input Data Pattern Encoding For Neural Net Algorithms, Hyeoncheol Kim, George Winston Zobrist
Computer Science Technical Reports
First, a brief overview of neural networks and their applications are described, including the BAM (Bidirectional Associative Memory) model.
A bucket-weight-matrix scheme is proposed, which is a data pattern encoding method that is necessary to transform a set of real-world numbers into neural network state numbers without losing the pattern property the set has. The scheme is designed as a neural net so that it can be combined with other data processing neural nets. The net itself can be used as a bucket-sorting net also. This shows that traditional data structure problems can be an area that neural networks may …
Algorithms And Probabilistic Bounds For The Chromatic Number Of Random Composite Graphs, Jack L. Oakes, Billy E. Gillett
Algorithms And Probabilistic Bounds For The Chromatic Number Of Random Composite Graphs, Jack L. Oakes, Billy E. Gillett
Computer Science Technical Reports
The composite graph coloring problem (CGCP) is a generalization of the standard graph coloring problem (SGCP). Associated with each vertex is a positive integer called its chromaticity. The chromaticity of a vertex specifies the number of consecutive colors which must be assigned to it.
An exact algorithm for solving the CGCP is presented. The algorithm is a generalization of the vertex-sequential with dynamic reordering approach for the SGCP. It is shown that the method is as effective on composite graphs as its counterpart is on standard graphs. Let X̅(CGnp) and X̅(SGnp) denote, respectively, the mean chromatic …
A Bound Of Data Availability When Networks Partition, Michael Goldweber, Donald B. Johnson
A Bound Of Data Availability When Networks Partition, Michael Goldweber, Donald B. Johnson
Computer Science Technical Reports
Many consistency or replication control schemes that increase data availability in distributed systems exist, and the search for improvements continues, though there have been no good nontrivial upper bound demonstrating how much improvement is possible. We present a new upper bound for data availability under replication for general networks. In addition we also describe a new technique that yields near optimal levels of data availability with respect to this bound.
A Fast O(K) Multicast Message Routing Algorithm, Thomas J. Sager, Bruce M. Mcmillin
A Fast O(K) Multicast Message Routing Algorithm, Thomas J. Sager, Bruce M. Mcmillin
Computer Science Technical Reports
In many multicomputer applications is it necessary for one node to send an identical message to many nodes. One to many communications are called multicasts. Although broadcasts (one to all) and unicasts (one to one) have been widely implemented, multicasts, in spite of their importance to efficient use of multicomputer systems, have not received much attention.
Minimal traffic multicasting is equivalent to the minimal Steiner tree problem and is known to be NP-complete. Therefore, a heuristic polynomial time approximation must be used; but, to take advantage of advances in second generation multicomputer hardware such as wormhole routing, a distributed multicast …
Computational Complexity Of Geometric Symmetry Detection In Graphs, Joseph Manning
Computational Complexity Of Geometric Symmetry Detection In Graphs, Joseph Manning
Computer Science Technical Reports
Constructing a visually informative drawing of an abstract graph is a problem of considerable practical importance, and has recently been the focus of much investigation. Displaying symmetry has emerged as one of the foremost criteria for achieving good drawings. Linear-time algorithms are already known for the detection and display of symmetry in trees, outerplanar graphs, and embedded planar graphs. The central results of this paper show that for general graphs, however, detecting the presence of even a single axial or rotational symmetry is NP-complete. A number of related results are also established, including the #P-completeness of counting the axial or …
Building Voronoi Diagrams For Convex Polygons In Linear Expected Time, L Paul Chew
Building Voronoi Diagrams For Convex Polygons In Linear Expected Time, L Paul Chew
Computer Science Technical Reports
Let P be a list of points in the plane such that the points of P taken in order form the vertices of a convex polygon. We introduce a simple, linear expected-time algorithm for finding the Voronoi diagram of the points in P. Unlike previous results on expected-time algorithms for Voronoi diagrams, this method does not require any assumptions about the distribution of points. With minor modifications, this method can be used to design fast algorithms for certain problems involving unrestricted sets of points. For example, fast expected-time algorithms can be designed to delete a point from a Voronoi diagram, …
Term Reduction Using Directed Congruence Closure, L Paul Chew
Term Reduction Using Directed Congruence Closure, L Paul Chew
Computer Science Technical Reports
Many problems in computer science can be described in terms of reduction rules that tell how to transform terms. Problems that can be handled in this way include interpreting programs, implementing abstract data types, and proving certain kinds of theorems. A terms is said to have a normal form if it can be transformed, using the reduction rules, into a term to which no further reduction rules apply. In this paper, we extend the Congruence Closure Algorithm, an algorithm for finding the consequences of a finite set of equations, to develop Directed Congruence Closure, a technique for finding the normal …
Planar Graphs And Sparse Graphs From Efficient Motion Planning In The Plane, L Paul Chew
Planar Graphs And Sparse Graphs From Efficient Motion Planning In The Plane, L Paul Chew
Computer Science Technical Reports
Given a source, a destination, and a number of obstacles in the plane, the Motion Planning Program is to determine the best path to move an object (a robot) from the source to the destination without colliding with any of the obstacles. For us, motion is restricted to the plane, the robot is represented by a point, and the obstacles are represented by a set of polygons with a total of n vertices among all the polygonal obstacles.
Applying The Take-Grant Protection Model, Matt Bishop
Applying The Take-Grant Protection Model, Matt Bishop
Computer Science Technical Reports
The Take-Grant Protection Model has in the past been used to model multilevel security hierarchies and simple protection systems. The models are extended to include theft of rights and sharing of information, and additional security policies are examined. The analysis suggests that in some cases the basic rules of the Take-Grant Protection Model should be augmented to represent the policy properly; when appropriate, such modifications are made and their effects with respect to the policy and its Take-Grant representations are discussed.
A Proactive Password Checker, Matt Bishop
A Proactive Password Checker, Matt Bishop
Computer Science Technical Reports
Password selection has long been a difficult issue; traditionally, passwords are either assigned by the computer or chosen by the user. When the computer does the assignments, the passwords are often hard to remember; when the User makes the selection, the passwords are often easy to guess. This paper describes a technique, and a mechanism, to allow users to select passwords which to them are easy to remember but to others would be very difficult to guess. The technique is site, user, and group configurable, and allows rapid changing of constraints impossed upon the passwords. Although experience with this technique …
Administrator's Guide To The Digital Signature Facility "Rover", Matt Bishop
Administrator's Guide To The Digital Signature Facility "Rover", Matt Bishop
Computer Science Technical Reports
This document describes the installation and maintenance of the rover utility, which provides a digital signature capability for internet messages.
Effects Of Replication On Data Availability, Donald B. Johnson, Larry Raab
Effects Of Replication On Data Availability, Donald B. Johnson, Larry Raab
Computer Science Technical Reports
In this paper we examine the effects of replication on the availability of data in a large network. This analysis differs from previous analyses in that it compares the performance of a dynamic consistency control protocol not only to that of other consistency control protocols, but also to the performance of non-replication and to an upper bound on data availability. This analysis also differes in that we gather extensive simulations on large networks subject to partitions at realistically high component reliabilities. We examine the dynamic consistency protocol presented by Jajodia and Mutchler [9, 12] and by Long and Paris[18] along …
Finding Optimal Quorum Assigments For Distributed Databases, Donald B. Johnson, Larry Raab
Finding Optimal Quorum Assigments For Distributed Databases, Donald B. Johnson, Larry Raab
Computer Science Technical Reports
Replication has been studied as a method of increasing the availability of a data item in a distributed database subject to component failures and consequent partitioning. The potential for partitioning requires that a protocol be employed which guarantees that any access to a data item is aware of the most recent update to that data item. By minimizing the number of access requests denied due to this constraint, we maximize availability. In the event that all access requests are reads, placing one copy of the data item at each site clearly leads to maximum availability. The other extreme, all access …