Using the jump number problem to efficiently detect global predicates in distributed systems

Simple item page
dc.contributor.advisorGarg, Vijay K. (Vijay Kumar), 1963-
dc.creatorClinton, Trokon Edward
dc.date.accessioned2017-07-17T21:27:51Z
dc.date.available2017-07-17T21:27:51Z
dc.date.issued2017-05
dc.date.submittedMay 2017
dc.date.updated2017-07-17T21:27:51Z
dc.description.abstractDetecting global predicates of a distributed computation is a key problem in testing and debugging distributed programs. It consists of searching the global state space of events to determine whether a given predicate could have occurred. For example a programmer may be interested in verifying whether a parallel program violates a global invariant, or detect a race condition between concurrent threads. This is a challenging problem because the number of consistent global states can grow exponentially when the number of events in the computation increases. This paper presents techniques that tackle the state explosion problem and help detect whether an arbitrary predicate is true in polynomial time. We first present a brute force algorithm, and then improve the performance with an exact and heuristic algorithm inspired by the jump number problem.
dc.description.departmentElectrical and Computer Engineering
dc.format.mimetypeapplication/pdf
dc.identifierdoi:10.15781/T2NV99S01
dc.identifier.urihttp://hdl.handle.net/2152/60467
dc.language.isoen
dc.subjectGlobal predicate detection
dc.subjectDistributed debugging
dc.subjectVerification
dc.subjectGlobal states
dc.subjectJump number
dc.titleUsing the jump number problem to efficiently detect global predicates in distributed systems
dc.typeThesis
dc.type.materialtext
thesis.degree.departmentElectrical and Computer Engineering
thesis.degree.disciplineElectrical and Computer Engineering
thesis.degree.grantorThe University of Texas at Austin
thesis.degree.levelMasters
thesis.degree.nameMaster of Science in Engineering

Access full-text files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
CLINTON-MASTERSREPORT-2017.pdf
Size:
321.01 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.45 KB
Format:
Plain Text
Description:
Download
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.84 KB
Format:
Plain Text
Description:
Download

Collections

UT Electronic Theses and Dissertations