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.