@make(PublicationOrderForm,Number 12,AnnouncementDate "June 1981")

@Entry(Code "STAN-CS-81-846",
	Title "The Byzantine Generals Strike Again",
	Author "Danny  Dolev",
	Price "$2.80",Free,
	Note "26 pages",
	Date "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 @i[any]  distributed system @i[if and only  if] 
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.

@Entry(Code "STAN-CS-81-847",
	Title "The  Optimal Locking  Problem in  a Directed  Acyclic Graph",
	Author "Henry F. Korth",
	Price "$2.20",Free,
	Note "6 pages",
	Date "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
@i[NP]-complete to find the optimal locking strategy for the transaction.

@Entry(Code "STAN-CS-81-848",
	Title "On the Problem  of Inputting Chinese Characters",
	Author "Chih-sung Tang",
	Price "$2.30",Free,
	Note "9 pages",
	Date "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.

@Entry(Code "STAN-CS-81-849",
	Title "Experiments on the Knee Criterion in a Multiprogrammed
Computer System",
	Author "Tohru Nishigaki",
	Price "$2.85",Free,
	Note "28 pages",
	Date "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.

@Entry(Code "STAN-CS-80-850",
	Title "Performing Remote Operations Efficiently on a Local Computer Network",
	Author "Alfred Z. Spector",
	Price "$2.70",Free,
	Note "23 pages",
	Date "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.

@Entry(Code "STAN-CS-81-851",
	Title "Binding in Information Processing",
	Author "Gio Wiederhold",
	Price "$3.25",Free,
	Note "41 pages",
	Date "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 acccording 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.


@Entry(Code "STAN-CS-81-852",
	Title "A View of Directions in Relational Database Theory",
	Author "Jeffrey D. Ullman",
	Price "$2.30",Free,
	Note "9 pages",
	Date "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.

@Entry(Code "STAN-CS-81-853",
	Title "Connections in Acyclic Hypergraphs",
	Author "David Maier and Jeffrey D. Ullman",
	Price "$2.30",Free,
	Note "10 pages",
	Date "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.

@Entry(Code "STAN-CS-81-854",
	Title "On the Security of Public Key Protocols",
	Author "D. Dolev and A. C. Yao",
	Price "$2.65",Free,
	Note "22 pages",
	Date "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 that can be
used to determine protocol security in these models will be given.