Verteilte Algorithmen und Datenstrukturen Christian Scheideler Institut für Informatik Universität...

Verteilte Algorithmen und Datenstrukturen

Christian Scheideler

Institut für Informatik

Universität Paderborn

Verteilte Algorithmen und Datenstrukturen

Vorlesung: Mi 14-16 Uhr, F0.530

Übung: Mi 16-17 Uhr, F0.530

Webseite: http://www.cs.uni-paderborn.de/?id=10640

Prüfung: • 50%: Softwareprojekt• 50%: mündliche Prüfung• Notenverbesserung um 0,3: Präsentation in Übung

Voraussetzungen: Grundkenntnisse in Algorith-men und Datenstrukturen

Verteilte Algorithmen und Datenstrukturen

Übungsaufgaben: • wöchentliche Ausgabe und Abgabe am

Mittwoch • teils theoretisch, teils praktisch

Skript und Übungsaufgaben: Webseite

Bücherempfehlungen: kein Buch (Vorlesung basiert auf neuesten Ergebnissen)

Verteilte Algorithmen und Datenstrukturen

Inhalt:

1. Einführung

2. Netzwerktheorie

3. Routing und Scheduling

4. Hashing und Caching

5. Verteilter Konsens und Transaktionen

6. Dynamische Netzwerke für Zusammenhang(Cliquen, Cliquegraphen und Expander)

7. Dynamische Netzwerke für Routing(Verankerte und dezentrale Netzwerke)

8. Verteilte Datenstrukturen

9. Drahtlose Netzwerke

Einführung

Übersicht:• Motivation• Was ist Robustheit?• Das Subjects Paradigma

(Grundlage für verteilte Programme)• Die Simulationsumgebung• Beispiele

Einführung

Sequentielle Algorithmenund Datenstrukturen

Verteilte Algorithmenund Datenstrukturen

Einführung

Was sind Kernprobleme für verteilte Systeme?

Verteilte Systeme

• Jedes verteilte System benötigt einen zusammenhängenden Wissensgraph über die Teilnehmer.

• Solch ein Graph: Overlaynetzwerk

Verteilte Algorithmen und Datenstrukturen

Inhalt:

1. Einführung

2. Netzwerktheorie

3. Routing und Scheduling

4. Hashing und Caching

5. Verteilter Konsens und Transaktionen

6. Dynamische Netzwerke für Zusammenhang(Cliquen, Cliquegraphen und Expander)

7. Dynamische Netzwerke für Routing(Verankerte und dezentrale Netzwerke)

8. Verteilte Datenstrukturen

9. Drahtlose Netzwerke

Verteilte Systeme

Skalierbares Overlaynetzwerk: • Hoher Durchsatz an Nachrichten• Jede Nachricht benötigt nur geringe Zeit

Verteilte Algorithmen und Datenstrukturen

Inhalt:

1. Einführung

2. Netzwerktheorie

3. Routing und Scheduling

4. Hashing und Caching

5. Verteilter Konsens und Transaktionen

6. Dynamische Netzwerke für Zusammenhang(Cliquen, Cliquegraphen und Expander)

7. Dynamische Netzwerke für Routing(Verankerte und dezentrale Netzwerke)

8. Verteilte Datenstrukturen

9. Drahtlose Netzwerke

Verteilte Systeme

Skalierbares Speichersystem: • Hoher Durchsatz an read/write Operationen• Jede Operation benötigt nur geringe Zeit

Verteilte Algorithmen und Datenstrukturen

Inhalt:

1. Einführung

2. Netzwerktheorie

3. Routing und Scheduling

4. Hashing und Caching

5. Verteilter Konsens und Transaktionen

6. Dynamische Netzwerke für Zusammenhang(Cliquen, Cliquegraphen und Expander)

7. Dynamische Netzwerke für Routing(Verankerte und dezentrale Netzwerke)

8. Verteilte Datenstrukturen

9. Drahtlose Netzwerke

Verteilte Systeme

In offenen verteilten System kann sich die Menge der Teilnehmer stark mit der Zeit verändern.

Problem: wie erhalten wir die Funktionalität eines verteilten Systems??

Verteilte Systeme

Drei grundlegende Ansätze:

verankert peer-to-peerserver-basiert

strukturierte Overlaynetzwerke

Verteilte Algorithmen und Datenstrukturen

Inhalt:

1. Einführung

2. Netzwerktheorie

3. Routing und Scheduling

