Shared Memory Concurrent System Verification using Kronecker Algebra

Details Shared Memory Concurrent System Verification using Kronecker Algebra Shared Memory Concurrent System Verification using Kronecker Algebra

2011-09-26

arxiv.org/abs/1109.5522v1

Computer Science

Logic in Computer Science

31 pages

Scientific paper

The verification of multithreaded software is still a challenge. This comes mainly from the fact that the number of thread interleavings grows exponentially in the number of threads. The idea that thread interleavings can be studied with a matrix calculus is a novel approach in this research area. Our sparse matrix representations of the program are manipulated using a lazy implementation of Kronecker algebra. One goal is the generation of a data structure called Concurrent Program Graph (CPG) which describes all possible interleavings and incorporates synchronization while preserving completeness. We prove that CPGs in general can be represented by sparse adjacency matrices. Thus the number of entries in the matrices is linear in their number of lines. Hence efficient algorithms can be applied to CPGs. In addition, due to synchronization only very small parts of the resulting matrix are actually needed, whereas the rest is unreachable in terms of automata. Thanks to the lazy implementation of the matrix operations the unreachable parts are never calculated. This speeds up processing significantly and shows that this approach is very promising. Various applications including data flow analysis can be performed on CPGs. Furthermore, the structure of the matrices can be used to prove properties of the underlying program for an arbitrary number of threads. For example, deadlock freedom is proved for a large class of programs.

Affiliated with

Also associated with

No associations

Rating

Shared Memory Concurrent System Verification using Kronecker Algebra does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Shared Memory Concurrent System Verification using Kronecker Algebra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shared Memory Concurrent System Verification using Kronecker Algebra will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689032