perm filename TWELVE.PUB[BIB,CSR] blob
sn#591720 filedate 1981-05-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00011 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 .require "setup.csr[bib,csr]" source file
C00005 00003 %3STAN-CS-81-846:
C00007 00004 %3STAN-CS-81-847:
C00008 00005 %3STAN-CS-81-848:
C00010 00006 %3STAN-CS-81-849:
C00012 00007 %3STAN-CS-80-850:
C00015 00008 %3STAN-CS-81-851:
C00017 00009 %3STAN-CS-81-852:
C00018 00010 %3STAN-CS-81-853:
C00020 00011 %3STAN-CS-81-854:
C00022 ENDMK
C⊗;
.require "setup.csr[bib,csr]" source file;
.once center
%3Stanford University Computer Science Reports%1
List Number 12↔June 1981
Listed here are abstracts of the most recent reports published by the
Department of Computer Science at Stanford University.
%3Request Reports:%1 Complete the enclosed order form, and return the
entire order form page (including mailing label) as soon as possible. In
many cases we can print only a limited number of copies, and requests will
be filled on a first come, first served basis as the reports become
available. If the code (FREE) is printed on your mailing label, you will
not be charged for hardcopy. be charged for hardcopy. This exemption
from payment is limited primarily to university libraries which have an
exchange agreement with our Computer Science Library. Because of
increased costs, we have had to reduce the number of people in the FREE
category. (California sales tax will be added at the time of invoicing.
%2Please send no money now, wait until you get an invoice.%1)
%3Alternatively:%1 Copies of most Stanford CS Reports may be obtained by
writing (about 2 months after the ''Most Recent CS Reports'' listing) to
National Technical Information Service, 5285 Port Royal Road, Springfield,
Virginia 22161. Stanford Ph.D. theses are available from University
Microfilms, 300 North Zeeb Road, Ann Arbor, Michigan 48106.
%3STAN-CS-81-846:
%2The Byzantine Generals Strike Again%1
by Danny Dolev (26 pages, March 1981)
Can unanimity be achieved in an unreliable distributed system? This
problem was named "The Byzantine Generals Problem," by Lamport, Pease and
Shostak . The results obtained in the present paper prove that
unanimity is achievable in %2any%1 distributed system %2if and only if%1
the number of faulty processors in the system is:
1) less than one third of the total number of processors; and 2) less than
one half of the connectivity of the system's network.
In cases where unanimity is achievable, algorithms to obtain it are given.
This result forms a complete characterization of networks in light of the
Byzantine Problem.
%3STAN-CS-81-847:
%2The Optimal Locking Problem in a Directed Acyclic Graph%1
by Henry F. Korth (6 pages, March 1981)
We assume a multiple granularity database locking scheme similar to that
of Gray, et al [1975] in which a rooted directed acyclic graph is used to
represent the levels of granularity. We prove that even if it is known in
advance exactly what database references the transaction will make, it is
%2NP%1-complete to find the optimal locking strategy for the transaction.
%3STAN-CS-81-848:
%2On the Problem of Inputting Chinese Characters%1
by Chih-sung Tang (9 pages, April 1981)
If Chinese-speaking society is to make the best use of computers, it is
important to develop an easy, quick, and convenient way to input Chinese
characters together with other conventional characters. Many people have
tried to approach this problem by designing special typewriters for
Chinese character input, but such methods have serious deficiencies and
they do not take advantage of the fact that the input process is just part
of a larger system in which a powerful computer lies behind the keyboard.
The purpose of this note is to clarify the problem and to illustrate a
promising solution based entirely on a standard ASCII keyboard.
%3STAN-CS-81-849:
%2Experiments on the Knee Criterion in a Multiprogrammed Computer System%1
by Tohru Nishigaki (28 pages, March 1981)
Although the effectiveness of the Knee Criterion as a virtual memory
management strategy is widely accepted, it has been impossible to take
advantage of it in a practical system, because little information is
available about the program behavior of executing jobs.
A new memory management technique to achieve the Knee Criterion in a
multiprogrammed virtual memory system is developed. The technique,
termed the Optimum Working-set Estimator (OWE), abstracts the programs'
behavior from their past histories by exponential smoothing, and modifies
their working set window sizes in order to attain the Knee Criterion.
The OWE method was implemented and investigated. Measurements demonstrate
its ability to control a variety of jobs. Furthermore the results also
reveal that the throughput improvement is possible in a space-squeezing
environment. This technique is expected to increase the efficiency of
multiprogrammed virtual memory systems.
%3STAN-CS-80-850:
%2Performing Remote Operations Efficiently on a Local Computer Network%1
by Alfred Z. Spector (23 pages, December 1980)
This paper presents a communication model for local networks, whereby
processes execute generalized remote references that cause operations to
be performed by remote processes. This remote reference/remote operation
model provides a taxonomy of primitives that (1) are naturally useful in
many applications and (2) can be efficiently implemented. The motivation
for this work is our desire to develop systems architectures for local
network-based multiprocessors that support distributed applications
requiring frequent interprocessor communication.
After a section containing a brief overview, Section 2 of this paper
discusses the remote reference/remote operation model. In it, we derive a
set of remote reference types that can be supported by a communication
system carefully integrated with local network interface. The third
section exemplifies a communication system that provides one remote
reference type. These references (i.e., remote load, store,
compare-and-swap, enqueue, and dequeue) take about 150 microseconds, or 50
average instruction times, to perform on Xerox Alto computers connected by
a 2.94 megabit Ethernet. The last section summarizes this work and
proposes a complete implementation resulting in a highly efficient
communication system.
%3STAN-CS-81-851:
%2Binding in Information Processing%1
by Gio Wiederhold (41 pages, May 1981)
The concept of binding, as used in programming systems, is analyzed and
defined in a number of contexts. The attributes of variables to be bound
and the phases of binding are enumerated.
The definition is then broadened to cover general issues in information
systems. Its applicability is demonstrated in a wide range of system
design and implementation issues. A number of Database Management Systems
are categorized according to the terms defined. A first-order
quantitative model is developed and compared with current practice. The
concepts and the model are considered helpful when used as a tool for the
global design phase of large information systems.
%3STAN-CS-81-852:
%2A View of Directions in Relational Database Theory%1
by Jeffrey D. Ullman (9 pages, May 1981)
We shall briefly survey what the author believes are some of the most
fruitful directions in relational database theory. These directions
include dependency inferences, support for the universal relation concept,
null value semantics, and an exploration of the properties of acyclic
database schemes.
%3STAN-CS-81-853:
%2Connections in Acyclic Hypergraphs%1
by David Maier and Jeffrey D. Ullman (10 pages, May 1981)
We demonstrate a sense in which the equivalence between blocks (subgraphs
without articulation points) and biconnected components (subgraphs in
which there are two edge-disjoint paths between any pair of nodes) that
holds in ordinary graph theory can be generalized to hypergraphs. The
result has an interpretation for relational databases that the universal
relations described by acyclic join dependencies are exactly those for
which the connections among attributes are defined uniquely. We also
exhibit a relationship between the process of Graham reduction [G] of
hypergraphs and the process of tableau reduction [ASaU] that holds only
for acyclic hypergraphs.
%3STAN-CS-81-854:
%2On the Security of Public Key Protocols%1
by D. Dolev and A. C. Yao (22 pages, May 1981)
Recently, the use of public key encryption to provide secure network
communication has received considerable attention. Such public key
systems are usually effective against passive eavesdroppers, who merely
tap the lines and try to decipher the message. It has been pointed out,
however, that an improperly designed protocol could be vulnerable to an
active saboteur, one who may impersonate another user or alter the message
being transmitted. In this paper we formulate several models in which the
security of protocols can be discussed precisely. Algorithms and
characterizations tht can be used to determine protocol security in these
models will be given.