Umut A. Acar

Thesis Title: Self-adjusting Computation
Degree Type: Ph.D. in Computer Science
Advisor(s): Guy Blelloch
Graduated: May 2005

Abstract:

This thesis investigates a model of computation, called self-adjusting computation, where computations adjust to any external change to their data (state) automatically. The external changes can change any data (e.g., the input) or decisions made during the computation. For example, a self-adjusting program can compute a property of a dynamically changing set of objects, or a set of moving objects, etc. This thesis presents algorithmic and programming-language techniques for devising, analyzing, and implementing self-adjusting programs.

From the algorithmic perspective, we describe novel data structures for tracking the dependences in a computation and a change-propagation algorithm for adjusting computations to changes. We show that the overhead of our dependence tracking techniques is O(1). To determine the effectiveness of change propagation, we present an analysis technique, called trace stability, and apply it to a number of applications.

From the languages perspective, we describe language facilities for writing self-adjusting programs in a type-safe and correct manner. The techniques make writing self-adjusting programs nearly as easy as ordinary (non-self-adjusting) programs. A key property of the techniques is that they enable the programmer to control the cost of dependence tracking by applying it selectively. Using language techniques, we also formalize the change-propagation algorithm and prove that it is correct.

We demonstrate that our techniques are efficient both in theory and in practice by considering a number of applications. Our applications include a random sampling algorithm on lists, the quick sort and merge sort algorithms, the Graham's Scan and the quick algorithm for planar convex hull, and the tree-contraction algorithm. From the theoretical perspective, we apply trace stability to our applications and show complexity bounds that are within an expected constant factor of the best bounds achieved by special-purpose algorithms. From the practical perspective, we implement a general purpose library for writing self-adjusting programs, and implement and evaluate self-adjusting versions of our applications. Our experiments show that our techniques dramatically simplify writing self-adjusting programs, and can yield very good performance even when compared to special-purpose algorithms, both in theory and in practice.

Thesis Committee:
Guy Blelloch (Co-chair)
Robert Harper (Co-chair)
Daniel Dominic Kaplan Sleator
Simon Peyton Jones (Microsoft Research, Cambridge, UK)
Robert Endre Tarjan (Princeton University)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Self-adjusting computation, dynamic algorithms, dynamic data structures, kinetic data structures, dynamic dependence graphs, memoization, change propagation, trace stability, functional programming, lambda calculus, type systems, operational semantics, modifiable references, selective memoization, sorting, convex hulls, parallel tree contraction, dynamic trees, rake-and-compress trees.