Globale Synchronisationsprotokolle und der Beweis ihrer Korrektheit (GSP&Co)

• Antragsteller: Privatdozent Dr.-Ing. Swen Jacobs
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 497132954

In diesem Projekt wollen wir Globale Synchronisationsprotokolle (GSPs) als ein neues Rechenmodell for nebenläufige Systeme mit einer parametrischen Anzahl von Komponenten einführen. Zusätzlich zu lokalen Updates einer Komponente unterstützen GSPs synchrone globale Updates des Systems, die mittels Bedingungen an den globalen Zustand des Systems beschränkt sein können. Mit dieser Kombination eignen sie sich zur Modellierung von Anwendungen, die auf globaler Synchronisation, z.B. mittels Consensus oder Leader Election, basieren - auf einem Abstraktionslevel der die interne Implementierung des Übereinstimmungsprotokolls verbirgt, aber seine Vor- und Nachbedingungen originalgetreu abbildet.Wir werden Bedingungen identifizieren, unter denen parametrierte Sicherheitsverifikation von GSPs entscheidbar bleibt, obwohl dieses Problem im Allgemeinen für die Kombination der in GSPs unterstützten Kommunikationsprimitive unentscheidbar ist. Eine vorläufige Version der GSPs unterstützt bereits globale Synchronisation und globale Transitionsbedingungen, und wir planen eine Erweiterung des Systemmodells um asynchrone Nachrichtenübermittlung sowie verschiedene Arten der Fehlerbehandlung, so dass die Entscheidbarkeit der parametrierten Verifikation erhalten bleibt.Weiterhin werden wir Bedigungen für kleine Cutoffs für die Sicherheitsverifikation identifizieren, d.h. kleine Schranken auf die Anzahl der Komponenten, die in Betracht gezogen werden müssen um parametrische Sicherheitsgarantien zu bestimmen. Basierend auf diesen Cutoffs werden wir auch einen Ansatz zur automatischen Synthese von GSPs entwickeln, die gegebene Eigenschaften per Konstruktion erfüllen. Zuletzt werden wir auch einen verfeinerungs-basierten Syntheseansatz für GSPs untersuchen, und seine Eigenschaften mit dem Cutoff-basierten Ansatz vergleichen.Unsere Erforschung entscheidbarer Fragmente von GSPs wird geleitet von Anwendungen in verschiedenen Bereichen, darunter Sensornetzwerke, Roboterschwärme und auf Blockchains basierende Anwendungen.

• DFG-Verfahren: Sachbeihilfen