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



Description:

In the previous example, the spanning tree is computed in a strictly sequential way since at any time at most one vertex is active (with label A).

We will give here a second version of this algorithm that will run in a more distributed way.



As before, we assume that a unique vertex has initially label A, all other vertices having label N and all edges having label 0.

At each step of the computation, an A-labelled vertex u may activate any of its neutral neighbours, say v. In that case, u keeps its label, v becomes A-labelled and the edge {u,v} becomes 1-labelled.

Hence, several vertices may be active at the same time. Concurrent steps will be allowed provided that two such steps involve distinct vertices.

The computation stops as soon as all the vertices have been activated. As before, the spanning tree is given by the 1-labelled edges. We give here a version of the Spanning Tree that will run in a distributed way.

We assume that a unique vertex has initially label A, all other vertices having label N and all edges having label 0.



Description

Proof

Snapshots


An animated example