Graph Relabelling Systems



Graph relabelling systems are useful to encode distributed algorithms, to prove their correctness, to understand their power and even to visualize them.

We illustrate this by a catalogue of examples of classical distributed algorithms. As usual, a network is represented by a graph whose vertices stand for processors and edges for (bidirectional) links between processors. At everytime, each vertex and each edge is in some particular state which is encoded by a vertex or edge label.

According to its own state and to the states of its neighbours, each vertex may decide to realize an elementary computation step. After this step, the states of this vertex, of its neighbours and of the corresponding edges may have changed according to some specific computation rules.

Let us recall that graph relabelling systems satisfy the following requirements:
  1. They do not change the underlying graph but only the labelling of its components (edges and/or vertices), the final labelling being the result,
  2. They are local, that is, each relabelling changes only a connected subgraph of a fixed size in the underlying graph,
  3. They are locally generated, that is, the applicability condition of the relabelling only depends on the local context of the relabelled subgraph.


For each of the examples given here, we present a relabelling system encoding the distributed algorithm, the used labels, the initial labellings, together with a few screen snapshots of the visualization of the algorithm.



Some animated examples