Paper Info
Title
Efficient reachability testing of asynchronous message-passing programs
Abstract
An asynchronous message-passing program P is nondeterministic. Given the same input, multiple executions of P may exercise different send/receive event sequences (or SR-sequences) and may even produce different results. Such nondeterminacy makes it difficult to determine the correctness of P. Let X be an input of P. Assume that any execution of P with X terminates. Reachability testing of P with X is to execute, in a systematic manner, all possible SR-sequences of P with X such that the correctness of P with X can be determined. The basic idea of reachability testing is described as follows. We first execute P with X nondeterministically to collect one or more SR-sequences. For each collected SR-sequence, we analyze its race conditions and generate race variants, which are prefixes of other SR-sequences. We replay race variants to generate new SR-sequences. For each new SR-sequence, we repeat the same process until we eventually execute all possible SR-sequences of P with X. We describe an efficient implementation of reachability testing of asynchronous message-passing programs. Our technique deals with partially-ordered SR-sequences and reduces the complexity and redundancy caused by totally-ordered SR-sequences.
Year
DOI
Venue
2002
10.1109/ICECCS.2002.1181496
ICECCS
Keywords
Field
DocType
totally-ordered sr-sequences,program testing,correctnessof p,parallel programming,asynchronous message-passing programs,efficient reachability testing,partially-ordered sr-sequences,send receive event sequences,reachability testing ofp,race conditions andgenerate race,allpossible sr-sequences,executeall possible sr-sequences,complexity,x terminates,redundancy,race conditions,asynchronous message-passing program isnondeterministic,reachability testing,p.let x,message passing,replay race variant,hazards and race conditions,nondeterministic program,race variants,reachability analysis,total order,race condition,partial order
Asynchronous communication,Programming language,Reachability testing,Nondeterministic algorithm,Computer science,Correctness,Real-time computing,Theoretical computer science,Prefix,Redundancy (engineering),Program testing,Message passing
Conference
ISBN
Citations 
PageRank 
0-7695-1757-9
20
1.07
References 
Authors
4
2
Name
Order
Citations
PageRank
Yu Lei111111.54
Kuo-chung Tai21274132.89