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