# The expansion and mixing time of skip graphs with applications

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.

## Abstract

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.

- SPAA 2005 proceedings version: PDF.
- Full version:
**PDF**.

## BibTeX

Download@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}
)

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page