Analysis of the algorithm

Once we have an algorithm, we want to know its correctness and if it is correct, then how

complex it is.

In this algorithm, we handle synchronization links one by one.Every step, we compute 

value change by one synchronization link and propagate this change to all other 

nodes.The propagation is processed recursively until the value change of current node 

will not affect any other node's value. In fact, every propagation is required to stop

at somewhere in this algorithm, or else it will never stop. 

So one question is : Will all propagation stop at some node? or in other words when will 

propagation never stop? I think, if the time value change propagation formed one circle,

which means after some steps in propagating, value change requirement arrives at the 

current node who cause this propagation,then it will cause a dead loop and it will never

stop if we let it propagate. This problem is related with the inconsistent specification,

I will discuss it later.

If the algorithm does stop, then can we prove that the time value we get is consistent

with the specification? (i.e. the correctness of this algorithm). In computer science,

two ways are mostly used to verify correctness. One is formal prove and the other is 

testing.It seems that testing will be easier,what we need to do is to check

the time value we get from this algorithm according to synchronization links in the 

hypergraph. If all of them are satified,then it is correct,else this algorithm is 

wrong. The problem with testing is no matter how many test cases we test,we can

not conclude that this algorithm is correct unless we can test all possible hypergraph

which is impossible. And for most algorithms, formal prove is required. So we need to

come up with formalism of this problem and algorithm and conclude if this algorithm is

right or not. This is not covered yet.

Let us assume correctness of this algorithm, then we want to know its complexity. The 

outer loop will be executed m times(m is the total number of synchronization links).And

when handling one synchronization link, it construct affected synchronization links set

and recursive process that set.The size of that set is hard to estimate. The worse case

will be including (m-1) synchronization links and some annotation (maybe 1 if propagating

from children nodes to parent, or n if propagating from parent to children) and the 

propagation should not exceed n*depth of the hypergraph (n is constant ,2 or 3,inaccurate)

The previous analysis is just one approximate analysis. However we can conclude that 

this algorithm will be exponential.

So, In conclusion, this algorithm is definitely needed to be improved. Also its 

correctness should be furtherly analyzed.