Physical Expander in Virtual Tree Overlay

In this paper, we propose a new distributed construction of constant-degree expanders motivated by their application in P2P overlay networks and in particular in the design of robust tree overlays. Our key result can be stated as follows. Consider a complete binary tree

T

and construct a random pairing Π between leaf nodes and internal nodes. We prove that the graph

G

Π

obtained from

T

by contracting all pairs (leaf-internal nodes) achieves a constant node expansion with high probability. In the context of P2P overlays our result can be interpreted as follows: if each physical node participating to the tree overlay manages a random pair that couples one virtual internal node and one virtual leaf node then the physical-node layer exhibits a constant expansion with high probability. We encompass the difficulty of obtaining the random tree virtualization by proposing a local, self-organizing and churn resilient uniformly-random pairing algorithm with

O

(log

2

n

) running time. Our algorithm has the merit to not modify the original tree overlay (we just control the mapping between physical nodes and virtual nodes). Therefore, our scheme is general and can be easilly extended to a large class of overlays.