jo

1 files changed, 0 insertions, 2857 deletions

diff --git a/docs/VS2007/verteilte-systeme.tex b/docs/VS2007/verteilte-systeme.tex
deleted file mode 100644
index 9c3e771..0000000
--- a/docs/VS2007/verteilte-systeme.tex
+++ /dev/null
@@ -1,2857 +0,0 @@
-\documentclass[bibtotocnumbered, headsepline,normalheadings]{scrreprt} 
-
-\usepackage[latin1]{inputenc} 
-\usepackage{german} 
-\usepackage{scrpage} 
-\usepackage{eurosym} 
-\usepackage{alltt} 
-\usepackage{graphicx}
-\usepackage{hyperref}
-
-\pagestyle{headings} 
-
-\begin{document} 
-\title{Vorlesungsmitschrift \\ Verteilte Systeme \\ SS 2007 FH-Aachen} 
-\author{Bei Prof. Dr.-Ing. O{\ss}mann \\ \\ Getext von Paul B\"{u}tow} 
-\date{Letzte Aktualisierung: \today} 
-\maketitle 
-
-\tableofcontents
-
-\newcommand{\m}[1]{$~\qquad {#1}$\\}
-\newcommand{\n}[1]{$~\qquad {#1}$}
-\newcommand{\q}{$ ~ \qquad $}
-\newcommand{\bs}{$\backslash$}
-\newcommand{\pre}[1]{\texttt{{#1}}}
-\newcommand{\set}[1]{\{{#1}\}}
-\newcommand{\ra}{ \rightarrow }
-\newcommand{\Ra}{ \Rightarrow }
-\newcommand{\E}{$\epsilon$}
-\newcommand{\N}{\mbox{$I\!\!N$}}
-
-\chapter{Diverses}
-
-\section{Ein bischen Blabla...}
-Ich garantiere nicht, dass der Inhalt dieses Dokuments weder korrekt noch vollst\"{a}ndig ist. \textit{Kursiv geschriebene Kommentare habe ich selbst hinzugef\"{u}gt.} Bei Fehlern bitte per E-Mail (\texttt{skript@paul.buetow.org}) an mich wenden!
-
-\subsection{Anmerkung zu den Grafiken}
-Die Grafiken sind etwas pixelig/unscharf. Ich bitte dies zu entschuldigen. Sie erf\"{u}llen jedoch ihren Zweck.
-
-\subsection{Download URL}
-Das aktuelle Dokument mitsamt Sourcen liegt unter:\\
-
-\url{ftp://ftp.buetow.org/pub/studium/FHAC\_VS-SS07/}
-
-\subsection{Technische Informationen}
-Falls es interessiert: Dieses Dokument wurde erstellt mithilfe von:
-\begin{itemize}
-	\item LaTeX, rubber, make
-	\item Dia (http://www.gnome.org/projects/dia/) 
-	\item Vim (http://www.vim.org)
-	\item FreeBSD (http://www.FreeBSD.org)
-\end{itemize}
-
-\chapter{Vorlesung}
-
-\section{\"{U}berblick}
-
-\begin{itemize}
-	\item Grundeigenschaften
-	\item Systemmodelle
-	\item Netzwerke, Interprozesskommunikation
-	\item Verteilte Objekte, entfernte Aufrufe
-	\item Verteilte Dateisysteme
-	\item Namensdienste
-	\item Zeit und globale Zust\"{a}nde
-	\item Koordination und Nebenl\"{a}ufigkeitskontrolle
-	\item Transaktionen
-	\item Replikationen
-\end{itemize}
-
-\section{Literatur}
-
-\begin{itemize}
-	\item Coulouris, Dollimore, Kindberg ``Verteilte Systeme''
-	\item Tanenbaum, van Steen ``Verteilte Systeme''
-\end{itemize}
-
-\section{Grundeigenschaften}
-
-Grundeingenschaften verteilter Systeme: Zusammenarbeit mehrerer Komponenten auf vernetzten Computern.
-Koordination und Kommunikation erfolgt durch den Austausch von Nachrichten.\\
-\\
-Daraus ergibt sich die Nebenl\"{a}ufigkeit der Komponenten. Keine globale Uhr. Unabh\"{a}ngige Ausf\"{a}lle von Komponenten.
-
-\section{Beispiele}
-
-\begin{itemize}
-	\item Tauschb\"{o}rsen
-	\item Sichere Speicherung auf verteilten Servern
-	\item Mobiles und Allgegenw\"{a}rtiges
-	\item Rechnen
-\end{itemize}
-
-\section{Motivation}
-
-Motivation f\"{u}r den Aufbau verteilter Systeme: Gemeinsame Nutzung von Ressourcen.\\
-\\
-Was ist der Unterschied zur Betriebssystem-Motivation? 
-
-\begin{itemize}
-	\item Heterogenit\"{a}t der Komponenten
-	\item Offenheit (weltweit akzeptierte Standards)
-	\item Sicherheit bei Teilausf\"{a}llen (Fehler, Angriffe) 
-	\item Skalierbarkeit (Systeme wachsen)
-\end{itemize}
-
-\section{Beispiele f\"{u}r gemeinsam genutzte Ressourcen}
-
-\begin{itemize}
-	\item Hardware: Drucker, Festplatten
-	\item Daten: Dateien
-	\item Dienste z.B. Suchmaschinen
-\end{itemize}
-
-\section{Client Server Modell}
-
-In verteilten Systemem verwendet man oft das ``Client Server Modell''. Ein Server bietet einen Dienst (Service) an (``passiv''). Ein Client fragt bei einem Server nach einen Dienst (``request for service'').\\
-\\
-Die Dienste bergrenzen den Ressourcenzugriff auf eine wohldefinierte Operationsmenge.
-Implementation von Servern erfolgt \"{u}blicher Weise durch einen Prozess auf einem vernetzten Computer.
-
-\begin{enumerate}
-	\item Client: Ruft eine Operation auf dem Server auf
-	\item Server: Schickt Antwort
-	\item Client: Erh\"{a}lt die Antwort
-\end{enumerate}
-
-$\ra$ ``Eine Interaktion'', ``remote invocation''\\
-\\
-Remote hei{\ss}t nicht ``geometrisch entfernt''. Besser: Es wird ein Dienst erbracht, der in einem anderen Adressraum bereitliegt.
-
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=100mm]{vs1.png}
-\end{center}
-\end{figure}
-\subsubsection{Frage}
-Gibt es in Java einen Adressraum?  Antwort: Ja (Siehe NullPointerException).\\
-\\
-Ein Prozess kann gleichzeitig Client und Server sein. 
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=105mm]{vs3.png}
-\end{center}
-\end{figure}
-\"{A}hnliche Beziehung: Funktions- bzw. Methodenaufruf. Server werden ``st\"{a}ndig'' ausgef\"{u}hrt. Clients reden mit der \"{u}bergeordneten Applikation. Das Client-Server Modell beschreibt viele verteilte Systeme (nicht alle).
-
-\section{Ziele beim Design eines verteilten Systems}
-
-Ber\"{u}cksichtigt werden:
-
-\begin{itemize}
-	\item Heterogenit\"{a}t
-	\item Offenheit
-	\item Skalierbarkeit
-	\item Sicherheit (gegen Angriffe)
-	\item Fehlertoleranz
-	\item Nebenl\"{a}ufigkeit
-	\item Transparenz
-\end{itemize}
-\subsection{Heterogenit\"{a}t}
-Heterogenit\"{a}t in den Bereichen
-\begin{itemize}
-	\item Netzwerk
-	\item Computerhardware
-	\item Betriebssysteme
-	\item Programmiersprachen
-\end{itemize}
-Wesentliches Hilfsmittel zur Implementation heterogener Systeme: Einf\"{u}hrung einer Middleware.
-Middleware ist eine Softwareschicht, die eine Programmierabstraktion zur Verf\"{u}gung stellt, und die Heterogenit\"{a}t des darunterliegenden Systems verbirgt.
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=30mm]{vs4.png}
-\end{center}
-\end{figure}
-\\
-Beispiele: Java, RMI, CORBA, SQL, RPC. (Bereitstellung einer einheitlichen Programmierschnittstelle).
-
-\subsection{Offenheit}
-Ziel Offenheit (Um sp\"{a}ter Erweiterungen vornehmen zu koennen). Z.B. Hinzuf\"{u}gung neuer Dienste f\"{u}r unterschiedliche Client-Programme.
-\begin{itemize}
-	\item Ziel wird erreicht durch Offenlegung der Spezifikation aller Softwareschnittstellen
-	\item Wird unterst\"{u}tzt durch Standardisierung der Schnittstellen.
-\end{itemize}
-Beispiele f\"{u}r Offenheit:
-\begin{itemize}
-	\item Internet-Protokolle
-	\item RFC (Request For Comment)\\
-		\url{http://www.ietf.org}
-\end{itemize}
-
-\subsection{Skalierbarkeit}
-Die Leistungsf\"{a}higkeit von Systemen soll durch Hinzuf\"{u}gen von Komponenten steigen. Steigender Bedarf an Dienstleistungen mu{\ss} mit beschr\"{a}nkten Kosten befriedigt werden.\\
-\\
-Ist ein Linux-Cluster ein skalierbares System? Nur schwer skalierbar (wg. Neuverkabelung bei Hinzunahme neuer Rechner).\\
-\\
-Wachstum bringt oft (relativen) Verlust an Leistung. Beispiel: Finden eines Objekts unter $n$ (Skalierungsgr\"{o}{\ss}e) Objekten. 
-
-\begin{itemize}
-	\item Bei linearem Suchen: Aufwand $\sim n$
-	\item Bei bin\"{a}rem Suchen: Aufwand $\sim log(n)$
-\end{itemize}
-Angestrebt wird ein Aufwandswachstum $\approx log(n)$ ($n$ ``Gr\"{o}{\ss}e des Systems'').\\
-\\
-Weiteres Problem: Manche Ressourcen ersch\"{o}pfen sich! Beispiel: IP-Adressen. Leistungsengp\"{a}sse sollten durch Dezentralisierung vermieden werden!\\
-\\
-Anfangs: Ein zentraler DNS-Server, der ``alles'' in einer Datei wusste.
-
-\subsection{Behandlung von Fehlern}
-
-Erkennen von Fehlern: 
-
-\begin{itemize}
-	\item Pr\"{u}fsummen (``leicht m\"{o}glich'')
-	\item Absturz eines Servers schwer zu erkennen
-\end{itemize}
-Maskierung von Fehlern:
-\begin{itemize}
-	\item Mehrfaches \"{U}bertragen von Nachrichten
-	\item Mehrfache Speicherung von Daten
-\end{itemize}
-Frage: Greifen diese Ma{\ss}nahmen garantiert? Nein. Absolute Garantien kann man nie erwarten. Im Normalfall kann man die Sicherheit jedoch ausreichend ``hochschrauben''.\\
-\\
-``Tolerieren von Fehlern'' ist eine weitere Vorgehensweise. 
-\begin{itemize}
-	\item Weiterleitung von Fehlern an den Benutzer (\"{u}bergeordnete Schicht). Beispiele:
-		\begin{enumerate}
-			\item Browser findet Seite nicht
-			\item Java: Exception 
-			\item C: Nichts (nur einen Crash)
-		\end{enumerate}
-	\item Oft kann die Schicht, die den Fehler feststellt, nicht entscheiden, wie weiter vorzugehen ist. 
-\end{itemize}
-Zur Maskierung von Fehlern verwendet man oft redundante Komponenten. Beispiele:
-\begin{itemize}
-	\item Mehrere Routen im Netzwerk
-	\item DNS: Jede Tabelle auf mehreren Servern
-	\item Replizierte Datenbanken (Techniken sp\"{a}ter im Detail)
-\end{itemize}
-
-\subsection{Nebenl\"{a}ufigkeit}
-``Gleichzeitige'' Benutzung von einer Ressource durch mehrere Benutzer. Ohne Nebenl\"{a}ufigkeit h\"{a}tten wir die sequentielle Benutzung von Ressourcen.
-$\ra$ Schlechter Durchsatz.
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=33mm]{vs5.png}
-\end{center}
-\end{figure}
-Im Allgemeinen lassen Server viele Clients gleichzeitig zu.  Ressource sei als Objekt gekapselt (Siehe Bild).\\
-\\
-In vielen F\"{a}llen ist die Synchronisation notwendig um inkonsistente Ergebnisse zu vermeiden. Objekte, die gemeinsam genutzte Ressourcen verwalten, m\"{u}ssen in einer nebenl\"{a}ufigen Umgebung \underline{korrekt} arbeiten.
-
-\subsection{Transparenz}
-Transparenz bedeutet, dass der Benutzer gewisse Details nicht ber\"{u}cksichtigen mu\ss, die die Implementation effizient machen.
-
-\begin{itemize}
-	\item \textbf{Zugriffstransparenz:} Lokale und entferne Zugriffe auf Objekte erfolgen mit den gleichen Methoden. Wenn man Sockets verwendet, kann man Nachrichten lokal und entfernt gleichartig verschicken.
-	\item \textbf{Orts- und Positionstransparenz:} Man kann auf Ressourcen zugreifen, ohne ihren Ort zu kennen. Man kann die Ressourcen von verschiedensten Orten aus benutzen.
-	\item \textbf{Nebenl\"{a}ufigkeitstransparenz:} Gemeinsame ``gleichzeitige'' Nutzung ohne Beeintr\"{a}chtigung. 
-	\item \textbf{Replikationstransparenz:} Man arbeitet mit Repliken (Kopien) ohne Beeintr\"{a}chtigung.
-	\item \textbf{Fehlertransparenz:} Partielle (teilweise) Ausf\"{a}lle beeintr\"{a}chtigen den Benutzer nicht.
-	\item \textbf{Leistungs- und Skalierungstransparenz:} Das System kann neu konfiguriert oder erweitert werden, um h\"{o}here Leistungen zu erzielen.
-\end{itemize}
-
-\section{Systemmodelle}
-Modelle heben strukturierte Eigenschaften von Systemen hervor und erm\"{o}glichen eine einheitliche Sichtweise auf verschiedenartige Realisationen.
-
-\begin{itemize}
-	\item \textbf{Architektonisches Modell:} Platzierung von Komponenten. Verbindungen und Beziehungen zwischen Komponenten.
-	\item \textbf{Interaktionsmodell:} Zusammenspiel zwischen Teilen beim Nachrichtentausch.
-	\item \textbf{Fehlermodell:} Beschreibung von Fehlerm\"{o}glichkeiten der Prozesse und Kommunikationskan\"{a}le. Festlegung was man als ``korrekt'' bzw. ``zuverl\"{a}ssig'' interpretiert.
-	\item \textbf{Sicherheitsmodell:} Beschreibung von Gefahren durch Angriffe und Abwehrma{\ss}nahmen.
-\end{itemize}
-\subsection{Beispiele f\"{u}r architektonische Modelle}
-\begin{itemize}
-	\item Client - Server
-	\item Peer to Peer (gleichrangige Prozesse)
-	\item Schichten-Architektur 
-\end{itemize}
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=60mm]{vs6.png}
-\end{center}
-\end{figure}
-Die Middleware stellt zur Verf\"{u}gung:
-\begin{itemize}
-	\item Entfernte Methodenaufrufe
-	\item Kommunikation in Gruppen
-	\item Benachrichtigung \"{u}ber Ereignisse 
-	\item Replikation von Daten
-	\item Namensdienste (z.B. Matr.-Nr. in einer HS)
-	\item Sicherheitskonzepte
-	\item Transaktionen 
-\end{itemize}
-Die \"{U}bertragung von Aufgaben an die Middleware vereinfacht den Entwurf und die Implementation von verteilten Systemen.\\
-\\
-Aber es gibt Funktionalit\"{a}ten, die vollst\"{a}ndig und zuverl\"{a}ssig nur bei Kenntnis der Applikation implementiert werden k\"{o}nnen. Solche Funktionen kann man nicht vollst\"{a}ndig in Middleware verstecken.\\
-\\
-\textbf{Beispiel:} Ist TCP/IP die geeigente Middleware um Sicherheit beim Transport von E-Mails zu gew\"{a}hrleisten?\\
-\\
-$\ra$ TCP/IP ist daf\"{u}r nicht geeignet, weil z.B. keine geeigneten Ma{\ss}nahmen gibt, um l\"{a}ngere Ausf\"{a}lle von Servern zu maskieren!
-
-\section{Interaktionsmodelle}
-\begin{itemize}
-	\item Wer kommuniziert mit wem, wann, warum, ... ?
-	\item Wie beeinflusst das Timing von Nachrichten die Kommunikation und den Ablauf?
-	\item Was ist der ``Zustand'' von einem verteilten Algorithmus?
-\end{itemize}
-
-\subsection{Synchrones verteiltes System}
-\begin{itemize}
-	\item F\"{u}r die Ausf\"{u}hrungszeit zu jedem Schritt eines Prozesses gibt es bekannte obere und untere Schranken.
-	\item Jede Nachricht wird innerhalb einer begrenzten Zeit (fehlerfrei) empfangen.
-	\item Die Abweichungsgeschwindigkeit von lokalen Uhren im Bezug wahren Zeit ist beschr\"{a}nkt. (\textit{Uhren gehen eigentlich nie zu 100 Prozent gleich. Die Abweichungsgeschwindigkeit ist das, wie schnell Uhren ``auseinanderwandern''})
-\end{itemize}
-Das sind sehr harte Forderungen! Von normalen Systemen sind diese nicht zu erf\"{u}llen. \textit{Dieses Modell ist eigentlich ein Wunschmodell.} (Wahrscheinliche Werte, Mittelwerte usw. sind oft leicht zu erf\"{u}llen).
-
-\subsection{Asynchrones verteiltes System}
-\begin{itemize}
-	\item Keine Begrenzung f\"{u}r Prozessausf\"{u}hrung
-	\item Unbegrenzte Nachrichtenverz\"{o}gerung
-	\item Uhrabweichungen
-\end{itemize}
-Schon das ``Einigungsproblem'' zwischen 2 Teilnehmern im asynchronen System ist nicht l\"{o}sbar.
-
-\section{Zeit und globale Zust\"{a}nde}
-F\"{u}r Ereignisse gilt:
-\begin{itemize}
-	\item Man will wissen, ob ein Ereignis vor oder nach einem anderen Ereignis stattfand (\textit{Wir denken bisher mit vor und nach an die Zeit, sp\"{a}ter werden wir auch an was Anderes denken}).
-	\item Man will wissen, ob man alle Informationen hat, die zu einem bestimmten Ereignis gef\"{u}hrt haben.
-	\item Man will wissen, ob ein System (aus mehreren Komponenten) sich (zu einem Zeitpunkt) in einem Zustand befunden hat.
-\end{itemize}
-\textbf{Ansatz 1:} Versuche Uhren zu bauen\\
-\\
-\q $N$ Prozesse (evtl. auf verschiedenen Rechnern)\\
-\\
-\q Die echte wahre Zeit sei $t$.\\
-\\
-\q Hardwareuhr: $H_i(t) \quad i = 1, ..., N$\\
-\\
-\q Softwareuhr: $C_i(t) = \alpha * H_i(t) + \beta$\\
-\\
-Ziele: 
-\begin{enumerate}
-	\item $C_i(t) \approx t$\\
-	\\
-	$C_i(t) - t$ hei{\ss}t Uhrabweichung von Uhr $i$ zum Zeitpunkt $t$.
-	\item $C_i(t) \approx C_j(t)$\\
-	\\
-	$C_i(t) - C_j(t)$ hei{\ss}t Synchronisationsfehler zwischen den Uhren $i$ und $j$ zum Zeitpunkt $t$.
-\end{enumerate}
-Uhren werden ``synchronisiert''. $S(t)$ sei eine Referenzuhr (z.B. UTC).
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=115mm]{gps.png}
-\end{center}
-\end{figure}
-
-\begin{enumerate}
-	\item \underline{Externe Synchronisierung} \"{u}ber einem Zeitintervall gilt f\"{u}r alle $t \in I$:\\
-\\
-\q $|S(t) - C_i(t) | < D$ f\"{u}r alle $i = 1, ..., N$\\
-\\
-So heissen die Uhren $C_i$ mit $i = 1, ..., N$ extern synchronisiert mit Genauigkeit $D$. ($D$ ist fest f\"{u}r alle $i$, $t$). Uhrabweichung in $I$ ist kleiner als $D$.\\
-\\
-$5$ Sekunden Abweichungen pro Tag: $\frac{5s}{24 * 3600s} = 57 * 10^{-6} = 57ppm$\\
-\\\textit{Bei billigen Uhren die man im Laden bekommt kann man leicht $10ppm$ erreichen. Atomuhren liegen bei einem Faktor von ca. $10^{-15}$.}
-	\item \underline{Interne Synchronisierung} git f\"{u}r alle $t \in I$ und $i,j \in {1, ..., N}$ dass\\
-	\\
-	\q $|C_i(t) - C_j(t) | < D$\\
-	\\
-	so heissen die Uhren intern synchronisiert mit Genauigkeit $D$. (Uhren stimmen untereiander bis auf $D$ \"{u}berein.
-\end{enumerate}
-Ist ein System extern $D$-Synchronisiert, ist es intern garantiert $2D$-synchronisiert. Wenn ein System intern $D$-Synchronisiert ist, kann das zugeh\"{o}rige externe $D$ beliebig gro{\ss} sein.
-
-\subsection{Einige Korrektheitsbegriffe f\"{u}r Uhren}
-
-\textit{Eine Uhr die still steht, geht 2 mal am Tag richtig. Eine Uhr die 1 Minute vor geht, geht immer falsch?!? Es ist nicht einfach die Korrektheit einer Uhr zu definieren.}
-\
-\begin{enumerate}
-	\item Eine Hardwareuhr hei{\ss}t korrekt, wenn ihre Abweichgeschwindigkeit (drift-rate) durch eine Schranke $\rho > 0$ begrenzt ist.\\
-	\\
-	D.h., der Fehler beim Messen von Intervallen zwischen Echtzeiten $t$ und $t'$ ist begrenzt durch:\\
-	\\
-	\q $(1-\rho) (t'-t) \le H(t') - H(t) \le (t'-t) (1+\rho)$\\
-	\\
-	\q $ \Leftrightarrow 1-\rho \le \frac{H(t')-H(t)}{t'-t} \le 1 + \rho$\\
-	\\
-	\q $ \ra -\rho \le \frac{H(t')-H(t)}{t'-t} -1 \le \rho$ (Gangabweichungsgeschwindigkeit)\\
-	\\
-	Erster Korrektheitsbegriff: Gangabweichungsgeschwindigkeit beschr\"{a}nkt.\\
-	\\
-	Frage: Darf eine in dem Sinne korrekte Uhr ``springen''? Antwort: \underline{nein}! \textit{Differenzierbare Funktionen m\"{u}ssen stetig sein}. Derartige Uhren d\"{u}rfte man nicht synchronisieren (``stellen''). $\ra$ Dieser Korrektheitsbegriff ist oft zu stark.
-	
-	\item Ein weiterer Korrektheitsbegriff: Eine Hardwareuhr hei{\ss}t korrekt, wenn sie ``monoton'' ist.\\
-	\\
-	\q $t < t' \ra H(t) < H(t')$\\
-	\\
-	$\ra$ Das ist oft ein zu schwacher Korrektheitsbegriff.
-
-	\item Eine Hardwareuhr hei{\ss}t korrekt, wenn sie monoton ist und die Gangabweichung zwischen Synchronisationspunkten begrenzt ist. 
-\end{enumerate}
-\section{Methoden zur Synchronisation}
-\subsection{Interne Synchronisation in einem synchronem System}
-Annahme: Die Transportzeit einer Nachricht (vom Senden zum Empfangen) liegt garantiert zwischen $t_{min}$ und $t_{max}$. D.h. $t_{min} \le t_{tr} \le t_{max}$. Die anderen Zeiten seien vernachl\"{a}ssigibar. Nenne $t_{max} - t_{min}$ die ``Unsicherheit''.\\
-\\
-Prozess $P_1$ senden seine Zeit $t$ in einer Nachricht zu Prozess $P_2$.\\
-
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=85mm]{vs7.png}
-\end{center}
-\end{figure}
-$P_2$ setzt beim Empfang seine Zeit auf:\\
-\\
-\q $t_2 = t + \frac{1}{2}(t_{max} + t_{min}) \ra$ Synchronisationsfehler $< \frac{U}{2}$\\
-\\
-Wenn man so $N$ Uhren intern synchronisiert, ist der Fehler $\le U(1-\frac{1}{N})$\\
-\\
-In asynchronen Systemen k\"{o}nnen keine Garantien gegeben werden.\\
-\\
-Beobachtung: Die Round-Trip Zeit (RTT) in realen Systemen ist oft relativ kurz.
-
-\subsection{Christians Methode zur externen Synchronisation}
-\begin{itemize}
-	\item Es handelt sich um einen ``probabilistischen Algorithmus''.
-	\item Mit Wahrscheinlichkeit $> p_0$ ist eine Synchronisation m\"{o}glich. 
-	\item Typische Roundtrip-Zeiten sind $1, ..., 10ms$
-	\item Abweichungsgeschwindigkeit der lokalen Uhr die zur Roundtrip-Zeimessung benutzt wird, ist vernachl\"{a}ssigbar klein.
-	\item Der Prozess, der mit Round-Trip den Zeitserver nach der Zeit gefragt hat, setzt seine Zeit auf $t$ (Zeitpunkt des Servers) $ + \frac{T_{round}}{2}$ sofern man keine zus\"{a}tzlichen Informationen hat.
-\end{itemize}
-Christians Methode: Benutze die Round-Trip Zeit, um die Transportzeit von Nachrichten f\"{u}r den Einzelfall zu ``kennen''.\\
-\\
-Der Prozess p setzt seine eigene Zeit auf $t + \frac{T_{round}}{2}$. Mit $t :=$ Zeitstempel des Servers.
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=70mm]{vs8.png}
-\end{center}
-\end{figure}
-Annahme: Es ist etwas mehr bekannt, n\"{a}mlich eine untere Schranke $T_{min}$ f\"{u}r den Nachrichtentransport ($\ra T_{round} \le T_{min}$).
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=75mm]{vs9.png}
-\end{center}
-\end{figure}
-Client setzt seine Uhr wie vorher auf $t + \frac{T_{round}}{2}$. Die Genauigkeit ist $\pm(\frac{T_{round}}{2} - T_{min})$.\\
-\\
-Synchronisiere nur, wenn die beobachte Round-Trip-Zeit klein genug ist. Vorsicht: Beim Synchronisieren sind ggf. Korrektheitsbedinungen (Monotonie o.\"{A}...) zu beachten! 
-\begin{itemize}
-	\item Schutz gegen Ausfall: Einrichtung mehrerer Server.
-	\item Erreichen kleinerer Round-Trip-Zeit: Benutze ``nahe'' Server.
-	\item Problem: Betr\"{u}gerische Server: Kryptologische Methoden (Authentifizierung). \\
-		Abgleich mehrerer Servern.
-\end{itemize}
-
-\subsection{Berkeley Algorithmus zur internen Synchronisierung}
-\begin{itemize}
-	\item Auswahll eines Koordinierungsmasters.
-	\item Der Master fragt die Slaves ab. Diese senden ihre eigene Uhrzeiten zur\"{u}ck.
-	\item Der Master sch\"{a}tzt die lokalen Zeiten der Slaves durch Beobachtung der Roundtrip-Zeit.
-	\item Der Master bildet (durch gewichtete Mittelung) eine ``m\"{o}glichst genaue'' Referenzzeit.
-	\item Der Master schickt allen Slaves ``Korrekturwerte'' die angeben, wie sie jeweils aus ihrer lokalen Zeit die Referenzzeit berechnen k\"{o}nnen.
-\end{itemize}
-Experiment: 15 Computer kann man in \"{u}blichen LANs relativ leicht auf ca. 25$\mu$s synchronisieren. (Bei ca 10ms Roundtrip)\\
-\\
-Keine Garantien!\\
-\\
-Problem (weiterhin): Uhren erm\"{o}glichen es nicht immer, die Frage zu beantworten, ob ein Ereignis a vor einem Ereignis b stattgefunden hat.\\
-\\
-Einf\"{u}hrung eines anderen Konzepts:
-\section{Logische Zeit und logische Uhren}
-Beobachtung: 
-\begin{enumerate}
-	\item Innerhalb eines Prozesses ist es leicht zu entscheiden, was ``fr\"{u}her'' oder ``sp\"{a}ter'' ist.
-	\item Prozesse treten nur mit Nachrichten in Kontakt. (Keine Back-Channels)
-\end{enumerate}
-\textbf{Modellvorstellung:} Ein Prozess ist eine wohldefinierte Abfolge von Ereignissen.\\
-\\
-\textbf{Typische Ereignisse:} Senden einer Nachricht, Empfangen einer Nachricht, Berechnung eines Ergebnisses, \"{A}nderung eines Attributes eines Objekts, Speichern einer Datei. \\
-\\
-Idee (Lamport) definiere eine ``geschehen vor'' Relation. Relation zwischen zwei Ereignissen.\\
-
-Schreibweise ``$\ra$''\\
-\\
-Zuerst f\"{u}r Ereignisse in einem Prozess $i$:\\
-\\
-$l_1 \ra_i l_2 \qquad l_1$ und $l_2$ im selben Prozess, dann ist die Reihenfolge klar.\\
-\\
-Die durch $\ra_i$ sortierte Folge der Ereignisse in einem Prozess nennt man eine ``history''. Klar ist: Eine Nachricht kann erst empfangen werden, nachdem sie gesendet wurde.\\
-\\
-Definiere die ``geschehen-vor'' Relation $\ra$ nun wie folgt:
-\begin{enumerate}
-	\item Falls es einen Prozess $i$ gibt, so dass\\
-		$l \ra_i e'$ dann gillt $l \ra e'$
-	\item F\"{u}r jede Nachricht $m$ gilt\\
-		send($m$)$\ra$receive($m$)
-	\item Es gilt $e\ra e'$ und $e'\ra e''$ dann gilt $e\ra e''\\$		
-\end{enumerate}
-Beispiel:
-\newpage
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=90mm]{vs10.png}
-\end{center}
-\end{figure}
-
-Ergibt:\\
-\\
-Wegen 1.: $\quad a\ra b \qquad c\ra d \qquad e\ra f$\\
-Wegen 2.: $\quad b\ra c \qquad d\ra f$\\
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=60mm]{vs11.png}
-\end{center}
-\end{figure}
-\\
-Frage: Gilt $e\ra c$?? Kann es sein, dass f\"{u}r zwei Ereignisse $e$ und $e'$ sowohl $e\ra e'$ als auch $e'\ra e$ gilt? Antwort: Nein!
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=70mm]{vs12.png}
-\end{center}
-\end{figure}
-Hier gibt es zwei Begr\"{u}ndungen f\"{u}r $a\ra f$.\\
-\\
-Es gilt weder $a\ra e$ noch $e\ra a$ so bezeichnet man $a$ und $e$ als nebenl\"{a}ufig. Schreibweise: $a||e$\\
-\\
-Die ``geschehen vor'' Relation stellt einen m\"{o}glichen Datenfluss dar. Fragen der Art: ``Hat Ereignis $e_i$ das Ereignis $e_j$ m\"{o}glicherweise beeinflusst?'' sollen beantwortet werden.\\
-\\
-Wie stellt man ``$\ra$'' auf einem Rechner fest?\\
-\\
-Erster Ansatz:
-\subsection{Logische Uhr von Lamport}
-\begin{itemize}
-	\item Jeder Prozess $i$ hat seine eigene logische Uhr $L_i$. $L_i$ w\"{a}chst monoton.
-	\item Die eigene Zeit wird Nachrichten als Zeitstempel mitgegeben.
-\end{itemize}
-Wie wird $L_i$ jeweils aktualisiert? $L_i$ wird vor (bei) einem Ereignis in $P_i$ erh\"{o}t. 
-
-\begin{itemize}
-	\item Sendet Prozess $P_i$ eine Nachricht $m$, so wird der Nachricht der Zeitstempel $t=L_i$ mitgegeben.
-	\item Beim Empfang einer Nachricht berechnet Prozess $P_j$ das Wort $L_j = max(L_j, t)+1$ und weist diesen Stempel dem Empfangsereignis zu.
-	\item Die $L_i$ (Lamport-Zeitstempel) werden mit $0$ initialisiert.
-\end{itemize}
-\textit{Diese Definition wurde W\"{o}rtlich aus dem Buch abgeschrieben, nicht ganz Widerspruchsfrei. Daher wirds im Folgenden nochmal Veranschaulicht dargestellt}.\\
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=110mm]{vs13.png}
-\end{center}
-\end{figure}
-\\
-Anschaulich: Das Empfangsereignis bekommt einen Zeitstempel der sowohl h\"{o}her ist als der Stempel des Sendeereignis als auch der Zeitstempel, der im eigenem Prozess vor ihm liegt.\\
-\\
-Frage: Was kann man aus Lamport-Zeitstempeln ableiten? Beispiel:\\
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=100mm]{vs14.png}
-\end{center}
-\end{figure}
-\begin{itemize}
-	\item Wenn $e\ra e'$ dann gilt $L(e) < L(e')$
-	\item Es gilt nicht: $L(e) < L(e') \Ra e\ra e'$ (Ein Beispiel: $L(b) > L(e)$ aber $e||b$)
-	\item Man kann aus $L(e) < L(e')$ nur folgern $e' \not \rightarrow  e$
-\end{itemize}
-Manchmal gibt es Probleme, bei welchen sich alle Teilnehmer \"{u}ber eine Reihenfolge einig sein m\"{u}ssen, wobei egal ist, welche Reihenfolge es ist.\\
-\\
-\textbf{Beispiel:} Eine Bank f\"{u}hrt Konten mehrfach damit man gegen Abst\"{u}rze einzelner Server gesichert ist.
-Transaktionen (\"{U}berweisungen) werden an alle Server geschickt.
-F\"{u}r den Kunden ist die Ausf\"{u}hrungsreihenfolge von Transaktionen egal.\\
-\\
-Korrektheitsforderung: 
-\begin{itemize}
-	\item Jede einzele Transaktion mu{\ss} korrekt gesendet werden.
-	\item Alle Server m\"{u}ssen zu dem gleichen Ergebnis kommen. D.h. die Server m\"{u}ssen sich auf eine (beliebige) Reihenfolge einigen.
-\end{itemize}
-Wenn die Server sich nicht einigen k\"{o}nnte folgendes passieren:
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=100mm]{vs15.png}
-\end{center}
-\end{figure}
-\begin{itemize}
-	\item Kunde hat 1000 EUR
-	\item Transaktion A: Einzahlung 100 \officialeuro
-	\item Transaktion B: Verzinsung um 1\%
-\end{itemize}
-Dieses Probem kann mit Lamport-Zeitstempeln gel\"{o}st werden, wie im Folgendem gezeigt wird:\\
-\\
-Grundidee der L\"{o}sung: Alle Server m\"{u}ssen die Transaktionen in der gleichen Reihenfolge ausf\"{u}hren. Angewandtes Konzept ist ein ``vollst\"{a}ndig geordneter Multicast'' (Totally Ordered Multicast).\\
-\\
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=90mm]{vs16.png}
-\end{center}
-\end{figure}
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=90mm]{vs16b.png}
-\end{center}
-\end{figure}
-Unterscheide von jetzt an konzeptionell zwischen dem Empfang von Nachrichten und der Auslierferung von Nachrichten. Bei einem ``vollst\"{a}ngig geordneten Multicast'' sorgt die Middleware daf\"{u}r, dass alle Anwendungen die Nachrichten in der gleichen Reihenfolge ausgeliefert bekommen.\\
-\begin{enumerate}
-	\item Teilschritt zur Realisation eines vollst. geordn. Multicasts mit Hilfe von Lamport Zeitstempeln: Erweitere die Lamport-Zeitstempel um die Rechner-Nummer (Prozess-ID o.\"{A}.) als Nachkommastelle!\\
-	\\
-	$\Ra$ Es gibt keine gleichen Zeitstempel mehr! D.h. f\"{u}r zwei verschiedene Ereignisse $e_1$ und $e_2$ gilt jetzt entweder $L(e_1) < L(e_2)$ oder $L(e_2) < L(e_1)$.
-	\item Teilschritt: Implementiere damit den ``Totally Ordered Multicast'' wie folgt:\\
-	\\
-	Jede Nachricht bekommt den Zeitstempel des Senders und wird auch an den Absender gesandt. Empfangene Nachrichten werden in eine lokale Warteschlange eingef\"{u}gt die nach Zeitstempeln geordnet wird.\\
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=70mm]{vs17.png}
-\end{center}
-\end{figure}
-\\
-Nun stelle eine weitere Forderung auf: Die Nachrichten die \underline{ein Sender} abschickt, kommen bei allen Empf\"{a}ngern in der Reihenfolge des Absendens an!
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=70mm]{vs17b.png}
-\end{center}
-\end{figure}
-Diese Forderung ist entscheidend, aber relativ leicht zu erf\"{u}llen (z.B. durch Nummerierung von Paketen oder verbindungsorientiertem Protokoll).\\
-	\\
-	Der Empf\"{a}nger einer Nachricht multicastet eine Best\"{a}tigungsnachricht (ACK Acknowledge) an alle anderen Prozesse. (Nachricht bekommt Zeitstempel und wird an den eigenen Absender gesandt!) Nun sammeln sich in den Warteschlangen die Originalnachrichten (die vollst. \textit{geordnet} ausgeliefert werden sollten) und die zugeh\"{o}rigen Best\"{a}tigungen.\\
-	\\
-	Eine Nachricht wird aus der Hold-Back Queue ausgeliefert, wenn sie an der Spitze steht und man von allen Prozessen die zugeh\"{o}rige ACK-Meldung bekommen hat.
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=70mm]{vs18.png}
-\end{center}
-\end{figure}
-Damit werden Nachrichten erst ausgeliefert, wenn klar ist, dass alle anderen Prozesse diese Nachricht auch empfangen haben.\\
-Vorsicht: Jede Nachricht die ``gemulticastet'' werden soll hat bei $N$ Teilnehmern $N^2$ ACK-Nachrichten zur Folge.
-\end{enumerate}
-Die Lamport-Zeitstempel waren nicht geeignet, die ``$\ra$''-Relation auf einfache Weise zu \"{u}berpr\"{u}fen. Deswegen: Erweiterung des Konzepts.
-
-\subsection{Vektor-Zeitstempel}
-\begin{itemize}
-	\item $N$-Prozesse, jeder Prozess $I$ f\"{u}hrt seine eigene Vektor-Uhr $V_i$. Jede Vektor-Uhr $V_i$ ist ein Vektor mit $N$ Eintr\"{a}gen $V_i[j]$.
-	\item Idee: $V_i[j] \quad$ (mit $i \ne j$) ist die Anzahl von Ereignissen in $P_j$, von welchen eventuell ein Datenfluss zu $P_i$ erfolgen konnte.
-	\item $V_i[i]$ ist die Anzahl der Ereignisse, welchen $P_i$ selbst Zeitstempel zugewiesen hat.
-	\item Initialisierung: $V_i[j] = 0 \quad$ f\"{u}r alle $i, j = 1 ..N$.
-\end{itemize}
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=85mm]{vs19.png}
-\end{center}
-\end{figure}
-Zuweisung eines Zeitstempels zu einem Ereignis:
-\begin{enumerate}
-	\item Eigenzeit erh\"{o}hen $V_i[i] := V_i[i]+1$
-	\item Bei einem Sendeereignis schickt man den eigenen Zeitstempel in der Nachricht mit, d.h. die korrekte Vektoruhr.
-	\item Beim Empfang: Nach Erh\"{o}hen der Eigenzeit (vgl. 1) Bildung des Maximums aus empfangenem Zeitstempel und eigener Vektoruhr (elementweise) ergibt neue Vektoruhrzeit.
-\end{enumerate}
-\subsubsection{Vergleich von Vektorzeitstempeln}
-\begin{itemize}
-	\item $v=v' \quad$ iff $\quad v[j] = v'[j]\quad$ ist f\"{u}r alle $j$
-	\item $v\le v' \quad$ iff $\quad v[j] \le v'[j]\quad$ ist f\"{u}r alle $j$
-	\item $v< v' \quad$ iff $\quad v[j] \le v'[j]$ und $v\ne v'\quad$ ist f\"{u}r alle $j$
-\end{itemize}
-Man kann zeigen: $e\ra e' \Ra v(e) < v(e')$ \textit{Das ging auch schon bei Lamport-Zeitstempeln}. $\quad$ und $v(e)<v(e') \Ra e\ra e'$. \textit{Das ging bei den Lamport-Zeitstempeln noch nicht}.\\
-\\
-Man kann erkennen, ob Ereignisse nebenl\"{a}ufig sind: $x||y$ wenn weder $x\le y$ ist noch $y\le x$ ist.\\
-\\
-D.h. Vektorzeitstempel erlauben es, die ``$\ra$''-Relation auszuwerten. 
-\textbf{Nachteil:} Hoher Aufwand (Speicher und Netzlast) bei gr\"{o}sserem $N$. \textbf{Aber:} Es gibt kein Verfahren mit ``kleinerem Aufwand'' um durch Vergleich logischer Uhren Nebenl\"{a}ufigkeit festzustellen.
-
-\section{Globale Zust\"{a}nde}
-\textbf{Aufgabe:} Man mu{\ss} feststellen k\"{o}nnen ob bestimmte Situationen vorliegen.\\
-\\
-\textbf{Beispiele:}
-\begin{itemize}
-	\item Ist ein Objekt \"{u}berfl\"{u}ssig? (Garbage Collection)
-	\item Ist ein verteilter Algorithmus fertig?
-	\item Ist ein Deadlock vorhanden?
-	\item Ist garantiert, dass Ereignis $A$ ``vor'' Ereignis $B$ auftritt?
-	\item Kann es m\"{o}glicherweise passieren, dass zwei Benutzer eine Datei gleichzeitig benutzen?
-\end{itemize}
-Zur verteilten Garbage Collection: 
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=105mm]{vs20.png}
-\end{center}
-\end{figure}
-Objekte werden durch Referenzen benutzbar. Referenzen, die  momentan transferiert werden, m\"{u}ssen ber\"{u}cksichtig werden.\\
-\\
-Das Erkennen, ob ein Algorithmus in einem verteilten System abgeschlossen ist, kann z.B. schwer sein, wenn folgendes gemacht wird:\\
-\\
-Prozesse warten (passiv) auf Aktivierung (d.h. Zusendung eines Arbeitspaketes).
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=85mm]{vs21.png}
-\end{center}
-\end{figure}
-W\"{a}hrend das Paket unterwegs ist, sind alle Prozesse ``passiv'', aber der Algorithmus noch nicht abgeschlossen.\\
-\\
-Problem: Weil es keine globale Zeit gibt, ist man nicht in der Lage eine Momentaufnahme (Snapshot) des Systems herzustellen. Deswegen kann man nicht feststellen ob zu einer Zeit $t$ eine Situation vorliegt.\\
-\\
-\textbf{Frage:} kann man aus lokalen Zust\"{a}nden, die zu unterschiedlichen Zeiten aufgenommen wurden, einen sinnvollen globalen Zustand zusammensetzen?\\
-\\
-\textit{Einfache aber schlechte} \textbf{Antwort:} Manchmal.\\
-\\
-Antworten auf Fragen der Art: 
-\begin{itemize}
-	\item H\"{a}tte das System in dem Zustand $X$ sein k\"{o}nnen?
-	\item Ist das System garantiert nie im Zustand $X$ gewesen?
-\end{itemize}
-sind teilweise m\"{o}glich.
-\newpage
-\subsection{Konzepte zur ``Formalisierung''}
-\subsubsection{Idee des ``Schnittes'' eines Systems}
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=95mm]{vs22.png}
-\end{center}
-\end{figure}
-~\\
-Die ``History'' von $P_1$ ist $e_1^0\quad e_1^1\quad e_1^2\quad e_1^3\quad ...$\\
-\\
-Die ``History'' von $P_2$ ist $e_2^0\quad e_2^1\quad e_2^2\quad e_2^3\quad ...$\\
-\\
-\begin{tabular}{cccc|}
-$e_1^0$ & $ e_1^1$ & $ ... $ & $ e_1^k$\\
-$e_2^0$ & $ e_2^1$ & $ ... $ & $ e_2^j$
-\end{tabular}
-\\
-\\
-\textit{$e_1^k$ und $e_2^j$ bilden die Front eines Schnittes. Die Front einschliesslich alle vorherigen Zust\"{a}nde sind ``im Schnitt enthalten''}\\
-\\
-Ein m\"{o}glicher Schnitt des obigen Systems w\"{a}re:\\
-\\
-\begin{tabular}{ccc|}
-~ & ~ & $e_1^0$\\
-$e_2^0$  & $e_2^1$ & $e_2^2$
-\end{tabular}
-\\
-\\
-\\
-Ein Schnitt ist konsistent, wenn f\"{u}r jedes Ereignis des in ihm enthalten ist, auch alle Ereignisse enthalten sind, die im Sinne der ``geschehen vor''-Relation ``vor ihm'' liegen.\\
-\\
-Der Schnitt \textit{von oben} ist inkonsistent, weil z.B. $e_1^1 \ra e_2^0$ und $e_2^0$ ist im Schnitt und $e_1^1$ ist nicht im Schnitt.
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=95mm]{vs23.png}
-\end{center}
-\end{figure}
-Ein konsistenter globaler Zustand wird definiert als konsistenter Schnitt. Der Zustand eines Systems entspricht nie einen inkonsistenten Schnitt.\\
-\\
-Die konsistenten Schnitte ensprechen alle m\"{o}glichen Situationen. Ein verteiltes System bewergt sich durch konsistente globale Zust\"{a}nde.\\
-
-$S_0 \ra S_1 \ra S_2 \ra ...$\\
-\\
-Ereignisse ``$\ra$'' in einzelnen Prozessen: ``Senden'', ``Empfangen'', ``inneres Ereignis''.\\
-\\
-Ein ``RUN'' ist eine Anordnung aller Ereignisse in einem System die konsistent ist mit jeder lokalen history. F\"{u}r das obige System ist\\
-
-$e_1^0 \quad e_1^1 \quad e_1^2 \quad e_1^3 \quad  e_2^0 \quad  e_2^1 \quad e_2^2$\\
-\\
-ein RUN.\\
-\\
-Ist ein RUN auch konsistent mit der globalen ``geschehen vor''-Relation, nennt man ihn eine Linearisierung des Systems. Es kann mehrere Linearisierungen geben! 
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=100mm]{vs24.png}
-\end{center}
-\end{figure}
-\subsection{Auswertung von Pr\"{a}dikaten in globalen Zust\"{a}nden}
-Interessante Pr\"{a}dikate:
-\begin{itemize}
-	\item System ist in einem Deadlock
-	\item Objekt ist ``Garbage''
-	\item Prozess ist terminiert
-	\item Ein Attribut eines Objektes hat einen bestimmten Wert
-\end{itemize}
-F\"{u}r viele Pr\"{a}dikate ist die Auswertung schwer. Deswegen definiert man ``neue Pr\"{a}dikate'' mit Hilfe der gew\"{u}nschten Pr\"{a}dikate.\\
-\\
-$\varphi$ ist ein Pr\"{a}dikat das in einem globalen Zustand ausgewertet werden kann.\\
-\\
-M\"{o}glicherweise $\varphi \quad$ iff $\quad$ Es gibt einen konsistenten globalen Zustand $S$, der eine Linearisierung der Hostorie $H$ durchl\"{a}uft, so dass $\varphi(S) = true$. 
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=40mm]{vs25.png}
-\end{center}
-\end{figure}
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=100mm]{vs25b.png}
-\end{center}
-\end{figure}
-Definitiv $\varphi \quad$ iff $\quad$ F\"{u}r alle Linearisierungen $L$ von $H$ gibt es einen konsistenten globalen Zustand $S$ (der kann von der Linearisierung abh\"{a}ngen) den $L$ durchl\"{a}uft mit $\varphi(S) = true$.\\
-\\
-Vorsicht: $\overline{moeglicherweise} \quad \varphi \ra definitiv \quad \overline{\varphi}$\\
-\\
-aber\\
-\\
-aus definitiv $\overline{\varphi}$ $\not{\ra}$ $\overline{moeglicherweise \quad \varphi}$\\ 
-\\
-Oft interessieren einen ``stabile Pr\"{a}dikate''. Ein Pr\"{a}dikat hei{\ss}t stabil, wenn daraus, dass es einen Zustand wahr ist folgt, dass es in m\"{o}glichen Folgezust\"{a}nde wahr ist.\\
-\\
-Anschaulich:\\
-\\
-M\"{o}glicherweise $\varphi$:$\quad$M\"{o}glicherweise hat sich das System so entwickelt, dass zu irgendeinem Zeitpunkt einmal $\varphi$ galt.\\
-\\
-Definitiv $\varphi$:$\quad$Das System hat sich definitiv so entwickelt, dass auf jeden Fall in irgendeinem Zustand $\varphi$ galt.\\
-\\
-\textbf{Beispiel:} 
-\begin{itemize}
-	\item Objekte k\"{o}nnen von Prozessen ``gelockt'' werden
-	\item $L(x)$ Lock auf ein Objekt haben
-	\item $U(x)$ Unlock (Lock sperrt) zur\"{u}ckgeben
-\end{itemize}
-Pr\"{a}dikat $\varphi$ ``es liegt ein Konflikt vor''. D.h. wenn ein Objekt zweimal gelockt wurde, liegt ein Konflikt vor. 
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=70mm]{vs26.png}
-\end{center}
-\end{figure}
-\begin{itemize}
-	\item definitiv (Konflikt) nein
-	\item m\"{o}glicherweise (Konflikt) nein
-	\item definitiv (kein Konflikt) ja
-	\item m\"{o}glicherweise (kein Konflikt) ja
-\end{itemize}
-\newpage
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=70mm]{vs27.png}
-\end{center}
-\end{figure}
-Alle Linearisierungen des Systems: $abc$, $acb$, $cab$.
-\begin{itemize}
-	\item definitiv (Konflikt) nein $abc$
-	\item m\"{o}glicherweise (Konflikt) ja $acb$
-	\item definitiv (kein Konflikt) ja am Anfang
-	\item m\"{o}glicherweise (kein Konflikt) ja am Anfang
-\end{itemize}
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=70mm]{vs28.png}
-\end{center}
-\end{figure}
-Reicht noch nicht um ``definitiv (Konflikt)'' wahr zu machen (denn es gibt noch die Linearisierung $abc$ die konfliktfrei ist)
-\begin{figure}[htbp]
-\begin{center}
-\includegraphics[width=70mm]{vs29.png}
-\end{center}
-\end{figure}
-\begin{itemize}
-	\item definitiv (Konflikt) ja
-	\item m\"{o}glicherweise (Konflikt) ja
-	\item definitiv (kein Konflikt) nein
-	\item m\"{o}glicherweise (kein Konflikt) nein
-\end{itemize}
-
-\section{Koordination und \"{U}bereinstimmung}
-Grundprobleme:
-\begin{itemize}
-	\item Zugriff auf gemeinsam genutzte Ressourcen mu{\ss} koordiniert werden.
-	\item In vielen Situationen mu{\ss} Einigkeit hergestellt werden (z.B. wer der Master ist, ob eine Transaktion g\"{u}ltig ist, ...).	
-\end{itemize}
-Algorithmmus f\"{u}r wechselseitigen Ausschluss:\\
-\\
-$N$ Prozesse $P_i\quad i = 1 ... N \quad$ greifen mit dem folgenden Protokoll auf eine Ressource zu:
-\begin{itemize}
-	\item enter(): Eintritt in den kritischen Bereich (ggf. blockiert)
-	\item exit(): Kritischen Bereich verlassen
-\end{itemize}
-Anforderungen an einem Algorithmus zur Realisierung des wechselseitigen Ausschlusses:
-\begin{enumerate}
-	\item Sicherheit: H\"{o}chstens ein Prozess ist zu einer Zeit in einem kritischen Bereich.
-	\item Liveness: