Analyse Diskreter Lastbalancierung auf Heterogenen Netzwerken (ADLON)
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.
(Siehe online unter 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.
(Siehe online unter 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.
(Siehe online unter 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.
(Siehe online unter 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.
(Siehe online unter 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.
(Siehe online unter https://dx.doi.org/10.1145/3323165.3323204)