4. Hashing und Caching

5. Verteilter Konsens und Transaktionen

6. Dynamische Netzwerke für Zusammenhang(Cliquen, Cliquegraphen und Expander)

7. Dynamische Netzwerke für Routing(Verankerte und dezentrale Netzwerke)

8. Verteilte Datenstrukturen

9. Drahtlose Netzwerke

Verteilte Datenstrukturen

Transparente Datenstrukturen:• Verteilte Hashtabelle• Verteilte Suchstrukturen• Verteilter Heap

Transparenz: keine extra Links notwendig

Verteilte Systeme

Korrektheit, Skalierbarkeit, Robustheit,...

Verteilte Algorithmen und Datenstrukturen

Inhalt:

1. Einführung

2. Netzwerktheorie

3. Routing und Scheduling

4. Hashing und Caching

5. Verteilter Konsens und Transaktionen

6. Dynamische Netzwerke für Zusammenhang(Cliquen, Cliquegraphen und Expander)

7. Dynamische Netzwerke für Routing(Verankerte und dezentrale Netzwerke)

8. Verteilte Datenstrukturen

9. Drahtlose Netzwerke

Verteilte Systeme

Robustheit: • Operationen arbeiten korrekt selbst unter

massiven Angriffen • System kann sich selbständig erholen

Fundamentales Dilemma

• Skalierbarkeit:Minimiere Ressourcen für Operationen

• Robustheit:Maximiere Ressourcen für Angriffe

Skalierbare Systeme leicht zu attackieren!!Trotzdem erstaunlich gute Lösungen möglich

Konsensus5

83

2

3

33

3

Konsensus

Modell:• n Spieler• Jeder Spieler kennt alle anderen• Zeit verläuft in synchronen Fragerunden• Pro Fragerunde kann jeder Spieler nur

O(1) viele Fragen stellen / beantworten

5 8Was ist Deine Nummer?

8.

Konsensus

Alle Spieler ehrlich:• Minimum-Regel:

• Nach O(log n) Runden haben alle Spieler dieselbe Nummer m.h.W.

x yWas ist Deine Nummer?

y.

x:=min{x,y} Zufälliger Spieler

Konsensus

Ein Spieler unehrlich:• Minimum-Regel: unbeschränkte Laufzeit.

5 1Was ist Deine Nummer?

5.

irgendwann später…

5 1Was ist Deine Nummer?

1.

Konsensus

Besser: Median-Regel:

• O(log n) Runden m.h.W.: ehrliche Spieler• O(log n loglog n): max n gegn. Spieler

x yNummer?

y.

x:=median{x,y,z} Zufälliger Spieler

z

Zufälliger Spieler

Nummer?

z.

Sie sind gefeuert!

DoS-resistentes Informationssystem

Past-Insider-Attacke: Gegner kennt alles über System bis (unbekannte) Zeit t0

Ziel: skalierbares Informationssystem, so dass alles, was nach t0 eingefügt oder aktualisiert worden ist, sicher (m.h.W.) gegen past-insider DoS Attacken ist

Robustheit

Entkopplung bzgl. Ort, Zeit und Fluss.

• Ortentkopplung: interagierende Prozesse müssen nicht ihre physikalischen Orte kennen

• Zeitentkopplung: interagierende Prozesse müssen nicht zur selben Zeit miteinander interagieren

• Flussentkopplung: die Ausführung einer Aktion innerhalb eines Prozesses sollte nicht von anderen Prozessen abhängen

Gesetze der Robustheit

Entkopplung und Selbsterholungvon jedem Zustand

Nur dann können verteilte Systeme

hochgradig skalierbar und verfügbar sein

Gesetze der Robustheit

Vollständige Kontrolle über Ressourcen

und Informationen

Nur dann können verteilte Prozesse sicher

ausgetauscht werden und miteinander interagieren

Gesetze der Robustheit

1. Eignerzustimmung und Kontrolle2. Geringste Ausgesetztheit3. Selbsterholung4. Entkopplung[POLA, K. Cameron: The laws of identity, D. Epp: The eight rules of security,…]

Gesetze der Robustheit

Eignerzustimmung und Kontrolle:• Eindeutig definierte Zuständigkeiten• Vollständige Kontrolle über Info & Ressourcen

Geringste Ausgesetztheit:• Nicht mehr Wissen als notwendig• Vollst. Kontrolle über Informationsfluss

Selbsterholung:• Erholung muss von jedem Zustand aus möglich sein

