[ont.events] U of Toronto Computer Science activities, April 11-15

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