clarke@utcsri.UUCP (Jim Clarke) (03/17/86)
(SF = Sandford Fleming Building, 10 King's College Road)
COLLOQUIUM, TUESDAY MARCH 18, 11 am, SF 1105
Dr. N. Meyerowitz
Brown University
Networks of Scholars' Workstations
SYSTEMS SEMINAR, Monday, March 24, 4 pm, SF 1101
Professor Bill Atwood
Concordia University
CUNIS: A design for an operating system
for the Homogeneous Multiprocessor
SYSTEMS SEMINAR, Tuesday, March 25, 11 am, SF 1105
Professor Kenneth P. Birman
Cornell University
Broadcast primitives for supporting
fault-tolerant process groups
A.I. SEMINAR, Tuesday, March 25, 3 pm, SF 1105
Professor William Rapaport
SUNY at Buffalo
Logical foundations for belief representation
THEORY SEMINAR, Tuesday, March 25, 4 pm, SF 1105
Professor Patrick Dymond
University of California, San Diego
Complexity of deterministic context-free languages
ABSTRACTS
Dr. N. Meyerowitz
Networks of Scholars' Workstations
The talk focuses on the Scholar's Workstation Project at Brown - a
decade-long project to help develop a new end-user paradigm for computing
that we expect will become the accepted paradigm for the 1990's. First,
the historical perspective is presented, to identify the impetus for the
project. Following this, the institutional imperatives to launch the pro-
ject are explained. Next, the requirements of the campus constituency, as
determined by extensive needs analysis, are discussed. Given this, the
technical architecture to meet these needs is examined in depth. Finally a
glimpse at some of the most interesting end-user software stemming from the
project is provided.
Professor Bill Atwood
CUNIS: A design for an operating system
for the Homogeneous Multiprocessor
The Homogeneous Multiprocessor consists of K processors and K
memories. Each processor P(K) is directly connected to its own memory
M(K). In addition, each processor PK may address the memories M(K-1) and
M(K+1). In addition, all processors are conneted to a 7 Mbyte/sec LAN.
The architecture appears to be particularly suited to distributed simula-
tion.
In order to construct a suitable operating system for this specialized
architecture, design ideas have been taken from TUNIS, from the work of
Denning on distributed operating systems, and from the work of Randell on
networking. The talk will concentrate on the lessons learned during our
investigation of potential designs.
Kenneth P.Birman
Broadcast Primitives for Supporting Fault-Tolerant Process Groups
A basic problem in constructing distributed computing programs that
maintain replicated data, tolerate failures, or reconfigure dynamically, is
that the communication primitives provided by existing operating systems
are too weak. This forces a substantial protocol design and synchroniza-
tion task on the user, a daunting prospect. I will report on the design
and correctness of a new communication facility for a distributed computer
system, which was developed as part of the ISIS project. Based on the idea
of atomic broadcast, this facility provides a variety of broadcast proto-
cols, which are used to transmit messages reliably to sets of destination
processes. Unlike previous protocols, our primitives respect a variety of
application-specific ordering constraints, ranging from total ordering (as
proposed elsewhere) to much weaker orderings that require less synchroniza-
tion and hence give better performance. Moreover, handling of failures and
recovery is integrated into the primitives. I will show how the primitives
can be used to implement fault-tolerant process groups, whose members
cooperate to provide some service reliably despite high levels of con-
currency and crash failures. A review of several uses for the protocols in
a large fault-tolerant program illustrates the simplification of higher-
level algorithms made possible by our approach. Progress towards an imple-
mentation is also reported.
William J. Rapaport
Logical Foundations for Belief Representation
This talk will focus on Knowledge Representation issues in modeling
the beliefs of a cognitive agent. We begin by examining the nature of
intensional entities and their usefulness for giving a fully intensional
semantics for the SNePS Semantic Network Processing System. We shall then
look at the use of SNePS to model the belief structure of a cognitive
agent. In particular, we shall consider the representations of de re, de
dicto, and de se belief reports; and we will look at some problems that
arise when extending these notions to knowledge reports (where knowledge is
taken as a kind of true belief).
Patrick W. Dymond
Complexity of deterministic context-free languages
and Parallel Random Access Machines with owner-restricted
write access to common global memory.
We describe a natural and frequently occurring subclass of
Concurrent-Read, Exclusive-Write Parallel Random Access Machines (CREW-
PRAM's). Called Concurrent-Read, OWNER-Write or CROW-PRAM's, these are
machines in which each global memory location is assigned a unique "owner"
processor, which is the only processor allowed to write into it. Most
known CREW-PRAM algorithms are in fact CROW-PRAM algorithms. We show that
the class of languages recognizable in time O(log n) on CROW-PRAM's is pre-
cisely equal to the class LOGDCFL of languages log space reducible to
deterministic context free languages. We describe other new results on the
complexity of the recognition problem for deterministic context-free
languages.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,ihnp4,linus,utzoo}!utcsri!clarke