COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "setup.csl[bib,csr]" source file
C00003 00003	.begin centerselect 3
C00004 00004	%3CSL TR-174:%1
C00006 00005	%3CSL TR-189:%1
C00011 00006	%3CSL TR-190:%1
C00016 00007	%3CSL TR-191:%1
C00020 00008	%3CSL TR-192:%1
C00022 00009	%3CSL TR-193:%1
C00023 00010	.next page <<CSL order form>>
C00027 ENDMK
C⊗;
.require "setup.csl[bib,csr]" source file;
.font A "math55";
.begin center;select 3
Stanford University 
Computer Systems Laboratory Reports
.end

@%1Listed here are abstracts of the most recent reports published by the
Computer Science Laboratory at Stanford University.  
Further information on these reports is
available by writing directly to:
Naomi Schulman, 
Computer Systems Laboratory,
ERL-234, 
STANFORD UNIVERSITY, 
Stanford, California 94305.
.skip

%3CSL TR-174:%1
.once preface 0
@%2Pascal*: A Pascal Based Systems Programming Language%1 by John Hennessy
(June 1980)

@Pascal%2*%1 (Pascal-star) is a new programming language which is upward compatible
with standard Pascal and suitable for systems programming.  Although there are
several additions to the language, simplicity remains a major design goal.  The
major additions reflect trends evident in newer languages such as Euclid, Mesa,
and Ada, including:  modules, simple parametric types, structured constants and
values, several minor extensions to the control structures of the language, random 
access files, arbitrary return types for functions, and an exception handling 
mechanism.
.skip

%3CSL TR-189:%1
.once preface 0
@%2Center-Bases Broadcasting%1 by
David W. Wall and Susan S. Owicki (25 pages, June 1980)

@We consider the problem of routing broadcast messages in a
loosely-coupled store-and-forward network like the ARPANET.  Dalal
discussed a solution to this problem that minimizes the cost of
a broadcast; in contrast, we are interested in performing broadcast
with small delay.  Existing algorithms can minimize the delay
but seem unsuitable for use in a distributed environment because they
involve a high degree of overhead in the form of redundant messages
or data-structure space.  We propose the schemes of center-based
forwarding: the routing of all broadcasts via the shortest-path
tree for some selected node called the center.  These
algorithms have small delay and also are easy to implement in a
distributed system.

@To evaluate center-based forwarding, we define four measures of
the delay associated with a given broadcast mechanism, and then propose
three ways of selecting a center node.  For each of the three forms of
center-based forwarding we compare the delay to the minimum delay for
any broadcasting mechanism and also to the minimum delay for any single
tree.  In most cases, a given measure of the delay on the centered tree
is bounded by a small constant factor relative to either of these two
minimum delays.  When it is possible, we give a tight bound on the
ratio between the center-based delay and the minimum delay; otherwise we
demonstrate that no bound is possible.  These results give corollary
bounds on how bad the three centered trees can be with respect to each
other; most of these bounds are immediately tight, and the rest are
replaced by better bounds that are also shown to be tight.
.skip

%3CSL TR-190:%1
.once preface 0
@%2Mechanisms for Broadcast and Selective Broadcast%1 by
David W. Wall (112 pages, June 1980)

@This thesis deals with a problem in the effective use of a
loosely-coupled store-and-forward network like the ARPANET.  Many
applications assume the existence of a mechanism to send a broadcast
message to every node in the network, or a selective broadcast message
to a specified group of nodes.  Previous work in this field has resulted
in several techniques for broadcasting to the entire network.  These
include an algorithm for imposing a minimum spanning tree on the network
and maintaining it in the face of failures and changing costs, so that a
broadcast can be routed along the branches of the MST at a minimum cost
to the network as a whole.

@We extend this work in two directions.  First of all, we discuss
ways of adapting existing broadcast mechanisms to the more general
problem of selective broadcast.  In one case this involves generalizing
the MST problem to the problem of finding a minimum Steiner tree, a
problem which is NP-complete.  we examine an existing approximation
algorithm and show how to modify it for use in a distributed
environment.  In the process we show that if we make a reasonable
assumption about the way ties between edges are broken then we can
considerably simplify this algorithm.

@Second, we propose an original broadcasting technique that
forwards along the branches of a single tree in the same manner as the
MST-based algorithm.  The tree used is a shortest-path tree for a
particular node that is, in some sense, "in the center" of the
network; hence this method is called center-based forwarding.  Using
such a tree allows us to provide a broadcast facility with a small delay
rather than a small cost; unfortunately it is impossible in general to
minimize the delay from every source if we use only a single tree.

