Approximate Verteilte Überwachung unter Partial-Synchronität: Balance zwischen Geschwindigkeit und Genauigkeit

In verteilten Systemen mit Prozessen, die keine globale Uhr teilen, wird Partial-Synchronität durch Uhrensynchronisation erreicht, die eine begrenzte Uhrabweichung zwischen allen Anwendungen garantiert. Bestehende Lösungen für die verteilte Laufzeitüberprüfung unter Partial-Synchronität gegen temporale Logikspezifikationen sind exakt, leiden jedoch unter erheblichem Rechenaufwand. In diesem Papier schlagen wir einen approximativen Algorithmus zur verteilten Überwachung für Signal Temporale Logik (STL) vor, der dieses Problem mildert, indem er potenzielle Überlappungsverhalten abstrahiert. Diese konservative Abstraktion ermöglicht eine signifikante Beschleunigung der verteilten Monitore, wenngleich mit einem Kompromiss in der Genauigkeit. Wir gehen diesen Kompromiss mit einer Methodik an, die unseren approximativen Monitor mit seinem exakten Gegenstück kombiniert, was zu einer verbesserten Effizienz führt, ohne die Präzision zu opfern. Wir evaluieren unseren Ansatz mit mehreren Experimenten und zeigen seine Wirksamkeit sowohl in realen Anwendungen als auch in synthetischen Beispielen.