  Maximal Independent Set (MIS) is one of the fundamental problems in
distributed computing. The round (time) complexity of distributed MIS has
traditionally focused on the \emph{worst-case time} for all nodes to finish.
The best-known (randomized) MIS algorithms take $O(\log{n})$ worst-case rounds
on general graphs (where $n$ is the number of nodes). Motivated by the goal to
reduce \emph{total} energy consumption in energy-constrained networks such as
sensor and ad hoc wireless networks, we take an alternative approach to
measuring performance. We focus on minimizing the total (or equivalently, the
\emph{average}) time for all nodes to finish. It is not clear whether the
currently best-known algorithms yield constant-round (or even $o(\log{n})$)
node-averaged round complexity for MIS in general graphs. We posit the
\emph{sleeping model}, a generalization of the traditional model, that allows
nodes to enter either ``sleep'' or ``waking'' states at any round. While waking
state corresponds to the default state in the traditional model, in sleeping
state a node is ``offline'', i.e., it does not send or receive messages (and
messages sent to it are dropped as well) and does not incur any time,
communication, or local computation cost. Hence, in this model, only rounds in
which a node is awake are counted and we are interested in minimizing the
average as well as the worst-case number of rounds a node spends in the awake
state.
  Our main result is that we show that {\em MIS can be solved in (expected)
$O(1)$ rounds under node-averaged awake complexity measure} in the sleeping
model. In particular, we present a randomized distributed algorithm for MIS
that has expected {\em $O(1)$-rounds node-averaged awake complexity} and, with
high probability has {\em $O(\log{n})$-rounds worst-case awake complexity} and
{\em $O(\log^{3.41}n)$-rounds worst-case complexity}.