@To evaluate center-based forwarding, we define four measures of
the delay associated with a given broadcast mechanism, and then propose
three ways of selecting a center node.  For each of the three forms of
center-based forwarding we compare the delay to the minimum delay for
any broadcasting mechanism and also to the minimum delay for any single
tree.  In most cases, a given measure of the delay on the centered tree
is bounded by a small constant factor multiplied by either of these two
minimum delays.  When it is possible, we give a tight bound on the
ratio between the center-based delay and the minimum delay; otherwise we
demonstrate that no bound is possible.  These results immediately imply
bounds on how bad the three centered trees can be with respect to each
other; most of these bounds are immediately tight, and the rest are
replaced by better bounds that are also shown to be tight.
.skip

%3CSL TR-191:%1
.once preface 0
@%2A Language-Oriented Approach to Computer Architecture%1
by Clark R. Wilcox (Thesis, June 1980)

@A language-oriented approach to computer architecture starts with a
high-level language, from which an "ideal" program representation and
execution environment is derived, which in turn determines an "ideal" processor
architecture.  This is in contrast to the conventional approach wherein a single
fixed instruction set supports all languages.

@A methodology is presented for deriving the following components:  an abstract
syntax and abstract semantics for the language; derivation and interpretation
of a token stream and a bit-oriented code stream; language processor architecture;
and program monitoring facilities.  The methodology is applied to a particular
high-level language to obtain detailed data concerning static program size and
dynamic execution characteristics.  A language-specific representation,
%2postfix code%1, is designed according to this methodology.

@A computer architecture is designed for interpretive execution of bit-oriented
code streams.  The 32-bit processor has a control store for micro-coded
interpreters, hardware maintenance of the code stream, table-driven variable-width
field extraction and operator dispatch in parallel with micro-code execution,
and two micro-level stacks.  A micro-coded postfix interpreter is used to execute
a number of program modules compiled into postfix code.  The postfix execution
is compared with a conventional implementation and shown to be superior in every
measured quantity; for example it has half as many instruction loads.

@A novel feature of postfix code is its ability to be decompiled into source
text, including variable names.  This provides the basis for a display-oriented
program development and monitoring environment which can decompile and display
the program text during a debugging session, with the cursor following the
execution locus while in single-step mode.  Breakpoints are set by moving the
cursor to the desired point in the displayed text.
.skip

%3CSL TR-192:%1
.once preface 0
@%2Verifying Network Protocols Using Temporal Logic%1 
by Brent T. Hailpern and Susan S. Owicki (June 1980)

@Programs that implement computer communications protocols can exhibit extremely
complicated behavior, and neither informal reasoning nor testing is reliable
enough to establish their correctness.  In this paper we discuss the application
of program verification techniques to protocols.  This approach is more reliable
than informal reasoning, but has the advantage over formal reasoning based on
finite-state models that the complexity of the proof does not grow unmanageably
as the size of the program increases.  Certain tools of concurrent program
verification that are especially useful for protocols are presented:  history
variables that record sequences of input and output values, temporal logic for
expressing properties that must hold in a future system state (such as eventual
receipt of a message), and module specification and composition rules.  The use
of these techniques is illustrated by verifying a simple data transfer protocol
from the literature.
.skip

%3CSL TR-193:%1
.once preface 0
@%2A Language for Microcode Description and Simulation in VLSI%1
by John Hennessy (July 1980)

@This paper preents a programming language based system for specifying and
simulating microcode in a VLSI chip.  The language is oriented towards PLA
implementations of microcoded machines using either a microprogram counter
or a finite state machine.  The system supports simulation of the microcode
and will drive a PLA layout program to automatically create the PLA.
.skip

.next page <<CSL order form>>
.once center
%3CSL REPORT ORDER FORM%1

@To order reports, complete and return this form to the Computer Systems Laboratory.
To return this form to us, simply fold it so that the Laboratory address on the
reverse side shows, taple and affix postage.

@Please %2DO NOT%1 send any money with your order.  A bill will be enclosed when
the reports are sent to you.  The number of copies available is limited and will
be distributed on a first-come, first-serve basis.
.skip 3
.begin nofill
Name:

Address:

City:

State:									Zip Code:

Country:
.end
.skip 3
.once center
Check off the reports you want.

.begin bf
.tabs 3,8,28,43,46,50,70
\\Hardcopy\\\\Microfiche
.skip
\|B\CSL TR-174\$2.00\\|B\CSL TR-174\FREE
\|B\CSL TR-189\$2.00\\|B\CSL TR-189\FREE
\|B\CSL TR-190\$4.50\\|B\CSL TR-190\FREE
\|B\CSL TR-191\$7.50\\|B\CSL TR-191\FREE
\|B\CSL TR-192\$2.00\\|B\CSL TR-192\FREE
\|B\CSL TR-193\$2.00\\|B\CSL TR-193\FREE
.end