  Overlay networks present an interesting challenge for fault-tolerant
computing. Many overlay networks operate in dynamic environments (e.g. the
Internet), where faults are frequent and widespread, and the number of
processes in a system may be quite large. Recently, self-stabilizing overlay
networks have been presented as a method for managing this complexity.
\emph{Self-stabilizing overlay networks} promise that, starting from any
weakly-connected configuration, a correct overlay network will eventually be
built. To date, this guarantee has come at a cost: nodes may either have high
degree during the algorithm's execution, or the algorithm may take a long time
to reach a legal configuration. In this paper, we present the first
self-stabilizing overlay network algorithm that does not incur this penalty.
Specifically, we (i) present a new locally-checkable overlay network based upon
a binary search tree, and (ii) provide a randomized algorithm for
self-stabilization that terminates in an expected polylogarithmic number of
rounds \emph{and} increases a node's degree by only a polylogarithmic factor in
expectation.
