Randomised distributed MIS and colouring algorithms for rings with oriented edges in O(log⁡n) bit rounds

We present and analyse Las Vegas distributed algorithms which compute a MIS or a colouring for anonymous rings with an arbitrary orientation of the edges; their bit complexity and time complexity are O(log⁡n) with high probability. These algorithms are optimal modulo a multiplicative constant.