(solange die Plattform noch im legalen Zustand ist)

Entkopplung: • keine Synchronisation notwendig für die Primitive

Subjects Paradigma

• Subjekte

• Objekte

• Relaypunkte

• Aktionen

Subjects Paradigma

Subjekte:• atomar• gebunden an Ort• statische Menge an Aktionen• sequentielle Abarbeitung von Aufgaben• Objekte und erzeugte Relays und Subjekte lokal

zum Subjekt• keine Identität, d.h. Informationsaustausch ist

nur über Relays möglich

Wichtig fürVerifikation

und Kontrolle!

Wichtig fürVerifikation

und Kontrolle!

Subjects Paradigma

atomar, anonym, aktiv, unbeweglich, enthält Objekte, Relays und Aktionen

atomar, anonym, passiv, beweglich

atomar, Identitäten erzeugbar, passiv, unbeweglich

atomar, anonym, unbeweglich,garantierte Terminierung

Subjekt

kann Verbindungen aufbauen,die nicht umlegbar sind

kann Objekte besitzen undAktionen ausführen

kann Subjekte erzeugen

Relaypunkte

Ausgehende Kante bei Erzeugung festgelegt.

a) ohne Identität b) mit Identität

R

Keine Anwender-zugreifbare Identität, aber (dunkle) Identitätsobjekte erzeugbar

R

A R

Erstes Kennenlernen

R

Öffentliche Identität (TAN)

• Subjekte besitzen keine Identität• Identitäten nicht kopierbar, nur einmal verwendbar• Relayverbindungen können nicht umgelegt werden

A B

R

Vorstellung

B>A

A B

CA>B

Zustimmung und Kontrolle, geringste Ausgesetztheit?

R>B

R

Delegation von Rechten

Zustimmung und Kontrolle, geringste Ausgesetztheit?

Quelle des Objekts

R’ R‘‘R

R

Startpunkt des Objekts wird dem Objekt mitgegeben.Damit kann bei R’’ überprüft werden, wer die Quelle des Objekts war.

Nachkommen

Ressourcenkontrolle

Mutter Kind

Kind in derselben Maschine wie Mutter.

Nachkommen

EinfrierenLöschen

Clones

Erinnerung: Subjekte unbeweglich, atomar

A‘A B A’

Zustimmung und Kontrolle, geringste Ausgesetztheit?

Clones

Objekte prinzipiell völlig offen gegenüber Eigner.Objekte mit Zugriffsrechten: Clones

A B S

Zustimmung und Kontrolle, geringste Ausgesetztheit?

OO

Erholbarkeit

• Existierende Objekte immer erreichbar, da immer Subjekt zugeordnet

• Nachkommenbaum der Subjekte immer zusammenhängend und damit Ressour-cenkontrolle lückenlos

• Kommunikation von Kind zu Mutter immer vorhanden, und damit immer schwacher Kommunikationszusammenhang der Subjekte

Subjects Paradigma

• Simulationsumgebung existiert basierend auf C++

• Vorlesungsseite: – Einführung in C++ – Link auf frei verfügbaren Compiler– Subjects Library und Beispielprogramme

Objekte

Object: Basisklasse für Objekte• Container für dynamische Daten• keine Identität (nur über Referenz

erreichbar)• keine Aktionen• transferierbar, aber hat zu jedem Zeitpunkt

eindeutigen Besitzer (Subjekt)• Besitzer kann auf alle Anwendungsdaten

innerhalb vom Objekt zugreifen

Objekte

Von Object abgeleitete Klassen:• Identity: enthält Identität eines Relaypunkts• Clone: enthält “schlafendes” SubjektObjekte dieser Klassen sind nur einmal verwendbar, und auf

deren Inhalte können Subjekte nicht zugreifen.

Benutzerdefinierte Objekte:

ObjectType(<UserObject>){public: <benutzerdefinierte Variablen>

<evtl. Konstruktor>};

Relays

Relay: Klasse für Relaypunkte• nicht transferierbar• nur eine ausgehende Kante, die bei

Generierung erzeugt wird und dann nicht mehr umgelegt werden kann

• anonym, aber Identitäten können für eingehende Kanten generiert und transferiert werden

Relays

Benutzerdefinierte Relays:

RelayType(<UserRelay>){public: <benutzerdefinierte Variablen>

<evtl. Konstruktor>};

Identitäten

Anweisungen:• new Identity(Relay *r): erzeugt neue

