Distributed Computation of a Spanning Tree With Local Detection of Termination, Each Process is Identified by a Unique Name
Description:
The main idea is that the unique initially
(A,n)-labelled vertex will keep
its label until the end of the computation, while other activated vertices will
be
(A',n)-labelled. As soon as an
(A',n)-labelled vertex is no
longer "useful" for the
growing of the tree, it will reach its final state (with label
(F,n)).
More precisely, we will use the following computation rules:
At each step of the computation, an active vertex (with label
(A,i)
or
(A',i)), say
u,
will act as follows:
- If u has a (X,j)-labelled neighbour v, where j<i and
X = {A,A',F}, then u will activate this neighbour: u keeps its
label, v becomes active (with label (A',i)) and the edge {u,v} becomes
i-labelled.
- If u is (A',i)-labelled, has no (X,j)-labelled neighbour,
where j <> i and X = {A,A',F}, and
is such that all its neighbours to which it is linked by an i-labelled edge except one
of these neighbours are (F,i)-labelled, then u becomes (F,i)-labelled.
At any time, the subgraph induced by the
n-labelled edges and the
(A,n)- or
(A',n)-labelled
vertices is a tree. Intuitively speaking, the second rule means that the vertex
u is
a leaf in this tree.