Humboldt-Universität zu BerlinMathematisch-Naturwissenschaftliche FakultätInstitut für Informatik

Verifikation eines zertifizierenden verteiltenAlgorithmus

Diplomarbeit

zur Erlangung des akademischen GradesDiplominformatiker (Dipl.-Inf.)

eingereicht von: David Asher

Gutachter: Prof. Dr. Wolfgang ReisigProf. Dr. Lars Grunske

eingereicht am: verteidigt am:

Inhaltsverzeichnis

1. Einleitung 5

2. Grundlagen 72.1. Zertifizierende Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.1. Zeugenprädikat und Zeugeneigenschaft . . . . . . . . . . . . . . 82.1.2. Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2. Verifikation zertifizierender Algorithmen . . . . . . . . . . . . . . . . . 112.2.1. Maschinelles Beweisen . . . . . . . . . . . . . . . . . . . . . . . 112.2.2. Formale Instanzkorrektheit . . . . . . . . . . . . . . . . . . . . . 12

2.3. Verteilte Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3.1. Rechenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3.2. Verteilter Bellman-Ford-Algorithmus . . . . . . . . . . . . . . . 14

2.4. Zertifizierende verteile Algorithmen . . . . . . . . . . . . . . . . . . . . 142.4.1. Lokaler Ansatz . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5. Theorembeweiser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.5.1. Interaktive Theorembeweiser . . . . . . . . . . . . . . . . . . . . 162.5.2. Beweisüberprüfung . . . . . . . . . . . . . . . . . . . . . . . . . 162.5.3. Coq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3. Methode 193.1. Überprüfung einer Kürzesten-Wege-Funktion . . . . . . . . . . . . . . . 19

3.1.1. Zeugeneigenschaft . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2. Der zertifizierende verteilte Bellman-Ford-Algorithmus . . . . . . . . . 21

3.2.1. I/O-Verhalten . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2.2. Die Zeugeneigenschaft in der verteilten Umgebung . . . . . . . . 23

3.3. Beweisverpflichtungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4. Überblick über den Beweisassistenten Coq 254.1. Funktionales Programmieren in Coq . . . . . . . . . . . . . . . . . . . . 25

4.1.1. Universen in Coq . . . . . . . . . . . . . . . . . . . . . . . . . . 264.2. Beweise als Objekte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.2.1. BHK-Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . 284.2.2. Curry-Howard-Isomorphismus . . . . . . . . . . . . . . . . . . . 29

4.3. Grundlegende Taktiken . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.3.1. Natürliches Schließen . . . . . . . . . . . . . . . . . . . . . . . . 304.3.2. Beweisautomatisierung . . . . . . . . . . . . . . . . . . . . . . . 32

3

4.4. Induktive Typdefinitionen . . . . . . . . . . . . . . . . . . . . . . . . . 344.4.1. Aufzählungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.4.2. Rekursive Definitionen . . . . . . . . . . . . . . . . . . . . . . . 344.4.3. Induktive Prädikate . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.5. Taktiken für induktive Typen . . . . . . . . . . . . . . . . . . . . . . . 364.5.1. Beweis durch Induktion . . . . . . . . . . . . . . . . . . . . . . 364.5.2. Beweis durch Fallunterscheidung . . . . . . . . . . . . . . . . . 36

4.6. Weitere Typen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.6.1. Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.6.2. Sigma-Typen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.7. Variablen und Sections . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5. Beweis der Zeugeneigenschaft in Coq 415.1. Formalisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.1.1. Gewichteter Graph . . . . . . . . . . . . . . . . . . . . . . . . . 415.1.2. Pfade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.1.3. Kürzeste-Pfade-Funktion delta . . . . . . . . . . . . . . . . . . 44

5.2. Beweis der Zeugeneigenschaft . . . . . . . . . . . . . . . . . . . . . . . 475.2.1. Lemma shortest_path_opt_substr . . . . . . . . . . . . . . . . 475.2.2. Lemma dist_leq_delta . . . . . . . . . . . . . . . . . . . . . . . 495.2.3. Lemma dist_geq_delta . . . . . . . . . . . . . . . . . . . . . . . 505.2.4. Theorem dist_eq_delta . . . . . . . . . . . . . . . . . . . . . . 50

5.3. Hilfslemmata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.3.1. Lemma shortest_path_existence . . . . . . . . . . . . . . . . . 515.3.2. Lemma arg_min_inequality . . . . . . . . . . . . . . . . . . . . 53

6. Beweis der globalen Zeugeneigenschaft in Coq 556.1. Formalisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

6.1.1. Lokale Eingabe einer Komponente . . . . . . . . . . . . . . . . . 556.1.2. Lokale Ausgabe einer Komponente . . . . . . . . . . . . . . . . 566.1.3. Lokales Zeugenprädikat . . . . . . . . . . . . . . . . . . . . . . 566.1.4. Der Netzwerkgraph . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.2. Beweis der globalen Zeugeneigenschaft . . . . . . . . . . . . . . . . . . 576.2.1. Hypothesen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586.2.2. Theorem dist_eq_network_delta . . . . . . . . . . . . . . . . . 58

7. Diskussion 61

A. Coq-Beweise 67

4

1. Einleitung

Eine herausfordernde Aufgabe des Software Engineering ist es die Korrektheit einesProgramms sicherzustellen. Bekannte Methoden sind das Testen und die formaleVerifikation. Beim Testen wird für eine Stichprobe der möglichen Eingaben einesProgramms gezeigt, dass es korrekt ist. Schwierig ist es hierbei eine möglichst reprä-sentative Stichprobe zu wählen. Für alle Eingaben außerhalb der Stichprobe erhaltenwir keine Korrektheitsgarantie. Eine stärkere Korrektheitsgarantie erhalten wir beider formalen Verifikation. Verifizieren wir ein Programm, so beweisen wir, dass esfür alle Eingaben korrekt ist. Die formale Verifikation eines Programms ist jedochoft zu aufwändig oder sogar unmöglich. Zum einen müssen wir die Korrektheit desAlgorithmus zeigen, zum anderen müssen wir zeigen, dass er korrekt implementiertist. Vor allem der Beweis der Korrektheit der Implementierung ist oft praktisch nichtdurchführbar.

Mehlhorn et. al. [MMNS11] schlagen das Konzept des zertifizierenden Algorithmus alsweiteren Ansatz zur Qualitätssicherung von Software vor. Ein zertifizierender Algorith-mus berechnet zu jedem Ergebnis, ein einfach zu überprüfendes Zertifikat, welches dieKorrektheit des Ergebnisses impliziert. Der Benutzer eines zertifizierenden Algorithmus,kann sich anhand des Zertifikats von der Korrektheit des Ergebnisses überzeugen. DieZertifikatsüberprüfung kann durch einen Entscheidungsalgorithmus – dem Checker erfol-gen. Auf diese Weise kann der Benutzer Gewissheit über die Korrektheit des Ergebnisseserlangen, ohne dem Algorithmus vertrauen zu müssen.

Rizkallah [Riz15] entwickelt aufbauend auf dem Konzept des zertifizierenden Algo-rithmus, den Begriff der formalen Instanzkorrektheit. Die Idee ist es die Aussage „derChecker akzeptiert ein Zertifikat für ein Ergebnis genau dann, wenn das Ergebniskorrekt ist“ mit Methoden der formalen Verifikation zu belegen. Der formale Beweiseder Aussage erfolgt über zwei Schritte: Als erstes wird bewiesen, dass Zertifikate immerdie Korrektheit eines Ergebnisses implizieren. Der nächste Schritt bildet der Korrekt-heitsbeweis der Checker-Implementation. Die Korrektheit des Ergebnisses ist damit– bei Akzeptanz des Checkers – durch einen maschinenüberprüfbaren Beweis abgesi-chert und so vertrauenswürdig, als wäre die Berechnung von einen formal verifiziertenAlgorithmus erfolgt.

Aufgrund ihres komplexen Verhaltens, ist der Beweis der Korrektheit verteilter Al-gorithmen, wesentlich herausfordernder als der von sequentiellen Algorithmen. ImRahmen ihrer Doktorarbeit überträgt Völlinger das Konzept des zertifizierenden Al-gorithmus auf verteilte Algorithmen. In [VR15] wird beschrieben, wie ein verteilter

5

Netzwerkalgorithmus zur Berechnung kürzester Pfade, zertifizierend gestaltet werdenkann. Jede Komponente des Netzwerks berechnet ein lokales Zertifikat, sodass allelokalen Zertifikate zusammen die Korrektheit des verteilten Ergebnisses belegen. DieÜberprüfung des verteilten Ergebnisses, erfolgt ebenfalls verteilt durch lokale Checker,welche jeder Komponente zugewiesen werden. Das verteilte Ergebnis ist genau dannkorrekt, wenn alle lokalen Checker akzeptieren. Völlinger bezeichnet dieses Vorgehenals den lokalen Ansatz.

Ziel der Arbeit

Das Ziel dieser Arbeit ist es, unter Verwendung des lokalen Ansatzes, einen lokalenChecker-Algorithmus zu entwickeln, welcher die verteilte Überprüfung des verteilten Er-gebnisses von einem Netzwerkalgorithmus zur Berechnung kürzester Pfade übernimmt.Weiterhin soll unter Einsatz des Beweisassistenten Coq, die formale Instanzkorrektheitder verteilten Überprüfung bewiesen werden. Auch hier soll der Nachweis über zweiSchritte erfolgen: Als erstes soll in Coq bewiesen werden, dass alle lokalen Zertifika-te zusammen das korrekte verteilte Ergebnis belegen. Der nächste Schritt setzt sichaus der Implementation und dem Korrektheitsbeweis des lokalen Checker-Programmszusammen.

Aufbau der Arbeit

Bevor wir unsere Umsetzung darlegen, vermitteln wir in Kapitel 2 die notwendigenGrundlagen. Dort führen wir die Begriffe zertifizierender Algorithmus und verteilterAlgorithmus ein. Weiterhin gehen wir kurz auf formale Verifikation mit Beweisassisten-ten ein. In Kapitel 3 geben wir eine Definition des lokalen Ansatzes auf dem unsereUmsetzung basiert. Darauf folgt in Kapitel 4 ein Überblick über den BeweisassistentenCoq. Der Überblick enthält alle für das Verständnis der Umsetzung erforderlichenSpezifika von Coq. Schließlich erläutern wir in Kapitel 5 und Kapitel 6 ausführlichunsere Umsetzung in Coq. Der Abschluss bildet Kapitel 7, in dem wir die Ergebnissezusammenfassen und diskutieren, wie auf die gewonnen Ergebnisse aufgebaut werdenkann.

6

2. Grundlagen

Ziel dieser Arbeit ist es einen verteilten zertifizierenden Algorithmus zu verifizieren.In diesem Kapitel vermitteln wir die dazu nötigen Begriffe. Als erstes führen wirAbschnitt 2.1 den Begriff des zertifizierenden Algorithmus. In Abschnitt 2.2 gehenwir darauf ein, wie zertifizierende Algorithmen verifiziert werden können. Der zentra-le Begriff des Abschnitts bildet die formalen Instanzkorrektheit. Abschnitt 2.3 legtdie Klasse der verteilten Algorithmen dar, auf die wir uns beschränken. Abschnitt2.4 geht auf Fragestellungen ein, wie sie sich im Kontext der Erweiterung des zerti-fizierenden Algorithmen auf verteilte Algorithmen ergeben. Schließlich geben wir inAbschnitt 2.5 einen Überblick über Beweisassistenten im Allgemeinen und Coq imbesonderen.

2.1. Zertifizierende Algorithmen

Ein zertifizierender Algorithmus [MMNS11] gibt für jedes Ergebnis ein Zertifikat bezie-hungsweise Zeugen aus. Dabei handelt es sich um ein mathematisches Artefakt, das dieKorrektheit des Ergebnisses belegt. Ein Zertifikat hängt dabei von der Eingabe und derAusgabe ab. Beispielsweise gibt ein zertifizierender Entscheidungsalgorithmus für Bipar-titheit eines Graphen einen ungeraden Kreis als Zeuge dafür aus, dass ein Graph nichtbipartit und eine 2-Färbung als Zeuge für dessen Bipartitheit. Die Eigenschaft, dass einZeuge die korrekte Berechnung impliziert heißt Zeugeneigenschaft.

Wie kann ein sich ein Benutzer eines zertifizierenden Algorithmus davon überzeugt,dass eine Ergebnis korrekt ist? Dazu muss er zwei Aufgaben lösen:

1. Er muss die Zeugeneigenschaft verstehen und

2. Er muss überprüfen ob der Zeuge korrekt ist.

Betrachten wir die beiden Aufgaben, des Benutzers am Beispiel des zertifizierendenEntscheidungsalgorithmus zur Bipartitheit. Wir unterscheiden hierfür die beiden Fälleeines nicht bipartiten und eines bipartiten Graphen. Im Falle eines nicht bipartitenGraphen, muss der Benutzer (1) die Zeugeneigenschaft verstehen: ein ungerader KreisT als Teilgraph eines Graphen G impliziert, dass G nicht bipartit ist. Er überprüft,dass der Zeuge korrekt ist (2), indem er zum einen überprüft, ob T ein ungerader Kreisist und zum anderen, ob T ein Teilgraph von G ist.

7

Im Falle eines bipartiten Graphen, muss der Benutzer verstehen (1), dass die eine2-Färbung für einen Graphen G, dessen Bipartitheit impliziert. Weiterhin muss erverifizieren (2), dass die 2-Färbung korrekt ist, also es keine Kante in G gibt, die Knotengleicher Farbe des gefärbten Graphen verbindet.

Die beiden Eigenschaften sind hinreichend um den Benutzer von der Korrektheit einesErgebnisses zu überzeugen. Insbesondere muss der Benutzer nicht verstehen, warum imjeden Fall ein Zeuge existiert, das Verständnis der Zeugeneigenschaft ist ausreichend.Auf den zertifizierenden Entscheidungsalgorithmus für Bipartitheit bezogen, muss derBenutzer beispielsweise nicht verstehen, warum ein nicht-bipartiter Graph immer einenungeraden Kreis hat. Das ist nur für den Entwickler des zertifizierenden Algorithmus vonBedeutung. Er muss sicherstellen, dass für jedes Ergebnis ein passender Zeuge berechnetwird. Die Herausforderung bei der Entwicklung eines zertifizierenden Algorithmus istes, Zeugen zu finden, die eine einfache Zeugeneigenschaft haben und sich leicht auf ihreKorrektheit überprüfen lassen. Die Idee hierbei ist, dass die Prüfung einfacher ist alsdie Konstruktion.

Der Begriff des zertifizierenden Algorithmus wurde als erstes in [KMMS03] einge-führt. Eine Einführung und eine Sammlung zertifizierender Algorithmen für bekannteProbleme findet sich in [MMNS11]. Weitere zertifizierende Algorithmen werden bei-spielsweise in [KN09] und [McC04] beschrieben. Praktisch eingesetzt werden sie inder LEDA-Projekt [NM90, MN95], welche eine Sammlung in C++ implementierterkombinatorischer und geometrischer Algorithmen enthält.

2.1.1. Zeugenprädikat und Zeugeneigenschaft

Um näher auf zertifizierender Algorithmen eingehen zu können, machen wir zunächsteinige Definitionen. Das gewünschte I/O-Verhalten eines Algorithmus lässt sich formalmittels zweier Prädikate angeben. Sei dafür die Menge X die Menge aller Eingabenund Y die Menge aller Ausgaben eines Algorithmus. Ein Algorithmus heißt korrekt,wenn er für jedes x ∈ X, welches die Vorbedingung ϕ(x) erfüllt, mit einer Ausgabey ∈ Y hält mit der die Nachbedingung ψ(x, y) gilt.

SeiW die Menge aller Zeugen, dann heißt ein PrädikatW ⊆ X×Y ×W Zeugenprädikat,wenn es die Zeugeneigenschaft erfüllt. Das heißt für alle x ∈ X, y ∈ Y und w ∈ Wgilt:

ϕ(x) ∧W(x, y, w)→ ψ(x, y).

8

Abbildung 2.1.: Eine Implementierung eines zertifizierendes Algorithmus für eine Funk-tion f (vgl. [MMNS11]).

