1 Agenten und verteilte Anwendungen Synchronisation und Konsistenzerhaltung in verteilten...

Agenten und verteilte Anwendungen

Synchronisation und Konsistenzerhaltung in verteilten Anwendungen

13. März 2003

Gliederung

• Grundlagen verteilter Anwendungen

• Einfache Verfahren zur

Nebenläufigkeitskontrolle

• Spezielle Verfahren zur

• Zusammenfassung

Grundlagen verteilter Anwendungen

• Definition von verteilten Anwendungen nach [BS2000, Seite 59]:

... application, whose functionality is split into a set of cooperating, interacting functional units...

... these functional units can be assigned to different machines...

... the functional units communicate with each other...

Aufbau von Verteilten Systemen

Verteiltes Rechensystem

Netzwerk Netzwerk

Verteiltes Ablaufsystem(Verwaltung der Systemobjekte auf die die Komponenten der Anwendung abgebildet werden) evtl. verteiltes BS

Verteilte AnwendungKomponente 1 Komponente n

...Komponente 2

Konsistenz (traditionell) (1)

• Aus Datenbanktechnik: Serialisierbarkeit als Korrektheitskriterium des Transaktionskonzeptes

Def.: Eine Transaktion ist eine Folge von Operationen, die die Datenbank von einem konsistenten Zustand in einen neuen Zustand überführen, wobei das ACID-Prinzip eingehalten werden muss.

• Atomicity

• Consistency

• Isolation

• Durability

Konsistenz (traditionell) (2)

• ABER:– Nicht alle Eigenschaften des Konsistenzkonzeptes

der Datenbanken bei verteilten Anwendungen erwünscht:

• Isolation der Benutzer• Hohe Verfügbarkeit eventuell wichtiger

Operationsgranularität

• Globale Daten (d.h. Daten mehrerer Komponenten)• Nebenläufige Zugriffe auf globale Daten führen

eventuell zu Inkonsistenz• Datei als globales Datum mögliche Zugriffseinheit

– Ganze Datei oder– Kapitel oder– Buchstabe usw.

• feine Granularität hoher Netzwerkverkehr

• grobe Granularität geringer Grad an Nebenläufigkeit

Konsistenz (erweitert)

• One-Copy-Serializable– Serialisierbarkeit im traditionellen Sinn bezüglich

eines Replikats– Zwei Operationen, die im Konflikt stehen, werden

auf allen Replikaten in der gleiche Reihenfolge ausgeführt.

• Mutual Consistency– alle Replikate eines Datums identisch oder – konvergieren zum gleichen Zustand

Nebenläufigkeitskontrolle (CC)

• Wichtig um Daten konsistent zu halten• Jedoch Erweiterung bei geographischer

Verteilung der Rechner:– Absturz einzelner Rechner Verfügbarkeit von

Daten– Ausfall von Kommunikationsverbindungen

Probleme bei verteilten Anwendungen, da häufig eine sehr hohe Verfügbarkeit gewünscht wird.

Partitionierung

schwer zu erkennenhöchstens in einer Partition darf

geschrieben werden

Partition 1 Partition 2

Gliederung

• Einfache Verfahren zur Nebenläufigkeitskontrolle (CC)

• Zusammenfassung

Klassifikation der Verfahren

optimistische pessimistische

zentrale Kontrolle dezentrale Kontrolle

Optimistische Verfahren

• Erlauben inkonsistente Zustände– Bei Datenbank: versucht alle Transaktionen nebenläufig

abzuhandeln. Bei Fehler wird Transaktion im Nachhinein abgebrochen

Je grober die Granularität, desto mehr KonflikteJe mehr Komponenten, desto mehr Konflikte

Konflikt kann bei verteilten Anwendungen nicht immer durch Anwendung behandelt werden (evtl. Benutzeraktion notwendig)

Pessimistische Verfahren

• Inkonsistente Datenbestände werden nicht geduldet

• Klassifikation:

Zentrale Kontrolle Dezentrale Kontrolle

Ausgezeichnete Kontrolleinheit

Token-Verfahren

Ausgezeichnete Kontrolleinheit

• Basiert auf Konzept der Zentralisierung• Eine Kontrolleinheit (KE) verantwortlich für alle

(Schreib-) zugriffe

Nachteile:

• Keine weiteren Zugriffe bei Ausfall der KE.

• Bei Partitionierung auch Lesezugriffe nur in Partition mit KE.

Token-Verfahren (1)

• Verschiedene Rechner verantwortlich für Konsistenz

• Token wandert in virtuellem Ring zwischen den Rechnern umher

• Rechner mit Token verantwortlich

Token-Verfahren (2)

• Nachteile:– Schwierige Handhabe des Rechnerrings– Erweiterbarkeit des Rings– Ring muss dynamisch rekonfigurierbar sein (falls

Ausfall einzelner Rechner oder Partitionierung)– Verlust des Tokens (erkennen und beheben)

• Vorteil:– Höhere Verfügbarkeit als Verfahren mit

ausgezeichneter KE

mit dezentraler Kontrolle

Zentrale Kontrolle Dezentrale Kontrolle Ausgezeichnete Kontrolleinheit Token-Verfahren

ohne Votierung mit VotierungEinfache SperrverfahrenFloor-Passing-VerfahrenTransaktionsverfahrenTransformationsverfahren

Einfache Sperrverfahren

• Anfordern und Setzen der Sperre kostet Zeit• Sperrgranularität hat entscheidenden Einfluss

auf den Grad an Nebenläufigkeit• Je nach Art des Systems (z.B: WYSIWIS)

muss geklärt werden, ab wann eine Sperre zu setzen ist

• Zwei Alternativen:– Tickle lock– Probabilistic lock

Tickle lock

Nachteil:• Absturz des Rechners der die Sperre besitzt

gesperrter Teil bleibt bis zu Neustart des Rechners gesperrt

• Sperre nur so lange wie benötigt

• Sobald Benutzer nichts mehr tut, wird Sperre automatisch frei gegeben

Probabilistic lock

• Sperre mit automatischem Time-out• Ist das Setzen bis zu einem Time-out nicht

möglich Benutzer muss entscheiden(Inkonsistenzen werden in Kauf genommen)

• gesetzte Sperre bleibt für feste Zeitspanne gesetzt

Nachteil:

Zeitweise nicht Einhalten der Konsistenz, aufgrund von Kommunikationsverzögerungen.

Floor-Passing-Verfahren

• Verfahren mit wechselnder Kontrolle• Sperrmechanismen werden nicht benötigta) explizites:

Kontrolle wird aktiv vom Benutzer weitergegeben

b) implizites:Vergabe der Kontrolle durch Koordinator

Vorteil: keine Benachteiligung von Komponenten

Nachteil: Ausfall des Koordinators

Nachteile: Benachteiligung anderer Komponenten

Ausfall der Einheit mit Kontrolle

Transformationsverfahren (1)

• Von Vorteil bei CSCW-Systemen mit WYSIWIS Eigenschaft

• Basiert auf Transformation von Operationen

• Implementationbeispiel:GROVE-Algorithmus (Group outline viewing editor): siehe [BS2000, Seite 202ff]

• Problemstellung:

„abcd“

„abxcd“

„abcd“

„abcyd“

„abxcyd“„abxycd“

O1=insert(x,3) O2=insert(y,4)

Ohne Anpassung der Operationen hängt das Ergebnis von der Reihenfolge der Operationsausführung ab.

Benutzer 1 Benutzer 2

• Operationstransformation, so dass:O`1° O2 = O`2 ° O1

• man benötigt:– Prioritäten von Operationen

(pi = Priorität von Aktion i)– Transformationsmatrix T

(insert(xi, Posi), insert(xj, Posj),pi,pj)

(delete(Posi), insert(xj,Posj),pi,pj)

(insert(xi,Posi), delete(Posj),pi,pj)

(delete(Posi), delete(Posj),pi, pj)

• Implementierung der Konfliktpaare von TT11: if (Posi<Posj) then O`i := insert(xi,Posi);

elsif (Posi>Posj) then O`i := insert(xi,Posi+1);

elsif (xi = xj) then O`i := no-op; elsif (pi > pj) then O`i := insert(xi,Posi+1);

else O‘i := insert(xi,Posi);

T12: usw.

Seien wieder O1=insert(x,3) und O2=insert(y,4). Index als Priorität.

O`1 = insert(x,3) bzw. O`2 = insert(y,5)

O`1° O2 („abcd“) = „abxcyd“ = O`2 ° O1(„abcd“)

Gliederung

• Zusammenfassung

Spezielle Verfahren

ohne Votierung mit VotierungEinfache SperrverfahrenFloor-Passing-VerfahrenTransaktionsverfahrenTransformationsverfahrenKodierungsverfahrenGitterprotokoll

Mit Mehrheitsentscheidunggewichteteswrite-all-read-anymit ZeugenAvailable-Copydynamisches

Aus dem Bereich der verteilten Dateisysteme

Gitterprotokoll

• Logische Organisation der dateibesitzenden Rechner

• Lesender Zugriff: min. 1 Rechner pro Spalte• Schreibender Zugriff: + alle Rechner einer Spalte

Votierungsverfahren

• Rechner stimmen über einen Lese- oder Schreibwunsch ab

• Hoher Kommunikationsbedarf• Korrekte Verwendung der Sperren wird

vorausgesetzt• Gut bei großen Datenblöcken

Datenblock

Datenblocknummer

Versionsnummer

Sperrzustand

Datenblockinhalt

Gebrauch des Datenblocks (1)

„ XX „

„ YY „ „ YY „

Rechner 1 Rechner 2 Rechner 3

Zustand vor Lesen

Gebrauch des Datenblocks (2)

„ ZZ „

„ ZZ „ „ YY „

Rechner 1 Rechner 2 Rechner 3

Zustand nach Schreiben

Votum und Quorum

• Votum: Stimmzahl der Rechner, die den Zugriff gestatten (d.h. erreichbar und keine Sperre gesetzt)

• Quorum: untere Schranke bei deren Erreichen oder Übertreffen der Zugriffswunsch gestattet wird

Votieren mit Mehrheitsentscheidung

• Jeder Rechner hat genau eine Stimme

Bsp.: Rechnernetz mit 4 Rechnern und vollständig repliziertem Datenbestand QU = 3 {{R1,R2,R3},{R1,R2,R4},{R1,R3,R4},{R2,R3,R4}}

11R1 R2

• Unterschiedliche Stimmgewichte si für die Rechner

(S = ∑i si)

• Für Lesequorum (QUl) und Schreibquorum (QUs) gilt:

QUl + QUs > S

2 * QUs > S

Vorteile: • Null-Votum (Rechner mit si=0) wirkt leistungs-erhöhend beim

Lesen (schneller Zugriff)• QUl und QUs können auf erwartete Zugriffshäufigkeiten

abgestimmt werden

Gewichtetes Votieren

Gewichtetes Votieren: Beispiel

QU = 3{{R1,R2},{R1,R3},{R1,R4},{R1,R2,R3}}

12R1 R2

write-all-read-any

• Jeder Rechner hat Stimmgewicht = 1• QUl = 1

• QUs = n

Vorteil: schneller Lesezugriff

Nachteil: schwierig bei Änderungen

Votieren mit Zeugen

• Rechner ohne Datenblock, aber mit Stimmberechtigung

Vorteile:– Höhere Verfügbarkeit– Geringer Speicherplatzbedarf– Bei Ausfall eines Rechners erweiterbar zu voller

KopieNachteil:

– Stimmmehrheit erreichbar, aber aktuellste Version nicht dabei (Zeuge hat höchste Versionsnummer), d.h. nur Schreiben möglich

Available-Copy-Verfahren (1)

• Schreibt nur aktuell erreichbare Datenblockkopien fort• Abgestürzte Rechner aktualisieren sich bei Neustart• Jeder Rechner hat Stimmgewicht = 1• QUl = 1

• 1 ≤ QUs ≤ n

Problem:

Im Falle einer Partitionierung werden nicht erreichbare Datenblockkopien nicht fortgeschrieben und bei einer Vereinigung der Partitionen werden diese Kopien nicht aktualisiert.

Nur für LANs geeignet

Gliederung

• Zusammenfassung

Zusammenfassung

• Grundlagen verteilter Anwendungen• Konsistenz Nebenläufigkeit• Verteilte Anwendungen häufig eingebettet in verteilte

Systeme ( weitere Möglichkeiten der Synchronisation, z.B. Multicast-Synchronisationsprotkolle, Arbeiten mit Zeitstempeln, usw.)

• Verschiedene Verfahren, die verteilte Anwendungen benutzen können

• Verfahren abhängig von Anwendung (Replikation, gewünschter Grad an Nebenläufigkeit, Anzahl der Teilnehmer, Anwendungsbereich (LAN, WAN,...),...)

Verfahren

Pessimistische

ohne Votierung mit VotierungEinfache SperrverfahrenFloor-Passing-VerfahrenTransaktionsverfahrenTransformationsverfahrenGitterprotokoll

Mit MehrheitsentscheidungGewichtetesWrite-all-read-anyMit ZeugenAvailable-Copy

Optimistische

FRAGEN

?Synchronisation und Konsistenzerhaltung in verteilten Anwendungen

1 Agenten und verteilte Anwendungen Synchronisation und Konsistenzerhaltung in verteilten...

Documents

Agenten in simulierten Umgebungen Landminensuche II Stefan Fleischer Stephan Kramer Alexander Simons Agenten in simulierten Umgebungen -1-

Laser-microwave synchronisation for ultrafast electron diffraction

Mobile Agenten als Architekturprinzip verteilter Systeme

4. Replikation und Synchronisation

Seminar: Agenten in simulierten Umgebungen 1 Soccer Server RoboCup Vortrag im Rahmen des Seminars: Agenten in simulierten Umgebungen 13.12.2004

Multi agenten-systeme

Rationale Agenten. Agenten Agent: Nimmt Umgebung über Sensoren wahr und beeinflusst diese durch Aktuatoren. Rationaler Agent: Maximiert Erfolgskriterium

Suchen mit Agenten Seminar Softwareagenten Simon Fischer

Prinzipal-Agenten- Theorie.............. 1 Prinzipal-Agenten-Theorie Präsentiert von Sven Hanus Partha Banerjee Hassan Amjahad

Sichere Synchronisation von E-Mail, Kalender, Kontakten ...€¦ · Sichere Synchronisation von E-Mail, Kalender, Kontakten und Dateien zwischen PC, Tablet, Smartphone oder Webzugang

Informationssammler Software Agenten Agenten zur Informationssammlung Tobias Gerke, Andreas Jäger nach Craig A. Knoblock & José Luis Ambite (1997)

Synchronisation und Spannungsstabilität in einem Netzwerk ... · Synchronisation und Spannungsstabilität in einem Netzwerk von Synchronmaschinen als Diplomarbeit vorgelegt von Katrin

Dokumenten-Synchronisation mit eigenem Cloud-Server

Entscheidungsunterstützungssysteme IWI Frankfurt 2004 Software-Agenten zur Entscheidungsunterstützung Warum Agenten? –Technologie- und Organisationstrends

Kunstliche Intelligenz -Logische Agenten

© 2002 Prof. Dr. G. Hellberg 1 Verzeichnisdienste mit XML-Technologie Synchronisation von Verzeichnisdiensten mittels XML-Technologie : XML und ihre Anwendungen

Robotfussball und Agenten

FMK2012: Synchronisation von redundanten Datenbeständen von Longin Ziegler

Einführung in die Theorie der Multi-Agenten-Systeme

Nonverbale Synchronisation in der Psychotherapie