Locally Self-Adjusting Tree Networks
This paper initiates the study of self-adjusting networks (or distributed data structures) whose topologies dynamically adapt to a communication pattern. The authors 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. They derive an upper bound for the amortized communication cost of a SplayNet based on empirical entropies, and show that SplayNets have several interesting convergence properties.