2.1.2. Checker

Es ist möglich einen zertifizierenden Algorithmus um einen zusätzliche Algorith-mus – dem Checker zu erweitern, welcher die Überprüfung des Zertifikats automati-siert. Genaugenomen ist der Checker ein Entscheidungsalgorithmus für Zeugenprädi-kat.

Wenn Zeugen der Anforderung der Einfachheit genügen, liegen die Vorteile auf derHand: Der Checker-Algorithmus ist einfach und lässt sich als zuverlässige Komponenteintegrieren. Ein Checker ist im Idealfall so einfach, dass er sich formal verifizieren lässt.Dies ist wesentlich einfacher als die Korrektheit einer Implementierung zu verifizie-ren.

Abbildung 2.1 veranschaulicht das Konzept eines zertifizierenden Programms inklusivedes Checker-Programms. Ein zertifizierendes Programm ist ein implementierter zertifi-zierender Algorithmus. Der obere Teil der Abbildung zeigt Programm, das eine Funktionf berechnet. Für eine Eingabe x wird eine Ausgabe y berechnet. Für den Benutzerbleibt offen, ob tatsächlich y = f(x). Im unteren Teil ist eine zertifizierende Variantedesselben Programms dargestellt; Es gibt zusätzlich zur Ausgabe y ein Zertifikat waus. Der Checker nimmt Werte für x, y und w entgegen und akzeptiert, falls w für xund y korrekt ist. Durch die Zeugeneigenschaft von w gilt nun f(x) = y. Lehnt derChecker ab, dann ist entweder w nicht korrekt für x und y oder y ist nicht korrekteAusgabe für x.

Beispiel: Größter gemeinsamer Teiler

Wir demonstrieren die eingeführten Definition am Beispiel [MMNS11, Riz15] deszertifizierenden euklidischen Algorithmus, der den größten gemeinsamen Teiler zweier

9

Zahlen berechnet.

Das Problem den größten Gemeinsamen Teiler zweier Zahlen zu finden, kann mit demerweiterten euklidischen Algorithmus zertifizierende gestaltet werden. Der erweiterteeuklidische Algorithmus gibt zusätzlich zum größtem gemeinsamen Teiler g zwei ganzeZahlen s und t aus, sodass g = s · a+ t · b. Diese beiden Zahlen bilden einen Zeugen,denn es gilt folgende Zeugeneigenschaft:

Zeugeneigenschaft. Seien a und b zwei nichtnegative ganze Zahlen, welche nichtbeide Null sind . Weiterhin seien s und t zwei ganze Zahlen, so dass

g = s · a+ t · b (1)g teilt sowohl a als auch b (2)

Dann ist g = ggT (a, b).

Beweis. Sei d ein beliebiger Teiler von a und b, dann ist g = (s · (a/d) + t · (b/d)) · d.Also ist d auch ein Teiler von g. Insbesondere muss also auch ggT (a, b) g teilen. Damitist ggT (a, b) ≤ g. Da nach Voraussetzung g a und b teilt, muss g auch ggT (a, b) teilen.Damit ist g ≤ ggT (a, b). Zusammen ist also g = ggT (a, b).

Auf das Beispiel des erweiterten euklidischen Algorithmus bezogen, sindX = W = Z×Zund Y = Z. Die Vorbedingung ϕ((a, b)) besagt, dass beide Zahlen positiv sind undeine der beiden Zahlen verschieden von Null. Die Nachbedingung ψ((a, b), g) sagt aus,dass g tatsächlich der größte gemeinsame Teiler von a und b ist. Das ZeugenprädikatW((a, b), g, (s, t)) ist genau dann erfüllt, wenn g = s · a+ t · b und g sowohl a als auchb teilt. Formal lassen sich ϕ, ψ und W spezifizieren als:

• ϕ((a, b)) := 0 ≤ a ∧ 0 ≤ b ∧ 0 < a+ b

• ψ((a, b), g) := ∀d ∈ Z, d | a ∧ d | b→ d ≤ g

• W((a, b), g, (s, t)) := g | s ∧ g | t ∧ g = s · a+ t · b

Der Checker des zertifizierenden euklidischen Algorithmus muss überprüfen, ob a undb durch g teilbar sind und ob tatsächlich g = s · a+ t · b ist. Akzeptiert der Checker,dann garantiert die Zeugeneigenschaft, dass g der größte gemeinsame Teiler für a undb ist.

10

2.2. Verifikation zertifizierender Algorithmen

Wir haben erläutert wie sich ein Benutzer von der Korrektheit eines Ergebnisses überzeu-gen kann, indem er die Zeugeneigenschaft versteht (1) und überprüft ob der berechneteZeuge Korrekt für die konkrete Eingabe und Ausgabe ist (2).

In diesem Unterkapitel gehen wir darauf ein, inwieweit dem Benutzer mit Methoden derformalen Verifikation den beiden Bedingungen geholfen werden kann. Die Überprüfungdes Zeugen kann dem Benutzer durch einen einen formal verifizierten Checker abgenom-men werden. Dadurch muss er nur dem maschinell geprüften Beweis der Korrektheitder Implementation des Checkers vertrauen. Doch auch die erste Bedingung kanndem Benutzer mit Methoden der formalen Verifikation abgenommen werden. Dazustellen wir dem Benutzer zusätzlich einen maschinellen Beweis der Zeugeneigenschaftzur Verfügung.

Zusammen beweisen damit zertifizierenden Algorithmen die Korrektheit einer Berech-nung durch einen formalen Beweis. Diese Eigenschaft nennen wir formale Instanzkor-rektheit [Riz15]. Der Benutzer muss lediglich den folgenden Werkzeugen vertrauen: demBeweisprüfer, der eingesetzt wurde um den Beweis der Zeugeneigenschaft zu prüfen undden Werkzeugen, welche eingesetzt wurden um die Korrektheit des Checker-Programmszu zeigen.

2.2.1. Maschinelles Beweisen

Maschinelle Beweise können mittels deduktiver Verifikation erstellt werden. Dazuwerden aus der Spezifikation eines Programms eine Reihe von Beweisverpflichtun-gen formuliert. Diese werden dann in einem mathematischen Kalkül bestehend ausAxiomen und Ableitungsregeln unter Zuhilfenahme von Spezialsoftware hergeleitet.Um einen maschinellen Korrektheitsbeweis für ein Computerprogramm zu führen, istes notwendig, dass dieses in einer Programmiersprache mit vollständig spezifizierterSemantik implementiert werden. Damit können in einem Kalkül Aussagen über dieTerminierung und des I/O-Verhalten von einem Programm formuliert und hergeleitetwerden. In diesem Unterkapitel gehen wir von der Existenz eines Kalküls aus, dasgenügend ausdrucksstark ist mathematische Wahrheiten auszudrücken (zum BeispielAussagen über ganze Zahlen und größte gemeinsame Teiler) und Aussagen über dieTerminierung und Ausgabe eines Programms herleitbar sind. Beispielsweise schreibenwir

pϕ(x)→ P (x) ↓ yq

11

um auszudrücken, dass Programm P mit der Ausgabe y hält, wenn die Eingabe ϕerfüllt. Wir setzen dabei eine Aussagen in Klammern der Form pq um zu verdeutlichen,dass sie im Kalkül formuliert ist.

2.2.2. Formale Instanzkorrektheit

Die Zeugeneigenschaft garantiert, dass ein Zeuge w für eine Ausgabe y und eine Eingabex die Nachbedingung erfüllt, falls x die Vorbedingung erfüllt. Damit ergibt sich folgendeBeweisverpflichtung für die Zeugeneigenschaft:

1. p∀x∀y∀w.ϕ(x) ∧W(x, y, w)→ ψ(x, y)q

Die Aufgabe des Checkers ist es anhand des Tripels (x, y, w) zu entscheiden, ob das Zeu-genprädikat W(x, y, w) erfüllt ist. Wir fordern die korrekte Ausführung des Checkersdabei nur, wenn eine Eingabe x die Vorbedingung ϕ(x) erfüllt. Falls die Vorbedingungnicht erfüllt ist, darf der Checker alles machen, insbesondere nicht terminieren odermit einer beliebigen Ausgabe anhalten. Das heißt es ergeben sich folgende Beweisver-pflichtungen für die Verifikation des Checkers:

2. p∀x∀y∀w.ϕ(x) ∧W(x, y, w)→ C(x, y, w) ↓ acceptq

3. p∀x∀y∀w.ϕ(x) ∧ ¬W(x, y, w)→ C(x, y, w) ↓ rejectq

Formale Instanzkorrekheit. Sei C eine Checker-Programm und seien die Beweis-verpflichtungen (1) bis (3) erfüllt. Dann gilt:

1. Wenn C (x, y, w) akzeptiert, dann ϕ(x)→ ψ(x, y)

2. Wenn C (x, y, w) verwirft, dann ϕ(x)→ ¬W(x, y, w)

Beweis. Falls C mit akzeptiert hält, dann folgt aus dem formalen Korrektheitsbeweis fürC, dass ϕ(x)→W(x, y, w). Zusammen mit dem formalen Beweis der Zeugeneigenschaftgilt damit ϕ(x) → ψ(x, y). Für den Fall, dass C verwirft, folgt ϕ(x) → ¬W(x, y, w)direkt aus dem Korrektheitsbeweis für C.

Bezugnehmend auf das Beispiel des zertifizierenden euklidischen Algorithmus, ergebensich zur Erstellung einer zertifizierenden Checkers-Implementation C also folgendeBeweisverpflichtungen:

1. p∀(a, b)∀g∀(s, t).(0 ≤ a ∧ 0 ≤ b ∧ 0 < a+ b) ∧ (g | s ∧ g | t ∧ g = s · a+ t · b)→(∀d.d | a ∧ d | b→ d ≤ g)q (Zeugeneigenschaft)

2. p∀(a, b)∀g∀(s, t).(0 ≤ a ∧ 0 ≤ b ∧ 0 < a+ b) ∧ (g | s ∧ g | t ∧ g = s · a+ t · b)→C((a, b), g, (s, t)) ↓ acceptq (Checker akzeptiert)

3. p∀(a, b)∀g∀(s, t).(0 ≤ a ∧ 0 ≤ b ∧ 0 < a+ b) ∧ ¬(g | s ∧ g | t ∧ g = s · a+ t · b)→C((a, b), g, (s, t)) ↓ rejectq (Checker verwirft)

12

2.3. Verteilte Algorithmen

Ein verteiltes System besteht aus Komponenten, welche miteinander kommunizierenkönnen. Jede Komponente kann Berechnungen ausführen. Bespiele für verteilte Systemesind, Mehrprozessor-Rechner, Netzwerke, wie das Internet oder auch Threads, die aufeinem Prozessor ausgeführt werden.

Verteilte Systeme werden in der Art und Weise wie einzelne Komponenten miteinan-der kommunizieren in Shared-Memory und Message-Passing Modelle unterschieden[Pel00]. In dem Shared-Memory-Modell kommunizieren die einzelnen Komponentenüber geteilte Ressourcen – beispielsweise über gemeinsame Variablen. Im Gegensatzdazu, kommunizieren beim Message-Passing die Komponenten über Nachrichtenkanä-le.

In dieser Arbeit beschäftigen wir uns mit Message-Passing-Systemen. Ein Messsage-Passing-System kann synchron oder asynchron arbeiten [Pel00]. Das synchrone Modellnimmt eine globale Uhr an, welche die Kommunikation in Runden einteilt. Jede Kom-ponente darf während einer Runde eine Nachricht verschicken. Dabei wird garantiert,dass diese in der nächsten Runde beim Nachbarn ankommt. Im Gensatz zum syn-chronen Modell, existiert beim asynchronen Modell keine solche globale Uhr. Dasheißt, jede Komponente darf zu jeder Zeit Nachrichten senden und kann zu jeder ZeitNachrichten empfangen. Die Reihenfolge, in der Nachrichten eintreffen wird hierbeinicht garantiert.

Den Zusammenschluss von Komponenten über asynchrone Nachrichtenkanäle nennenwir ein Netzwerk. Ein Netzwerk lässt sich als ungerichteter, zusammenhängender Graphmodellieren. Ein Knoten entspricht hierbei einer Komponente und eine Kante entsprichteinem Nachrichtenkanal. Die Nachbarschaft einer Komponente sind diejenigen Kompo-nenten, welche über Nachrichtenkanäle mit dieser verbunden sind.

Ein verteilter Algorithmus ist ein Algorithmus, der zu jeder Komponente eines Netz-werks einen lokalen Algorithmus definiert, so dass alle Komponenten gemeinsam einProblem lösen. Der lokale Algorithmus einer Komponente, regelt deren Berechnungs-und Kommunikationsverhalten.

2.3.1. Rechenmodell

Ein Komponente befindet sich zu jedem Zeitpunkt des Ablaufs des verteilten Algo-rithmus in einen Zustand. Der Zustand setzt sich aus dem Speicher der Komponente,insbesondere also allen Variablen des lokalen Algorithmus, welche zur Ausführung not-wendig sind. Es gibt drei Ereignisse, welche den Zustand einer Komponente verändernkönnen: ein internes Rechenschritt, der Empfang einer Nachricht und das Versendeneiner Nachricht. Die Konfiguration eines Netzwerks zu einem Zeitpunkt, setzt sich ausder Vereinigung der Zustände aller lokalen Komponenten zusammen. Die Berechnung ist

13

die Folge von Konfigurationen, wie sie sich aus dem Berechnungs- und Kommunikations-verhalten der lokalen Algorithmen ergibt. Wir betrachten ausschließlich terminierendeverteilte Algorithmen. Das heißt, wir fordern die Existenz eines bestimmten Zeitpunkts,ab dem sich durch das Berechnungs- und Kommunikationsverhalten keine Folgekonfi-gurationen mehr ergeben. Außerdem fordern wir, dass jeder lokale Algorithmus wissenmuss, dass dieser Zeitpunkt eingetreten ist.

Zu Beginn der Berechnung, befindet sich das Netzwerk in einer initialen Konfiguration.Die initiale Konfiguration bezeichnen wir als globale Eingabe. Den Zustande einer lokalenKomponenten in der initialen Konfiguration, bezeichnen wir als lokale Eingabe. Durchunsere Forderung der Terminierung gibt es eine Endkonfiguration, welche wir als globaleAusgabe bezeichnen. Den Zustand einer lokalen Komponente in dieser Konfiguration,bezeichnen wir als lokale Ausgabe.

2.3.2. Verteilter Bellman-Ford-Algorithmus

Der verteilte Bellman-Ford-Algorithmus löst das kürzeste Pfade Problem mit einer Quel-le auf dem Netzwerkgraphen mit gewichteten Kanten. Die globale Eingabe des Algorith-mus setzt zusammen aus dem Netzwerkgraphen G = (V,E), einer Kantenbewertungs-funktion c : E → N>0, welcher jeder Kante ein positives Kantengewicht zuordnet undeinen ausgezeichnet Knoten s ∈ V , welcher der Quelle entspricht.

Die lokale Eingabe des lokalen Algorithmus, der Komponente i setzt sich wie folgtzusammen:

• Die Anzahl |V | = n aller Knoten im Netzwerkgraph

• Das Wissen ob die Komponente die Quelle ist, also ob i = s gilt

• Der Nachbarschaft, also

– der Menge der Nachbarknoten Ei = {j ∈ V | {i, j} ∈ E}

– den Kantengewichten zu den Nachbarn. Also einer Funktion ci : Ei → N>0,sodass ci(j) = c({i, j}).

Die Aufgabe des verteilten Bellman-Ford-Algorithmus ist es in einen Endzustand zugelangen, so dass die lokale Ausgabe der Komponente i dem Gewicht eines kürzestenPfades ausgehend von der Quelle s entspricht.

2.4. Zertifizierende verteile Algorithmen

Bei dem Versuch das Konzept des zertifizierenden Algorithmus auf verteilte Algorithmenzu übertragen, ergeben sich mehrere Fragen. Darunter fallen Fragen nach der Gestalt derZeugeneigenschaft und der Architektur der Checker. Wer muss die Zeugeneigenschaft

14

versehen? Wie sollen die Checker in das Netzwerk integriert werden? Ist die Generierungund Überprüfung des Zertifikats tatsächlich einfacher als die verteilte Berechnung?Da das Ergebnis der Berechnung auf mehrere Komponenten verteilt ist, stellt sichdie Frage, ob jede lokale Ausgabe verifiziert werden soll oder die globale Ausgabeals Ganzes. Soll es einen Zeugen je Komponente oder einen Zeugen je Netzwerkgeben?

2.4.1. Lokaler Ansatz

Völlinger und Reisig beschreiben in [VR15] eine zertifizierende Variante des verteilten,terminierenden Bellman-Ford-Algorithmus. Als Zeugen des lokalen Ergebnisses einerKomponente, dienen dabei die berechneten Ergebnisse der Nachbarkomponenten. JedeKomponente erhält ihren eigenen Checker, der die Überprüfung der lokalen Ausgabeanhand des Zeugen der Komponente berechnet. Das globalen Ergebnisses ist damitgenau dann korrekt wenn alle lokalen Checker akzeptieren.

Völlinger verallgemeinert die Betrachtungen aus [VR15] zum sogenannten lokalen An-satz. Beim lokalen Ansatz werden weiterhin nur terminierende verteilte Algorithmenbetrachtet. Jeder lokale Algorithmus berechnet zusätzlich zur lokalen Ausgabe einenlokalen Zeugen. Für jede Komponente wird ein lokales Zeugenprädikat definiert, dessenÜberprüfung vom lokalen Checker der Komponente übernommen wird. Von der Kon-junktion der lokalen Zeugenprädikate, dem globalen Zeugenprädikat, wird gefordert,dass diese das korrekte globale Ergebnis impliziert. Die Begriffe werden ausführlich inKapitel 3 behandelt.

2.5. Theorembeweiser

Ein Theorembeweiser ist ein Programm, das einem Benutzer bei der Entwicklungeines formalen Beweises unterstützt. Der Zweck ist es, von einer bestimmten mathe-matischen Aussage zu zeigen, dass sie die logische Konsequenz aus einer Menge vonvorher gemachten Aussagen ist. Dazu werden die Aussagen in der Syntax einer Logikformuliert, so dass sie dem Theorembeweiser als syntaktische Objekte zur Weiterverar-beitung zur Verfügung stehen. Die Logik, welche dem Theorembeweiser zugrunde liegt,schränkt die Möglichkeiten zur computergestützten Beweissuche ein. Für ausdrucks-schwache Logiken, wie der Aussagenlogik, ist es möglich die logische Folgebeziehungalgorithmisch festzustellen. Für die ausdrucksstärkere Prädikatenlogik hingegen, gibtes kein solches Verfahren, da das Gültigkeitsproblem für prädikatenlogische Formelnnur semi-entscheidbar ist. Das heißt logische Folgebeziehungen, sind zwar entscheid-bar, jedoch ist es nicht immer feststellbar, dass eine logische Folgebeziehung nichtgilt.

15

2.5.1. Interaktive Theorembeweiser

Inwieweit die Beweissuche für einen Theorembeweiser automatisiert werden kann, hängtvon der Ausdrucksstärke der zugrunde liegenden Logik ab.

Automatische Theorembeweiser ermöglichen das Beweisen per Knopfdruck. Ihre be-grenzte Ausdrucksstärke macht es jedoch unmöglich in einem solchen System eineallgemeine mathematische Theorie auszudrücken.

Aus diesem Grund wurden interaktive Theorembeweiser (auch bekannt als Beweisassis-tenten) entwickelt. Diese basieren auf einer ausdrucksstarken Logik (zum Beispiel Logikhöherer Stufe). Da das Gültigkeitsproblem ausdrucksstarke Logiken unentscheidbarist, können höchstens Teile der Beweisfindung automatisiert werden. Deshalb ist esnotwendig, dass der Benutzer den Beweisprozess steuert. Dazu stellt ein interaktiverTheorembeweiser dem Benutzer eine Menge von Taktiken zur Verfügung. Diese er-lauben es einzelne Schritte in einem Beweis auszuführen. Führt eine Kombinationverschiedener Taktiken zu einem gültigen Beweis, so werden diese in einem Beweisskriptfestgehalten.

2.5.2. Beweisüberprüfung

Ein Problem, das im Kontext von Theorembeweisern auftritt, ist das der Beweis-überprüfung [Geu09]. Ein Beweisüberprüfer hat die Aufgabe einen Beweis auf seineKorrektheit zu überprüfen. Diese Aufgabe ist wesentlich einfacher als Beweisfindung,da zur Überprüfung lediglich die einzelnen Beweisschritte mechanisch überprüft werdenmüssen. Deshalb können Beweisüberprüfer als einfache Programme implementiertwerden, deren Korrektheit oft selbst verifiziert wird. Ein formaler Beweis, der mit einemTheorembeweiser erstellt wurde und von einem Beweisprüfer überprüft wurde hat ausdiesem Grund eine hohe Vertrauenswürdigkeit.

Ein weitere Anforderung, die oft an Theorembeweiser gestellt wird, ist das de-Brujin-Kriterium [Geu09]. Ein Theorembeweiser, der das Kriterium erfüllt, erzeugt währenddem interaktiven Beweisprozess ein Beweisobjekt. Von diesem Beweisobjekt wirdgefordert, dass es einfach und unabhängig überprüft werden kann. De-Brujin-Systemensind oft so umgesetzt, dass sie Beweisobjekte generieren, welche die Schritte des Beweisesin einem Kalkül des natürlichen Schließens widerspiegeln. Die Überprüfung kann voneinem Beweisüberprüfer übernommen werden.

2.5.3. Coq

In diese Arbeit wird der Beweisassistent Coq1 verwendet. Die Grundlage für Coq bildetdas Kalkül der induktiven Konstruktionen. Dabei handelt es sich im Wesentlichen

1https://coq.inria.fr/

16

um ein typisiertes λ-Kalkül höherer Ordnung, erweitert um induktive Typdefinitionen.Das Kalkül kombiniert eine funktionale Programmiersprache mit einer Logik höhererStufe.

Als funktionale Programmiersprache erlaubt Coq es das Schreiben von funktionalenProgrammen sowie das Definieren von algebraischen Datentypen, wie sie von anderenfunktionalen Sprachen, wie beispielsweise Haskell, bekannt sind. Eine Einschränkung istjedoch, dass Coq nur strukturelle Rekursion zulässt, so dass jede Funktion terminiert.Als Folge ist die funktionale Sprache von Coq nicht turingmächtig. Ein interessantesFeature von Coq ist die Programm-Extraktion mit der verifizierte Programme inäquivalente Scheme, OCaml oder Haskell transformiert werden.

Als interaktiver Theorembeweiser ermöglicht Coq die Definition von mathematischenObjekten, das Führen von formalen Beweisen, das Formulieren von Spezifikationen sowiedas Führen von Korrektheitsbeweisen für in Coq geschriebene Programme. Die zugrundeliegende Logik ist mächtig genug, um große Teile der Mathematik zu formalisieren.Coq wurde beispielsweise dazu benutzt, einen maschinenüberprüfbaren Beweis für denVier-Farben-Satz zu entwickeln.

Die Kombination aus funktionaler Programmiersprache und logischem Kalkül ist füruns von besonderem Interesse. Einerseits können in Coq Checker implementieren undderen Korrektheit zeigen und andererseits können wir die Zeugeneigenschaft beweisen.Wir benötigen außer Coq also keine zusätzlichen Werkzeuge.

17

3. Methode

In diesem Kapitel überlegen wir uns, wie der verteilten Bellman-Ford-Algorithmuszertifizierend gestaltet werden kann. Dazu erläutern wir zuerst ein bekannte Zeuge-neigenschaft für das Kürzeste-Pfade-Problem mit einer Quelle in der sequentiellemUmgebung. Im darauf folgenden Abschnitt überlegen wir uns, wie der lokale Ansatzauf das Problem angewendet werden kann.

Sei im weiteren Verlauf des Kapitels G = (V,E, s) ein ungerichteter, zusammenhängen-der Graph mit einem ausgezeichneten Startknoten s ∈ V . Weiterhin sei c : E → N>0eine Kantenbewertungsfunktion.

Definition (Pfad). Ein Pfad p von einem Knoten s ∈ V zu einem Knoten t ∈ V isteine Folge von Knoten (v1, . . . , vn), so dass v1 = s, vn = t und {vi, vi+1} ∈ E für alle1 ≤ i ≤ n− 1.

Definition (Pfadkosten). Die Pfadkosten eines Pfades p = (v1, . . . , vn) entsprechen derSumme der Kantengewichte entlang des Pfades, also dem Wert ∑

1≤i≤n−1 c ({vi, vi+1}).

Definition (Kürzeste-Wege-Funktion). Die Funktion δ : V → N≥0 mit der Eigenschaftδ(v) = min{Pfadkosten von p | p Pfad von s nach v} für alle v ∈ V , heißt Kürzeste-Wege-Funktion des Graphen G.

3.1. Überprüfung einer Kürzesten-Wege-Funktion

Ein Algorithmus zur Lösung des Kürzesten-Pfade-Problems mit einer Quelle, wie bei-spielsweise der Dijkstra-Algorithmus, berechnet einen Spannbaum mit der Quelle alsWurzel. Der Weg von der Wurzel zu einem Knoten des Spannbaums, hat minimale Pfad-kosten. Der Spannbaum ist nicht notwendigerweise eindeutig. Aus dem Spannbaum lässtsich jedoch eine eindeutige Funktion D : V → N≥0 ableiten. Die Funktionswerte ent-sprechen den Pfadkosten eines kürzesten Pfades. Wir beschränken uns zunächst darauf,wie diese Funktion auf ihre Korrektheit überprüft werden kann.

3.1.1. Zeugeneigenschaft

Eine Funktion D : V → N≥0 kann einfach darauf überprüft werden, ob sie tatsäch-lich identisch mit der Kürzeste-Wege-Funktion für den Graph G ist. Dazu muss die

19

Ausgabe D lediglich auf drei Eigenschaften überprüft werden. In diesem Fall fälltder Zeuge mit der Ausgabe zusammen. Das heißt es bedarf zur Überprüfung der Er-gebniskorrektheit, keines zusätzlichen mathematisches Artefakts, welches als Zeugefungiert.

Zeugeneigenschaft.

D(s) = 0 (Starteigenschaft)

∀{u, v} ∈ E : D(v) ≤ D(u) + c({u, v}) (Dreiecksungleichung)

∀v ∈ V \ {s} : ∃u ∈ V : {u, v} ∈ E : D(v) = D(u) + c({u, v}) (Ausgleichseigenschaft)

Dann ist für alle v ∈ V

D(v) = δ(v).

Beweis. Wir zeigen (der Beweis folgt im Wesentlichem [MMNS11]) zwei Richtungen,die Zusammen die Gleichheit belegen.

D(v) ≤ δ(v) Der Beweis erfolgt per Induktion über die Pfadlänge eines kürzestenPfades.

Induktionsanfang Ein Pfad der Länge eins, besteht nur aus dem Startknoten sselbst. Dieser ist auch der eindeutige kürzeste Pfad, da aufgrund der positivenKantengewichte alle längeren Pfade positive Kosten haben. Daraus und derStarteigenschaft folgt, dass D(s) = δ(s) = 0.

Induktionsschritt Wir haben einen kürzesten Pfad (v1, . . . , vi+1) der Länge i+ 1.Wir nehmen an, dass für Pfade der Länge i gilt, dassD(vi) ≤ δ(vi). Weiterhingilt wegen der optimalen Substruktur von kürzesten Pfaden, dass δ(vi+1) =δ(vi) + c({vi, vi+1}).

D(vi+1) ≤ D(vi) + c({vi, vi+1}) (Dreiecksungleichung)≤ δ(vi) + c({vi, vi+1}) (Induktionsannahme)= δ(vi + 1) (optimale Substruktur)

D(v) ≥ δ(v) Zur Erzeugen eines Widerspruchs nehmen wir an, dass es ein v gibt,sodass D(v) < δ(v). Von allen v mit D(v) < δ(v), sei v so gewählt, dass D(v)minimal ist (das heißt für alle v′ mit D(v′) < D(v) ist D(v′) ≥ δ(v′)). Da D(s) =δ(s) = 0, wissen wir, dass v 6= s. Dann muss es wegen der Ausgleichseigenschaft,einen Knoten u geben, sodass D(v) = D(u) + c({u, v}). Aufgrund der positivenKantengewichte ist D(u) < D(v). Wegen unser Wahl von v, muss D(u) ≥ δ(u)sein. Aufgrund der ersten Richtung gilt aber auch D(u) ≤ δ(u). Zusammen istalso D(u) = δ(u). Mit der Ausgleichskante, können wir einen Pfad nach v mit

20

Kosten δ(u) + c({u, v}) konstruieren. Ein kürzester Pfad nach v hat Kosten δ(v).Deswegen muss δ(v) ≤ δ(u) + c({u, v}) sein. Zusammen gilt:

δ(v) ≤ δ(u) + c({u, v})= D(u) + c({u, v}) (D(u) = δ(u))= D(v), (D(v) = D(u) + c({u, v}))

was ein Widerspruch zur Annahme darstellt.

Ein Spannbaum kann auf seine Korrektheit überprüft werden, indem die Ausgleichsei-genschaft mit der Baumkante überprüft wird.

3.2. Der zertifizierende verteilte Bellman-Ford-Algorithmus

Gemäß dem lokalen Ansatz, erfolgt die Überprüfung des verteilten Ergebnisses mithilfelokal berechneter Zeugen durch lokale Checker. Wie kann das Ergebnis des verteiltenBellman-Ford-Algorithmus auf Korrektheit überprüft werden? Wir beobachten, dasszur Feststellung der Gültigkeit der Dreiecksungleichung und der Ausgleichseigenschaft,ausschließlich die Funktionswerte der Nachbarschaft benötigt werden. Die Feststellungder Starteigenschaft benötigt keine zusätzliche Information. Dies motiviert die Defi-nition des lokalen Zeugen einer Komponente, als die Menge der berechneten Werteder Nachtbarschaft [VR15]. Dieser wird vom lokale Checker zur Teilüberprüfung desglobalen Ergebnisses verwendet. Beispielsweise hält nach der Ausführung des zertifi-zierenden verteilten Bellman-Ford-Algorithmus auf dem Netzwerk aus Abbildung 3.1,die Komponente e die Werte yb und yc als lokalen Zeugen. Der Checker der Kompo-nente e muss überprüfen, ob die Dreiecksungleichung und Ausgleichseigenschaft in derNachbarschaft erfüllt sind. Die Überprüfung der Starteigenschaft entfällt, da e nichtdie Quelle ist. Zur Überprüfung der Dreiecksungleichung müssen die Ungleichungenyd ≤ yb + 8 und yd ≤ yc + 1 überprüft werden. Weiterhin muss der lokale Checker zurÜberprüfung der Ausgleichseigenschaft feststellen, ob eine der Ungleichung tatsächlicheine Gleichheit ist. Hier stellt er fest, dass yd = yc + 1.

Im Rest des Abschnitts verallgemeinern wir unsere Überlegungen und geben eineformale Definition des lokalen Ansatzes. Dazu führen wir die Bergriffe globale Eingabe,globale Ausgabe, lokaler Zeuge, lokales Zeugenprädikat und globale Zeugeneigenschaftein.

21

d{ya 7→ 0, yc 7→ 5}

a{yb 7→ 2, yc 7→ 5, yd 7→ 7}

c

{ya 7→ 0, yb 7→ 2, yd 7→ 7, ye 7→ 6}

b {ya 7→ 0, yc 7→ 5, ye 7→ 6}

e {yb 7→ 2, yc 7→ 5}

10

2

5

2

1

3 8

Abbildung 3.1.: Netzwerk mit der Quelle a nach der Ausführung des zertifizieren-den verteilten Bellman-Ford-Algorithmus. Jede Komponente hältnach Ausführung als lokalen Zeugen, die berechneten Distanzen derNachbarkomponenten.

3.2.1. I/O-Verhalten

Im weiteren Verlauf betrachten wir den Graph G, als Netzwerk eines verteilten Algo-rithmus. Das I/O-Verhalten eines terminierenden verteilten Algorithmus kann, wie imSequentiellem, mit zwei Prädikaten ϕ und ψ angegeben werden.

Definition (Globale Eingabe). Sei X die Menge der möglichen Eingaben eines lokalenAlgorithmus. Die Menge aller möglichen globalen Eingaben X entspricht dem kartesi-schem Produkt X |V |. Die globale Eingabe eines Netzwerks ist ein Element x aus derMenge X.

Definition (Globale Ausgabe). Sei Y die Menge der möglichen Eingaben eines lo-kalen Algorithmus. Die Menge aller möglichen globalen Ausgaben Y entspricht demkartesischem Produkt Y |V |. Die globale Ausgabe eines Netzwerks ist ein Element y ausder Menge Y .

Ein verteilter terminierender Algorithmus heißt korrekt, wenn er für jede globale Eingabex ∈ X, welches die Vorbedingung ϕ(x) erfüllt, mit einer globalen Ausgabe y ∈ Y hält,mit der die Nachbedingung ψ(x, y) gilt.

Die lokale Eingabe einer Komponente i bezeichnen wir mit xi. Sie besteht aus:

• der Information ob i die Quelle ist, also ob i = s

• der Menge der Nachbarknoten Ei = {j ∈ V | {i, j} ∈ E}

• den Kantengewichten zu den Nachbarn. Also einer Funktion ci : Ei → N>0,sodass ci(j) = c({i, j}).

Die lokale Ausgabe einer Komponente i bezeichnen wir mit yi. Sie besteht aus:

• einer natürlichen Zahl, welcher den Pfadkosten eines kürzesten Weges von s nachi entspricht.

22

Wir fordern, dass ϕ(x) genau dann erfüllt ist, wenn der durch x definierte Graphungerichtet und zusammenhängend ist. Die Nachbedingung ψ(x, y) soll genau danngelten, wenn yi = δ(i) für alle i ∈ V . Dabei ist δ die Kürzeste-Wege-Funktion des durchx definierten Graphen.

3.2.2. Die Zeugeneigenschaft in der verteilten Umgebung

Definition (Zeugenkonfiguration). Sei W die Menge der möglichen lokalen Zeugeneines lokalen Algorithmus. Die Menge aller möglichen Zeugenkonfigurationen W ent-spricht dem kartesischem Produkt W |V |. Die Zeugenkonfiguration eines Netzwerks istein Element w aus der Menge W .

Lokales Zeugenprädikat einer Komponente

Den lokale Zeugen einer Komponente i bezeichnen wir mit wi. Er wird definiert als dieMenge der berechneten Werte der Nachbarschaft:

wi := {yj | j ∈ Ei}.

Mithilfe des lokalen Zeugen definieren wir das lokale Zeugenprädikat wp(xi, yi, wi) für dieverteilte Konstruktion einer Kürzesten-Wege-Funktion wie folgt:

Falls i = s ist wp(xi, yi, wi) genau dann erfüllt, wenn

yi = 0 (Starteigenschaft)∀yj ∈ wi : yi ≤ yj + ci(j) (Dreiecksungleichung)

Falls i 6= s ist wp(xi, yi, wi) genau dann erfüllt, wenn

∀yj ∈ wi : yi ≤ yj + ci(j) (Dreiecksungleichung)∃yj ∈ wi : yi = yj + ci(j) (Ausgleichseigenschaft)

Globale Zeugeneigenschaft

Das Prädikat W(x, y, w) = wp(x1, y1, w1) ∧ . . . ∧ wp(x|V |, y|V |, w|V |) heißt globales Zeu-genprädikat, wenn es die globale Zeugeneigenschaft erfüllt. Das heißt für alle x ∈ X,y ∈ Y und w ∈ W gilt:

23

ϕ(x) ∧W(x, y, w)→ ψ(x, y)

3.3. Beweisverpflichtungen

Das weitere Vorgehen ist in Coq die Beweisverpflichtung (1) für die globale Zeugenei-genschaft zu erfüllen. Dazu formalisieren wir als ersten Schritt gewichtete Graphenund kürzeste Pfade. Darauf aufbauend beweisen wir zunächst die Zeugeneigenschaft inder sequentiellen Umgebung. Der Coq-Beweis orientiert sich stark an dem textuellenBeweis aus Abschnitt 3.1.1 und wird in Kapitel 5 vorgestellt. Der zweite Schritt istder Coq-Beweis der globalen Zeugeneigenschaft, welcher in Kapitel 6 vorgestellt wird.Dafür ist es notwendig die lokale Ein- uns Ausgabe sowie das lokale Zeugenprädikateiner Komponente zu formalisieren.

1. p∀x ∈ X ∀y ∈ Y ∀w ∈ W . ϕ(x) ∧W(x, y, w)→ ψ(x, y)q

Der Vollständigkeit halber seien hier noch die Beweisverpflichtungen (2) und (3) fürdie Korrektheit des Checker-Algorithmus C zu genannt. Da Coq ein Beweiskalkül miteiner funktionalen Programmiersprache verbindet, kann die Implementierung von Cdirekt in Coq erfolgen. Da jede Funktion in Coq terminiert, kann die Voraussetzung,dass die Checker nur bei Netzwerken terminieren in denen die Vorbedingung giltentfallen.

2. p∀x ∈ X ∀y ∈ Y ∀w ∈ W. wp(x, y, w)→ C(x, y, w) ↓ acceptq

3. p∀x ∈ X ∀y ∈ Y ∀w ∈ W. ¬wp(x, y, w)→ C(x, y, w) ↓ rejectq

24

4. Überblick über denBeweisassistenten Coq

Dieses Kapitel dient dazu, einen Eindruck über das Beweisen in Coq zu vermitteln. Wirerklären dabei die Spezifika von Coq in dem Umfang wie sie für das Verständnis unsererFormalisierung in Kapitel 5 und Kapitel 6 notwendig sind.

Für eine umfassende Spezifikation, verweisen wir den Leser an [BC04]. Eine guteEinführung in Coq bietet, neben der offiziellen Einführung [PM11], der Online-Kurs„Software-Foundations“ [PCG+15] von Benjamin Pierce. Chlipala gibt in [Ada11]neben einer Einführung in Coq eine Besprechung vieler fortgeschrittener Beweistechni-ken.

4.1. Funktionales Programmieren in Coq

Konstanten

Ein Coq-Term hat einen Namen und (mindestens) einen Typ. Die Wohlgeformtheitund der Typ eines Terms t, lässt sich mit dem Kommando Check t feststellen. Diesveranlasst Coq dazu, den Algorithmus zur Typüberprüfung auszuführen. Ein Termist immer relativ zu einer Umgebung wohlgeformt. Die Umgebung setzt sich aus denvorher gemachten Deklarationen und Definitionen zusammen.

< Check true.true : bool< Check O.O : nat

Die Konstante true hat den Typ bool, welcher zur Darstellung von Wahrheitswertendient. Dieser Typ ist Teil der Standardbibliothek von Coq. Wenn das entsprechendeModul geladen ist, ist der Term wohlgeformt. Der Typ nat zur Repräsentation vonnatürlichen Zahlen ist ebenfalls Teil der Standardbibliothek. Coq erlaubt die Definitionvon Typen (siehe Abschnitt 4.4).

25

Funktionsabstraktion

Wie von einer funktionalen Sprache zu erwarten, lassen sich in Coq (anonyme) Funk-tionen definieren.

Der Term fun x y : nat => x, ist eine zweistellige anonyme Funktion, welche zweinatürlicher Zahlen entgegen nimmt und die erste zurück liefert. Sie hat Typ nat ->nat -> nat. Der Abstraktionspfeil ist dabei rechtsassoziativ. Mehrstellige Funktionenentstehen durch Currying.

< Check fun x y : nat => x.fun x y : nat => x : nat -> nat -> nat

Funktionsanwendung

Eine anonyme Funktion kann auf einen Term angewendet werden, wenn die Typenpassen. Beispielsweise kann die oben definierte Funktion vom Typ nat -> nat ->nat auf den Term O vom Typ nat angewendet, um eine anonyme Funktion vom Typnat -> nat zu erhalten. Funktionsanwendung ist linksassoziativ.

< Check (fun x y : nat => x) O.(fun x y : nat => x) O : nat -> nat

Funktionen

Mit dem Schlüsselwort Definition lassen sich Funktionen mit Namen definieren.Beispielsweise ist folgende Definition eine Funktion vom Typ nat -> nat mit demNamen double:

Definition double (x : nat) : nat :=plus x x.

4.1.1. Universen in Coq

Im Gegensatz zu gewöhnlichen funktionalen Programmiersprachen, sind Typen in Coqselbst Terme. Da jeder Term in Coq einen Typ hat, muss ein Typ konsequenterweiseebenfalls einen Typ haben. Ein Typ der Kategorie „Typ von Typ“ heißt Sorte. In Coqgibt es zwei wichtige Sorten, nämlich Set und Prop.

26

Die Sorte Set

Die Sorte Set stellt das Universum der „kleinen Mengen“ dar. Es soll diejenigenTypdefinitionen umfassen, wie sie in funktionalen Programmiersprachen wie Haskellgemacht werden. Beispielsweise enthält Set Typen fürWahrheitswerte (bool), natürlicheZahlen (nat) und Produkte (prod). Funktionen über diese Datentypen sind ebenfallsin Set enthalten.

Die Sorte Prop

Ein spezieller Datentyp in Coq ist der Typ Prop, welcher für logischen Aussagen steht.Tabelle 4.1.1 gibt eine Überblick über die Syntax von logischen Aussagen in Coq. DieAussagen P und Q müssen jeweils vom Typ Prop sein. Die Quantoren dürfen über jedenTyp quantifizieren (insbesondere also über Typen aus der Sorte Set und über Propselbst). Der Typ kann weggelassen werden, wenn er aus dem Kontext hervorgeht. DieNegation und die Ungleichheit sind in Wirklichkeit syntaktischer Zucker für P -> Falseund (t = u) -> False.

Operation mathematische Notation Coq-SyntaxFalsum ⊥ FalseVerum > TrueGleichheit t = u t = uUngleichheit t 6= u t <> uNegation ¬P ~PKonjunktion P ∧Q P /\ QDisjunktion P ∨Q P \/ QImplikation P → Q P -> Quniverselle Quantifizierung ∀x : T, P forall x: T, Pexistentielle Quantifizierung ∃x : T, P exists x: T, P

Tabelle 4.1.: Syntax für logische Aussagen in Coq (vgl. [PM11])

Die Sorte Type(i)

Aus Konsistenzgründen muss eine Sorten auch einen Typ haben. Die Sorten Setund Prop haben den Typ Type(0). Eine Sorte vom Type(i) hat den Typ Type(i+1),so dass eine unendliche Hierarchie entsteht. Der hierarchische Aufbau verhindertdas Formulieren des typentheoretischen Äquivalents der Russellschen Antinomie[Ada11].

27

4.2. Beweise als Objekte

In diesem Abschnitt beleuchten wir eine interessante Beziehung zwischen typisiertenλ-Kalkülen und Kalkülen des natürlichen Schließens. Die Beziehung, welche als Curry-Howard-Isomorphismus [BG01] bekannt ist, besteht zwischen Beweisen innerhalb einesKalküls des natürlichen Schließen und Termen innerhalb des typisierten λ-Kalküls.Sie besagt, dass sich ein Beweis im ersteren als Term bestimmten Typs im letzterendarstellen lässt. Coq, welches auf dem Kalkül der induktiven Konstruktion basiert,beruht auf diesem Zusammenhang. Dieses Kalkül ist jedoch zu komplex um es hier inGänze darzustellen, sodass wir uns hier lediglich auf die Darstellung der Grundideebeschränken.

4.2.1. BHK-Interpretation

Im Gegensatz zur klassischen Logik, werden logische Aussagen in Coq konstruktiv durchdie BHK-Interpretation1 [BG01] verstanden. Der (klassische) Wahrheitsbegriff wirddabei durch den Begriff der Beweisbarkeit ersetzt. Dadurch lassen sich die logischenOperatoren (∧, ∨ und →) folgendermaßen interpretieren:

• Ein Beweis für A ∧B ist ein Beweis für A und ein Beweis für B.

• Ein Beweis für A ∨B ist entweder ein Beweis für A oder ein Beweis für B.

• Ein Beweis für A→ B ist eine Funktion, die einen Beweis für A auf einen Beweisfür B abbildet.

Für jede logische Operation, lässt sich ein mathematisches Artefakt konstruieren,dass die Operation bezeugt [BG01]. Für die Konjunktion A ∧B können wir ein Paarkonstruieren, deren Komponenten aus dem Beweis fürA und dem Beweis fürB bestehen.Die Disjunktion A ∨B lässt sich als disjunktes Paar darstellen. Das heißt die zweiteKomponente besteht entweder aus dem Beweis für A oder aus dem Beweis für B,während die erste Komponente angibt, welche der beiden Alternativen zutrifft. DieImplikation lässt sich wie gehabt als Funktion darstellen.

Die Negation lässt sich folgendermaßen interpretieren [BG01]: Es gibt ein Symbol ⊥,welches „Falsch“ repräsentiert und keinen Beweis hat. Um ¬A zu beweisen, beweist manA→ ⊥. Das heißt ein Beweis für ¬A, ist eine Funktion, die aus jedem (hypothetischen)Beweis für A einen Beweis für „Falsch“ konstruiert.

Da bei der Disjunktion angegeben werden muss, welche Alternative gilt, ist die BHK-Interpretation intuitionistisch. Das heißt, der Satz vom ausgeschlossenem Dritten istnicht beweisbar [BG01].

1benannt nach Brouwer, Heyting und Kolmogorov

28

4.2.2. Curry-Howard-Isomorphismus

Für Aussagenlogik ist es relativ leicht im Kalkül der induktiven Konstruktionen Typenzu definieren, die den mathematischen Artefakten der BHK-Interpretation entsprechen[BG01]. Paare und disjunktive Paare lassen sich als (induktive) Typen darstellen.Funktionen entsprechen λ-Abstraktionen im typisiertem Kalkül. Weiterhin, existiert imKalkül der Typ „Falsch“, für den sich jedoch kein Term mit diesem Typ konstruierenlässt.

Um den selben Zusammenhang auch für Aussagen mit Quantoren herzustellen, reichtein einfaches Typsystem nicht mehr aus. Das Kalkül von Coq stellt dazu sogenannteabhängige Typen [BG01] zur Verfügung.

Um zu sehen, wie abhängige Typen Beweise für quantifizierte Aussagen kodifizie-ren, sei hier die BHK-Interpretation für logische Aussagen mit Quantoren aufge-führt:

• Ein Beweis für ∀x : T,B ist eine Funktion, die jedes x : T auf einen Beweis fürB[x← t] abbildet.

• Ein Beweis für ∃x : T,B ist eine Term t, und einen Beweis für B[x← t].

Wenn bei der universellen Quantifizierung, die Variable x in B nicht frei vorkommt,handelt es sich um denselben Fall wie bei der Implikation. Ein Beweis wird durcheine einfachen λ-Term realisiert. Im anderen Fall, muss der Rückgabetyp von derEingabe abhängen. Eine Funktion dessen Rückgabetyp von der Eingabe abhängt, heißtabhängige Funktion.

Eine existentielle Quantifizierung wird durch ein abhängiges Paar realisiert. Dies istein Paar, in dem der Typ der rechten Komponente von dem der linken Komponentenabhängig ist.

Zusammenfassend ist also eine Aussage beweisbar, wenn es einen Term gibt, der denzur Aussage passenden Typ hat. Ein Term mit dieser Eigenschaft heißt Beweisterm.Der Curry-Howard-Isomorphismus hat zur Konsequenz, dass zur Beweisüberprüfunglediglich der Algorithmus zur Typüberprüfung auf den Beweisterm angewendet werdenmuss.

4.3. Grundlegende Taktiken

Die Wahrheit einer Aussage in Coq, wird durch einen Beweis festgestellt. Coq stelltzur Beweisführung sogenannte Taktiken bereit. Eine Taktik überführt das aktuelleBeweisziel, in eine Menge von Unterbeweiszielen, mit der Eigenschaft, dass das Beweisender Unterziele hinreichend für das Zeigen des ursprünglichen Beweisziels ist. Die Menge

29

der generierten Unterziele, einer Taktik kann auch leer sein. Der Beweis ist abgeschlossen,wenn alle Beweisziele erreicht wurden.

4.3.1. Natürliches Schließen

Die Grundlage der Beweisführung in Coq, bildet ein Kalkül des natürlichen Schließens.Ziel ist es für eine Aussage A einen Beweisterm p : A zu finden, so dass p : A, unterder aktuellen Umgebung Γ wohlgeformt ist und den Typ A hat. Dies wird mit derSchreibweise Γ ` p : A ausgedrückt.

Ziel ist es, mit den Regeln des Kalküls, Schritt für Schritt, einen solchen Beweistermzu konstruieren. Dazu gib es für jeden logischen Operator (Gleichheit, Junktor bzw.Quantor) sowohl eine Einführungs- als auch eine Beseitigungsregel. Die Regeln desKalküls, sind in Tabelle 4.2 und Tabelle 4.3 aufgeführt.

Die Einführungsregel für einen Operator, beschreibt, wie einfachere Aussagen, in eineAussage mit diesem Operator als Hauptoperator überführt werden kann.

Die Beseitigungsregel für einen Operator beschreibt, wie schon bewiesene Aussagenmit diesem Operator verwendet werden können.

Regel Taktik

¬ Γ, h : A ` FalseΓ `? : ¬A

intro h

→ Γ, h : A `? : BΓ `? : A→ B

intro h

∀ Γ, y : A `? : B[x← y]Γ `? : ∀x : A,B

intro y

∧ Γ `? : A Γ `? : BΓ `? : A ∧B

split

∨

Γ `? : AΓ `? : A ∨B

left

Γ `? : BΓ `? : A ∨B

right

∃ Γ ` t : A Γ `? : B[x← t]Γ `? : ∃x : A,B

exists t

= t ≡ u

Γ `? : t = ureflexivity

Tabelle 4.2.: Logische Einführungsregeln mit entsprechenden Taktiken (vgl. [PM11])

30

Regel Taktik

⊥ Γ `? : FalseΓ `? : C

exfalso

¬ Γ ` h : ¬A Γ `? : AΓ `? : C

destruct h

→ Γ ` h : A→ B Γ `? : AΓ `? : B

apply h

∀ Γ ` h : ∀x : A,B Γ ` t : AΓ `? : B[x← t]

apply h with (x:=t)

∧ Γ ` h : A ∧B Γ, l : A,m : B `? : CΓ `? : C

destruct h as [l m]

∨ Γ ` h : A ∨B Γ, l : A `? : C Γ, l : B `? : CΓ `? : C

destruct h as [l|l]

∃ Γ ` h : ∃x : A,B Γ, x : A, l : B `? : CΓ `? : C

destruct h as [x l]

= Γ ` h : t = u Γ `? : C[x← u]Γ `? : C[x← t]

rewrite h

Tabelle 4.3.: Logische Beseitigungsregeln mit entsprechenden Taktiken (vgl. [PM11])

Das Ziel ist es mit Hilfe der Regeln einen Beweisterm zu erzeugen, welcher die Kor-rektheit der zu beweisenden Aussage bezeugt. Die Regeln werden dabei rückwärtsangewandt. Das heißt, wenn das aktuelle Beweisziel der Folgerung einer Regel entspricht,entsteht für jede der Voraussetzungen der Regel, welche ein Fragezeichen enthält, einneues Beweisziel. Die Fragezeichen entsprechen den Lücken im Beweisterm, welche zuvervollständigen sind.

Das Symbol „≡“ bei der Einführungsregel der Gleichheit, bedeutet syntaktische Gleich-heit nach Auswertung im λ-Kalkül.

Das Axiom des Kalküls – Die Taktiken exact und assumption

Das Axiom des Kalküls ist der Fall, dass die Konklusion einer Hypothese im Beweis-kontext erscheint. Diese Regel kann mit der exact-Taktik angewendet werden. DieAnwendung der Taktik löst das Beweisziel.

h : A ∈ ΓΓ ` h : A

exact h

Eine allgemeinere Form des Axioms bildet die Taktik assumption, bei der die Notwen-digkeit zur Benennung der Hypothese entfällt.

31

Zwischenbeweise mit der Taktik assert

Während eines Beweises, kann es hilfreich sein, zu bestimmten Zeitpunkten, einenZwischenbeweis für eine Aussage zu führen. In einen Zwischenbeweis, dürfen allezu dem Zeitpunkt existierenden Hypothesen des Beweiskontextes verwendet werden.Coq stellt dazu die Taktik assert bereit. Die Taktik, generiert ein neues Beweiszielmit der Zwischenbehauptung B als Konklusion. Die Hypothesen des Beweiskontextes,entsprechen denjenigen zum Zeitpunkt der Anwendung dieser Taktik. Nachdem dasBeweisziel erfüllt ist, steht die Zwischenbehauptung B, als zusätzlich Hypothese mitdem Namen h zur Verfügung.

Γ `? : B Γ, h : B `? : AΓ `? : A

assert (h : B)

Beispiel: Kommutativität der Konjunktion

Wir Beweisen zur Demonstration der Taktiken ein einfaches Lemma, welches Kommu-tativität der Konjunktion ausdrückt. Das vollständige Beweisskript ist in Abbildung 4.1aufgeführt. Das initiale Beweisziel wird mit dem Schlüsselwort Lemma gefolgt von demNamen and_commutative und der Aussage vom Typ Prop eingeführt. Mit Proof wirdder interaktive Beweismodus gestartet. Nachdem alle Beweisziele gelöst sind, beendetman den Beweis mit dem Schlüsselwort Qed. Dies übergibt den Beweisterm, welcherdurch das Beweisskript generiert wurde, dem Typchecker, welcher ihn auf Korrektheitüberprüft.

Nach der Beweisüberprüfung, steht das Lemma unter dem Namen and_commutativezur Verfügung und kann in anderen Beweisen mit der Taktik apply verwendet wer-den.

4.3.2. Beweisautomatisierung

Zur Vereinfachung der Beweisführung implementiert Coq einige Automatisierungen.Für jede Automatisierung existiert eine Taktik, welche versucht das Beweisziel zu lösen.Wenn dies nicht gelingt, bleibt das Beweisziel unverändert.

• Die Taktik auto durchsucht eine Datenbank nach Lemmata, welche das Beweisziellösen.

• Die Taktik tauto ruft einen Entscheidungsprozedur für intuitionistische Aussagen-logik auf. Diese Taktik kann beispielsweise die Kommutativität der Konjunktionsofort lösen.

32

Lemma and_commutative : forall A B: Prop A /\ B -> B /\ A.Proof.

______________________________________forall A B: Prop, A /\ B -> B /\ A

intro A. intro B. intro H.

A: PropB: PropH: A /\ B______________________________________B /\ A

destruct H as [a b].

A: PropB: Propa: Ab: B______________________________________B /\ A

split.A: PropB: Propa: Ab: B______________________________________(1/2)B

A: PropB: Propa: Ab: B______________________________________(2/2)A

exact b.exact a.

Qed.

Abbildung 4.1.: Beweis für die Kommutativität der Konjunktion. Die Rahmen enthaltenBeweisziele, die nach Anwendung der Taktiken entstehen. Die split-Taktik generiert zwei Beweisziele, welche jeweils mit der Taktik exactgelöst werden können.

33

• Die Taktik omega implementiert ein Entscheidungsverfahren für die Theorieder Presburger Arithmetik. Sie ist in der Lage Beweisziele zu lösen, welcheaus Ungleichungen und arithmetischen Aussagen bestehen, welche nur Additionverwenden [PCG+15].

4.4. Induktive Typdefinitionen

Ein wichtiger Schritt jeder Formalisierung in Coq eines mathematischen Problems, istdas Definieren von eigenen Typen, welche verschiedene Teilaspekte des Gesamtproblemserfassen. Dazu stellt Coq induktive Typen zur Verfügung. Dabei handelt es sich umeine Verallgemeinerung von algebraische Datentypen, wie sie zum Beispiel aus Haskellbekannt sind. Mithilfe eines induktiv definierten Typs, können, neben einfachen Aussa-gen über Terme diesen Typs, auch Aussagen über alle Terme des Typs formuliert undbewiesen werden. Letzteres wird dadurch ermöglicht, dass Quantoren in Coq immer überVariablen eines bestimmten Typs quantifizieren. Universell quantifizierte Aussagen mitinduktive Typen, werden durch Induktionsbeweise ermöglicht.

4.4.1. Aufzählungen

Der einfachste induktive Datentyp in Coq ist die Aufzählung. Als Beispiel betrachtenwir den Typ bool aus der Standardbibliothek.Inductive bool : Set :=| true : bool| false : bool.

Die Definition besteht aus zwei Teilen. Der erste Teil beschreibt, den Namen des induk-tiven Typs und spezifiziert welchem Universum der Datentyp angehört. Hier wird einenneuer Typ mit dem Namen bool im Universum Set eingeführt. Der zweite Teil bestehtaus einer Liste von Konstruktoren, welche beschreiben, wie Terme dieses Typs erstelltwerden können. Jeder induktive Typ ist bezüglich seiner Konstruktoren abgeschlossen.Das bedeutet, dass die Konstruktoren alle Elemente eines induktiven Typs bestimmten.In diesem Beispiel muss ein Term vom Typ bool, also entweder durch den Konstruktortrue oder durch Konstruktor false eingeführt worden sein.

4.4.2. Rekursive Definitionen

Ein Typ der unendliche viele Elemente enthält, lässt sich mit einem induktiven Typenrealisieren. Ein solcher Typ unterscheidet sich von einer Aufzählungen, in dem Punkt,dass er mindestens ein Konstruktor vom Typ Funktion hat, dessen Funktionsargument

34

vom selben Typ wie der induktive Typ ist. Als Beispiel führen wir den Typ nat der Stan-dardbibliothek zur Repräsentation der natürlichen Zahlen auf.

Inductive nat : Set :=| O : nat| S : nat -> nat.

Der Typ nat hat zwei Konstruktoren, einen zur Konstruktion der natürlichen Zahl Null(O) und einen zur Konstruktion des Nachfolgers einer natürlichen Zahl (S). Die Zahlen0 und 4, werden beispielsweise durch die Terme O und S(S(S(S(O)))) repräsentiert.Tatsächlich ist in Coq eine Zahl in Dezimalschreibweise nichts Weiter als syntaktischeZucker für diese Schreibweise.

4.4.3. Induktive Prädikate

Als letzte induktive Typdefinition beschäftigen wir uns mit abhängigen induktivenTypen. Dies ist ein induktiver Typ in dem mindestens ein Konstruktor die Formeiner abhängigen Funktion annimmt. Mit Hilfe von abhängig induktiven Typen, lassensich in Coq Prädikate induktiv definieren. Ein Prädikat ist eine Funktion P vomTyp

T1 -> ... -> Tn -> Prop,

mit beliebigen Typen Ti [Ada11]. Um eine Aussage zu erhalten, muss die Funkti-on also auf n Terme entsprechenden Typs angewendet werden. Die so entstehendeAussage, kann natürlich nicht beweisbar sein. Die abhängigen Konstruktoren sorgenjedoch dafür, dass nur für bestimmte Wertekombination Beweisterme erstellt werdenkönnen.

Als Beispiel geben wir hier die Definition des Kleiner-Gleich-Prädikats le der Stan-dardbibliothek von Coq.Inductive le (n : nat) : nat -> Prop :=| le_n : le n n| le_S : forall m : nat, le n m -> le n (S m)

Die erste Zeile gibt an, dass der induktive Typ le ein zweistelliges Prädikat auf dennatürlichen Zahlen definiert. Die erste Variable, erhält dabei einen Namen, damit sie inden Konstruktoren verwendet werden kann. Der Konstruktor le_n drückt die Reflexi-vität des Prädikats aus. Der Konstruktor le_S ist abhängig. Dies ist daran erkennbar,dass die universell quantifizierte Variable m, auf der rechten Seite des Abstraktionspfeil,Teil einer Funktionsapplikation ist. Er drückt aus, dass wenn eine Zahl kleiner odergleich einer anderen ist, diese auch kleiner oder gleich dem Nachfolger der anderen Zahlist.

35

4.5. Taktiken für induktive Typen

4.5.1. Beweis durch Induktion

Coq beweist automatisch für jeden induktiven Typ ein Induktionsprinzip und fügtes dem Kontext hinzu, sodass es wie ein normales Lemma verwendet werden kann[Ada11]. Das Induktionsprinzip drückt aus, welche Beweisziele erfüllt werden müssen,damit eine universell quantifizierte Aussage über den induktiven Typ, wahr ist. DasInduktionsprinzip entspricht dem Prinzip der strukturellen Induktion und ergibt sichdirekt aus der Typdefinition. Die Induktionshypothesen entsprechen den Prämissender rekursiven Regeln.

Das Lemma für das Induktionsprinzip setzt sich aus den Namen des induktiven Typsund dem Suffix _ind zusammen. Für den induktiven Typ der natürlichen Zahlen natlautet es:nat_ind

: forall P : nat -> Prop,P 0 -> (forall n : nat, P n -> P (S n)) -> forall n : nat, P n

Es entspricht genau dem Peanos Induktionsprinzip für natürliche Zahlen. Um einenInduktionsbeweis zu führen, stellt Coq die Taktik

induction t

zur Verfügung, wobei t ein Term induktiven Typs ist. Die Taktik lässt sich auf einenTerm im Beweiskontext anwenden und generiert Beweisziele gemäß dem Induktions-prinzip.

Beispiel: Null ist die kleinste natürliche Zahl

Zur Demonstration der Taktik beweisen wir, dass Null die kleinste natürliche Zahlist. Abbildung 4.2 zeigt den vollständige Coq-Beweis mitsamt allen Unterzielen. DieTaktik induction generiert zwei neue Beweisziele, welche dem Induktionsanfang unddem Induktionsschritt entsprechen. Das Symbol <= ist syntaktischer Zucker für dasPrädikat le (vgl. Abschnitt 4.4.3).

4.5.2. Beweis durch Fallunterscheidung

Im Verlauf eines Beweises, kann es notwendig sein, anhand einer induktiven Hypo-these, eine Fallunterscheidung zu machen. Für solche Situationen stellt Coq die Tak-tik

inversion H

36

zur Verfügung, wobei H eine Hypothese induktiven Typs ist. Die Anwendung dieserTaktik, erstellt für jeden Konstruktor des induktiven Typs ein Beweisziel. Dem Kontextjeden Beweisziels, werden die Prämissen des Konstruktors hinzugefügt. Zusätzlichwird in jedem Unterziel, die Konklusion des Konstruktors mit H unifiziert und dieGleichheiten, welche sich daraus ergeben, dem Kontext des Unterziels hinzugefügt. Coqversucht dabei triviale Unterziele selbstständig zu lösen.

4.6. Weitere Typen

4.6.1. Records

Ein Record dient zur Zusammenfassung von mehreren Einträgen zu einem Typ.Beispielsweise lässt sich ein Punkt in einer Ebene als folgender Record definie-ren:Record point : Set := mk_point {

nat x;nat y

}.

Ein Record in Coq ist nichts weiter als ein induktiver Typ mit nur einem Konstruktor.Coq fügt zusätzlich für jeden Eintrag eine Projektionsfunktion dem Kontext zu. DerRecord point ist also ein induktiver Typ mit dem Konstruktor mk_point vom Typnat -> nat -> point. Die beiden Projektionsfunktionen sind vom Typ point -> natund erhalten die Namen x und y.

4.6.2. Sigma-Typen

Als letzten Typen stellen wir den Typ Sigma vor, welcher ein abhängiges Paar im Set-Universum repräsentiert. Genau genommen handelt es sich hierbei um eine induktiveTypdefinition. Coq erlaubt jedoch eine vereinfachte Schreibweise, welche komfortablerzu betrachten ist. Die Syntax für Sigma lautet:

{ x : A | P }

Die linke Seite besteht aus einer einfachen Variablendefinition, mit einem beliebigenVariablennamen und einem Typ A, der aus dem Universum Set stammt. Das P isteine beliebige Aussage vom Typ Prop, welche von der Variablen auf der linken Seiteabhängen darf. Ein Term von diesem Typ, definiert also ein Objekt im Universum Setund trifft eine Aussage über das Objekt.

Coq stellt die beiden Funktionen proj1_sig und proj2_sig, welche das abhängigePaar auf die linke beziehungsweise rechte Komponente projiziert.

37

Ein Sigma-Typ wird auch als Subset-Typ bezeichnet, da er einen Typ aus dem Univer-sum Set auf bestimmte Terme beschränkt.

4.7. Variablen und Sections

Coq bietet die Möglichkeit während der Definitionsphase den Beweiskontext durch eigeneVariablen zu erweitern. Dies ist sinnvoll, wenn viele Lemmata auf die selben Definitionenzurückgreifen. Eine Variable wird mit folgender Syntax eingeführt:

Variable x : T.

Nach der Variablendefinition können Lemmata, welche diese Variable verwenden, for-muliert werden. Neben dem Schlüsselwort Variable stellt Coq auch noch die Schlüs-selworte Hypothesis und Axiom zur Verfügung, welche die selbe Semantik haben,dem Benutzer jedoch erlauben hervorzuheben, welche Rolle die Variablendefinitioneinnimmt.

Der Gültigkeitsbereich von Variablendefinitionen, lässt sich mit dem Section-Mechanis-mus von Coq einschränken. Eine Section wird mit dem Schlüsselwort Section gefolgtvon einem Namen eingeleitet und wird mit dem Schlüsselwort End abgeschlossen. DasSchließen der Section, führt zur Abstraktion aller Definitionen und Lemmata, welchevon Variablen innerhalb der Section abhängig sind. Das bedeutet, dass die Variablenaußerhalb der Section entweder als Implikation oder als universelle Quantifizierungauftreten.

38

Lemma zero_minimal : forall n : nat, 0 <= n.Proof.

______________________________________forall n : nat, 0 <= n

intro n.

n : nat______________________________________0 <= n

induction n.

______________________________________(1/2)0 <= 0

n : natIHn : 0 <= n______________________________________(2/2)0 <= S n

apply le_n.apply le_S.

n : natIHn : 0 <= nn : nat______________________________________(2/2)0 <= n

exact IHn.Qed.

Abbildung 4.2.: Induktionsbeweis dafür, dass 0 die kleinste natürliche Zahl ist. DieRahmen enthalten die Beweisziele, die nach Anwendung der Taktikenentstehen. Der Induktionsanfang lässt sich mit durch Anwendung desKonstruktors le_n lösen. Der Induktionsschritt ändert sich Anwendungdes Konstruktors le_S nach 0 <= n, so dass sie der Induktionshypo-these entspricht und mit der exact Taktik gelöst werden kann.

39

5. Beweis der Zeugeneigenschaft inCoq

Dieses Kapitel dient dazu, einen Überblick über den Coq-Beweis der Zeugeneigenschaftzu verschaffen. Ziel ist es, das Theorem dist_eq_delta zu beweisen, welches dieÄquivalenz einer die Zeugeneigenschaft erfüllenden Funktion dist mit der Kürzesten-Wege-Funktion delta ausdrückt.

Abbildung 5.1 gibt einen Überblick über die Struktur des Beweises. Den Ausgangspunktdes Beweises bilden die Hypothesen Hstart_prop, Htrian_prop und Hjustf_prop,welche eine Funktion dist entsprechend der Zeugeneigenschaft charakterisieren. Dazukommt noch die Hypothese Hpath_existence, welche Erreichbarkeit aller Knoten vomStartknoten ausdrückt.

Das Kapitel gliedert sich in drei Teile. Im ersten Teil, erläutern wir die Definitionen,welche wir zur Formulierung der globalen Zeugeneigenschaft benötigen. Im zweitemTeil, gehen wir auf die verwendeten Beweistechniken für die wichtigsten Lemmata ein.Im letzte Teil erläutern wir die Beweise zweier Hilfslemmata.

5.1. Formalisierung

Wir werden im Folgenden auf die Definitionen eingehen, mit denen wir die Zeuge-neigenschaft formulieren. Dies sind die Typdefinitionen für gewichtete Graphen undkürzeste Wege, sowie die Charakterisierung der Kürzesten-Wege-Funktion eines Gra-phen.

5.1.1. Gewichteter Graph

Knotenmenge

Zur Formalisierung eines Graphen, benötigen wir eine Repräsentation der Knotenmen-gen des Graphen. Für unsere Zwecke, genügt eine Beschränkung auf endliche Graphen.Die Idee hinter der Definition von set n, ist es, die Elemente der Knotenmenge mit derKardinalität n, mit denjenigen natürliche Zahlen zu identifizieren, welche kleiner alsn sind. Ein Element der Knotenmenge mit Kardinalität ist n, ist dadurch einfach ein

41

Axiom unique_choice

Lemma delta_existence

Axiomconstructive_indefinite_description

Lemma minimal_exists

Lemma shortest_path_existence

Lemma delta_prop_functional

Lemma dist_leq_delta

Lemma dist_geq_delta

Theorem dist_eq_delta

Hypothesis Hpath_existence

Lemma shortest_path_opt_substr

Lemma arg_min_inequality

Hypothesis Hstart_propHypothesis Htrian_prop

Hypothesis Hjustf_prop

Axiom classical

Abbildung 5.1.: Die Beweisabhängigkeiten des Theorems dist_eq_delta, welches dieglobale Zeugeneigenschaft ausdrückt. Ein Pfeile bedeutet „wird ver-wendet in“.

Term vom Typ set n. Die linke Komponente des Terms entspricht der natürlichen Zahl,welche den Knoten repräsentiert, während der Beweisterm der rechten Komponentesicherstellt, dass nur gültige Knoten deklariert werden können.Definition set n := { x : nat | x < n }.

Der Record graph

Mit der Formalisierung von Knoten als Terme vom Typ set n, definieren wir auffolgende Weise den Record graph, zur Repräsentation eines endlichen, gewichtetenGraphen:Record graph : Set := mk_graph {

V : nat;E : (set V) -> (set V) -> nat;s : (set V)

}.

Den Einträgen des Records, kommt folgende Bedeutung zu:

• V : nat entspricht der Kardinalität der Knotenmenge

• s : (set V) entspricht dem Startknoten.

42

• E : (set V) -> (set V) -> nat entspricht einer Kombination aus Kantenmen-ge und Kantenbewertungsfunktion. Wir machen folgende Konvention: Ist fürzwei Knoten u und v, der Funktionswert E u v gleich 0, so gehört die Kante(u,v) nicht zur Kantenmenge. Andernfalls, also wenn Funktionswert positiv ist,so gehört die Kante (u,v) zur Kantenmenge und hat das Kantengewicht E u v.

5.1.2. Pfade

Als nächstes definieren wir einen induktives Prädikat, welches einen Pfad in einemGraphen repräsentiert.Inductive path (g : graph) :

list (set g.(V)) -> set g.(V) -> set g.(V) -> nat -> Prop :=| zerop : forall v,

path g (v::nil) v v 0| consp : forall u v,

g.(E) u v > 0 ->forall p sv d, path g (u::p) u sv d ->path g (v::u::p) v sv (d + g.(E) u v).

Die Definition hat fünf Stellen, welchen folgende Bedeutung zukommt:

• graph Der Graph g auf den der Pfad bezogen ist.

• list (set g.(V)) Die Liste der traversierten Knoten aus g. Die Reihenfolge derKnoten, ist dabei „rückwärts“ zu verstehen. Das heißt der zuletzt traversierteKnoten eines Pfades, ist immer das erste Element in der Liste. Diese Konventionvereinfacht viele Beweise, in denen eine Fallunterscheidung mit der inversion-Taktik gemacht werden. Angewendet auf Hypothesen mit dem ::-Konstruktor,ist die Taktik in der Lage, viele triviale Beweisziele selbst zu beweisen, welchesonst mühsam per Hand gelöst werden müssten.

• set g.(V) Der zuletzt traversierte Knoten des Pfades. Die Aufnahme dieserInformation, hat sich als vorteilhaft erwiesen, da dadurch manche Hypothesen überPfade, mit der inversion-Taktik, in eine Form gebracht werden können, welchees ermöglicht (hypothetische) Pfade mit dem Konstruktor consp zu erweitern.

• set g.(V) Der erste Knoten des Pfades.

• nat Die Gesamtkosten des Pfades, also die Summe Kantengewichte entlang desPfades.

Der induktive Typ hat zwei Konstruktoren:

• zerop Mit diesem Konstruktor, kann der der leere Pfad, von einem Knoten zusich selbst mit den Kosten Null erzeugt werden. Er kann auf jeden Knoten einesGraphen angewendet werden.

43

• consp Mit diesem Konstruktor, kann ein Pfad um eine Kante erweitert werden.Die Pfadkosten erhöhen sich dabei um das Kantengewicht. Zu Erweiterung sindfolgende Prämissen erforderlich:

• g.(E) u v > 0 eine Kante im Graphen mit Kantengewicht g.(E) u v

• path g (u::p) u sv d einen Pfad von von einem beliebigen Startknotensv nach u mit Kosten d.

Mit diesen Prämissen ergibt sich folgender Pfad:

path g (v::u::p) v sv (d + g.(E) u v).

5.1.3. Kürzeste-Pfade-Funktion delta

Ein zentraler Bestandteil unserer Formalisierung, ist die Kürzest-Pfade-Funktion deltaeines Graphen. Wir definieren zunächst das Prädikat delta_prop, welches das Gesamt-gewicht eines kürzesten Pfades, von der konkreten Pfadwahl abstrahiert. Als nächsteszeigen wir, dass unter der Voraussetzung des Graphzusammenhangs, das Prädikatdelta_prop eine Funktion darstellt. Schließlich zeigen wir, wie sich mit der geleistetenVorarbeit, die Funktion delta im Set-Universum definieren lässt, sodass diese in derFormulierung von Lemmata verwendet werden kann.

Das Kürzeste-Pfade-Prädikat delta_prop

Mit Hilfe des induktiven Prädikats path, lässt sich das Prädikat shortest_path defi-nieren, welches die Existenz und Minimalität eines Pfades ausdrückt. Die Bedeutungder einzelnen Stellen des Prädikats, ist dabei die Gleiche, wie bei der Definition vonpath.

Definition shortest_path (g : graph) (p : list (set g.(V)))(v sv : set g.(V)) (d : nat) : Prop :=path g p v sv d /\ forall p' d', path g p' v sv d' -> d <= d'.

Die Pfadauswahl lässt sich mit der Einführung eines Existenzquantors abstrahieren, sodass sich für delta_prop folgende Definition ergibt:

Definition delta_prop (g : graph) (v : set g.(V)) (d : nat) : Prop :=exists p, shortest_path g p v g.(s) d.

44

Rechtseindeutigkeit und Linkstotalheit von delta_prop

Die auf allen Knoten definierte Kürzesten-Wege-Funktion für einen Graph, exis-tiert nur unter Voraussetzung, dass alle Knoten des Graphen vom Startpunkt auserreichbar sind. Die Erreichbarkeit drücken wir mit dem Prädikat path_existenceaus.Definition path_existence (g : graph) : Prop :=

forall v, exists p d, path g p v g.(s) d.

Das Lemma delta_prop_functional besagt, dass das Prädikat delta_prop rechtsein-deutig und linkstotal ist, wenn path_existence vorausgesetzt wird. Der Existenzquan-tor mit dem Ausrufezeichen, drückt die eindeutige Existenz aus. Er ist syntaktischerZucker für existentiell quantifizierte Konjunktion, welche zum Einen die Existenzausdrückt und zum Anderen die Eindeutigkeit aussagt.Lemma delta_prop_functional : forall g,

path_existence g ->forall v, exists ! d, delta_prop g v d.

Der Beweis der Eindeutigkeit von beruht hauptsächlich auf der Minimalität von kürzes-ten Pfaden und ist recht einfach. Jedoch stellte sich das im Beweis benötigte Hilfslemmashortest_path_existence (vgl. Abschnitt 5.3.1), als relativ schwierig zu beweisen her-aus.

Auswahl der Kürzesten-Pfade-Funktion delta

Intuitiv ist es einleuchtend, dass es für jede rechtseindeutige und linkstotale Re-lation P (x, y) eine Funktion f existiert, sodass P (x, f(x)) für alle x. Das Kalkülder induktiven Konstruktionen ist jedoch nicht ausdrucksstark genug, um dieseTatsache herzuleiten. Deshalb stellt die Standardbibliothek von Coq im ModulCoq.Logic.ClassicalUniqueChoice das Axiom unique_choice zur Verfügung, welchesgenau unsere Intuition ausdrückt.Axiom unique_choice :

forall (A B : Set) (P : A -> B -> Prop),(forall x : A, exists ! y, P x y) ->

(exists f, forall x : A, P x (f x)).

Um Lemma über eine Funktion formulieren zu können, muss diese im Universum Setliegen. Das Axiom unique_choice garantiert jedoch nur die Existenz einer Funktion imUniversum Prop. Einen Ausweg bildet das im Modul Coq.Logic.Epsilon befindlicheAxiom constructive_indefinite_description, welches eine Brücke zwischen denbeiden Universen Prop und Set schlägt.

45

Axiom constructive_indefinite_description :forall (A : Type) (P : A -> Prop),

(exists x, P x) -> { x : A | P x }.

Das Lemma delta_existence_lemma, welches die Existenz der Kürzesten-Pfade-Funktion garantiert, lässt sich mit der geleisteten Vorarbeit nun einfach bewei-sen:Lemma delta_existence_lemma : forall g,

path_existence g ->{ f | forall v, delta_prop g v (f v) }.

Proof.intros.apply constructive_indefinite_description.apply unique_choice.apply delta_prop_functional.assumption.

Qed.

Beweise mit der Kürzesten-Wege-Funktion delta

Der letzte Schritt ist es zu erläutern, wie man das Lemma delta_existence verwendenkann, um Aussagen über die Kürzesten-Wege-Funktion zu formulieren. Das Lemmabesagt, als Funktion betrachtet, dass wir eine Kürzeste-Wege-Funktion erhalten, wennwir diesen auf einen Term anwenden, der ausdrückt, dass ein Graph zusammenhängendist. Die Kürzeste-Wege-Funktion wird als abhängiges Paar ausgedrückt: Die linkeKomponente ist eine Funktion vom Typ set v.(g) -> nat. Die recht Komponenteentspricht einem Beweis der Aussage, dass diese Funktion für jeden Knoten v genaudas Gesamtgewichte eines kürzesten Pfades nach v zurückliefert.

Um die Kürzeste-Wege-Funktion zu verwenden, führen wir zwei Variablen in denKontext ein. Zum einen eine Variable g, welche den Graph repräsentiert, für den wirdie Kürzeste-Wege-Funktion „materialisieren“ wollen. Zum anderen die HypotheseHpath_existence, welche den Zusammenhang im Graph g ausdrückt.Variable g : graph.Hypothesis Hpath_existence : path_existence g.

Mit den Variablen lassen sich zwei Terme definieren, die genau den beiden Komponentendes abhängigen Paars entsprechen. Die Terme entstehen durch Funktionsanwendungund anschließender Projektion auf die jeweilige Komponente.Definition delta := proj1_sig (delta_existence g Hpath_existence).Definition delta_ok := proj2_sig (delta_existence g Hpath_existence).

46

5.2. Beweis der Zeugeneigenschaft

Mit den oben gemachten Definitionen haben wir nun alle Zutaten zusammen, umAussagen zu formulieren, die den Voraussetzungen der Zeugeneigenschaften entspre-chen:Variable dist : set g.(V) -> nat.

Definition start_prop :=dist g.(s) = 0.

Definition trian_prop := forall u v,g.(E) u v > 0 -> dist v <= dist u + g.(E) u v.

Definition justf_prop := forall v,v <> g.(s) -> exists u, g.(E) u v > 0 /\ dist v = dist u + g.(E) u v.

Für den Rest des Kapitels nehmen nehmen wir folgende drei Hypothesen in unserenBeweiskontext auf:Hypothesis Hstart_prop : start_prop.Hypothesis Htrian_prop : trian_prop.Hypothesis Hjustf_prop : justf_prop.

Ziel ist es unter Verwendung dieser Hypothesen, die Gleichheit der Funktion dist undder Kürzesten-Pfade-Funktion delta zu belegen.

Der Rest dieses Kapitels dient dazu, auf die verwendeten Beweistechniken und Be-sonderheiten bei der Beweisführung einzugehen. Der Beweis in Coq orientiert sichstark an den textuellen Beweis aus Kapitel 3. In Abschnitt 5.2.1 gehen wir auf dieBeweis der optimalen Substruktur von Pfaden ein. Insbesondere erläutern wir, wiesich Widerspruchsbeweise in Coq führen lassen. Abschnitt 5.2.2 beschreibt die Lösungfür ein kleines Problem, welches sich bei einer Induktion über den Aufbau der Pfadeergab.

5.2.1. Lemma shortest_path_opt_substr

Das Lemma drückt aus, dass ein kürzester Pfad vom Startknoten g.(s) über zweioder mehr Knoten nach v, die Komposition von dem kürzesten Pfad bis zum vor-letzten Knoten u und einer Kante g.(E) u v > 0 ist. Das Gesamtgewicht kürzestenPfades, ist die Summe von dem Gewicht des Subpfades und dem Kantengewichtsg.(E) u v.Lemma shortest_path_opt_substructure : forall u v p d,

g.(E) u v > 0 ->shortest_path g (v::u::p) v g.(s) (d + g.(E) u v) ->

shortest_path g (u::p) u g.(s) d.

47

Das Lemma lässt sich indirekten beweisen. Da indirekte Beweise in der intuitionis-tischen Logik von Coq, nicht ohne Weiteres möglich sind, müssen wir das ModulCoq.Logic.Classical_Prop laden, welches den Satz des ausgeschlossenem Dritten alsAxiom enthält.Axiom classic : forall P : Prop, P \/ ~P.

Die Beweisverpflichtung sieht nach dem Anwenden der intros Taktik, welche die quanti-fizierte Variablen in den Beweiskontext schiebt, folgendermaßen aus:g : graphu : set (V g)v : set (V g)p : list (set (V g))d : natHE_uv : E g u v > 0HSP_vup : shortest_path g (v :: u :: p) v (s g) (d + E g u v)______________________________________shortest_path g (u :: p) u (s g) d

Um einen Widerspruch zu erzeugen, muss die Negation der Konklusion mit in denBeweiskontext aufgenommen werden. Dies lässt sich mit folgenden Teilskript bewerk-stelligen:destruct (classic (shortest_path g (u::p) u g.(s) d)) as

[HSP_up | notHSP_up].assumption.exfalso.

Der Taktik destruct, wird die Konklusion eingebettet in das Axiom classic übergeben.Dies erzeugt zwei neue Beweisziele. Das erste Beweisziel enthält als zusätzliche Hypothe-se die Konklusion, während das zweite Ziel als zusätzliche Hypothese die negierten Formder Konklusion enthält. Das erste Ziel lässt sich einfach mit der Taktik assumptionlösen. Die letzte Anweisung verändert die Konklusion zu False. Nach Anwendung desTeilskripts sieht das Beweisziel folgendermaßen aus:g : graphu : set (V g)v : set (V g)p : list (set (V g))d : natHE_uv : E g u v > 0HSP_vup : shortest_path g (v :: u :: p) v (s g) (d + E g u v)notHSP_up : ~ shortest_path g (u :: p) u (s g) d______________________________________False

48

Nachdem Einsetzen der Definition shortest_path und einigem aussagenlogischenSchließens nimmt die Hypothese notHSP_up folgende Form an.

notHSP_up : ~(forall (p' : list (set (V g))) (d' : nat),path g p' u (s g) d' -> d <= d')

Die Negation lässt sich nach innen ziehen, so dass die Existenz eines Pfades vom Start-knoten nach u behauptet wird, dessen Gewicht kleiner als d ist. Mit dem Konstruktorconsp lässt sich nun ein Pfad nach v konstruieren, der kürzer ist, als der in der Hypo-these HSP_vup behauptete. Ein Widerspruch lässt sich nun einfach mit der Definitionvon shortest_path und der omega Taktik konstruieren.

5.2.2. Lemma dist_leq_delta

Das Lemma entspricht der ersten Richtung des Beweises für die Zeugeneigenschaft.Der Beweis erfolgt per Induktion über den Aufbau von Pfaden und Verwendung derHypothesen Hstart_prop und Htrian_prop.

Lemma dist_leq_delta : forall v,dist v <= delta v.

Das Beweisziel vor Anwendung der induction-Taktik, sieht folgendermaßen aus:

...v : set (V g)p : list (set (V g))HP_v : path g p v (s g) (delta v)HSP_v : forall (p' : list (set (V g))) (d' : nat),

path g p' v (s g) d' -> delta v <= d'______________________________________dist v <= delta v

Die Hypothese HP_v behauptet die Existenz eines Pfades vom Startknoten g.(s) zumKnoten v. An diesem Punk scheint es sinnvoll, den Beweis per Induktion über denAufbau von Pfaden weiterzuführen. Jedoch generiert die Anweisung induction HP_vfolgendes Beweisziel für den Induktionsanfang:

...v : set (V g)HSP_v : forall (p' : list (set (V g))) (d' : nat),

path g p' v v d' -> 0 <= d'______________________________________(1/2)dist v <= 0

49

Coq benutzt unbeirrt das Induktionsprinzip für Pfade und verwirft die Information,dass die ursprüngliche Hypothese HP_v, einen Pfad vom Startknoten g.(s) ausdrückt.Ein Ausweg aus der Situation, gelingt mit folgendem Teilskript:

set (tmp_s := g.(s)) in *.assert (H_s : tmp_s = g.(s)) by reflexivity.

Es ersetzt alle Vorkommen von g.(s) in den Hypothesen durch eine neue Variabletmps_s. Weiterhin fügt es dem Beweiskontext, die Gleichung tmp_s = g.(s), unterden Namen H_s, als zusätzliche Hypothese hinzu. Mit der Taktik rewrite und derGleichung, lässt sich die Information, dass der Pfad vom Startknoten ausgeht, wiederherstellen.

5.2.3. Lemma dist_geq_delta

Das Lemma entspricht der zweiten Richtung des Beweises der Zeugeneigenschaft.Der Beweis erfolgt indirekt. Die wichtigsten Beweisschritte verwenden das Lemmadist_leq_delta, das Hilfslemma arg_min_inequality und die beiden HypothesenHstart_prop und Hjustf_prop.

Lemma dist_geq_delta : forall v,dist v >= delta v.

5.2.4. Theorem dist_eq_delta

Die Zeugenschaft ergibt sich schließlich, aus den beiden Richtungen dist_leq_delta unddist_geq_delta und der Antisymmetrie von der Kleiner-Gleich-Relation:

Theorem dist_eq_delta : forall v,dist v = delta v.

Proof.intro v.apply le_antisym.apply dist_leq_delta.apply dist_geq_delta.

Qed.

50

5.3. Hilfslemmata

5.3.1. Lemma shortest_path_existence

Das Lemma drückt aus, dass wenn ein Pfad von dem Startknoten zu einem Knotenv existiert, auch ein kürzester Pfad zu diesem Knoten existieren muss. Wir verwendendas Lemma im Beweis für die Rechtseindeutigkeit der Relation für delta_prop (Lemmadelta_prop_functional).Lemma shortest_path_existence : forall g v,

(exists p d, path g p v g.(s) d) ->exists p d, shortest_path g p v g.(s) d.

Das Lemma ist ein gutes Beispiel dafür, warum Beweisen mit einem Beweisassistentenwesentlich schwieriger sein kann, als ein Beweis mit Papier und Bleistift. Währendes bei letzterem ein Selbstläufer ist, benötigen wir in Coq eine neue Beweistechnik,nämlich das Prinzip der wohlfundierten Induktion.

Wir erläutern im Rest des Unterabschnitts, den Begriff der wohlfundierten Induktion undzeigen, wie wir diese Technik verwenden um das Lemma zu beweisen.

Wohlfundierte Relation

Sei M eine Menge, eine zweistellige Relation ≺⊆M ×M heißt wohlfundiert, wenn eskeine unendlichen absteigende Ketten gibt. Das heißt, es gibt keine unendliche Folgea1, a2, . . . von Elementen aus M , so dass ai ≺ ai+1 für alle i. Insbesondere ist, diekleiner Relation < auf den natürlichen Zahlen N wohlfundiert.

Wohlfundierte Induktion

Eine wohlfundierte Relation lässt sich verwenden um zu zeigen, dass eine Aussage füralle Elemente der Trägermenge, der Relation gilt.

Sei ≺ eine wohldefinierte Relation auf M . Um zu zeigen, dass P (x) für alle Elementeaus M gilt, genügt es zu Zeigen, dass für jedes a aus M , aus der Annahme, dassdie Aussage für die vollständige und durch a beschränkte Kette wahr ist, folgt dassauch P (a) wahr ist. Für die natürlichen Zahlen mit der kleiner Relation, lautet dasInduktionsprinzip ausformuliert folgendermaßen [Tay99]:

∀a ∈ N : (∀b ∈ N : b < a⇒ P (b))︸ ︷︷ ︸Induktionsannahme

⇒ P (a)

=⇒ ∀a ∈ N : P (a)

51

Um in Coq Beweise mit wohlfundierter Induktion zu führen, benötigen wir das ModulCoq.Arith.Wf_nat aus der Standardbibliothek. Diese stellt das Lemma lt_wf_ind zurVerfügung, welche genau das Prinzip der wohldefinierten Induktion über natürlicheZahlen mit der kleiner Relation zum Ausdruck bringt. Im Beweismodus kann dann dieTaktik induction n as [n IH] using lt_wf_ind auf eine natürliche Zahl im Beweis-kontext angewendet werden. Dies führt eine neue Hypothese IH ein, welche genau derInduktionsannahme entspricht.

Das Lemma minimal_exists

Wir können mit Hilfe wohlfundierter Induktion nun folgendes Hilfslemma beweisen, wasausdrückt, dass jede nicht-leere Relation ein kleinstes Element hat.

Lemma minimal_exists: forall (P : nat -> Prop),(exists n, P n) -> exists m, P m /\ forall p, p < m -> ~ P p.

Wir beschränken uns darauf, den Beweis in Textform zu geben. Der Beweis in Coqverläuft analog.

Beweis. Wir beweisen zunächst mit wohlfundierter Induktion für alle x ∈ N die Aussage

A(x) := P (x)⇒ (∃m : P (m) ∧ ∀p : p < m⇒ ¬P (p)) .

Sei also x eine beliebige natürliche Zahl. Wir müssen aus der Induktionsannahme

∀b : b < x⇒ (P (b)⇒ (∃m : P (m) ∧ ∀p : p < m⇒ ¬P (p)))

schließen, dass auch A(x) wahr ist. Wir nehmen an, dass P (x) wahr ist, das heißt,es bleibt zu zeigen, dass ∃m : P (m) ∧ ∀p : p < m ⇒ ¬P (p). Aus dem Satz desausgeschlossenem Dritten folgt, dass für x, entweder gilt, dass ∀p : p < x⇒ ¬P (p) oder∃m : m < x ∧ P (m). Im ersten Fall ist x also das kleinste Elemente von P , und dieAussage folgt trivialerweise. Sei alsom < x und P (m) wahr. Die Behauptung folgt durchAnwendung der äußeren und der nächst-inneren Implikation der Induktionsbehauptung.

Die ursprüngliche Version des Lemmas ist eine direkte Folge aus der Aussage

∀x : A(x).

52

Beweis von shortest_path_existence

Das Lemma shortest_path_existence kann nun einfach bewiesen werden. Dazumuss nur die Reihenfolge der Quantoren des vorderen Teils der Implikation vertauschtwerden und anschließend Lemma minimal_existence angewendet werden. Der Rest desBeweises ergibt sich durch einfaches prädikatenlogisches Schließen.

5.3.2. Lemma arg_min_inequality

Als letztes beschäftigen wir uns mit dem Hilfslemma arg_min_inequality, welches imBeweis vom Lemma dist_geq_delta verwendet wird.Variable n : nat.Variable f : { m : nat | m < n } -> nat.Variable g : { m : nat | m < n } -> nat.

Lemma arg_min_inequality : forall x,(f x < g x) -> (exists x, f x < g x /\

forall y, f y < f x -> f y >= g y).

Dies ist das einzige Lemma unserer Formalisierung, für das wir keinen Beweis gefundenhaben. Unsere Bemühungen, ähnlich wie für das Lemma minimal_existence, einen Be-weis mit wohlfundierter Induktion zu führen, sind leider fehlgeschlagen.

Eine andere Möglichkeit einen Beweis für das Lemma zu finden, ergibt sich aus derTatsache, dass der Definitionsbereich der Funktionen f und g endlich ist. Die Beobach-tung erlaubt das Definieren einer terminierenden rekursiven Funktion, die den Wertberechnet, dessen Existenz behauptet wird. Der nächste Schritt wäre, einen Korrekt-heitsbeweis für die Funktion zu führen. Mit diesen beiden Voraussetzungen lässt sich derBeweis mit der Einführungsregel für den Existenzquantor führen.

53

6. Beweis der globalenZeugeneigenschaft in Coq

In diesem Kapitel geben wir einen Überblick, über den Beweis der globalen Zeugeneigen-schaft des globalen Zeugenprädikats in Coq. Ziel ist es, das Theorem dist_eq_network_delta mithilfe des Theorems dist_eq_delta aus Kapitel 5 zu beweisen. Es garantiertdie Gleichheit der Kürzesten-Wege-Funktion des Netzwerkgraphen mit der globalenAusgabe dist des Netzwerks, unter der Voraussetzung, dass das globale Zeugenprädikaterfüllt ist.

Das Kapitel gliedert sich in zwei Teile. Im ersten Teil erläutern wir die Formalisierung derlokalen Eingabe, der lokalen Ausgabe, des lokalen Zeugenprädikats sowie dem Netzwerk-graphen. Im zweiten Teil gehen wir kurz auf den Coq-Beweis ein.

6.1. Formalisierung

Alle Definitionen unserer Formalisierung, hängen von der Anzahl der Komponentenim Netzwerk an. Wir nehmen deshalb die Variable n, welche der Komponentenanzahlentspricht, mit in den Kontext auf:Variable n : nat.

6.1.1. Lokale Eingabe einer Komponente

Die erste Definition, die wir machen besteht aus dem Record component, welcher dielokale Eingabe einer Komponente im Netzwerk repräsentiert.Record component : Set := mk_component {

is_s : bool;i : (set n);E_i : (set n) -> nat

}.

Die Definition von set ist dieselbe wie in Kapitel 5. Den Einträgen des Records kommtfolgende Bedeutung zu:

55

• is_s : bool ist genau dann wahr, wenn die Komponente der Quelle ist

• i : (set n) entspricht der Identität der Komponente

• E_i : (set n) -> nat entspricht der Nachbarschaft der Komponente. Ist fürein i, der Wert von E_i positiv, so gehört die Komponente mit der Identitäti zur Nachbarschaft und kann mit den Kosten E_i i erreicht werden. Ist derWert Null, so bedeutet dies, dass die Komponente mit der Identität i nicht zurNachbarschaft gehört.

Zugriff auf die lokale Eingabe einer bestimmten Komponente

Bei manchen der folgenden Definitionen, ist es notwendig, anhand der Identität einerKomponente, auf die lokale Eingabe der Komponente mit dieser Identität zuzugreifen.Um dies zu bewerkstelligen, nehmen wir die Existenz einer Funktion select an, welchegegeben die Identität einer Komponente, die Eingabe der Komponente mit dieserIdentität zurückliefert.Variable select : (set n) -> component.Axiom select_ok : forall i' : set n, (select i').(i) = i'.

6.1.2. Lokale Ausgabe einer Komponente

Wie in Kapitel 5 fügen wir dem Kontext, eine Funktion vom Typ set n -> nathinzu. Wir interpretieren diese als die globale Ausgabe des Netzwerks. Gemäß dieserKonvention, entspricht die lokale Ausgabe der Komponente mit der Identität i demWert dist i.Variable dist : set n -> nat.

6.1.3. Lokales Zeugenprädikat

Die Definition des lokalen Zeugenprädikats, ist mit den gemachten Definitionen jetztleicht umzusetzen. Zur Vereinfachung der Definition, haben wir darauf verzichtet, zusätz-lich die lokalen Zeugen einer Komponente zu formalisieren. Es ist jedoch offensichtlich,dass die Definitionen local_trian_prop und local_justf_prop ausschließlich dielokalen Ausgaben der Nachbarschaft verwenden.Definition local_start_prop (c : component) : Prop :=

dist c.(i) = 0.

Definition local_trian_prop (c : component) : Prop :=forall j, c.(E_i) j > 0 -> dist c.(i) <= dist j + c.(E_i) j.

56

Definition local_justf_prop (c : component) : Prop :=exists j, c.(E_i) j > 0 /\ dist c.(i) = dist j + c.(E_i) j.

Definition local_wtnss_prop (c : component) : Prop :=(c.(is_s) = true -> local_start_prop c /\ local_trian_prop c) /\(c.(is_s) = false -> local_trian_prop c /\ local_justf_prop c).

6.1.4. Der Netzwerkgraph

Um das das Theorem dist_eq_delta verwenden zu können, definieren wir einenTerm network_g vom Typ des Records graph. Dazu definieren wir zuerst network_Evom Typ set n -> set n -> nat, welche dem Eintrag E des Records, also der Kom-bination der Kantenmenge und Kantenbewertungsfunktion des Graphen entspricht.Eine Kante zwischen zwei Knoten i und j, besteht genau dann, wenn die Nach-barschaft der Komponente mit der Identität j, die Komponente mit der Identität ienthält. Die Kantengewichte entsprechen genau den positiven Funktionswerten vonnetwork_E. Den Startknoten, führen wir als die Variable start_i ein. Anschließendkonstruieren wir den Netzwerkgraph als network_g mit dem Konstruktor mk_graphdes Records.

Variable start_i : (set n).

Definition network_E (i : (set n))(j : (set n)) : nat :=(select j).(E_i) i.

Definition network_g : graph :=mk_graph n network_E (select start_i).(i).

6.2. Beweis der globalen Zeugeneigenschaft

In diesem Abschnitt gehen wir auf den Coq-Beweis der globalen Zeugeneigenschaft ein.In dem ersten Unterabschnitt legen wir die Hypothesen dar, die den Ausgangspunkfür den Beweis bilden. Im zweitem Unterabschnitt legen wir dar, wie wir das Theo-rem dist_eq_delta aus Kapitel 5 verwenden, um die Zeugeneigenschaft des globalenZeugenprädikats beweisen.

57

6.2.1. Hypothesen

Globales Zeugenprädikat

Die Hypothese Hlw_conjunction entspricht dem globalen Zeugenprädikat, also der For-derung, dass das lokale Zeugenprädikat für jede Komponente erfüllt sein muss.

Hypothesis Hlw_conjunction : forall (c : set n),local_wtnss_prop (select c).

Vorbedingung

Die Hypothesen Hstart_component_existence und Hstart_component_unique drückenaus, dass die Komponente mit der Identität start_i, die eindeutige Quelle ist.

Hypothesis Hstart_component_existence : (select start_i).(is_s) = true.Hypothesis Hstart_component_unique :

forall c, c <> (select start_i) -> c.(is_s) = false.

Zusammenhang des Netzwerkgraphen

Die Hypothese Hpath_existence drückt aus, dass jeder Knoten des Netzwerkgraphenvon der Quelle erreichbar ist.

Hypothesis Hpath_existence : path_existence network_g.

Sie wird benötigt um, wie in Kapitel 5, einen Term zu definieren, welche der Kürzeste-Pfade-Funktion delta_network_g des Netzwerkgraphen entspricht.

Definition delta_network_g := proj1_sig (delta_existence network_gHpath_existence).

Definition delta_network_ok := proj2_sig (delta_existence network_gHpath_existence).

6.2.2. Theorem dist_eq_network_delta

Das Theorem, das wir beweisen wollen, drückt aus, dass die Kürzeste-Wege-Funktiondes Netzwerkgraphen, identisch mit der globalen Ausgabe ist.

Theorem dist_eq_network_delta : forall (v : set network_g.(V)),dist v = delta_network_g v.

58

Zunächst beweisen wir drei Lemmata global_start_prop, global_trian_prop undglobal_justf_prop, welche jeweils den Voraussetzungen Hstart_prop, Htrian_propund Hjustf_prop des Theorems dist_eq_delta aus Kapitel 5 entsprechen. Das Theo-rem selber ergibt sich dann aus Anwendung dieser Lemmata mittels der Taktikapply.

59

7. Diskussion

Ziel der Arbeit war es mit formalen Methoden den zertifizierenden verteilten Bellman-Ford-Algorithmus zu verifizieren. Dabei wurde [VR15] folgend, der lokale Ansatzgewählt. Die Verifikation mithilfe des Ansatz erfolgt über zwei Meilensteine. Dererste Meilenstein ist es, die globale Zeugeneigenschaft mit einem Beweisassistentenzu beweisen. Der zweite Meilenstein ist es einen lokalen Checker-Algorithmus zuimplementieren und zu verifizieren, dass er das lokale Zeugenprädikat entscheidet.Während der erste Meilenstein erreicht ist, steht der zweite noch aus. Im weiteren Verlaufder Diskussion wollen wir uns auf drei Fragen konzentrieren:

1. Was bedarf es um den zweiten Meilenstein mit unserer Formalisierung zu errei-chen?

2. Eignet sich Coq für die Aufgabenstellung?

3. Zukünftige Arbeiten?

Der zweite Meilenstein

Der nächste Schritt der Methode ist es in Coq eine Funktion zu definieren, welchedas lokale Zeugenprädikat entscheidet. Von dieser Funktion muss die Korrektheitnachgewiesen werden. Jedoch stellte sich für uns schon der Versuch der rekursivenFunktionsdefinition mit unserer Formalisierung als schwierig heraus. Ein Problemergibt sich aus unserer Designentscheidung, einen Knoten als Term vom Typ set g.(V)darzustellen. Der Term ist ein abhängiges Paar bestehend aus einer natürlichen Zahlund einem Beweis, dass diese Zahl kleiner als g.(V) ist. Während es einfach ist, übereine natürliche Zahl rekursiv abzusteigen, muss beim rekursiven Abstieg über einenTerm vom Typ set g.(V), ebenfalls die abhängige Komponente mit angepasst werden.Dies ist uns leider nicht gelungen. Deshalb stellt sich die Frage ob zur Implementati-on, Verifikation und Extraktion der Checker, es notwendig ist unsere Formalisierunganzupassen.

Konkret wollen wir zwei Möglichkeiten zur Anpassung der Graphrepräsentation nennen,welche zumindest die Implementation der Checker vereinfachen. Eine Möglichkeit wäre,den Typ set g.(V) durch den Typ nat zu ersetzen und eine zusätzliche Hypotheseeinzuführen, welche die Wohlgeformtheit des Graphen ausdrückt. Chlipala beschreibtin [Ada11, S. 165] ein Möglichkeit zur Darstellung endlicher Mengen, welche nicht

61

auf einem abhängigen Paar sondern auf einer induktive Typdefintion beruht. DieDefinition ähnelt sehr, der von natürliche Zahlen und sollte problemlos in einer re-kursiven Funktion verwendet werden können. Dieser Typ kann in einer alternativenGraphrepräsentation die Rolle von set g.(V) einnehmen. Die Beweise müssen beieiner alternativen Repräsentation natürlich angepasst werden.

Inwiefern ist Coq für die Aufgabenstellung geeignet?

Während unsere Formalisierung sind uns zwei Punkte aufgefallen. Uns sind zweiGraphbibliotheken für Coq bekannt. Dies sind zum einen die Bibliothek GraphBasic1

von Jean Duprat und zum anderen die Bibliothek fingraph der Coq-Erweiterung ssreflect2.Beide enthalten jedoch keine Definitionen für gewichtete Graphen und kürzeste Pfade.Die Bibliotheken dementsprechend zu erweitern, würde einen nicht unerheblichenAufwand bedeuten. Im Gegensatz dazu existiert für den Theorembeweiser Isabelledie ziemlich umfangreiche Graphbibliothek GraphTheory3. Rizkallah [Riz15] benutztdiese um die Zeugeneigenschaft des Kürzesten-Pfade-Problems zu beweisen. Jedochentfällt bei Isabelle die Möglichkeit der Programmextraktion. Dies hat zur Folge, dassdie Erstellung eines verifizierten Checker-Algorithmus in Isabelle aufwändiger ist als inCoq.

Der zweite Punkt ist, dass es für die beiden unkontroversen Lemmata minimal_existsund arg_min_inequality in Coq, keine einfachen Beweise zu geben scheint. Hierlohnt sich ein Blick auf die Coq-Erweiterung ssreflect. Diese Erweiterung stellt zu-sätzliche Taktiken und Bibliotheken zur Verfügung, welche helfen können Beweisezu verkürzen. Eine Nachfrage auf der Coq-Mailingliste ergab, dass es beispielsweisefür das Lemma arg_min_inequality formuliert mit den Typen, welche ssreflect zurVerfügung stellt, einen relativ kurzen Beweis gibt. Allerdings ist uns nicht bekannt,inwiefern sich die von ssreflect bereitgestellt Typen zum funktionalen Programmiereneignen.

Die Frage ob man für die Aufgabe Isabelle Coq vorzuziehen sollte, ist schwer zu be-antworten. Wir gaben Coq den Vorzug, da die Betreuerin der Arbeit mit diesem Toolvertraut ist. Wenn man Coq verwendet, lohnt sich jedenfalls ein Blick in ssreflect zuwerfen.

Zukünftige Arbeiten

Natürlich wäre es interessant sich Zeugeneigenschaften für weitere verteilte terminie-rende Algorithmen zu überlegen und diese zu verifizieren. Weitere Herausforderung

1http://www.lix.polytechnique.fr/coq/distrib/8.2/contribs/GraphBasics.html2http://ssr.msr-inria.inria.fr/3http://afp.sourceforge.net/entries/GraphTheory.shtml

62

ergeben sich, wenn die Forderung nach der Terminierung fallen gelassen wird. Es istzu überlegen ob ein Begriff ähnlich der formalen Instanzkorrektheit entwickelt werdenkann, der sich auf diese Art von Algorithmen angewandt werden kann. Mit einemsolchen Begriff wäre zu überlegen, inwiefern mit Methoden der formale Verifikation,das Vertrauen in die korrekte Berechnung erhöht werden kann.

63

Literaturverzeichnis

[ABMR11] Eyad Alkassar, Sascha Böhme, Kurt Mehlhorn und Christine Rizkallah:Computer Aided Verification: 23rd International Conference, CAV 2011,Snowbird, UT, USA, July 14-20, 2011. Proceedings, Kapitel Verification ofCertifying Computations, Seiten 67–82. Springer Berlin Heidelberg, Berlin,Heidelberg, 2011.

[Ada11] Chlipala Adam: Certified programming with dependent types: a pragmaticintroduction to the Coq proof assistant. MIT Press, 2011.

[BC04] Yves Bertot und Pierre Castéran: Interactive Theorem Proving and ProgramDevelopment, Coq’Art:the Calculus of Inductive Constructions. Springer-Verlag, 2004.

[BG01] Henk Barendregt und Herman Geuvers: Chapter 18 - Proof-AssistantsUsing Dependent Type Systems. In: Alan Robinson, und Andrei Voronkov(Herausgeber): Handbook of Automated Reasoning, Seiten 1149 – 1238.North-Holland, Amsterdam, 2001.

[CDH+09] Ernie Cohen, Markus Dahlweid, Mark A. Hillebrand, Dirk Leinenbach,Michal Moskal, Thomas Santen, Wolfram Schulte und Stephan Tobies:VCC: A Practical System for Verifying Concurrent C. In: Theorem Provingin Higher Order Logics, 22nd International Conference, TPHOLs 2009,Band 5674 der Reihe Lecture Notes in Computer Science, Seiten 23–42.Springer, 2009.

[dNP05] Hans de Nivelle und Ruzica Piskac: Verification of an Off-Line Checkerfor Priority Queues. In: Bernhard K. Aichernig und Bernhard Beckert(Herausgeber): SEFM, Seiten 210–219. IEEE Computer Society, 2005.

[Geu09] H. Geuvers: Proof assistants: History, ideas and future. Sadhana, 34(1):3–25, 2009.

[KMMS03] Dieter Kratsch, Ross McConnell, Kurt Mehlhorn und Jeremy P. Spinrad:Certifying Algorithms for Recognizing Interval Graphs and PermutationGraphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposiumon Discrete Algorithms (SODA-03), Seiten 158–167, Baltimore, USA, 2003.SIAM.

65

[KN09] Haim Kaplan und Yahav Nussbaum: Certifying algorithms for recognizingproper circular-arc graphs and unit circular-arc graphs. Discrete AppliedMathematics, 157(15):3216 – 3230, 2009.

[McC04] Ross M. McConnell: A certifying algorithm for the consecutive-ones pro-perty. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium onDiscrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January11-14, 2004, Seiten 768–777, 2004.

[MMNS11] R.M. McConnell, K. Mehlhorn, S. Näher und P. Schweitzer: Certifyingalgorithms. Computer Science Review, 5(2):119 – 161, 2011.

[MN95] Kurt Mehlhorn und Stefan Näher: LEDA: A Platform for Combinatorialand Geometric Computing. Commun. ACM, 38(1):96–102, Januar 1995.

[NM90] Stefan Näher und Kurt Mehlhorn: LEDA: A Library of Efficient DataTypes and Algorithms. In: Mike Paterson (Herausgeber): ICALP, Band 443der Reihe Lecture Notes in Computer Science, Seiten 1–5. Springer, 1990.

[NPW02] Tobias Nipkow, Lawrence C. Paulson und Markus Wenzel: Isabelle/HOL— A Proof Assistant for Higher-Order Logic, Band 2283 der Reihe LNCS.Springer, 2002.

[PCG+15] Benjamin C. Pierce, Chris Casinghino, Marco Gaboardi, Michael Greenberg,Catalin Hriţcu, Vilhelm Sjoberg und Brent Yorgey: Software Foundations.Electronic textbook, 2015.

[Pel00] David Peleg: Distributed Computing: A Locality-sensitive Approach. Societyfor Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.

[PM11] Christine Paulin-Mohring: Introduction to the Coq Proof-Assistant forPractical Software Verification. In: Bertrand Meyer und Martin Nordio(Herausgeber): LASER Summer School, Band 7682 der Reihe Lecture Notesin Computer Science, Seiten 45–95. Springer, 2011.

[Ray13] Michel Raynal: Distributed Algorithms for Message-Passing Systems. Sprin-ger Publishing Company, Incorporated, 2013.

[Riz15] Christine Rizkallah: Verification of Program Computations. Dissertation,Universität des Saarlandes, Saarbrücken, 2015.

[Tay99] Paul Taylor: Practical Foundations of Mathematics, Band 59 der ReiheCambridge studies in advanced mathematics. Cambridge University Press,1999.

[VR15] Kim Völlinger und Wolfgang Reisig: Certifcation of Distributed AlgorithmsSolving Problems with Optimal Substructure. In: Software Engineering andFormal Methods, 2015.

66

A. Coq-Beweise

Die komplette Formalisierung inklusive aller Beweise ist unter folgender URL verfügbar:https://github.com/asherrecv/coq-shortest-path

67

Selbständigkeitserklärung

Ich erkläre hiermit, dass ich die vorliegende Arbeit selbständig verfasst und noch nichtfür andere Prüfungen eingereicht habe. Sämtliche Quellen einschließlich Internetquellen,die unverändert oder abgewandelt wiedergegeben werden, insbesondere Quellen fürTexte, Grafiken, Tabellen und Bilder, sind als solche kenntlich gemacht. Mir ist bekannt,dass bei Verstößen gegen diese Grundsätze ein Verfahren wegen Täuschungsversuchsbzw. Täuschung eingeleitet wird.

Berlin, den 23. Mai 2016

69