zur Startseite

Hauptseminar - Prinzipien verteilter Systeme (WS19/20)

Prinzipien verteilter Systeme -- Verarbeitung großer Graphen
Dozent Prof. Dr. rer. nat. Dr. h. c. Kurt Rothermel
Umfang2 SWS
Sprache Deutsch
Studiengänge Master
Zielgruppe Softwaretechnik, Informatik
Termine1. Termin: 17.10.2019
Kurzbeschreibung

Für viele Internetdienste sind große Graphen heute ein essentieller Bestandteil. Ein prominentes Beispiel ist der Freundschafts-Graph von Facebook, der die Beziehungen der Facebook-Nutzer untereinander darstellt, aber auch andere Internetdienste wie Google, Pinterest, Amazon, Reddit und LinkedIn nutzen großen Graphen um Verbindungen von Webseiten, Produkten, Nutzern und deren Eigenschaften zu speichern und auszuwerten. Weiterhin werden große Graphen zum Design von Netzwerken und Hardware (VLSI Designs) eingesetzt.

 

Graphen wie diese haben oft Millionen bis Milliarden von Knoten und um vieles mehr an Kanten. Auswertungen auf diesen Graphen, wie beispielsweise Page Rank,  Graphenisomorphie, Bestimmung des kürzesten Pfads oder Empfehlungsmechanismen, müssen somit hochgradig skalierbar sein. Sie erfordern deshalb eine parallele und verteilte Ausführung. Damit verbunden ist die Herausforderung, die Graphen in geeigneter Weise zu partitionieren, sowie die Entwicklung effizienter Algorithmen für partitionierte Graphen.

 

Graphenstrukturen werden auch bei der verteilten Auswertung von Datenströmen angewendet. Insbesondere in der Verarbeitung von Ereignisströmen (complex event processing – CEP), werden sogenannte Operatorgraphen genutzt, um Erkenntnisse aus beobachteten Ereignissen in nahezu Echtzeit zu gewinnen. Im Vergleich zur Stapelverarbeitung (Batch-Processing) kann so auf Ereignisse unmittelbar reagiert werden. CEP Systeme müssen mit Millionen von Daten pro Sekunde umgehen und entsprechend skalieren.

 

Im Rahmen dieses Hauptseminars sollen Frameworks für die Verarbeitung großer Graphen besprochen werden, die wir für die verteilte Berechnung auf großen Graphen nutzen können. Dies umfasst auch die zugrunde liegenden Programmiermodelle. Außerdem werden verteilte Graphen-Algorithmen und –Approximationsmethoden besprochen, wie etwa Verfahren für Clustering, Graphen-Kolorierung, Kürzeste Pfade, Spannbäume sowie Page Rank und Community Detection. Des Weiteren sollen Möglichkeiten erarbeitet werden, wie CEP Systeme hohe Datenmengen verarbeiten können. Dies sind beispielsweise parallele Verarbeitung der Datenströme, sowie Load Balancing und Load Shedding zur Lastkontrolle der einzelnen Operatoren. Auch bekannte Frameworks, mittels derer hoch-skalierbare CEP Anwendungen entwickelt werden können, wie das von Twitter® genutzte Heron, sollen besprochen werden.

Organisatorisches:

Jeder Studierende bereitet einen Vortrag sowie eine schriftliche Ausarbeitung vor. Zudem wird die Mitarbeit bewertet. Die Anwesenheit an den Terminen ist verpflichtend. Studierende auf der Warteliste können als Nachrücker berücksichtigt werden, wenn sie zum ersten Termin erscheinen. Die Veranstaltung ist auf Deutsch, Präsentationen und Ausarbeitungen können jedoch auf Deutsch oder Englisch verfasst werden.

Ansprechpartner: Michael Schramm, David Hellmanns

Voraussetzungen

Grundkenntnisse in Verteilten Systemen und Kommunikationsnetzen bzw. Rechnernetzen sind hilfreich.

externer Link