Arik Motskin, Tim Roughgarden, Primoz Skraba and Leonidas Guibas. Lightweight Coloring and Desynchronization for Networks. Proc. of IEEE INFOCOM, 2009.

Abstract:

We study the distributed desynchronization problem for graphs with arbitrary topology. Motivated by the severe computational limitations of sensor networks, we present a randomized algorithm for network desynchronization that uses an extremely lightweight model of computation, while being robust to link volatility and node failure. These techniques also provide novel, ultra-lightweight randomized algorithms for quickly computing distributed vertex colorings using an asymptotically optimal number of colors.

Bibtex: 

@inproceedings{mrsg-lcdn-09,
 author = {Arik Motskin and Tim Roughgarden and Primoz Skraba and Leonidas Guibas},
 title = {Lightweight Coloring and Desynchronization for Networks},
 booktitle = {IEEE INFOCOM'09: Proceedings of the 28th Conference on Computer Communications},
 year = {2009},
 location = {Rio de Janeiro, Brazil},
 publisher = {IEEE},
 }