Entwicklung effizienter verteilter Algorithmen in großen selbstorganisierenden Netzwerken

• Applicant: Professor Dr. Robert Elsässer
• Subject Area: Theoretical Computer Science
• Term: from 2005 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5447394

Die Untersuchung der Eigenschaften von großen selbstorganisierenden Netzwerken ohne zentrale Kontrollinstanz (wie z.B. das Internet) ist zu einem bedeutenden Forschungsfeld auf dem Gebiet der Theoretischen Informatik geworden. Solche Netzwerke werden von einer Menge von Rechenknoten dynamisch gebildet, indem diese beim Aufbau der Verbindungen ihre eigenen Zielfunktionen zu optimieren versuchen. In den vergangenen Jahren wurden erste strukturelle Eigenschaften dieser Netzwerke untersucht. Man hat dabei festgestellt, dass für viele praxisrelevante Zielfunktionen der Knoten die Verbindungstruktur des Netzes der sogenanten "power low" Verteilung unterliegt. Basierend auf dieser Erkenntnis wurden die bereits existierenden Random Graph Modelle erweitert, um den Aufbau von selbstorganisierenden Netzwerken zu beschreiben. In diesem Forschungsvorhaben werden die Zusammenhänge zwischen den spektralen und strukturellen Eigenschaften dieser Random "power low" Graphen mit Hilfe von Techniken aus der spektralen Graphentheorie untersucht. Anschließend werden Algorithmen entwickelt, die in diesen großen selbstorganisierenden Netzwerken eine schnelle Informationsausbreitung garantieren und für eine faire Auslastung der Rechenknoten sorgen.

• DFG Programme: Research Fellowships