[Colloq] REMINDER: PhD Thesis Proposal - Peter Dillinger, Thurs. June 18

[Rachel Kalweit]

The College of Computer and Information Science Presents - Thesis Proposal Presentation:
Speaker: Peter Dillinger
Date: June 18, 2009 (Thurs.)
Time: 10:00 AM (will start promptly at 10am)
Where: WVH 366

Breakfast will be available!

Thesis title: Adaptive Approximate State Storage

Abstract

Efficiently storing and matching visited states is key to the
effectiveness of explicit-state model checkers such as SPIN.  Models
of concurrent programs often have too many reachable states to
enumerate easily in main memory, and an efficient model checker can
exhaust main memory in minutes by storing state descriptors exactly.
A popular alternative is to over-approximate the set of visited states
using a randomized, probabilistic data structure, such as a Bloom
filter.  Because the approximation is sound and does not slow down the
search with revisitation of states, it tends to find errors quickly.
Because it is probabilistically complete, the approach can also
convincingly demonstrate lack of errors.

However, current techniques for approximate state storage are often
less effective than they could be because of a configuration dilemma.
They rely on a good estimate of the reachable state space size for the
likelihood of finding all errors to be near the maximum.  Such an
estimate is usually only available *after* checking a model.  I solve
this dilemma with an efficient storage scheme that is adaptive:
regardless of the number of states encountered at run time, its
accuracy is near the information-theoretic optimal.  It is also
competitively fast, thanks to a novel in-place adaption algorithm and
a favorable access pattern to memory.  My central contribution is
recognizing and exploiting the adaptability of an obscure kind of hash
table by Cleary and applying it to this problem.


Thesis committee:

Javed Aslam
Gene Cooperman
Pete Manolios (thesis advisor)
Willem Visser (University of Stellenbosch, external member)


_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq