[PRL] Talk: Self-Adjusting Computation (MIT, 4/21, 3pm)

[Mitchell Wand]

Self-Adjusting Computation
Speaker: Umut Acar
Speaker Affiliation: Carnegie Mellon University
Host: Butler Lampson
Host Affiliation: MIT

Date: 4-21-2004
Time: 3:00 PM - 4:00 PM
Refreshments: 2:45 PM
Location: Stata Center - 044

Many application domains require programs to react to dynamically
changing environments: network links go down, roads get closed,
software gets modified, robots try to avoid moving objects etc.

In this talk, I introduce the concept of self-adjusting computation
which enables writing programs that adapt their output to changes in
their input.  Self-adjusting computation generalizes incremental
computation to support a much richer class of programs, including
general methods for obtaining dynamic and kinetic versions of static
algorithms.

Self-adjusting computation is based on a novel combination of
algorithmic and programming-language techniques.  Self-adjusting
programs maintain a record of the dynamic dependences that arise among
data values in a computation. This dependence information is then used
to adjust the result of the computation whenever any of the data
values change.  These mechanisms are placed under programmer control
through a type system that distinguishes changeable from stable values
and tracks all dependences to ensure correctness of the adaptive
results.  An analysis technique, called trace stability, enables the
programmer to determine the performance of self-adjusting programs.

As examples, I describe self-adjusting versions of a number of
important algorithms, including Quicksort, MergeSort, Parallel Tree
Contraction, and several Convex-Hull algorithms.  The resulting
self-adjusting algorithms meet the bounds for (problem-specific)
dynamic algorithms solving the corresponding dynamic problems.

For more information please contact: Valerie DiNardo, 617-253-1996,
valerie at csail.mit.edu 

_______________________________________________
Seminars mailing list
Seminars at lists.csail.mit.edu
http://lists.csail.mit.edu/mailman/listinfo/seminars