Self-adjusting computation is an approach for automatically dynamizing static algorithms. That is, given an algorithm which supports a set of query operations on a given input data, self-adjusting computation can help support efficient update operations on the input data simultaneously. Recently, Anderson et al. (SPAA '21) proposed a framework for writing parallel algorithms in such a framework with provable bounds on the work and span of the algorithms written in the framework, while also providing compelling empirical evidence of efficiency. This report deals with two key applications of the framework: binary search trees with parallel operations such as Filter and MapReduce, and a dynamic convex hull algorithm inspired by Overmars' algorithm. This report also discusses an imperative extension of parallel self-adjusting computation: the framework presented by Anderson et al. has a write-once restriction for its key variables, and some parallel algorithms and data structures such as Breadth-first search and hash tables are imperative by nature, proving a need for imperative parallel self-adjusting computation.

54 pages

Thesis Committee:
Guy Blelloch (Chair)
Umut Acar

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu