Verteilte Reaktive Programmierung ist eine Programmiertechnik zur modularen und zeitgleich deklarativen Implementierung verteilter interaktiver Anwendungen. Diese werden als ein über mehrere Rechner verteilter dynamischer Datenfluss-Graph aus voneinander abhängenden Berechnungen definiert, ähnlich zu Formeln in Tabellenkalkulation. Eine Laufzeitbibliothek propagiert eingehende Änderungen durch diesen Datenfluss-Graphen, indem sie die Ergebnisse betroffener Berechnungen neu berechnet und zugleich die Topologie des Datenfluss-Graphen an möglicherweise geänderte Abhängigkeitsbeziehungen anpasst. Nutzerstudien haben ergeben, dass Reaktive Programmierung Code-Qualität sowie Verständlichkeit und Wartbarkeit von Programmen verbessert im Vergleich zu modularen Designs interaktiver Anwendungen basierend auf dem Beobachter-Entwurfsmuster. Ein Teil dieser Verbesserungen basiert auf synchroner Semantik für die Propagation von Änderungen: keine Neuberechnung können einen nur teilweise aktualisierten Zustand des Datenfluss-Graphen beobachten. Dies führt dazu, dass sämtliche Neuberechnungen infolge einer eingehenden Änderung augenscheinlich instantan stattfinden.

Klassischerweise wurde synchrone Semantik in lokalen und nicht nebenläufigen Anwendungen durch das Sicherstellen der Konsistenzeigenschaft “Glitch-Freiheit” erreicht: jede Neuberechnung darf nur ausgeführt werden, nachdem alle nötigen Neuberechnungen ihrer Abhängigkeiten zuvor abgeschlossen wurden. In verteilten Anwendungen sind existierende Ansätze aufgrund zweierlei Gründe jedoch nicht mehr anwendbar. Zum einen impliziert Glitch-Freiheit synchrone Semantik nur solange Propagationen von Änderungen isoliert voneinander ausgeführt werden. Verteilte Anwendungen sind unweigerlich nebenläufig, was bedeutet, dass mehrere Änderungen zeitgleich durch denselben Datenfluss-Graphen propagiert werden. Um mehrere nebenläufig Änderungspropagationen voneinander zu isolieren, müssen daher Algorithmen zur Einschränkung der Nebenläufigkeit in die Laufzeitbibliothek integriert werden. Zum anderen ist der Datenfluss-Graph in verteilten Anwendungen über mehrere Rechner verteilt, welche nur über Netzwerkverbindungen miteinander kommunizieren können. Es können daher, sowohl zum Einhalten von Glitch-Freiheit als auch zur Einschränken von Nebenläufigkeit, ausschließlich Algorithmen eingesetzt werden, die dezentralisiert sind, was bedeutet dass sie ohne Zugriff auf gemeinsamen Arbeitsspeicher funktionieren müssen. Eine umfangreiche Studie themenverwandter früherer Arbeiten zeigt, dass bisher keine Lösung für diese Problemstellung existiert.

Die vorliegende Dissertation präsentiert FrameSweep, den ersten Algorithmus der synchrone Semantik für nebenläufige Propagation von Änderungen auf dynamischen und verteilten Datenfluss-Graphen sicherstellt. FrameSweep isoliert nebenläufige Propagationen und stellt ihre Glitch-Freiheit sicher, indem es mehrere Algorithmen aus dem Feld der Datenbanken für atomar erscheinende Transaktionen mit Aspekten von Algorithmen zur Änderungspropagation aus den Gebieten der Reaktiven Programmierung und der Automatischen Inkrementalisierung kombiniert. Die Korrektheit von FrameSweep wird durch Anwendung von establierter Theorie zur Nebenläufigkeitskontrolle durch Multiversionen formal bewiesen. FrameSweep dezentralisiert all seine algorithmischen Bestandteile und kann dadurch syntaktisch transparent in jegliche Laufzeitbibliotheken für Reaktive Programmierung integriert werden, was bedeutet, dass existierende Programme FrameSweep ohne Anpassungen ihres Quelltexts verwenden können. FrameSweep implementiert somit auf Basis identischer Syntax identische Semantik wie klassische, lokale, nicht-nebenläufige Reaktive Programmierung. Dadurch ist FrameSweep ein beispielhafter Beweis, dass interaktive Anwendungen alle Vorteile Reaktiver Programmierung genießen können, selbst wenn sie nebenläufige oder verteilte Systeme sind.

Eine umfangreiche empirische Evaluation misst durch Benchmarks, wie sich die Performanz und Skalierbarkeit von FrameSweep verhalten unter diversen Faktoren wie mehr oder weniger häufige Zugriffskonflikte zwischen nebenläufigen Prozessen, Topologie des Datenfluss-Graphen, Änderungen dieser Topologie, oder Topologie der Verteilung des Datenfluss-Graphen über verschiedene nur durch Netzwerk verbundene Rechner. Die Evaluation zeigt, dass Vergleiche der Performanz lokaler Anwendungen gegen globalen wechselseitigen Ausschluss und transaktionalen Speicher vorteilhaft zugunsten von FrameSweep ausfallen. Durch Migration einer bestehenden, mittels Reaktiver Programmierung implementierten Anwendung zu FrameSweep werden darüber hinaus die Behauptungen zu unveränderter Syntax und Semantik empirisch verifiziert.