Analyse Diskreter Lastbalancierung auf Heterogenen Netzwerken (ADLON)

• Antragsteller: Professor Tobias Friedrich, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 223438688

• Erstellungsjahr: 2019

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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.
  
• 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.
  
• 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.
  
• De-anonymization of heterogeneous random graphs in quasilinear time. Algorithmica 80. (2018), 3397–3427
  Bringmann, K., Friedrich, T., Krohmer, A.
  
• 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.
  
• 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.