Question 9 of 9: Software Validation

Question 9: Software Validation (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Sequential vs. Parallel Validation

A sequential program has a single thread of control: for a given input, it always follows exactly one, deterministic sequence of statement executions. This has two direct consequences for validation. First, any failure found during testing is reproducible — re-running the same input reliably re-creates the same execution path and the same failure, which is what makes systematic debugging and regression testing possible in the first place. Second, the space of behaviours that must be tested is, in principle, enumerable from the program's input domain and its (finite) set of control-flow paths, so structural testing techniques (path coverage, branch coverage) can meaningfully claim to have exercised "most" of the program's behaviour.

A design involving parallel or concurrent processes loses both properties. The actual order in which operations from different processes/threads interleave at run time depends on scheduling decisions, relative timing, and system load — factors outside the program's own logic — so the same inputs can produce different interleavings, and therefore potentially different outcomes, on different runs. A defect that depends on one specific interleaving (a race condition, a deadlock that only occurs when two processes reach a lock in a particular order) may simply not occur again when the test is re-run, making such failures notoriously hard to reproduce and debug. Worse, the number of distinct interleavings grows combinatorially with the number of concurrent processes and the number of operations each performs — even a handful of processes with a handful of steps each can produce many thousands of distinct legal interleavings — so exhaustively enumerating and testing every possible interleaving quickly becomes computationally infeasible, unlike the sequential case where the path space, while it can still be large, is at least fixed and does not additionally depend on run-time scheduling.