Locally Self-Adjusting Tree Networks
Chen
Avin
author
Bernhard
Häupler
author
Zvi
Lotker
author
Christian
Scheideler
author 20792
Stefan
Schmid
author
79
department
SFB 901
project
SFB 901 - Subprojekt A1
project
SFB 901 - Project Area A
project
This paper initiates the study of self-adjusting networks (or distributed data structures) whose topologies dynamically adapt to a communication pattern $\sigma$. We present a fully decentralized self-adjusting solution called SplayNet. A SplayNet is a distributed generalization of the classic splay tree concept. It ensures short paths (which can be found using local-greedy routing) between communication partners while minimizing topological rearrangements. We derive an upper bound for the amortized communication cost of a SplayNet based on empirical entropies of $\sigma$, and show that SplayNets have several interesting convergence properties. For instance, SplayNets features a provable online optimality under special requests scenarios. We also investigate the optimal static network and prove different lower bounds for the average communication cost based on graph cuts and on the empirical entropy of the communication pattern $\sigma$. From these lower bounds it follows, e.g., that SplayNets are optimal in scenarios where the requests follow a product distribution as well. Finally, this paper shows that in contrast to the Minimum Linear Arrangement problem which is generally NP-hard, the optimal static tree network can be computed in polynomial time for any guest graph, despite the exponentially large graph family. We complement our formal analysis with a small simulation study on a Facebook graph.
/download/513/1303/513-ipdps13_01.pdf
application/pdf
2013
Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2013.40
395-406
Avin, Chen et al. “Locally Self-Adjusting Tree Networks.” <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>. N.p., 2013. 395–406. Web.
Avin, Chen, Bernhard Häupler, Zvi Lotker, Christian Scheideler, and Stefan Schmid. “Locally Self-Adjusting Tree Networks.” In <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>, 395–406, 2013. doi:<a href="http://dx.doi.org/10.1109/IPDPS.2013.40">10.1109/IPDPS.2013.40</a>.
C. Avin, B. Häupler, Z. Lotker, C. Scheideler, S. Schmid, in:, Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2013, pp. 395–406.
@inbook{Avin_Häupler_Lotker_Scheideler_Schmid_2013, title={Locally Self-Adjusting Tree Networks}, DOI={<a href="http://dx.doi.org/10.1109/IPDPS.2013.40">10.1109/IPDPS.2013.40</a>}, booktitle={Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)}, author={Avin, Chen and Häupler, Bernhard and Lotker, Zvi and Scheideler, Christian and Schmid, Stefan}, year={2013}, pages={395–406}}
C. Avin, B. Häupler, Z. Lotker, C. Scheideler, and S. Schmid, “Locally Self-Adjusting Tree Networks,” in <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>, 2013, pp. 395–406.
Avin, C., Häupler, B., Lotker, Z., Scheideler, C., & Schmid, S. (2013). Locally Self-Adjusting Tree Networks. In <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i> (pp. 395–406). http://doi.org/<a href="http://dx.doi.org/10.1109/IPDPS.2013.40">10.1109/IPDPS.2013.40</a>
Avin C, Häupler B, Lotker Z, Scheideler C, Schmid S. Locally Self-Adjusting Tree Networks. In: <i>Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>.; 2013:395-406. doi:<a href="http://dx.doi.org/10.1109/IPDPS.2013.40">10.1109/IPDPS.2013.40</a>.
5132017-10-17T12:42:32Z2018-04-16T06:12:23Z