Evaluating Ordering Heuristics for Dynamic Partial-Order Reduction Techniques

Date Added: Jan 2010
Format: PDF

Actor programs consist of a number of concurrent objects called actors, which communicate by exchanging messages. Non-determinism in actors results from the different possible orders in which available messages are processed. Systematic testing of actor programs explores various feasible message processing schedules. Dynamic Partial-Order Reduction (DPOR) techniques speed up systematic testing by pruning parts of the exploration space. Based on the exploration of a schedule, a DPOR algorithm may find that it need not explore some other schedules. However, the potential pruning that can be achieved using DPOR is highly dependent on the order in which messages are considered for processing.