metivier:hal-00695983
Yves Métivier, J.M. Robson, Nasser Saheb-Djahromi, Akka Zemmari. On the Time and the Bit Complexity of Distributed Randomised Anonymous Ring Colouring. Theoretical Computer Science, 445:1-12, May 2012.
Download
Download paper:
Follow the link
Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Abstract
{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.}
Keywords
[ Bit complexity ] [ Colouring ] [ Mellin transform ] [ Probabilistic analysis ] [ Randomised distributed graph algorithm ] [ Ring ] [ Time complexity ] [ Bit complexity ]
Contact
Yves Métivier
John-Michael Robson
Nasser Saheb-Djahromi
Akka Zemmari
BibTex Reference
@article{metivier:hal-00695983,
Author = {Métivier, Yves and Robson, J.M. and Saheb-Djahromi, Nasser and Zemmari, Akka},
Title = {{On the Time and the Bit Complexity of Distributed Randomised Anonymous Ring Colouring}},
Journal = {Theoretical Computer Science},
Volume = {445},
Pages = {1--12},
Month = {May},
Year = {2012}
}
EndNote Reference [help]
Get EndNote Reference (.ref)