Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
Articles 1 - 11 of 11
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. …
The Duke Internet Programming Contest, Owen Astrachan, Vivek Khera, David Kotz
The Duke Internet Programming Contest, Owen Astrachan, Vivek Khera, David Kotz
Dartmouth Scholarship
On the evening of October 23, 1990, electronic mail messages started to pour into the computers at the Duke University Computer Science Department. Teams of programmers from all over the world were registering to compete in the first global (as far as the authors are aware) programming contest to be held on the Internet. During the three hour competition, modeled after the annual ACM scholastic programming contest, 60 teams from 37 institutions in 5 countries attempted to solve a set of six programming problems using C or Pascal. Their solutions were sent by electronic mail to Duke, where their programs …
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.
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 …