  This paper presents a randomized self-stabilizing algorithm that elects a
leader $r$ in a general $n$-node undirected graph and constructs a spanning
tree $T$ rooted at $r$. The algorithm works under the synchronous message
passing network model, assuming that the nodes know a linear upper bound on $n$
and that each edge has a unique ID known to both its endpoints (or,
alternatively, assuming the $KT_{1}$ model). The highlight of this algorithm is
its superior communication efficiency: It is guaranteed to send a total of
$\tilde{O} (n)$ messages, each of constant size, till stabilization, while
stabilizing in $\tilde{O} (n)$ rounds, in expectation and with high
probability. After stabilization, the algorithm sends at most one constant size
message per round while communicating only over the ($n - 1$) edges of $T$. In
all these aspects, the communication overhead of the new algorithm is far
smaller than that of the existing (mostly deterministic) self-stabilizing
leader election algorithms.
  The algorithm is relatively simple and relies mostly on known modules that
are common in the fault free leader election literature; these modules are
enhanced in various subtle ways in order to assemble them into a communication
efficient self-stabilizing algorithm.
