So I need to write an abstract for my dissertation. Anyone wanna glance over this and tell me what you think?
If you suggest any edits, keep in mind that it's currently at 300 words, which is the maximum allowed. I'm frustrated that I couldn't explain things in more detail, so if you can think of any way to make things clearer while not increasing the overall word count, I'm all ears.
Deterministic-by-construction parallel programming models guarantee
that programs have the same observable behavior on every run,
promising freedom from bugs caused by schedule nondeterminism. To
make that guarantee, though, they must sharply restrict sharing of
state between parallel tasks, usually either by disallowing sharing
entirely or by restricting it to one type of data structure, such as
I show that lattice-based data structures, or LVars, are the
foundation for a guaranteed-deterministic parallel programming model
that allows a more general form of sharing. LVars allow multiple
assignments that are inflationary with respect to an
application-specific lattice. They ensure determinism by allowing
only inflationary writes and "threshold" reads that block until a
lower bound is reached. After presenting the basic LVars model, I
extend it to support event handlers, which enable an event-driven
programming style, and non-blocking "freezing" reads, resulting in a
quasi-deterministic model in which programs behave deterministically
I demonstrate the viability of the LVars model with LVish, a Haskell
library that provides a collection of lattice-based data structures, a
work-stealing scheduler, and a monad in which LVar computations run.
LVish leverages Haskell's type system to index such computations with
effect levels to ensure that only certain LVar effects can occur,
hence statically enforcing determinism or quasi-determinism. I present
two case studies of parallelizing existing programs using LVish: a
k-CFA control flow analysis, and a bioinformatics application for
comparing phylogenetic trees.
Finally, I show how LVar-style threshold reads apply to the setting of
convergent replicated data types (CvRDTs), which specify the behavior
of eventually consistent replicated objects in a distributed system.
I extend the CvRDT model to support deterministic, strongly consistent
threshold queries. The technique generalizes to any lattice, and
hence any CvRDT, and allows deterministic observations to be made of
replicated objects before the replicas' states converge.