Distributed Computation of a Spanning Tree With Local Detection of the Global Termination
Description:
As before, we assume that a unique vertex has initially label A, all other vertices having label N and all edges having label 0.The main idea is that the unique initially A-labelled vertex will keep its label until the end of the computation, while other activated vertices will be A'-labelled. As soon as an A'-labelled vertex is no longer "useful" for the computation, it will reach its final state (with label F).
More precisely, we will use the following computation rules:
At each step of the computation, an active vertex (with label A or A'), say u, will act as follows:
- If u has a N-labelled neighbour v, then u will activate this neighbour: u keeps its label, v becomes active (with label A') and the edge {u,v} becomes 1-labelled.
- If u is A'-labelled, has no N-labelled neighbour and is such that all its neighbours to which it is linked by a 1-labelled edge except one of these neighbours are F-labelled, then u becomes F-labelled.
Thus, this algorithm runs in two phases (that may overlap): in the first phase, the tree is growing until all vertices are reached; in the second phase, it will decrease (by loosing its leaves) until it is reduced to the initially A-labelled vertex. This vertex is then able to detect that the algorithm has terminated since all its neighbours are F-labelled.
Here we use an other local control mechanism : forbidden contexts. A relabelling rule with forbidden contexts may be applied on some occurrence if and only if this occurrence is not included in an occurrence of some of its forbidden contexts.