Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
The expansion and mixing time of skip graphs with applications

James Aspnes and Udi Wieder

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 can be used to sample a node in the skip graph in a highly efficient manner. We also show that the expansion property can be used to load balance the skip graph quickly. Finally, it is shown that the skip graph could serve as an unstructured P2P system, making it a good candidate for a hybrid P2P system.

Details

Publication typeInproceedings
Published inSPAA '05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures
Pages126–134
ISBN1-58113-986-1
AddressNew York, NY, USA
PublisherACM
> Publications > The expansion and mixing time of skip graphs with applications