clarke@csri.toronto.edu (Jim Clarke) (04/06/88)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
A.I. SEMINAR, Tuesday, April 12, 2 pm, GB119 -- Ken Forbus:
"A Qualitative Physics Sampler"
SYSTEMS SEMINAR, Thursday, April 14, 11 am, GB 119 -- G. Neiger:
"Techniques for Simplifying the Design of Distributed Systems"
THEORY SEMINAR, Thursday, April 14, 3 p.m., GB119 -- Naomi Nishimura:
"Complexity Issues In Tree-Based Version Control"
NUMERICAL ANALYSIS SEMINAR, Friday, April 15, 10 am, GB220 - Christina Christara
"Domain Decomposition Methods for Solving
Elliptic Partial Differential Equations on Hypercube Architectures"
------------------
A.I. SEMINAR, Tuesday, April 12, 2 pm, GB119
Professor Ken Forbus
University of Illinois
"A Qualitative Physics Sampler"
This talk has two parts. The first part is an overview of our group's
work, including qualitative simulation, measurement interpretation, plan-
ning in physical domains, spatial reasoning, cognitive simulation of ana-
logical reasoning, and learning physical theories by analogy. The second
part is a detailed look at a particular project, motivated by our efforts
in modeling Space Station subsystems for NASA. In particular, I will
describe our "molecular collection" ontology for reasoning about liquids.
This ontology provides a substrate for qualitative reasoning about thermo-
dynamic cycles, and the necessary framework for subsequent quantitative
analysis.
SYSTEMS SEMINAR, Thursday, April 14, 11 am, GB 119
Dr. G. Neiger
Cornell University
"Techniques for Simplifying the Design of Distributed Systems"
Distributed systems include a range of networked computer systems from
local area networks to systems distributed across a continent. Programming
such systems is complicated by the possibility of failures and a lack of
synchronization between processors. My work deals with the simplification
of this programming task, using *system translations*; these allow the
*simulation* of one programming environment within another. Programs writ-
ten for a simple (idealized) system may be automatically translated to run
correctly in a more complex (realistic) system. In a sense, the simpler
system is *simulated* within the more complex system.
The difficulty of designing *fault-tolerant* programs depends greatly on
the type of behavior that faulty processors exhibit; this may range from
``crashing,'' where a processor simply halts, to completely arbitrary
behavior. For such systems I provide techniques that convert a program
tolerant of crash failures to one that tolerates arbitrary behavior.
In failure-free systems, the programming task is more difficult if the
clocks of processors are not synchronized, or if there is no bound on mes-
sage transmission times. For such systems I discuss a technique that
*simulates* perfectly synchronized clocks. This improves the ability of
processors to coordinate their actions. Building upon this, I provide a
message passing primitive that simulates *common knowledge*, and thus
allows an even greater degree of coordination.
THEORY SEMINAR, Thursday, April 14, 3 p.m., GB119
Ms. Naomi Nishimura
University of Toronto
"Complexity Issues In Tree-Based Version Control"
Version control systems enable us to efficiently store and access multiple
versions of programs. One popular approach is to store certain versions in
their entirety and others as the differences between versions, or deltas.
Although many systems manipulate programs as lists of lines, we exploit the
tree structure underlying most programming languages. The storage of pro-
grams as trees follows naturally from the practice of translating code into
abstract syntax trees during compilation. Of particular interest is the
problem of storing deltas between trees. We are concerned with the space
required to store a delta and the time required to reconstruct a new ver-
sion of a tree given an original version of a tree and a delta. In certain
cases, we will present efficient upper bounds; in others, we will show that
the problems are difficult by giving NP-completeness results.
NUMERICAL ANALYSIS SEMINAR, Friday, April 15, 10 am, GB220
Ms. Christina Christara
Purdue University
"Domain Decomposition Methods for Solving
Elliptic Partial Differential Equations on Hypercube Architectures"
We consider the integration of a domain decomposition technique with a
new quadratic spline collocation discretization scheme for solving second
order elliptic boundary value problems on rectangles. The domain
decomposition method is based on the capacitance matrix technique. Due
to the limitations of existing methods for solving the corresponding
capacitance problem, we develop and analyze iterative methods for its
solution. The optimum partitioning and mapping of the underlying computa-
tion is studied on hypercube architectures. A numerical realization of
this method is presented on NCUBE/7 (128 processors) and its compara-
tive efficiency is measured. The resulting parallel quadratic
spline collocation-capacitance method is seen to be efficient in achiev-
ing accurate solutions and in using parallel architectures.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke