Analysis of Discrete Load Balancing on Heterogeneous Networks (ADLON)

• Applicant: Professor Dr. Tobias Friedrich, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 223438688

• Final Report Year: 2019

Final Report Abstract

Load balancing is an important prerequisite for the efficient usage of large parallel networks. In the typical theoretical abstraction, processors are represented by nodes of a graph, links are represented by edges, and loads are represented by vertex weights. Within this project, we have studied iterative algorithms to distribute the load on heterogeneous networks. Regarding network models, we focused on various models of deterministic and random scale-free graphs. For the Chung-Lu random graph model we proved that load-balancing can be done in double-logarithmic time, which is not achievable on homogeneous networks. We also developed a framework to systematically evaluate generative network models regarding how well they represent real-world networks.

Publications

• Ultra-fast load balancing on scale-free networks. International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science. (2015), 516–527
  Bringmann, K., Friedrich, T., Hoefer, M., Rothenberger, R., Sauerwald, T.
  (See online at https://dx.doi.org/10.1007/978-3-662-47666-6_41)
• Greed is good for deterministic scale-free networks. Foundations of Software Technology and Theoretical Computer Science (FSTTCS). (2016), 33:1–33:15
  Chauhan, A., Friedrich, T., Rothenberger, R.
  (See online at https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.33)
• Randomized load balancing on networks with stochastic inputs. 44th International Colloquium on Automata, Languages, and Programming (ICALP). (2017), 139:1–139:14
  Cai, L., Sauerwald, T.
  (See online at https://dx.doi.org/10.4230/LIPIcs.ICALP.2017.139)
• De-anonymization of heterogeneous random graphs in quasilinear time. Algorithmica 80. (2018), 3397–3427
  Bringmann, K., Friedrich, T., Krohmer, A.
  (See online at https://doi.org/10.1007/s00453-017-0395-0)
• Random walks on dynamic graphs: mixing times, hitting times, and return probabilities. 46th International Colloquium on Automata, Languages, and Programming (ICALP). (2019), 93:1–93:15
  Sauerwald, T., Zanetti, L.
  (See online at https://dx.doi.org/10.4230/LIPIcs.ICALP.2019.93)
• The dispersion time of random walks on finite graphs. 31st ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA). (2019), 103–113
  Rivera, N., Sauerwald, T., Stauffer, A., Sylvester, J.
  (See online at https://dx.doi.org/10.1145/3323165.3323204)