10.1109/IPDPS.2013.40
Avin, Chen
Chen
Avin
Häupler, Bernhard
Bernhard
Häupler
Lotker, Zvi
Zvi
Lotker
Scheideler, Christian
Christian
Scheideler
Schmid, Stefan
Stefan
Schmid
Locally Self-Adjusting Tree Networks
2013
2017-10-17T12:42:32Z
2019-01-03T13:16:46Z
conference
/record/513
/record/513.json
518804 bytes
application/pdf
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.