next up previous
Next: Coping with inhomogeneity Up: Observability Previous: Observability

Assuring determinism

So far, whenever we have been unable to predefine something we need, we have consistently tried to observe it instead. When observing, we found that the original abstract concept that we tried to describe is not what we need, and that something less descriptive and more observable suffices. While we initially searched for a way to define precedences for tasks, we only truly need an order in which the tasks will function properly. This order can be discovered dynamically, even if the precedences remain hidden.

Applying this approach to homogeneity of a set of scripts, it is the observable results of homogeneity that we desire, rather than the property itself. Minimally, the execution of every set of scripts should have a deterministic outcome so there are `no surprises'. If this outcome is inappropriate, we know that our scripts are incorrect. If a script has an inhomogeneity that does not affect the outcome, we will never know about it, and perhaps need not even care.

To assure determinism in the outcome of executing a set of scripts that are convergent and deterministic in isolation from one another, we can run them in a particular order on a functioning network. If they are homogeneous with one another, this will make no changes to the network. If they are inhomogeneous but convergent, a script that disagrees with another will make a conflicting change to the network. Even so, the fact that the scripts were executed in a predetermined order guarantees a result dependent upon that order.

Once we have agreed upon this as a goal, detecting inhomogeneity becomes easier. If each script reports whether it changed anything, we can record whether there are any inhomogeneities apparent within the sequence in which we execute the scripts. This is much easier to determine than detecting inhomogeneities between all pairs of scripts, as we need only concern ourselves with anomalies in executing one permutation of the scripts, not all permutations (as would be required to detect the subtle examples of inhomogeneity presented above).

Suppose that in a functioning network, we run a sequence of scripts twice. We can conclude, in the absence of other external effects, that any script that reports changes twice during this process is inhomogeneous with at least one of the scripts invoked between its two invocations. For example, if the sequence of scripts is ABCDE, and we invoke them twice with the following results:

script: A B C D E A B C D E
change: n y n n y n y n n y
we can conclude that B and E are inhomogeneous with one another, while the other scripts are observably homogeneous. In more complex cases it may not be clear which scripts are inhomogeneous with others, as in
script: A B C D E A B C D E
change: n y y n y n y n n y
We can say little about the relationship between C and the others, as it only makes changes once. All that we can conclude from this is that E must follow B to ensure the result achieved by this run. It is unclear whether C is inhomogeneous with either B or E from this evidence.


next up previous
Next: Coping with inhomogeneity Up: Observability Previous: Observability
Alva L. Couch
2001-10-02