Random ring-based overlay networks have been used to study the small world
phenomenon and model fault-tolerant peer-to-peer systems (Kleinberg, 2006). It
has been shown that when each of $n$ nodes has $\ell = O(\log n)$ links,
assigning contacts according to an inverse power-law distance distribution
allows greedy routing to perform in $O(\log^2 n / \ell)$ steps (Aspnes et al.
2002). In this paper, we generalize this result by showing the same upper bound
holds when nodes are assigned a random number of links according to an
arbitrary distribution with mean $\ell$.