öffentliche Identität von Relay r• new Identity(Relay *r, Relay *r’): erzeugt

private Identität von r für r’• delete i: löscht Identität

Clones

Anweisungen:• publicClone(<UserSubject>,NONE) oder

publicClone(<UserSubject>,<UserObject> *o): erzeugt öffentliches Clone vom Typ UserSubject

• privateClone(<UserSubject>,NONE, Relay *r) oderprivateClone(<UserSubject>,<UserObject> *o, Relay *r): erzeugt privaten Clone vom Typ UserSubject für Relay r

• delete c: löscht Clone

Subjekte

Subject: Basisklasse für Subjekte• atomar, anonym• können Objekte und Relays besitzen• nicht transferierbar• Kindsubjekt immer am selben Ort wie Mutter• frei definierbare, aber von Anfang an fest

vorgegebene Aktionen, die auf alle Anwen-dungsdaten innerhalb eines Subjekts und deren Objekte zugreifen können

Subjekte

Benutzerdefiniertes Subjekt:

SubjectType(<UserSubject>){ protected: <benutzerdefinierte Variablen> <interne benutzerdefinierte Methoden>

public: FirstAction(<UserSubject>,<Action>)

<benutzerdefinierte Aktionen>};

Subjekte

Alle extern aufrufbaren Aktionen müssen

folgende Form haben:

Action <UserAction>() {…}

Action <UserAction>(<UserObject> *o) {…}

Start der Subjects-Umgebung:

runSubjects(<UserSubject> *s, <UserObject> *o, t); // t=0: laufe, bis keine Aufgaben mehr

Subjekte

Reservierte Variablen:• ulong _debugID: eindeutige Identität für

Debugging• Relay *parent: Relay zu Muttersubjekt• ulong source: ID des Relays, von dem

Aufruf kam (lokal eindeutig)• ulong sink: ID des Relaypunkts, der Aufruf

empfangen hat

Subjekte

Anweisungen:• new(<UserSubject>,NONE) oder

new(<UserSubject>,<UserObject> *o): erzeugt neues Subjekt

• wakeupClone(Clone *c): aktiviert Subjekt im Clone c

• delete(s): löscht Subject (muss Kind sein, damit möglich)

Wichtig: bei new/delete “()” benutzen!

Subjekte

Anweisungen:• new Relay: erzeugt neuen Relaypunkt, dessen

ausgehende Kante zum Subjekt selbst zeigt• new Relay(Identity *i): erzeugt Relaypunkt mit

Verbindung zum Relaypunkt mit Identität i (damit wird i invalidiert)

• delete r: löscht Relaypunkt r• call(verb, object | NONE): generiert Anfrage

verb(object) für eigenes Subjekt• rcall(verb, object | NONE): generiert Anfrage

verb(object) für Ziel von Relay r

Subjekte

Anweisungen:• wakeup(s): weckt Subjekt s auf (und alle

seine Nachfolger im Stammbaum)• freeze(s): friert Subjekt s ein (und alle

seine Nachfolger im Stammbaum)• int idle(): gibt an, ob noch Anfragen für

Subjekt• int idle(Relay *r): gibt an, ob noch

ausgehende Anfragen für Relay r

Subjects Paradigma

• Ursprung: Hewitts Actor Modell (1973)für neuronale Netzwerke

• Seitdem hauptsächlich Arbeiten im Bereich der Betriebssysteme und Programmiersprachen(EROS, E Language, Singularity,…)

Beispiele

• Hello-Beispiele und anderes auf der Webseite

• SPAM-resistentes Email-System• Robustes DNS• Digital Rights Management• Online Banking

SPAM-resistente Emails

Einsichten:• Grundlegendes Problem: ungenehmigte

Emails• Genehmigung muss an Absender und

nicht an Emails geknüpft sein • Genehmigungen müssen zurücknehmbar

sein• Die Identität des Absenders (und des

Adressaten) darf nicht transferierbar sein.

SPAM-resistente Emails

Subjects: anfangs kann niemand mit Alice kommunizieren (nicht einmal die Mutter).

Alice

SPAM-resistente Emails

Alice und Bob sind nicht verbunden:

Bob kann keine Nachricht direkt an Alice schicken.

Alice Bob

SPAM-resistente Emails

Erste Kontaktaufnahme:

SPAM von Bob: Alice löscht R

R

Öffentliche Identität (TAN)

Alice Bob

R

SPAM-resistente Emails

