Self-Testing/Correcting Protocols

Carsten Rebbien225868

Inhalt Einführung Begriffsklärung / Definitionen Byzantine Agreement / Crusader

Agreement Funktionen Self-Tester für Agreement Funktion Self-Corrector für Agreement

Funktion Zusammenfassung

Einführung Testen von Programmen:

Ergebnisse müssen bekannt sein Wie bekannte Ergebnisse ermitteln?

„Von Hand“ prüfen Programm zur Bestimmung der Ergebnisse

Programmchecker Läuft parallel zum eigentlichen

Programm Prüft nur Korrektheit einzelner Eingaben

Einführung Selbsttestender Programmchecker (Self-

Tester) Ruft zu testendes Programm P mit Eingabe x auf Bestimmt Wahrscheinlichkeit mit der f(x)=P(x) gilt

Selbstkorrigierendes Programm (Self-Corrector) Korrigiert fehlerhaftes Programm, falls die vom

Self-Tester errechnete Wahrscheinlichkeit niedrig genug ist

Begriffe / Definitionen Verteilte Funktion: Φ : Vn → Rn, V=R

mit Bezug auf Umgebung: f : Wn → Sn

wobei W=V (S=R) plus Charakteristika zur Etikettierung der Prozessoren

Protokoll: Implementierung von f vollständig verbundenes Netzwerk

von n Prozessoren pro Prozessor ein Programm

Begriffe / Definitionen Orakelprotokoll P :

Protokoll P ruft Protokoll P auf (Schreibweise: P P) Dv : W‘keitsverteilung nach der die Eigaben

vi , 1≤i≤n, bestimmt werden Ε : Umgebung in der P läuft P[i]: Ausgabe von Prozessor i error(f,P,Dv ,Ε):W‘keit, dass f P β: Zufriedenheitsparameter

Begriffe / Definitionen Self-Testing Protokoll T :

If error(f,P,Dv ,Ε)≤ε1 then Pr(i:T P[i]="PASS") ≥ 1-β

If error(f,P,Dv ,Ε)≥ε2 then Pr(i:T P[i]="FAIL") ≥ 1-β

0 ≤ ε1 < ε2 ≤ 1

Self-Correcting Protokoll C: If error(f,P,Dv ,Ε)≤ε then Pr(i: C P[i]=f[i]) ≥ 1-β 0 ≤ ε < 1

Begriffe / Definitionen „Klein-o“-Bedingung:

Berechnung erfolgt in mehreren Runden Laufzeit = Anzahl der Runden

Laufzeit von T P und C P muss o(R) betragen, wenn Aufrufe von P als o(1) aufgefasst werden, R= minimale worst-case Laufzeit von P

Agreement Funktion Byzantine Agreement (BA):

Quelle s sendet Startwert vs V nach Termination geben alle korrekten

Prozessoren diesen Wert wieder aus V: Eingabemenge B = {faulty, nonfaulty} T = {true, false} BA: (V B)n → (V T)n

Agreement Funktion Gültigkeitsbedingung:

i bi = nonfaulty

Agreement Bedingung:

Crusader Agreement (CA): genau wie Agreement Bedingung:

falls s nicht korrekt ist, entscheiden sich nur korrekte Prozessoren, die nicht ausdrücklich wissen, dass s nicht korrekt ist, für den gleichen Wert

Self-Tester für Agreement Funktion (BA), für Prozessor i

Self-Tester für Agreement Funktion (BA), für Prozessor i

Self-Tester für Agreement Funktion (BA), für Prozessor i

Yl[i] :0/1-Zufallsvar. (Prozessor i wird im lten Aufruf mit fail charakterisiert)

Sei μi=E[Yl[i]], Korollar 1:

Sei μ' ≤ μi für alle i, und sei N=1/μ'16ln(2n/β). Dann Pr(i: Y[i] ≤ μ'/2) ≤ β

Korollar 2: Sei μ"≥ μi für alle i, und sei N=1/μ"4ln(2n/β).

Dann Pr(i: Y[i] ≥ 2μ") ≤ β

Self-Tester für Agreement Funktion (BA), für Prozessor i

Theorem 1: Der Agreement_Tester(AT) ist ein (ε/8,ε)-Self-Tester.

Beweis: Erwartete Ausgabe: E[Y[i]]=μi=δ error, ½<δ<1 (error≥ε) Sei μ'= ε/2 und N=1/ε32ln(2n/β). Laut Kor.1 ist

Pr(i:Y[i]≤ε/4)≤β. Jedoch, im AT gibt Prozessor i "FAIL" aus falls Y[i]>ε/4. Also, falls error≥ε gibt der AT mit einer W‘keit von mind. 1- β "FAIL" für jeden Prozessor aus.

(error≤ε/8) Sei μ"= ε/8 und N=1/ε32ln(2n/β). Laut Kor.2 ist Pr(i:Y[i]≥ε/4)≤β. Jedoch, falls Y[i]<ε/4 gibt Prozessor i "PASS" aus. Also, falls error≤ε/8 gibt der AT mit einer W‘keit von mind. 1- β "PASS" für jeden Prozessor aus.

Self-Corrector für Agreement Funktion (BA), für Prozessor i

Self-Corrector für Agreement Funktion (BA) Proposition: Sei ≥ ¾ und seien X1,X2,...,Xn

unabhängig gleichverteilte Zufallsvariablen mit Werten 0 und 1, so dass Pr[Xi=1]≥, i=1,2,...,N. Dann

Beweis: Chernoff-Schranken

Self-Corrector für Agreement Funktion (BA) Theorem 2: Der Agreement_Corrector(AC) ist

ein ε-Self-Corrector für BA. Beweis: Angenommen, für alle i ist bei einem

einzigen Durchlauf mit einer W‘keit von höchstens ε die Ausgabe des Prozessors i P[i]r (P[i]x-r). Dann geben beide Aufrufe von P mit einer W‘keit von mind. 1-2ε ein korrektes Ergebnis zurück. Mit =1-2ε und n Durchläufen folgt die Aussage direkt aus der Proposition.

Zusammenfassung Programmchecker Byzantine Agreement Funktion Selbsttestende/-korrigierende

Protokolle Self-Tester für BA Self-Corrector für BA