%0 Journal Article %F metivier:hal-00695983 %A Métivier, Yves %A Robson, J.M. %A Saheb-Djahromi, Nasser %A Zemmari, Akka %T {On the Time and the Bit Complexity of Distributed Randomised Anonymous Ring Colouring} %J Theoretical Computer Science %V 445 %P 1-12 %X {We present and analyse a very simple randomised distributed vertex colouring algorithm for ring graphs. Its time complexity is ${\log\_2 n} + o(\log n)$ on average and $2{\log\_2 n}+ o(\log n)$ with probability $1- o(n^{-1}).$ Each message containing $1$ bit we deduce the same values for its bit complexity. Then we compose this algorithm with another and we obtain a $3$-colouring algorithm for ring graphs. Thanks to an overlapping, we obtain once more the same values for the time complexities on average and with probability $1- o(n^{-1}).$ The same results hold for the bit complexity. These results are obtained using the Mellin transform. We establish lower bounds (on average and with probability $1- o(n^{-1})$) for the distributed randomised anonymous ring colouring problem. We prove that our algorithms match these lower bounds modulo a negligible additive function (negligible with respect to $\log\_2 n$). We assume that the ring is anonymous: unique identities are not available to distinguish the processes; we only assume that each vertex distinguishes between its neighbours. Furthermore we do not assume that the size (or an upper bound on the size) of the ring is known.} %U http://hal.archives-ouvertes.fr/hal-00695983 %8 May %D 2012 %K Bit Complexity %K Colouring %K Mellin Transform %K Probabilistic Analysis %K Randomised Distributed Graph Algorithm %K Ring %K Time Complexity %K bit complexity