B>A

Alice Bob

CarolA>B

R>B

R

Vorstellung:

SPAM-resistente Emails

Problem: Alice will mit David kommunizie-ren, kennt aber David nicht.

Lösung: System, das Beziehungen zeigt? (wie Xing, Facebook,…)

Alice Bob Carol David

Robustes DNS

Root ServerBenutzer

DNS: Hierarchische Menge von Servern

Internet Internet

Robustes DNS

Aufgabe des DNS: Namen IP-Adressen

Aufgabe hier: übersetze Namen in Identitäten

Besserer Schutz?

Amazon

Google

Benutzer

A AA

Robustes DNS

Aufgabe des DNS: Namen IP-Adressen

Aufgabe hier: übersetze Namen in Identitäten

Besserer Schutz?

Amazon

Google

Benutzer

A AA

Angreifer

Angreifer

Angreifer

Robustes DNS

Google hat festen Link zu Amazon: kein Angreifer kann Amazon übernehmen

Amazon

Google

Benutzer

A AA

Angreifer

Robustes DNS

Benutzer hat festen Link zu Google: kein Angreifer kann Google übernehmen, es sei denn, Benut-zer fällt auf Phishing-Atacke rein…

Amazon

Google

Benutzer

A AA

Angreifer

Robustes DNS

Benutzer versucht, alle Identitäten von Amazon (z.B. für DoS-Attacke) an sich zu ziehen: Google kann das erkennen und schließt Benutzer aus.

Amazon

Google

Benutzer

A AA

Angreifer

Robustes DNS

Problem: Angreifer startet Sybil-Atacken (d.h. generiert beliebig viele Benutzer)

Amazon

Google

Benutzer

A AA

Angreifer

Digital Rights Management

Problem: Digitaler Content ist kopierbar.Hardware:• Kassettenrekorder• CD-Brenner• DVD-Brenner• Blueray-BrennerSoftware:• Digitaler Schutz knackbar / umgehbar

Hauptproblem

Digital Rights Management

Software-Attacken:• Benutzer installiert Ripping-Software, um

Raubkopien seines Contents zu erstellen• Benutzer holt sich Content von einer

Tauschbörse• Legaler Content vom Benutzer wird über

Virus / Trojaner von außen gestohlen

Digital Rights Management

Nutzungsproblem: DRM-Modelle der Provi-der oft sehr eingeschränkt, was legale Nutzer verärgert.

Mögliche Modelle für Provider und Nutzer:1. Content kopierbar, aber nur von einem

Benutzer verwendbar.2. Content nicht kopierbar, aber beliebig

weitergebbar.

Digital Rights Management

2. Modell: Content nicht kopierbar, aber beliebig weitergebbar.

Durch Clones umsetzbar:

Sony Alice Bob

Song XX

X

Song X

X X

Digital Rights Management

2. Modell: Content nicht kopierbar, aber beliebig weitergebbar.

Vorteil: Nutzer kann X nicht inspizieren, da Zugriff über Sony-Subjekt kontrolliert.

Sony Alice Bob

X

Digital Rights Management

2. Modell: Content nicht kopierbar, aber beliebig weitergebbar.

Vorteil: X kann nicht von außen (ohne Hand-lung von Alice) gestohlen werden.

Sony Alice Bob

X

Online Banking

Problem: Sichere Transaktionen zwischen Kunde und Bank

Online Banking

Umsetzung in Subjects-Umgebung:

Probleme:• R kommt nicht von Bank• R wird durch Gegner abgefangen

R

Öffentliche Identität (TAN)

Bank Kunde

R

Online Banking

Probleme:• R kommt nicht von Bank• R wird durch Gegner abgefangen

Lösung: Verwende sicheren Offline-Transfer (persönliche Abholung, Brief)

Weitere Probleme:• Phishing Attacken auf Kunde• Kunde möchte von beliebigem Rechner Zugriff

Online Banking

Phishing Attacke auf Kunde:

Bank

R

Angreifer

R’

Kunde

R‘

Angreifer kann keinen Kontaktzu R herstellen!

Online Banking

Phishing Attacke auf Kunde:

Bank

R

Angreifer

R’

KundeR‘

Bank akzeptiert nur Anfragen,die bei R starten!

Online Banking

Zugriff über beliebigen Rechner:

Verwende z.B. USB-Stick mit Minirechner, um Emulationsproblem zu umgehen?

Details noch zu klären…

Fragen?