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


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.


 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},