perm filename TWELVE.PUB[BIB,CSR]1 blob
sn#580989 filedate 1981-04-23 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00006 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 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 [LSP80]. 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 [7] as a virtual memory management
sttrategy is widely accepted, it has been impossible to take advantage of it in a
praactical system, because liitle 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 ttechnique, 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 efficienty of multiprogrammed virtual memory systems.