Message-passing programs are difficult to test because of their non-deterministic behavior - DoingStuff.DonaldNoyes.20141106
One approach, called NonDeterministicTesting, involves executing a message-passing program with the same input many times in hope that faults will be exposed by one of these executions.
NonDeterministicTesting has been widely used in practice, but unfortunately, in an ad-hoc manner.
- I don't think MessagePassing has to be so difficult. At some level of description, the program has to be deterministic. Treat those individual modules as black-boxes that have a consistent, documented, input-output relationship. As long as each of these (testable) modules performs as documented, then any program composed of these modules should be trustable as long as it is "well-formed" (i.e. logically-composed). You might be interested in the discussion under ObjectOrientedRefactored which goes into a message-passing framework to take OOP to it`s ultimate.
A novel framework for non-deterministic testing of message-passing programs has been presented in an IEEE paper by Yu Lei and Eric Wong [1]
The framework they propose uses a coverage criterion to guide the testing process.
- During each test run, the sequence of send and receive events that are executed is recorded in an execution trace.
- After each test run, the trace is analyzed to identify race conditions, which are used to derive coverage elements that have not been covered yet.
- Random delays are inserted at a chosen set of program locations in order to increase the chance of covering the uncovered elements in the next test run.
This framework
- provides a heuristic condition that can be used to decide when to stop testing.
- The condition is easy to compute and its satisfaction signals that the coverage criterion has likely been satisfied
- can be automated at the source code level and allows one to obtain a measure of test coverage at the end of the testing process
In the paper they describe a prototype tool and report some empirical results that demonstrate the effectiveness of the framework.
Citation:
- [1] - Yu Lei, Eric Wong, "A Novel Framework for Non-Deterministic Testing of Message-Passing Programs", HASE, 2005, Ninth IEEE International Symposium on High-Assurance Systems Engineering (HASE'05), Ninth IEEE International Symposium on High-Assurance Systems Engineering (HASE'05) 2005, pp. 66-75, doi:10.1109/HASE.2005.2
CategoryParallelProcessing
Deterministic Message Passing