Exploiting awareness

If we know that the scripts we are running are aware as well as homogeneous, we can make this iterative process more efficient. If they are aware, they know when they succeed. If they are homogeneous, one success for each script suffices. Thus we need only execute each script until it succeeds, and the permutation embedding algorithm can skip invoking scripts that have already succeeded.

Suppose, e.g., that we have six scripts A,B,C,D,E,F, to be executed in that order, and that in actuality D and E must occur before B; E before C; C before A; and A before F. Let us notate a success of A as =A (representing unification with A's postconditions) and a failure of A as !A. Then the algorithm's execution will proceed as follows:

 
!A !B !C =D =E !F    
!A =B =C .. .. !F    
=A .. .. .. .. =F

In the first pass, A, B, C, and F fail, while D and E succeed, because !C implies !A, !D and !E imply !B, !E implies !C, and !A implies !F. In the second pass B and C succeed because their predecessors D and E have succeeded in the first. In the last pass, A and F succeed because all their preconditions are satisfied. So an appropriate total order is D, E, B, C, A, F.

The worst case is that the precedences are the reverse of the order of the list. In this case the algorithm takes O(n²) executions, where n is the number of scripts:

 
!A !B !C !D !E =F
!A !B !C !D =E ..
!A !B !C =D .. ..
!A !B =C .. .. ..
!A =B .. .. .. ..
=A

There are (n-1)(n-2)/2 script failures due to inappropriate precedence. Once we know the reverse order is more appropriate, however, a subsequent run will take only O(n) executions.

The driving idea here is that

Proposition 6: The execution order for an aware, convergent, and homogeneous set of scripts need not be predeclared through precedences, but can be discovered by executing the scripts and observing their effects.

We should note that this does not mean that we can discover the true precedences between scripts, just that we can discover some execution order that obeys those precedences. Further, Frode Eika Sandnes shows that knowing this order does not in general aid in inferring the true precedences between actions[25].