Upload
elfi-heidorn
View
109
Download
0
Embed Size (px)
Citation preview
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
Benutzer
A AA
Robustes DNS
Aufgabe des DNS: Namen IP-Adressen
Aufgabe hier: übersetze Namen in Identitäten
Besserer Schutz?
Amazon
Benutzer
A AA
Angreifer
Angreifer
Angreifer
Robustes DNS
Google hat festen Link zu Amazon: kein Angreifer kann Amazon übernehmen
Amazon
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
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
Benutzer
A AA
Angreifer
Robustes DNS
Problem: Angreifer startet Sybil-Atacken (d.h. generiert beliebig viele Benutzer)
Amazon
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?