Trace Spaces: an Efficient New Technique for State-Space Reduction

Details Trace Spaces: an Efficient New Technique for State-Space Reduction Trace Spaces: an Efficient New Technique for State-Space Reduction

2012-04-02

arxiv.org/abs/1204.0414v1

ESOP - 21st European Symposium on Programming 7211 (2012) 274-294

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

10.1007/978-3-642-28869-2_14

State-space reduction techniques, used primarily in model-checkers, all rely on the idea that some actions are independent, hence could be taken in any (respective) order while put in parallel, without changing the semantics. It is thus not necessary to consider all execution paths in the interleaving semantics of a concurrent program, but rather some equivalence classes. The purpose of this paper is to describe a new algorithm to compute such equivalence classes, and a representative per class, which is based on ideas originating in algebraic topology. We introduce a geometric semantics of concurrent languages, where programs are interpreted as directed topological spaces, and study its properties in order to devise an algorithm for computing dihomotopy classes of execution paths. In particular, our algorithm is able to compute a control-flow graph for concurrent programs, possibly containing loops, which is "as reduced as possible" in the sense that it generates traces modulo equivalence. A preliminary implementation was achieved, showing promising results towards efficient methods to analyze concurrent programs, with very promising results compared to partial-order reduction techniques.

Affiliated with

Also associated with

No associations

Rating

Trace Spaces: an Efficient New Technique for State-Space Reduction 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 Trace Spaces: an Efficient New Technique for State-Space Reduction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trace Spaces: an Efficient New Technique for State-Space Reduction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-509782