Summary: As we are at the end of an era of increasing individual processor power, modern computer networks have to balance their load among an increasing number of nodes. Despite a large body of theoretical studies on load balancing, most results do not match the complex and heterogenous structure of the underlying network and the corresponding load balancing tasks. In fact, most research is concentrated on the analysis of very well-structured homogenous graphs like complete graphs, hypercubes, and tori. On the other hand, many computer networks are nowadays scale-free, that is, they have an irregular structure and a very skewed non-homogenous degree distribution. Besides the graph structure, heterogeneity may also be reflected in varying job sizes, computational power, and communication speed; as well as dynamic changes in the networks and the load distribution.
The main goal of this project is to bridge the gap between the well-studied homogenous setting and the theoretically much less understood heterogenous load balancing problems that occur in practice. We will examine various protocols and study the impact of different heterogenous networks and assumptions on the load distribution. As performance measures, we will focus on the running time and the smoothness of the load distribution. We will also regard communication-related aspects like synchrony and incurred traffic.
