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