Randomized distributed self-adjusting tree networks

In this paper we investigate the benefits of randomization in the design of self-adjusting network topologies: networks that dynamically adapt themselves toward the demand they currently serve, in an online manner. We present a randomized self-adjusting tree network, which leverages randomization to reduce the expected network reconfiguration cost by a constant factor, compared to existing deterministic solutions. The new solution is simple, easy-to-implement, fully distributed and concurrent. We prove algorithm correctness, provide expected amortized cost limits, and present simulation results on workloads with variable spatial and temporal complexity.