Distributed Computation of a Spanning Tree With Local Detection of the Global Termination



We give here a distributed version of the spanning tree having the property of local detection of the global termination.

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).



Description

Proof

Snapshots