Preparing traces for replay

Following $m$ runs of an application through the causality engine, each node has $m$ traces that must be merged. All $m$ traces for a given node should contain the same file I/O calls, otherwise an error will be flagged indicating that the application is not deterministic.

Recall that at most one of the $m$ traces for a given node has the SIGNAL() calls for that node; this is the trace produced when the node is being throttled. The other traces for that node only have the WAIT() calls; these are the traces produced when other nodes are being throttled. After the merge, each I/O has at most $m-1$ preceding WAIT() calls, $m-1$ succeeding SIGNAL() calls, and one COMPUTE() call (obtained using Approaches 1 or 2).

Figure 6: Before merging the traces

Figure 7: After merging the trace files

The example in Figure 6 shows the trace files for a hypothetical 3-node application. In this case, every node is throttled in turn. Only the traces for node 0 are shown. A merge of these three traces will produce the final trace for node 0 (Figure 7).