id: 05965695
dt: a
an: 05965695
au: Izumi, Taisuke; Gradinariu Potop-Butucaru, Maria; Valero, Mathieu
ti: Physical expander in virtual tree overlay.
so: Peleg, David (ed.), Distributed computing. 25th international symposium,
DISC 2011, Rome, Italy, September 20‒22, 2011. Proceedings. Berlin:
Springer (ISBN 978-3-642-24099-7/pbk). Lecture Notes in Computer
Science 6950, 82-96 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc:
ut:
ci:
li: doi:10.1007/978-3-642-24100-0_6
ab: Summary: 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.
rv: