Global Optimization Algorithms and their Application to Distributed Systems

In this report, we discuss the application of global optimization and Evolutionary Computation to distributed systems. We therefore selected and classified many publications, giving an insight into the wide variety of optimization problems which arise in distributed systems. Some interesting approaches from different areas will be discussed in greater detail with the use of illustrative examples.

Autonomes Performance-Management in dienstorientierten Architekturen

Die Bedeutung des Dienstgüte-Managements (SLM) im Bereich von Unternehmensanwendungen steigt mit der zunehmenden Kritikalität von IT-gestützten Prozessen für den Erfolg einzelner Unternehmen. Traditionell werden zur Implementierung eines wirksamen SLMs Monitoringprozesse in hierarchischen Managementumgebungen etabliert, die einen Administrator bei der notwendigen Rekonfiguration von Systemen unterstützen. Auf aktuelle, hochdynamische Softwarearchitekturen sind diese hierarchischen Ansätze jedoch nur sehr eingeschränkt anwendbar. Ein Beispiel dafür sind dienstorientierte Architekturen (SOA), bei denen die Geschäftsfunktionalität durch das Zusammenspiel einzelner, voneinander unabhängiger Dienste auf Basis deskriptiver Workflow-Beschreibungen modelliert wird. Dadurch ergibt sich eine hohe Laufzeitdynamik der gesamten Architektur. Für das SLM ist insbesondere die dezentrale Struktur einer SOA mit unterschiedlichen administrativen Zuständigkeiten für einzelne Teilsysteme problematisch, da regelnde Eingriffe zum einen durch die Kapselung der Implementierung einzelner Dienste und zum anderen durch das Fehlen einer zentralen Kontrollinstanz nur sehr eingeschränkt möglich sind. Die vorliegende Arbeit definiert die Architektur eines SLM-Systems für SOA-Umgebungen, in dem autonome Management-Komponenten kooperieren, um übergeordnete Dienstgüteziele zu erfüllen: Mithilfe von Selbst-Management-Technologien wird zunächst eine Automatisierung des Dienstgüte-Managements auf Ebene einzelner Dienste erreicht. Die autonomen Management-Komponenten dieser Dienste können dann mithilfe von Selbstorganisationsmechanismen übergreifende Ziele zur Optimierung von Dienstgüteverhalten und Ressourcennutzung verfolgen. Für das SLM auf Ebene von SOA Workflows müssen temporär dienstübergreifende Kooperationen zur Erfüllung von Dienstgüteanforderungen etabliert werden, die sich damit auch über mehrere administrative Domänen erstrecken können. Eine solche zeitlich begrenzte Kooperation autonomer Teilsysteme kann sinnvoll nur dezentral erfolgen, da die jeweiligen Kooperationspartner im Vorfeld nicht bekannt sind und – je nach Lebensdauer einzelner Workflows – zur Laufzeit beteiligte Komponenten ausgetauscht werden können. In der Arbeit wird ein Verfahren zur Koordination autonomer Management-Komponenten mit dem Ziel der Optimierung von Antwortzeiten auf Workflow-Ebene entwickelt: Management-Komponenten können durch Übertragung von Antwortzeitanteilen untereinander ihre individuellen Ziele straffen oder lockern, ohne dass das Gesamtantwortzeitziel dadurch verändert wird. Die Übertragung von Antwortzeitanteilen wird mithilfe eines Auktionsverfahrens realisiert. Technische Grundlage der Kooperation bildet ein Gruppenkommunikationsmechanismus. Weiterhin werden in Bezug auf die Nutzung geteilter, virtualisierter Ressourcen konkurrierende Dienste entsprechend geschäftlicher Ziele priorisiert. Im Rahmen der praktischen Umsetzung wird die Realisierung zentraler Architekturelemente und der entwickelten Verfahren zur Selbstorganisation beispielhaft für das SLM konkreter Komponenten vorgestellt. Zur Untersuchung der Management-Kooperation in größeren Szenarien wird ein hybrider Simulationsansatz verwendet. Im Rahmen der Evaluation werden Untersuchungen zur Skalierbarkeit des Ansatzes durchgeführt. Schwerpunkt ist hierbei die Betrachtung eines Systems aus kooperierenden Management-Komponenten, insbesondere im Hinblick auf den Kommunikationsaufwand. Die Evaluation zeigt, dass ein dienstübergreifendes, autonomes Performance-Management in SOA-Umgebungen möglich ist. Die Ergebnisse legen nahe, dass der entwickelte Ansatz auch in großen Umgebungen erfolgreich angewendet werden kann.

Einfluss der Flächenwahl, Anbaudichte und Landschaftsstruktur auf den Befallsstatus und die Ausbreitung der Möhrenfliege Psila rosae F. (Diptera: Psilidae) im ökologischen Möhrenanbau

Durch die vermehrte Nachfrage von Biomöhren im Lebensmitteleinzelhandel ist die Anbaufläche ökologisch erzeugter Möhren in den letzten zehn Jahren deutlich angestiegen. Der Anbau konzentriert sich auf bestimmte Regionen und erfolgte damit zunehmend auf großen Schlägen in enger räumlicher und zeitlicher Abfolge. Mit der steigenden Wirtspflanzenpräsenz steigt auch der Befallsdruck durch die Möhrenfliege. Während der Schädling im konventionellen Anbau mit Insektiziden kontrolliert wird, stehen dem Ökologischen Landbau bisher keine direkten Regulative zur Verfügung. Ziel der Untersuchungen war es, unter den Praxisbedingungen des ökologischen Möhrenanbaus einzelbetriebliche und überregionale Muster beteiligter Risikofaktoren im Befallsgeschehen zu identifizieren und so Möglichkeiten einer verbesserten Prävention und Regulation aufzuzeigen. Über einen Zeitraum von drei Jahren wurden auf fünf Betrieben in Niedersachsen und Hessen umfangreiche Felddaten erhoben und diese unter Verwendung von GIS – Software und dem Simulationsmodell SWAT analysiert. Untersuchte Einflussgrößen umfassten (1) die Distanz zu vorjährigen Möhrenfeldern, (2) die zeitliche Möhrenanbauperiode, (3) Vegetationselemente und (4) der experimentelle Einsatz von Fangpflanzen zur Unterdrückung der Fliegenentwicklung. Unter der Berücksichtigung deutlicher einzelbetrieblicher Unterschiede sind die wichtigsten Ergebnisse der Studie wie folgt zu benennen: (1) Auf Betrieben mit Befall im zurückliegenden Anbaujahr zeigte sich die Distanz zu vorjährigen Möhrenfeldern als der wichtigste Risikofaktor. Das Ausbreitungsverhalten der 1. Generation Möhrenfliege erwies sich zudem als situationsgebunden anpassungsfähig. Fliegensumme und Befall waren jeweils in dem zu Vorjahresflächen nächstgelegen Feld am größten, während jeweils dahinter liegende Möhrenschläge entsprechend weniger Fliegenzahlen und Befall auswiesen. Aus den Ergebnissen wird als vorrangige Verbreitungskapazität der 1. Generation Möhrenfliegen innerhalb von 1000 m abgeleitet. (2) Betriebe mit kontinuierlicher Möhren - Anbaubauperiode (ca. April – Oktober), die langfristig die Entwicklung sowohl der 1. als auch der 2. Generation Fliegen unterstützten, verzeichneten stärkere Fliegenprobleme. Hinsichtlich einer verbesserten Prävention wird empfohlen mit einer strikten räumlichen Trennung früher und später Sätze ein Aufschaukeln zwischen den Generationen zu vermeiden. (3) Der Einfluss der Vegetation ließ sich weniger eindeutig interpretieren. Einzelbetriebliche Hinweise, dass Kleingehölze (Hecken und Bäume) im Radius zwischen aktueller und vorjähriger Möhrenfläche die Befallswahrscheinlichkeit erhöhen, konnten mit einem berechneten Gesamtmaß für die regionale holzige Vegetation nicht bestätigt werden. Der großräumigen holzigen Vegetation wird im Vergleich zur Feldrandvegetation daher beim Befallsgeschehen eine geringe Bedeutung zugeschrieben. (4) Drei Meter (vier Dämme) breiter Möhren – Fangstreifen auf den vorjährigen Möhrenfeldern eignen sich bereits ab dem Keimblattstadium, um erhebliches Befallspotential zu binden. Eine mechanische Entfernung der Fangpflanzen (Grubbern) mitsamt dem Befallspotential erzielte in 2008 eine 100 %-ige Unterdrückung der Möhrenfliegenentwicklung, in 2009 jedoch nur zu maximal 41 %. Als mögliche Synthese der Ergebnisse zur Ausbreitung der Möhrenfliegen im Frühjahr und zur zeitlichen Koinzidenz mit der Möhrenentwicklung wird als Empfehlung diskutiert, mit Hilfe einer angepassten Flächenwahl die Fliegenausbreitung räumlich an frühen Sätzen zu binden, um entsprechend befallsarme Regionen für entfernt liegende späte (empfindlichere) Möhrensätze zu schaffen.

Simulative Risikoanalyse von Biomethanprojekten

Im Zuge der Novellierung der Gasnetzzugangsverordnung sowie des Erneuerbare-Energien-Gesetzes entwickelte sich die Einspeisung von Biomethan in das Erdgasnetz als alternative Investitionsmöglichkeit der Erneuerbare-Energien-Branche. Als problematisch erweist sich dabei die Identifikation und Strukturierung einzelner Risikofaktoren zu einem Risikobereich, sowie die anschließende Quantifizierung dieser Risikofaktoren innerhalb eines Risikoportfolios. Darüber hinaus besteht die Schwierigkeit, diese Risikofaktoren in einem cashflowbasierten und den Ansprüchen der Investoren gewachsenem Risikomodell abzubilden. Zusätzlich müssen dabei Wechselwirkungen zwischen einzelnen Risikofaktoren berücksichtigt werden. Aus diesem Grund verfolgt die Dissertation das Ziel, die Risikosituation eines Biomethanprojektes anhand aggregierter und isolierter Risikosimulationen zu analysieren. Im Rahmen einer Diskussion werden Strategien und Instrumente zur Risikosteuerung angesprochen sowie die Implementierungsfähigkeit des Risikomodells in das Risikomanagementsystem von Investoren. Die Risikomaße zur Beschreibung der Risikoauswirkung betrachten die Shortfälle einer Verteilung. Dabei beziehen sich diese auf die geplanten Ausschüttungen sowie interne Verzinsungsansprüche der Investoren und die von Kreditinstituten geforderte minimale Schuldendienstdeckungsrate. Im Hinblick auf die Risikotragfähigkeit werden liquiditätsorientierte Kennzahlen hinzugezogen. Investoren interessieren sich vor dem Hintergrund einer gezielten Risikosteuerung hauptsächlich für den gefahrvollsten Risikobereich und innerhalb dessen für den Risikofaktor, der die größten Risikoauswirkungen hervorruft. Zudem spielt der Zeitpunkt maximaler Risikoauswirkung eine große Rolle. Als Kernaussage dieser Arbeit wird festgestellt, dass in den meisten Fällen die Aussagefähigkeit aggregierter Risikosimulationen durch Überlagerungseffekte negativ beeinträchtigt wird. Erst durch isoliert durchgeführte Risikoanalysen können diese Effekte eliminiert werden. Besonders auffällig gestalten sich dabei die Ergebnisse der isoliert durchgeführten Risikoanalyse des Risikobereichs »Politik«. So verursacht dieser im Vergleich zu den übrigen Risikobereichen, wie »Infrastruktur«, »Rohstoffe«, »Absatzmarkt« und »Finanzmarkt«, die geringsten Wahrscheinlichkeiten avisierte Planwerte der Investoren zu unterschreiten. Kommt es jedoch zu einer solchen Planwert-Unterschreitung, nehmen die damit verbundenen Risikoauswirkungen eine überraschende Position im Risikoranking der Investoren ein. Hinsichtlich der Aussagefähigkeit des Risikomodells wird deutlich, dass spezifische Risikosichtweisen der Investoren ausschlaggebend dafür sind, welche Strategien und Instrumente zur Risikosenkung umgesetzt werden. Darüber hinaus wird festgestellt, dass die Grenzen des Risikomodells in der Validität der Expertenmeinungen und dem Auffinden einer Optimallösung zu suchen sind.

Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.