Software Engineering White Papers
Maximal Independent Sets in Radio Network
Overview This paper study the distributed complexity of computing a Maximal Independent Set (MIS) in radio networks with completely unknown topology, asynchronous wake-up, and no collision detection mechanism available. Specifically, it propose a novel randomized algorithm that computes a MIS in time O (log2n) with high probability, where n is the number of nodes in the network. This significantly improving on the best previously known solutions. A lower bound of ¬ - (log2n= log n) given in implies that the algorithm's running time is close to optimal. The result shows that the harsh radio network model imposes merely an additional O (log n) factor compared to Luby's MIS algorithm in the message passing model.
| Publisher | Association for Computing Machinery | File Format | |
|---|---|---|---|
| Date Published | July 2005 | ||
| Format | White Papers | ||
| Topics | |||
-
Did you find this white paper useful?
White Paper RSS
Download
