Computing a Maximal Independent Set Using Beeps

Details Computing a Maximal Independent Set Using Beeps Computing a Maximal Independent Set Using Beeps

2011-08-09

arxiv.org/abs/1108.1926v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

We consider the problem of finding a maximal independent set (MIS) in the discrete beeping model. At each time, a node in the network can either beep (i.e., emit a signal) or be silent. Silent nodes can only differentiate between no neighbor beeping, or at least one neighbor beeping. This basic communication model relies only on carrier-sensing. Furthermore, we assume nothing about the underlying communication graph and allow nodes to wake up (and crash) arbitrarily. We show that if a polynomial upper bound on the size of the network n is known, then with high probability every node becomes stable in O(\log^3 n) time after it is woken up. To contrast this, we establish a polynomial lower bound when no a priori upper bound on the network size is known. This holds even in the much stronger model of local message broadcast with collision detection. Finally, if we assume nodes have access to synchronized clocks or we consider a somewhat restricted wake up, we can solve the MIS problem in O(\log^2 n) time without requiring an upper bound on the size of the network, thereby achieving the same bit complexity as Luby's MIS algorithm.

Affiliated with

Also associated with

No associations

Rating

Computing a Maximal Independent Set Using Beeps does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing a Maximal Independent Set Using Beeps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing a Maximal Independent Set Using Beeps will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-70271