Kommunikationseffiziente Verteilte Algorithmen

Mit dem schnellen Wachstum von Netzwerken und der rasanten Zunahme des Datenvolumens werden verteilte Algorithmen in Netzwerken eine entscheidende Rolle in unserer Zukunft spielen und in fast allen Lebensbereichen von Bedeutung sein. Dieses Projekt zielt darauf ab, unser Verständnis für die grundlegenden Aspekte dieser Bereiche zu verbessern. Algorithmen, die in solchen Umgebungen arbeiten, müssen mit verschiedenen Formen von Kommunikationsbeschränkungen umgehen wie zum Beispiel Bandbreitenbeschränkungen der Kommunikationsverbindungen zwischen den Computern. Das Hauptziel dieses Projekts ist es, eine grundlegende Theorie bereitzustellen und das Verständnis für die Rolle von Kommunikationsbeschränkungen bei verteilten Berechnungen erheblich zu erweitern. In diesem Projekt geht es also darum, neue kommunikationseffiziente verteilte Algorithmen für zentrale Probleme in diesem Bereich zu entwickeln. Ein Beispielproblem, das wir untersuchen, ist das Problem der Zuweisung von Frequenzen in einem Sensornetz, so dass die Frequenzen für eine störungsfreie Kommunikation genutzt werden können. Das Ziel ist es also, wenige Frequenzen zu verwenden und nahe beieinander liegenden Sensoren nicht dieselbe Frequenz zuzuweisen. Oft ist es viel einfacher, diese Probleme zu lösen, wenn die Computer sogenannte Zufallsentscheidungen treffen können. Im Prinzip bedeutet dies, dass die Computer einen Würfel werfen können, um über den nächsten Schritt zu entscheiden. In Teilen dieses Projekts zielen wir darauf ab, schnelle Algorithmen zu entwickeln, die ohne solche Zufallsentscheidungen auskommen. Der Vorteil dieser Algorithmen ist, dass sie zuverlässiger sind und nie Fehler machen. Eine andere Gruppe von Problemen, die wir untersuchen, sind Optimierungsprobleme. Ein Beispiel für solch ein Problem bildet die Platzierung von Servern in einem Netzwerk, um ein Update auszuführen. Hier besteht das Ziel darin, wenige Server zu verwenden und sicherzustellen, dass jeder Computer des Netzwerks einen Server in seiner Nähe hat. Es scheint, dass es viel schwieriger ist, diese Probleme mit begrenzter Bandbreite zu lösen. In diesem Projekt untersuchen wir, inwieweit dies wirklich und gegebenenfalls auch warum dies der Fall ist. Alle in diesem Projekt betrachteten Probleme dienen als wesentliche Bausteine in anderen Algorithmen.