Lightweight Coloring and Desynchronization for Networks

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Motskin, A., Roughgarden, T., Skraba, P., Guibas, L.
Format: Conference Proceeding
Language:English
Subjects:
Communications Society
Computational modeling
Computer networks
Convergence
Distributed computing
Greedy algorithms
Network topology
Peer to peer computing
Protocols
State feedback
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0743-166X
2641-9874
DOI:10.1109/INFCOM.2009.5062165