  We present randomized distributed algorithms for the maximal independent set
problem (MIS) that, while keeping the time complexity nearly matching the best
known, reduce the energy complexity substantially. These algorithms work in the
standard CONGEST model of distributed message passing with $O(\log n)$ bit
messages. The time complexity measures the number of rounds in the algorithm.
The energy complexity measures the number of rounds each node is awake; during
other rounds, the node sleeps and cannot perform any computation or
communications.
  Our first algorithm has an energy complexity of $O(\log\log n)$ and a time
complexity of $O(\log^2 n)$. Our second algorithm is faster but slightly less
energy-efficient: it achieves an energy complexity of $O(\log^2 \log n)$ and a
time complexity of $O(\log n \cdot \log\log n \cdot \log^* n)$. Thus, this
algorithm nearly matches the $O(\log n)$ time complexity of the
state-of-the-art MIS algorithms while significantly reducing their energy
complexity from $O(\log n)$ to $O(\log^2 \log n)$.
