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:
  1. 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.
  2. 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.



Description

Proof

Snapshots