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:  
C00014 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.