James Aspnes and Udi Wieder. The expansion and mixing time of skip graphs with applications. Distributed Computing 21(6):385–393, March 2009. An earlier version appeared in Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 2005, pages 126–134.
We prove that with high probability a skip graph contains a 4-regular expander as a subgraph, and estimate the quality of the expansion via simulations. As a consequence skip graphs contain a large connected component even after an adversarial deletion of nodes. We show how the expansion property could be used to sample a node in the skip graph in a highly efficient manner. We also show that the expansion property could be used to load balance the skip graph quickly. Finally it is shown that the skip graph could serve as an unstructured P2P system, thus it is a good candidate for a hybrid P2P system.
@article(AspnesW2009,
title="The expansion and mixing time of skip graphs with applications",
author="James Aspnes and Udi Wieder",
journal="Distributed Computing",
month=mar,
year=2009,
pages={385--393}
)