Verteilte Komplexität der stochastischen räumlichen Koordination

• Antragsteller: Professor Dr. Joel Rybicki
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 539576251

In diesem Projekt wird untersucht, was in stochastischen verteilten Systemen, die aus ressourcenbeschränkten Recheneinheiten bestehen, effizient berechnet werden kann. Insbesondere untersuchen wir die rechnerische Komplexität verschiedener verteilter Koordinationsprobleme und räumliche Dynamik, die beim Entwurf räumlich strukturierter, stochastischer, verteilter biologischer Systeme, wie z.B. mikrobieller Schaltkreise, auftreten. Zu diesem Zweck betrachten wir das sogenannte räumliche Populationsmodell, bei dem das System durch einen Interaktionsgraphen beschrieben wird, in dem jeder Knoten ein Individuum darstellt und die Kanten Paare von Individuen bezeichnen, die direkt miteinander interagieren können. In jedem Zeitschritt wählt ein stochastischer Scheduler zufällig ein Paar benachbarter Individuen aus, die miteinander interagieren und ihre internen Zustände aktualisieren. Bisher wurde die Komplexität der stochastischen Koordinationsprobleme in diesem Modell hauptsächlich für den speziellen Fall untersucht, dass der Interaktionsgraph eine Clique ist. Dies entspricht der Situation gut durchmischter chemischer Systeme, die dem Gesetz der Massenwirkungskinetik folgen: Die räumlichen Positionen der Individuen werden ignoriert und zwei beliebige Individuen haben die gleiche Wahrscheinlichkeit, direkt zu interagieren. Dies ist zwar eine plausible Annahme für die Modellierung molekularer Berechnungen in chemischen Reaktionsnetzwerken, doch die meisten biologischer Systeme sind nicht gut durchmischt, da sie eine starke räumliche Struktur aufweisen. In diesem Projekt gehen wir über gut durchmischte Systeme hinaus und entwickeln eine Theorie der Berechnungskomplexität in stochastischen, räumlich strukturierten Populationen. Im Rahmen des Projekts wird systematisch untersucht, wie die räumliche Struktur die Kompromisse bei der Komplexität der Lösung grundlegender verteilter Koordinationsprobleme beeinflusst. Insbesondere wollen wir erklären, welche Signalverstärkungs- und Symmetriebrechungsprobleme durch einfache, ressourceneffiziente Algorithmen schnell gelöst werden können und welche nicht.

• DFG-Verfahren: Sachbeihilfen