Locally self-adjusting distributed algorithms

In this dissertation, we study self-adjusting algorithms for large-scale distributed systems. Self-adjusting algorithms enable distributed systems to adjust their properties dynamically as the input pattern changes. Self-adjustment is an attractive tool as it has the potential to significantly improve the performance of distributed systems, especially when the input patterns are skewed.

We start with a distributed self-adjusting algorithm for skip graphs that minimizes the average routing costs between arbitrary communication pairs by performing topological adaptation to the communication pattern. Our algorithm is fully decentralized, conforms to the CONGEST model (i.e. uses O(log n) bit messages), and requires O(log n) bits of memory for each node, where n is the total number of nodes. Upon each communication request, our algorithm first establishes communication by using the standard skip graph routing, and then locally and partially reconstructs the skip graph topology to perform topological adaptation. We propose a computational model for such algorithms, as well as a yardstick (working set property) to evaluate them. Our working set property can also be used to evaluate self-adjusting algorithms for other graph classes where multiple tree-like subgraphs overlap (e.g. hypercube networks). We derive a lower bound of the amortized routing cost for any algorithm that follows our model and serves an unknown sequence of communication requests. We show that the routing cost of our algorithm is at most a constant factor more than the amortized routing cost of any algorithm conforming to our computational model. We also show that the expected transformation cost for our algorithm is at most a logarithmic factor more than the amortized routing cost of any algorithm conforming to our computational model.

As a follow-up work, we present a distributed self-adjusting algorithm (referred to as DyHypes) for topological adaption in hypercubic networks. One of the major differences between hypercubic networks and skip graphs is that hypercubic networks are more rigid in structure than that of skip graphs. This property of hypercubic networks makes self-adjustment significantly different compared to skip graphs. Upon a communication between an arbitrary pair of nodes, DyHypes transforms the network to place frequently communicating nodes closer to each other to maximize communication efficiency, and uses randomization in the transformation process to speed up the transformation and reduce message complexity. We show that, as compared to DSG, DyHypes reduces the transformation cost by a factor of O(log n), where n is the number of nodes involved in the transformation. Moreover, despite achieving faster transformation with lower message complexity, the combined cost (routing and transformation) of DyHypes is at most a log log n factor more than that of any algorithm that conforms to the computational model adopted for this work. Similar to DSG, DyHypes is fully decentralized, conforms to the CONGEST model, and requires O(log n) bits of memory for each node, where N is the total number of nodes.

Finally, we present a novel distributed load balancing algorithm called Meezan to address the load imbalance among large-scale networked cache servers. Modern web services rely on a network of distributed cache servers to efficiently deliver content to users. Load imbalance among cache servers can substantially degrade content delivery performance. Due to the skewed and dynamic nature of real-world workloads, cache servers that serve viral content experience higher load as compared to other cache servers. Our algorithm Meezan replicates popular objects to mitigate skewness and adjusts hash space boundaries in response to load dynamics in a novel way. Our theoretical analysis shows that Meezan achieves near perfect load balancing for a wide range of operating parameters. Our trace driven simulations shows that Meezan reduces load imbalance by up to 52% as compared to prior solutions.