Balanced overlay networks (BON): Decentralized load balancing and analysis of large-scale systems

We present a self-organizing distributed computing architecture that encodes the information about each node's available computational resources in the structure of the links connecting the nodes in the network. Each node's degree is kept proportional to its free resources by adding or deleting edges when node resources are freed or consumed. The result of this local edge rewiring algorithm is that short, O(logN), random walks preferentially sample nodes with high degree and thus high node resources. Different variations of this algorithm produce Erdos-Renyi random graphs, nearly d-regular random graphs and random power-law graphs. What each variation has in common is that each node bears a load that is proportional to its resources, which is a useful load-balancing metric for any resource distribution. There have been prior studies on using random walks to distribute jobs, but BON distinguishes itself by continually reshaping the network structure to permit efficient node sampling using short random walks.; Some of the most recent distributed computing systems have been based on distributed hash tables (DHTs). We have developed a tool called the reachable component method (RCM) to evaluate the scalability and performance of these types of systems. RCM is a generally-applicable technique for predicting structured DHT routing performance in the presence of random failures. Here we apply this method to seven popular DHT architectures and find that some systems are scalable under random failures and some are not. DHT routing algorithms that continue to function under a non-zero rate of random failures as N → infinity are scalable. Unscalable DHT algorithms are unable to route at all for any non-zero node failure rate as N → infinity. These predictions enable the effective planning and use of DHT systems to ensure a desired quality of service.