We present the design and analysis of STAR, a fully decentralized self-stabilizing randomized membership protocol building a strongly connected overlay graph with sub-logarithmic diameter and almost homogeneous logarithmic degree. STAR is the first protocol to simultaneously maintain the following properties on the resulting graph $G$: {(i)} The graph maintains the {\em Eulerian\/} property, namely that the in-degree and out-degree of each node are the same, and that $G$ is strongly connected. {(ii)} The out-degree of each node automatically converges to an average of $2 \ln (n)+O(1)$ without any node knowing the exact size $n$ of the network. {(iii)} The diameter of the overlay graph will be $\frac{\ln n}{\ln \ln n + \ln 2}+O(1)$ with high probability. {(iv)} STAR is self-stabilizing. Starting from an arbitrary graph topology, or after disruptive error, {\stella} will cause the overlay graph to converge to the desired properties.