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