Tech Note

Title:               Dynamic Validation
Date:              July 10, 2003
Written by:      Peter Bosch
Number:        TN-010
Version:         0.1

Background – When running, tasks receive an input state and compute an output state based on user-defined parameters and algorithms. Validation is the process of configuring a model’s parameters such that each task can correctly compute its output state, and the model can therefore execute to completion. We desire (a) that during a particular attempt, graph validation shall be performed as far as possible along any given path, (b) that a given graph validation attempt shall not have to be performed on any more tasks than necessary and (c) that for a given task across multiple validation operations, it should need to validate a minimal number of times.

A task graph validates from its first vertex to its last vertex, through the various paths in the graph, advancing along a temporal cut. Once a task declares itself unable to validate (invalid), that task and all tasks downstream of it should skip any further validation action, since such action may be presumed to be relying on potentially invalid input state information. However, all other paths unaffected by that invalidation should continue to attempt validation, as long as the tasks in that path have no dependency on any other preceding invalidity. Moreover, if a task that was previously invalid becomes valid, then downstream tasks that were previously valid should only be required to revalidate if the input state upon which they based that validity has changed.

There is another requirement that arises from the fact that tasks consume time, and some tasks impose effects upon other tasks while both tasks are running. We use the concept of a synchronizer to represent a structure wherein two or more concurrent tasks must start together, and may have a relationship where one affects the other. A synchronizer starts both tasks at the same simulation time, but the one that affects the other is started first.  If the task supplying that effect determines itself to be invalid prior to imposing that effect, the task consuming the effect should, from that moment on, consider itself to have an invalid input state, and should not presume that its computed pre-state is valid. Therefore, simply relying on validity in a task’s pre-state is insufficient, since the driver of invalidity can arise during the task’s execution, too. A task may also have to consider the validity state of concurrently running tasks when determining its own post-validation SelfValidState.

In Figure 1, below, Task 4A and Task4B are coexecutors in a shared synchronizer. The vertex marked as ‘i’ is fired before the vertex marked as ‘ii’, (both are fired at the same simulation clock time, though) so Task 4B is a subsequent coexecutor in a shared synchronizer to Task 4A, and Task 4A is a precedent coexecutor in a shared synchronizer to Task 4B. This models the dependent relationship implied by the arrow between Task 4A and Task 4B. Tasks 1 and 2 are predecessors to Task 4A, and Task 3 is a predecessor to Task 4B. Task 4A is a successor to tasks 1 and 2.

 

task relationship description

Figure 1 Task Relationship Description

Notable Cases

The following two cases illustrate some of the nuances of this mechanism.

Since 3 is invalid, 4B does not revalidate. 4A may compute a different transfer material, but regardless, due to task 3’s invalidity, 4B cannot attain validity, so it does not attempt to do so. If 3 later becomes valid, only 4B sill need to validate, and will do so using the transfer spec that 4A previously computed.

4B must also revalidate in case 4A changes its material transfer spec. Strictly, this violates requirement (b) in the background section. We should plan to create a memento-based mechanism at some point to eliminate this minor inefficiency.

Implementation

We address these requirements with the following implementation.

A task has three components to its validity – its SelfValidState, its AllPredecessorsValid state, and its AllChildrenValid state. The task is only valid if all three sub-states are true. We use the first two in satisfaction of the preceding requirements. The third is provided as a bookkeeping mechanism for discerning, for example, recipe-level validity without having to iterate through all tasks in the recipe.

A task will only start validating if its SelfValidState is false. The first thing it does is update its AllPredecessorsValid state from all of its predecessors, not including coexecutors in a shared synchronizer. If its AllPredecessorsValid state is false, then it skips validation. If its AllPredecessorsValid state is true, then it speculatively marks its SelfValidState as true, and proceeds to attempt validation through user-defined code. The user-defined code must revert the task’s SelfValidState to false if it wishes to signify unsuccessful validation.

After user-defined code has run, the task checks its SelfValidState. If it shares a synchronizer with coexecutors, then it also checks the then-current SelfValidStates of all of the preceding coexecutors. If the task itself, or one or more of its preceding coexecutors has declared itself invalid, then the task itself marks itself as invalid regardless of its own self-computed validity state. The task then checks to see if its output state is different from its previously recorded output state. If it is, then it marks all immediate successors – and any task that follows any successor in a shared synchronizer as SelfValidState = false. It marks successors as invalid since, in effect, their input states just changed, and it marks the successors’ subsequent coexecutors as invalid because they will need to run in order to accommodate dependencies provided by their preceding coexecutors.

validation algorithm

Figure 2 Validation Algorithm