Some simple distributed algorithms for sparse networks

We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2 Delta - 1 colours, and maximal matchings can be computed within O(log* n + Delta) deterministic rounds, where Delta is the maximum degree of the network. We also show how to find maximal independent sets and (Delta + 1)-vertex colourings within O(log* n + Delta (2)) deterministic rounds. All hidden constants are very small and the algorithms are very simple.