Fast, Responsive Decentralised Graph Colouring

Understand

We solve, in a fully decentralised way (\ie with no message passing), the classic problem of colouring a graph.

• We propose a novel algorithm that is automatically responsive to topology changes, and we prove that it converges quickly to a proper colouring in $O(N\log{N})$ time with high probability for generic graphs (and in $O(\log{N})$ time if $\Delta=O(1)$) when the number of available colours is greater than $\Delta$, the maximum degree of the graph.
• We believe the proof techniques used in this work are of independent interest and provide new insight into the properties required to ensure fast convergence of decentralised algorithms.