Deadlock detection and dihomotopic reduction via progress shell decomposition

Author

David Andrew Cape

Abstract

"Deadlock detection for concurrent programs has traditionally been accomplished by symbolic methods or by search of a state transition system. This work examines an approach that uses geometric semantics involving the topological notion of dihomotopy to partition the state space into components, followed by an exhaustive search of the reduced state space. Prior work partitioned the state-space inductively; however, this work shows that a technique motivated by recursion further reduces the size of the state transition system. The reduced state space results in asymptotic improvements in overall runtime for verification. Thus, with efficient partitioning, more efficient deadlock detection and eventually more efficient verification of some temporal properties can be expected for large problems"--Abstract, page iii.

Advisor(s)

McMillin, Bruce M.

Committee Member(s)

Tauritz, Daniel R.
Weigert, Thomas
Sedigh, Sahra
Liu, Xiaoqing Frank

Department(s)

Computer Science

Degree Name

Ph. D. in Computer Science

Publisher

Missouri University of Science and Technology

Publication Date

Spring 2010

Pagination

xii, 135 pages

Note about bibliography

Includes bibliographical references (pages 133-134).

Rights

© 2010 David Andrew Cape, All rights reserved.

Document Type

Dissertation - Open Access

File Type

text

Language

English

Subject Headings

Electronic data processingHomotopy theoryMultiprogramming (Electronic computers)Parallel processing (Electronic computers)

Thesis Number

T 9638

Print OCLC #

679571427

Electronic OCLC #

608217206

Recommended Citation

Cape, David Andrew, "Deadlock detection and dihomotopic reduction via progress shell decomposition" (2010). Doctoral Dissertations. 1899.
https://scholarsmine.mst.edu/doctoral_dissertations/1899