###### tags: `fh` `VS`
# Verteilte Systeme 2
[TOC]
## OSS: Operating System Support
Unterlagen:
* Buch: 10.2.1, Kapitel 3
* Folien zu Operating System Support

POL TUT ca 2:15:00
### 1.Wiederholen Sie den Unterschied zwischen Prozess und Thread.
**Process:**
Jegliches Programm zur Ausführungszeit ist ein Prozess. Ein Prozess kann ein oder mehr Threads haben. Der Prozess-Kontrollblock enthält informationen über priorität, Prozess ID, Prozess Status, CPU, Register.
Verschiedene Prozesse teilen keinen Memoryspace mit anderen Prozessen.
Braucht mehr Zeit um fertig zu werden.
**Thread:**
Ist ein Teil eines Prozesses und hat 3 Zustände:
* running
* ready
* blocked
Braucht vergleichsweise wenig Zeit um fertig zu werden.
Threads teilen sich Memoryspace untereinander(solange sie vom gleichen Prozess sind)
#### Ausarbeitung POL
To execute a program, an opertaing system creates a number of **virtual processors**, each one for running a different program. To **keep track** of these virtual processors, the OS has a **process table**, containing entries to store **CPU register values, memory maps, open files, accounting information, privileges, etc.**

**Prozess:**
* **Programm**, das gerade in einem der **virtuellen Prozessoren** des OS **läuft**
* **Eigener Adressraum** und kann nur auf die **eigenen Daten zugreifen** und sie **verändern**
* **Unabhängig** und **geschützt von anderen Prozessen**
* **Kapselt** das Programm und den **Zustand** des Programms, auf den das OS zugreifen kann (Context)
* Prozesse werden durch **Context Switches** vom OS nacheinander abgearbeitet
* "quasi-gleichzeitig" (Multitasking) = **concurrency transparency**
* Beim Context-switch werden die Werte der **Registern** am **Stack** abgelegt und neue geladen
* **Befehle** eines Prozesses werden **sequentiell abgearbeitet**
* **Vorteil:** Prozesse sind voneinenader geschützt
* **Nachteile**
* Jedem Prozess muss ein eigener Adressraum zugewiesen werden
* Context-Sitch, Abspeichern und Neuladen der Prozessregister (Kosten)
* Ist nicht genug Hauptspeicher vorhanden, muss das OS Prozesse vom RAM auf die Festplatte auslagern, bevor es die CPU weitergeben kann
* Hardwareabhängigkeit (Register)

**Thread**
* **Läuft unabhängig** von anderen Threads
* Ein Prozess besteht aus mind. einem Thread (threads exist as a **subset** of a process)
* Wobei verschiedene Threads auf **unterschiedlichen Prozessoren** laufen können

**Unterschied zu Prozess:**
* **leistung ist wichter** als concurrency transparency
* Threads haben den **selben Speicherbereich** des Prozesses
* Austausch von Daten und **Kommunikation** dadurch wesentlich einfacher
* Threading Context switch, the virtual memory space remains the same
* Cost of switching out the registers is the largest fixed cost of performing a context switch.
* Switching only the **processor state** (program counter and register countents) is generally very efficient.
* Thread sind **nicht** automatisch **voreinander geschützt** und muss vom Dev. übernommen werden

**Vorteile von Threads**
* **Einfache Implementierung:** Ein thread pro Teilproblem, anstatt dass ein Prozess alles macht
* **Höherer Durchsatz:** Wenn ein Thread blockiert, kann einfach (billig) geswitched werden
* **Latency transparency:** während ein Thread wartet, kann ein anderer weiterarbeiten

**2 Arten von Threads**
* **User level threads**
verwalten das Programm des Anwenders komplett selbst. Der Kernel weis nichts von der Existenz der Threads. Sie können daher auf jedem OS laufen. Nachteil davon ist, dass bei einem blockierenden System Call der gesamte Prozess blockert wird (damit alle Threads). Die Verwendung von Multiprozessoren ist nicht möglich.
* **Kernel level threads**
laufen unter der Steuerung durch das OS ab. Somit passiert das Switching über den Systemaufruf, was teuer ist. Blockierung wie beim User L.T. können aber nicht passieren. Mehrere Prozessoren können verwendet werden.

Der **Rozess** bilder die Einheit der **Ressourcenverwaltung** und der **Schutzes**.
Die **Threads** kümmern sich um die **Ausführung**
### 2.Welche Bedeutung haben Threads in verteilten Systemen, insbesonders in Client/Server-Umgebungen?
Threads **lassen blockierende Systemaufrufe zu, ohne den gesamten Prozess lahm zu legen, sodass eine **Parallelverarbeitung** trotzdem möglich ist. Das bringt **Vorteile** für verteilte Systeme. Denn blockierende Systemaufrufe **vereinfachen** die Programmierung, während die Parallelverarbeitung die **Leistung** erhöht.

**Multithreaded clients:** In WANs kommt es zu langen Weiterleitungszeiten von Nachrichten zwischen den Prozessen. Die Kommunikationsverzögerung müssen VS irgendwie verberge. (distribution transparency). The usual way to hide communication latencies is to initiate communication and immediately proceed with something else.

**Webbrowser:**
* Für das Abrufen dieser einzelnen Elemente einer Website (html, css, js) muss der Browser eine **TCP/IP-Verbingund** aufbauen, die eingehenden Daten lesen und an die Anzeige übergebn. Der Aufbau der Verbindung und das **Lesen der eingehenden Daten sind blockierende Operationen.**
* Wird der Browser als ein Multithreaded-Client programmiert, wird der Vorgang vereinfacht indem der Webbrowser die HTML-Hauptseite abruft und sie bereits anzeigt, während die Daten noch empfangen werden, sodass der Benutzer schon Zugriff auf den Text hat, während zB die Bilder erst später angezeigt werden.
* Sobalt die HTML-Haupseite abgerufen ist, werden verschiedenen **Threads aktiviert**, die sich um den Abruf der noch fehlenden Teile kümmern
* Jeder Thread baut eine eigene Verbindung zum Server auf und ruft die Daten ab (-> verschiedene Verbindungen, die gleichzeitig geöffnet sind)
* Der Verbindungsaufbau und das Lesen der Daten vom Server geschehen über die blockierenden Systemaufrufe. Der User bemerkt zwar Verzögerungen bei der Anzeige von Bildern u.ä. aber agesehen davon steht ihm das Dokument bereits zur Verfügung.
* Ein weitere Vorteil: **Load balancing**
* Beim eben beschriebenen Prozedere wurden alle Verbindungen zu einem Server hergestellt, ist dieser aber stark ausgelastet, kommt es zu keinen Leistungsvorteilen
* Viele Webserver sind auf mehrere Computer repliziert, die alle genau dieselbe Menge von Webdokumenten bereitstellen und unter demselben Namen bekannt sind.
* Wenn eine Anforderung nach einer Website eingeht, wird sie an einen der Server weitergeleitet, wobei oft ein **sheduling algorithm** (zB Round Robin) zum Einsatz kommt
* Werden Multithread-Clients verwendet, können Verbindungen zu verschiedenen Replikaten aufgebaut werden um Daten parallel zu übertragen
* Durch Multithread-Browser kann das gesamte Webdokument also in viel kürzerer Zeit angezeigt werden.

**Multithreaded servers:**
In VS wird **multithreading hauptsächlich** auf der **Server-Seite** eingesetzt. Der Server-Code und die Entwicklung von Servern werden **dadurch deutlich vereinfacht**, selbst Einzelprozessorsysteme sind damit leistungsstärker.

**Fileserver:** Der Ablauf ist normalerweise der Folgende: der Server wartet auf eine eingehende Anforderung für eine Dateioperation, führt die Anforderung aus und sendet die Antwort zurück. Er muss gelegentlich eine Blockierung durchführen, wenn er auf die Festplatte wartet.

**MODELL 1: Multithreaded-Server**(Parallelism, blocking calls)
* Client **sendet die Anforderungen** an einen Standardendpunkt des Servers
* Dort liest der **Dispatcherthread** (Koordinator) die eingehenden Anforderungen für eine Dateioperation
* Nachdem die Anforderung untersucht wurde, wählt der Server einen **Worker-Thread** aus, der gerade im Leerlauf ist und übergibt ihm die Anforderung
* Der Worker-**Thread führt einen blockierenden Lesevorgang** im lokalen Dateisystem durch, was dazu führen kann, dass der Thread erst fortfahren kann, wenn die Daten von der Festplatte abgeholt wurden

**MODELL 2: Singlethread-Server** (No parallelism, blocking callse)
* Die Hauptschleife des Dateiservers erhält eine Anforderung, diese wird untersucht und bis zum Schluss durchgeführt, bevor die Nächste angenommen wird
* Während dessen können Anforderungen anderer Clients nicht bearbeitet werden, außerdem ist die CPU im Leerlauf, während der Dateiserver auf die Festplatte wartet

**MODELL 3: Finite state-machine**(singlethread)(Parallelism, nonblocking calls)
* Eine Anforderung geht ein und wird vom einzigen Thread untersucht, und entweder kann sie aus dem Cache heraus beantwortet werden oder es muss eine Nachricht an die Festplatte gesendet werden.
* Anstatt nun zu blockieren, zeichnet der Server den Staus der aktuellen Anforderung in einer Tabelle auf und holt anschließend die nächste Nachricht ein
* Diese nächste Nachricht kann entweder eine weitere Anforderung sein oder eine Antwort von der Festplatte über die vorherige Operation
* Ist es eine neue Aufgabe, wird mit der Bearbeitung sofort begonnen
* Ist es eine Antwort von der Festplatte, werden die relevanten Informationen von der Tabelee abgerufen, die Antwort wird verarbeitet und anschließend an den Client gesendet
* Der Server muss dafür "nicht-blocierende" Aufrufe für send und receive verwenden
* Dieses Modell entspricht nicht dem eines sequentiellen Prozesses: der Status für die Berechnung muss für jede gesendete und empfangege Nachricht expizit in einer Tabelle gespeichert und wiederhergestellt werden
* Der Prozess wird als endlicher Zustandsautomat betrieben, dem ein Ereignis zugeführt wird und der dann, je nach dem was darin enthalten ist, darauf reagiert
### 3.Welche Aspekte Verteilter Systeme sind auf Client-Seite zu berücksichtigen? Wie werden User Interfaces in die Architektur Verteilter Systeme eingebunden? Wie können dabei verschiedene Arten der Transparenz unterstützt werden? Hinweis: Erläutern Sie nicht das angegebene X-Windows-Beispiel. Beziehen Sie die Frage auch auf den Überblick über aktuelle UI-Architekturen. Interessierte finden in dem Paper über die Entwicklung von User Interface Tools weitere Informationen.
**Arten** wie ein Client die Kommunikation zu einem Server ermöglicht:
* a)Für **jeden Remote Service** hat der Client ein **Gegenstück** (Thick client)
* b)UI greift direkt auf **remote Services** zu (**Thin Client/Dumb terminal**)


**Interact** with human **user** and remote **server** in **parallel** (non blocking towards user)
* **Hide communication latencies:** Do sth. else in parallel (e.g. Web browser load .js, .html, .css)
* **Load balancing** (only useful if supported on server side): connections to different replicas, data transfer in parallel
* **Higher Performance:** Local data processing


**Transparency:**
Ziel ist es, dass der User nicht merkt, dass er mit einem remote Server kommuniziert.
* **Distribution**- Client verwendet **Threads** für nebenläufige Aufgaben (evt. **non-blocking calls**)
* **Access** - **Client stub** erzeugt aus dem Interface des Server und versteckt damit die Unterschiede in den Architekturen und die Kommunkation da es wie ein local call aussieht
* **Location** **migration und relocation** Ein geeignetes **Naming System** ist entscheidend. Eine Middleware auf dem Client kann den verwendeten Server vom Client-Prozess verbergen. Wird dieser nun ausgetauscht sorgt die **Middleware** dafür, dass eine Verbindung zum neuen Server aufgebaut wird. Der Client merkt kaum etwas von dieser Änderung (**Naming / (re-)binding**)
* **Replication** Wie beim Punkt zuvor werden die Kopien durch die **Middleware** vom Client-Prozess verborgen oder mittels **Proxy**
* **Failure** Meist von der **Middleware** übernommen (**retry, redirect, cache**)
* **Concurrency** Wird durch spezielle Zwischen-Server gehandhabt und braucht daher keine Unterstützung von der Client Software (**transaction monitor**)
* **Persistence** Wird sehr oft komplett vom Server gehandhabt

**User Interfaces**(nach MVC-Pattern)
* **Model** (Datenmodell): Enthält die dazustellenden Daten
* **View** (Präsentation): Darstellung, Rendering
* **Control** (Programmsteuerung): Verwaltung der View & Überprüfung - Event Handlers

UIs werden oft in einem Schicht-Model realisiert (**Vertikale Verteilung**) Einzelne Schichten können auf verschiedenen Maschinen laufen (**Horizontale Verteilung**) (Distributed UserInterface)

**MVC.Architektur**
* **Modell:** Enthält die **darzustellenden Daten** und ev. auch die **Geschäftslogik**. Es ist von Präsenation und Steuerung **unabhängig**. Die **Änderungen** an Daten im Modell werden nach dem **Observer Pattern** verbreitet.
* **View:** **Darstellung der Daten aus dem Model** und **Entgegennahme von Benutzerinteraktionen. Kennt** sowohl ihre **Steuerung** als auch das **Modell**, dessen Daten sie präsentiert. Im Regelfall wird die Präsentation über Änderungen von Daten im Modell mithilfe des Observer Pattern unterrichtet und kann sich daraufhin die aktualisierten Daten besorgen.
* **Controller:** **Verwaltet** eine oder mehrere **"Views"** und **nimmt von ihnen Benutzeraktionen entgegen, wertet** diese aus und **agiert** entsprechend. **Zu jeder Präsentation existert ein Modell**. Es ist nicht die Aufgabe der Steuereung, Daten zu manipulieren. Der "Controller" entscheidet aufgrund der Benutzeraktion in der Präsentation, welche **Daten** im Modell **geändert** werden müssen. Sie enthält weiterhin Mechanismen, um die Benutzerinteraktionen der Präsenation einzuschränken. Präsentation und Steuerung verwenden zusammen das Entwurfsmuster "Strategie", wobei die Steuerung der Strategie entspricht. Der Controller kann in manchen Implementierungen ebenfalls zu einem "Beobachter" des Modells werden, um bei Änderungen der Daten die View direkt zu manipulieren.


### 4.Ein Client-seitiger Proxy kann u.a. Replikations-Transparenz unterstützen. Unter welchen Umständen kann es dazu kommen, dass Server-seitige Objekte mehrfach (repliziert) aufgerufen werden?

Q: Proxies can support replication transparency by invoking each replica, as explained in the text. Can (the server side of) an object be subject to a replicated invocation?
A: YES: consider a replicated object A invoking another (nonreplicated) object B. If A consists of k replicas, an invocation of B will be done by each replica. However, B should normally be invoked only once. Special measures are needed to handle such replicated invocations.
### 5.Geben Sie grundlegende Design-Entscheidungen für Server an und bewerten Sie diese.

1. Iterativ oder Concurent
2. Wie kann ein Server gefunden werden?
3. Ob und wie wird ein server unterbrochen?
4. Stateless oder stateful?
5. vertieft in frage 6

#### Ausarbeitung POL
Ein **Server ist ein Prozess**, der einen bestimmten Dienst implementiert. Prinzipiell **wartet** ein **server** auf eine **Anfrage** von einem Client, verarbeitet er diese und wartet dann wieder. Hier müssen einige Design-Entscheidungen getroffen werden.
**1.Iterativ or concurrent?**
* Iterativ - Der Server **selbst verarbeitet die Anfragen** und gibt den Client eine **Antwort zurück**
* Concurrent - Der Server **leitet die Anfrage weiter** zu einem seperaten Thread oder Prozess. (Ein Multithreaded Server ist ein Bsp für concurrent Server)

**2.Where/how to find/bin the server?**
* Globale Zuweisung - Hier werden **bekannte Dienste** auf bestimmte **well-known ports** ausgeführt (z.B. HTTP) In dem Fall braucht der Client nur mehr wissen, in welchem Netz sich der Server befindet.
* Dynamische Zuweisung - (Name or directory servers)
Dienste, die keine vordefinierten Ports benötigen, kann man **dynamisch/beliebig** von ihrem **OS** einen Port zuweisen lassen. Aber wie erkennt der Client auf welchem Port er seine Anfrage hinaus schicken soll?
**Solution a)**(Client-to-server binding using a daemon)
Habe a special **daemon** running on each machine that runs servers. The daemon keeps **track** of the current **end point** of each service. The daemon itself **listens to a well-known end point**. A client will first contact the daemon, request the end point, and then contact the specific server.
**Solution b)**(Client-to-server binding using a superserver)
Implementing each service by means of seperate server may be a waste of resources. It is common to have lots of servers running simultaneously, with most of them passively waiting. **Instead of having to keep track of** so many **passive processes**, it is often more efficient to have a **single superserver listening to each end point** associated with a specific service. When a **request** comes in, the **daemon forks a process** to take further care of the request. That process will exit after it is finished.

**3.How to interrupt the server/Out-of-band control?**
* **Abruptly exit** - the clien **application**(which will automatically break the connection to the server), **immediately restart** it, and pretend nothing happened. The **server will eventually** tear down the old connection, **thinking** the **client** has propably **crashed**
* **Better approach** is to develop the client and server such that it is possible to send **out-of-band data**, which is data that is to be processed by the server before any other data from that client.
* **Solution a** Is to let the server **listen** to a **separate control end point** through which the **normal data** (commands) passes.
* **Solution b** Send **out-of-band data** across the **same connection** through which the client is sending the original request. In TCP, for example, it is possible to transmit urgent data. When urgent data are received at the server, the latter is interrupted (e.g., through a signal in Unix systems)

**4.Stateless, stateful, soft state or session state?**
* **Stateful:** Server **speichert alle Infos** über den Client. Falls man die verwerfen will, muss man diese **explizit löschen**.
* Performance higher while running, but slower after restart (need to load state)
* **Stateless:** Server speichert den Client State nicht und kann den eig. state ändern ohne Clients zu informieren.
* **Soft state:** Spezieller stateless Server. Hier **speichert** der Server die **Infos und Status** vom Client für eine **gewisse Zeit**.
* **Session state:** One should distinguish between (temporary) **Session state** and **permanent state**. State should be maintained for some time, but not indefinitly. Often in three-tiered clientserver architectures, where the application server actually needs to access a database server through a series of queries before being able to respond to the requesting client. The issue here is that no real harm is done if session state is lost, provided that the client can simply re-issue the original request. This observation **allows** for **simpler** and **less reliable storage of state**
* **Permanent state:** Typically information maintained in database.
### 6.Ist ein Server der via TCP mit dem Client verbunden ist stateful oder stateless? Wie sieht es mit einem Web-Server aus, der im Cache ein Mapping von Client-IP-Adressen zu den vom jeweiligen Client am häufigsten aufgerufenen Seiten unterhält, um bei einem neuerlichen Aufruf diese Seite sofort liefern zu können - ist ein solcher Web-Server stateful oder stateless?
Q: Is a server that maintains a TCP/IP connection to a client statful or stateless?

A: Assuming the server maintains no other information on that client, one could justiably argue that the server is stateless. The issue is that not the server, but the transport layer at the server maintains state on the client. What the local operating system keep track of is, in principle, of no concern to the server. -> interceptor

### 7.Was sind die Besonderheiten von Objekt-Servern? Welche Arten gibt es dabei für die "Invocation", also den Aufruf (evtl. auch die Aktivierung) eines Objektes auf Server-Seite?
**Definition:** An object server is a server tailored to **support distributed objects**
* Provides means to **access objects remotely** according to different activation policies
* Object **creation on invocation vs. during server initization**
* **Seprate memory segments vs shaing code**(class definition)
* Thread policies (single, one per object, one per request,...) and pool vs. on demant
* object adapter implements policies

**Besonderheiten:**
The important difference between a general object server and other (more traditional) servers:
* **Object server** by itself does **not provide a specific service**
* Specific **services** are **implemented by ** the **objects** that reside in the server.
* Essentially, the **server provides only the means to invoke local objects**, based on requests from remote clients
* It is relatively easy to change services by simply adding and removing objects
* An object server thus acts as a place where objects live.

Also, there are **differences** in the **way** an object server **invokes** its **objects**. For example. in a multithreaded server, each object may be assigned a seperate thread, or a seperate thread may be used for each invocation request.

**Alternatives for invoking objects:**
An object consists of two parts: **date representing its state** and the **code for executing its methods**.
For an object to be invokes, the object **server needs to know:**
* Which code to execute
* On whcih data it should operate
* Whether it should start a separate thread to take care of the invocation

**Approach A:**
* Assume that **all objects look alike** and that there is only **one way to invoke an object**
* Such an approach is generally **inflexible** and often **unnecessarily constrains developers** of dist. obj.

**Approach B:**
* Server to **support different policies
* **Policy A**: Create a transient (flüchtig) object **at invokation req.** and **destroy** once no client is bound to it anymore.
* **Advantage:** An obj. will need a server's **resources** only as long as the object is really needed
* **Drawback:** An **invocation** my **take some time** to complete, because the object need to be created first.
* **Policy B** Create **all transient objects at the time the server is initializied**
* At the cost of consuming resources even when no client is making use of the object.

**Approach C:**
* **Each** of its **objects** is placed in its **own memory segment (objects share neither code nor data)**
* For security reason or if obj. impl. doesnt speparate data and code.
* The alternative approach is to let objects **at least share their code**

**Approach D:**
* Respect to **threading**
* The simplest approach is to implement the server with only a **single thread of control**
* Alternatively, the server **may have several threads**, one **for each** of its **objects**
* Whenever an invocation request comes in for an object, the **server passes the request to the thread** responsible for that object.
* If the **thread** is currenty **busy**, the **request** is temporarily **queued**
* **Advantage:** Objects are automatically protected against concurrent access: all invocations are serialized through the single thread associated with the object. Neat and simple
* It is also possible to use a separate thread for each invocation reuqest, requiring that objects should have already been protected against concurrent access. Independent of using a thread per method is the coiche of whether threads are created on deamd or the server maintains a pool of threads.

Generally, there is **no single apporach/policy**

### 8.Was ist ein Objekt-Adapter, wozu wird er benötigt und wie funktioniert er? Hinweis: Erläutern Sie nicht das angegebene C++-Beispiel im Detail, sondern stellen Sie die zugrundeliegenden Prinzipien dar. Interessierte finden in der CORBA Spezifikation im Kapitel 11 (POA - Portable Object Adapter) eine konkrete Umsetzung des allgemeinen Objekt-Adapter-Konzeptes.
Decisions on **how to invoke an object** are referred to as **activation policies**, in many cases the object itself must first be brought into the server*s address space before it can actually be invoked.
**Object Adapter/Wrapper:**
* Software implementing a **specific activation policy**/mechanism to **group objects by policy**
* **Object adapters** come as **generic components** to assist developers (genaue Schnittstellen ihrer Objekte sind unbekannt)
* Only needs **to be configured for a specific policy**
* An object adapter has **one or more objects under its control**
* Several adapters to support multiple activation policies
* Invocation requests are dispatched to the appropriate object adapter
* **Unaware** of the **specific interfaces** of the object they control. (otherwise, they could never be generic)
* Can **extract** an **object reference** from an **invocation request**, and subsequently dispatch the request to the referenced object, but now following a specific activation policy. Rather than passing the request directly to the object, an adapter hands an invocation request to the server-side stub of that object. The stub, also called a skeleton, is normally generated from the interface definitions of the object, unmarshals the request and invokes the appropriate method.

**INFO:** A **servant** is the general term for a piece of code that forms the **implementation of an object**

1. Wenn eine Aufrufanforderung beim Server eintrifft, wird diese Anforderung dem zugeordneten Objektadapter zugeleitet
2. Anforderung wird dann an dem Server-Stub (Skeleton)übergeben.
3. Dieser Server-Stub packt die Anforderung aus und ruft die entsprechende Methode auf.

### 9.Erläutern Sie die wichtigsten Aspekte der Code Migration.
Bei der **Code-Migration** können neben Daten auch ganze **Teilprogramme verschickt werden**

**REASONS FOR MIGRATING CODE:**
* Improve the **overall system performance / load distribution by parallelism** or by moving processes from heavily loaded to **lightly-loaded machines**.
* Increases flexibility and scalability by dynamically configuring the client and provide service interfaces on demand:
* Also: Improved **versioning** and **evolution**


The principle of dynamically configuring a client to communicate to a server. The client first fetches the necessary software, and then invoked the server (e.g. Java applet).

**MODELLE FÜR CODE-MIGRATION**
Ein Prozess besteht aus 3 Segmenten:
* **Code-Segment**(tatsächlicher Programmcode)
* **Ressourcen-Segment** (Referenzen zu externen Ressourcen, wie Dateien, Drucker, Geräte, andere Prozesse,...)
* **Execution-Segment** (Speichert den Ausführungszustand des Prozesses: private Daten, Stack, Programm Counter,...)

**WEAK MOBILITY**
* Hier wird **nur** das **Code-Segment** übertragen
* Es ist hier **nur möglich** das Programm an **einer, von** möglicherweise **mehreren, vordefinierten Positionen zu starten**
* Vorteil in diesem Modell ist die Einfachheit.
**STRONG MOBILITY**
* Hier wird das **Code-Segment** und das **Execution-Segment übertragen**
* Hier ist es **möglich** den **laufenden Prozess anzuhalten**, auf eine andere Maschine **zu übertragen**, und an der letzten Stelle **fortzusetzen**.
* **Nachteil**, es ist **schwieriger zu implementieren**

Hingegen können **Ressourcen-Segmente nicht einfach** ohne Vorsicht mit den anderen Segmenten **übertragen** werden. Zur Übertragung des Ressourcen-Segment müssen die einzelnen Ressourcen in Betracht gezogen werden. Dazu gibt es 3 verschiedene **Arten** wie man eine **Ressource ansprechen** kann. Das beschreibt die **Prozess-zu-Ressourcen-Bindung.**

**PROZESS-ZU-RESSOURCEN BINDUNG**
* **Bindung durch Identifier:** zB ein Programm das eine eindeutige URL verwendet um auf eine Website zu verweisen.
* **Bindung durch Wert:** zB ein Programm dass sich auf Standardbibliotheken stützt, wie in C
* **Bindung durch Typ:** zB bei Referenzen auf lokale Geräte, wie Monitore, Drucker, usw.

Bei der Codemigration müssen wir oft **Referenzen auf Ressourcen austauschen**, ohne aber die Art der Bindung ändern zu können. D.h. es muss geschaut werden, ob die **Ressource** eventuell **an ein Programm gebungen** ist oder nicht. Dies beschreibt die **Ressourcen-zu-Computer-Bindung**.

**RESSOURCEN ZU COMPUTER BINDUNG**
* **Unattached/Ungebundene Ressourcen:** Können einfach zwischen verschiedenen Computern verschoben werden.(zB Dateien, die nur mit dem Programm verbunden sind)
* **Fastened/Gebundene Ressourcen:** möglich, aber nur zu relativ hohen Kosten(zB lokale DB)
* **Fixe Ressourcen:** Eng an einen Computer oder eine Umgebung gebunden und können nicht verschoben werden.

Daraus ergeben sich **neue Möglichkeiten** für das **Senden von Ressourcen** in einem Code

### 10.Erläutern Sie das Konzept der Virtualisierung und in weiterer Folge deren Bedeutung für die Code Migration in heterogenen Umgebungen.
Hardware und low-level Systemsoftware ändern sich relativ schnell, während abstraktere Software (Middleware, Anwendungen) stabiler ist. Mit **Virtualisierung** können **veraltete Schnittstellen** einer alten Plattform **auf neue Plattformen portiert** werden.
Virtualisierung **erweitert oder ersetzt** somit eine **bestehende Schnittstellt** so, dass sie das **Verhalten** eines anderen Systems **nachahmt** (a) Allgemeine Gliederung von Programm, Schnittstelle und System; (b) allgemeine Gliederung eines virtuellen Systems A oberhalb von B

**ARTEN DER VIRTUALISIERUNG**
**Process Virtual Machine**
* Es wird ein **Runtime System** erstellt, das einen **abstrakten Befehlssatz** zum Ausführen von Anwendungen bietet.
* Die Befehle können **interpretiert** werden (zB Java runtime environment) oder **emuliert** werden (Wine: Windows Anwendungen auf UNIX plattformen)
* Bei der **Emulation** muss auch das Verhalten von **Systemaufrufen nachgeahmt** werden, was **komplex** ist.
* Die **Virtualisierung** findet **nur für einen einzigen Prozess** statt.

**Virtual Machine Monitor (VMM):**
* Es wird ein **System als eigene Schicht implementiert**, das die **ursprüungliche Hardware vollständig abschirmt**
* Es bietet den **kompletten Befehlssatz** dieser (oder anderer HW) als Interface
* Dieses Interface kann **gleichzeitig verschiedene Anwendungen** zu Verfügung gestellt werden.
* Damit ist es möglich **mehrere und verschiedene OS unabhängig und gleichzeitig** (concurrent) auf derselben Plattform laufen zu lassen
* VMM bezeichnet die Schicht. Bsp.: VMware, VirtualBox(Oracle)

**BEDEUTUNG FÜR CODE MIGRATION IN HETEROGENOUS SYSTEMS:**
* Mit **Process virtual machines** kann man einzelne **Prozesse migrieren**, da sie entweder direkt den Quellcode (Bsp Skripsprache wie Python) oder den vom Compiler erzeugten Code (Bsp.: Java) interpretieren können
* **VMM's** ermöglichen die **Migration von ganzen Computerumgebungen**
* **Starke Mobilität** (Prozesse können an einem beliebigen Punkt der Ausführung verschoben werden und fahren anschließend am selbsen Punkt fort). Bindungen von Prozessen an lokale Ressourcen bleiben of erhalten, da sie Teil der migrierten Umgebung sind.
**WAYS TO HANDLE MIGRATION (CAN BE COMBINED)**
* **Pushing memory pages** to the new machine and **resending the ones** that are later **modified during the migration** process (extra effort)
* **Stopping** the current virtual machine; **migrate memory, and start the new VM.** (Long service interruption)
* Letting the new VM pull in new pages as needed, that is, let processes start on the new VM immediately and **copy memory pages on demand** (long migration period)
* **Pre-copy approach:** method1 + mehtod2 (~200ms interruption)

Fazit: mit VMM's kann man laufend Systeme inkl. Betriebssystem migrieren.

## NAM: Naming
Unterlagen:
Buch: Kap. 5
### 1. Erläutern Sie die Begriffe "Name", "Identifier", "Address" sowie den Bezug zwischen diesen Begriffen in der Praxis.
**Name**
Ein String aus bits oder Chars welche eine entität refernzieren. Diese Entität kann praktisch alles sein in einem VS:
* hosts
* printer
* disks
* files
* processes
* users
* mailboxes
* newsgroups
* WebPages
* etc.

Sollte location independent sein -> Name ist unabhängig von der Adresse um besser verständlich für Menschen zu sein.
**Adress**
Ist der Name eines Access Points welche zugriff auf eine entität gewährt.
Es kann mehrere Adressen/AccessPoints für eine Entität geben.
Bsp.:
* Via Telefon erreicht man eine Person
* Eine Person kann mehrere Telefone haben -> meherere Nummern -> mehrere Adressen.
Adressen können sich ändern. ZB wenn sich die physische location von der Entität ändert. (vgl. in ein anderes Land umziehen -> Nummer ändert sich)

**Identifier**
Sind Namen die eine Entität eindeutig identifizieren. Folgende Kriteren müssen dafür erfüllt sein:
* referenziert maximal eine Entität
* jede Entität ist durch maximal einen Identifier referenziert
* ein Identifier referenziert stets die gleiche Entität

Bsp.: Die Telefonnummer von Bob kann sich ändern, und es kann mehrere Bob's geben. Seine Sozialversicherungsnummer ändert sich jedoch nicht.
#### Ausarbeitung POL
**Name:**
* **String of bits or characters**
* used to **refer to an entity**
* regular, nonuinque, nonidentifying name
* often human readable

**Entity:**
* An entity in a distributed system **can be practically anything**
* Typical **examples** include resources such as hosts, printers, disks, and files
* Other well-known examples of entities that are often explicitly named are processes, users, mailboxes, newsgroups, Web pages, graphical windows, messages, network connections, and so on
* **Entities can be operated on** and therefore needs an access point
* **access points are special kind of entity**

**Address:**
* **Name (location) of an access point**
* The **address of an access pooint** of an entity is also simply called an **address of that enitity**
* An entity can offer **more than one** access point
* An entity **may change its access points** in the course of time
* An address is thus **just a special kind of name:** it refers to an access point of an entity.
* Adresses used as regular names is generally very **inflexible** and **often human unfriendly**, and hardly ever done
* Let a service be known by a seperate name independent of the address of the associated server in case the service will be located on a different server with a different address
* Address as name of entity? No - Addresses can be reasigned.

**Identifier:**
* Names that are used to **uniquely identify** an entity
* A true identifier is a name that has the following properties
* An identifier refers to **at most one entity**
* Each entity is referred to by **at most one identifier**
* An identifier always **refers to the same city** (i.e. it is never reused)
* By using identifies, it becomes **much easier to** unambiguously **refer** to an entity
* Identifiers are **location independant (transparenxy)**
* Addresses can be reassigned, so we cannot use it as identifier

**Addresses** and **identifiers** are **2 important types of names** that are each **used for very different purposes**. In many computer systems, addresses and identifiers are **represented in machinereadable form only**, that is, in the form of bit strings
### 2. Was ist ein "Name Space" und woraus besteht er? Erläutern Sie das Grundprinzip der "Name Resolution" und des "Closure Mechanismus" anhand eines Beispieles (zB Unix File System).
**NameSpace**
Eine methode Namen zu organisieren/strukturieren.
Für stukturierten Namen kann der NameSpace als beschrifteter gerichteter Graph mit 2 Arten von Nodes dargestellt werden.
* Leaf nodes
* repräsentiert eine benannte Entität
* hat keine ausgehenden Graphen
* stores information
* directory node
* hat mindestens einen ausgehenden benannten Graphen
* all Graphen werden im Directory table gespeichert
* root node
* ist eine directory node
* hat allerdings keine Graphen die zu ihre führen.
* ist die "oberste"

Names sind IMMER in einem NameSpace organísiert ->
**NameResolution**
Bezeichnet den Vorgang mit hilfe eines gegebenen Namens den Pfad zu finden welcher zu der Node führt und die Daten dort auszulesen
Liefert den Identifier einer Node.
**Closure Mechanismus**
Zu wissen wo und wie man startet mit der NameResolution (bei der Root node).
Wählt aus was als RootNode hergenommen wird um von dort mit der NR zu beginnen.
#### Ausarbeitung POL
**Namespace**
* **names** are commonly **organized** in name spaces
* convenient mechanism for storing and receiving information about entities by means of names
* can be represented as a **labeled, directed graph**
* **Nodes:**
* **each node** is considered another **entity**
* and has its own **identifier**
* **leaf node:**
* Represents a named entity
* Has no outgoing edges
* stores information on the entity its representing
* **Directory node:**
* Has a number of outgoing edges
* edges are labled with names
* a **local name** is always defined relative only to a directory node
* a global name denotes the same entity no matter where
* **Directory table:**
* contains all outgoing edges
* represented as a pair (edge label, node identifier)
* **Root nodes**
* special form of **directory nodes**
* only outgoing, no incoming edges
* possible for a naming graph to have several root nodes(for simplicity, many systems have only one)

* **Path name**
* can be referred to by the sequence of labels
* corresponding ot the edges in the path
* sequence of edges / lables: **N:[Label1, Label2, .... Labeln]** (N first node in path)
* **Absolute Path** First node in path is the root node
* **Relative Path** First node in path is NOT the root node
* Generally represented as a single string separated by a special separator (e.g. "/")

In the naming graph for UNIX a **directory node** represents a **file directory**, whereas a **leaf node** represents a **file**. There is a **single root dir**, represented in the naming graph by the **root node**. The implementation of the **naming graph** is an integral part of the complete implementation of the **file system**. That **implementation** consists of a **continuous series of blocks** from a logical disk, generally divided into a **boot block**, a **suberblock**, a series of index nodes (called **inodes**), and a **file data block**

**Boot block:**
* special block of data and **instructions**
* **Automatically loaded** into main memory **on boot**
* Used to **load the OS** into memory

**Superblock**
* Contains **information** on the **file system**
* E.g. Size, which blocks are not yet allocated, which inodes are not yet used, etc.

**Inodes:**
* Refferd to by **index number**
* Starting at **zero, reserved for root directory** inode
* Contains information on **where teh data can be found** on the disk
* contain additional info: Owner, time of creation, protection, etc.
* when given the index number of an inode, it is possible to access its associated file
* each dir is implemented as a file
* also the case for the root dir
* contains a mapping, between file names and index numbers of inodes
* the index number of an inode corresponds to a node identifier in the mapping graph

**name resolution**
* process of looking up a name
* returns the identifier node

**closure mechnism**
* Knowing how and where to start name resolution
* Deals with selecting the initial note in the namespace
* from which name resolution starts
* der closure-mechanismus bei DNS sind die IP-Adressen der 13 DNS-Root-Server.
* Start punkt muss ausserhalb des namespace definiert sein (Root server DNS IP muss bekannt sein)

Name resolution in the naming graph for a UNIX file system makes use of the fact that the **inode of the root dir** is the **first node** in the logical disk representing the file system. Its actual byte offset is calculated from the values in other fields of the **superblock**, together with hard-coded information in the OS itself on the internal organization of the superblock
To explain how name resolution works, let us consider a path name such as N:[label1,label2,... labelN]. Resolution of this name **starts at node N** of the naming graph, where the **name label1 is looked up in the dir table**, and which **returns the identifier of the node** to which label1 refers. **Resolution the continues** at the identified node by looking up the name lable2 in its directory table, and so on. Assuming that the named path actually exists, **resolution stops** at the last node referred to by labelN, by **returning the contet of that node**.

### 3. Was ist ein Alias? Erläutern Sie die Begriffe "hard link", "soft link" und "mounting". Können Sie sich eine Alternative zum "Mounting" vorstellen?
**Alias**
Ein alternativer Name für eine Entität.
2 Wege das zu implementieren:
* mehrere absolute Pfade zulassen
* beide Pfade welche in der Abbildung zu sehen sind werden als **HardLinks** bezeichnet

* Eine Entität von einer "LeafNode" repräsentieren zu lassen
* die Node speichert einen Absoluten Pfad Namen welcher verfolgt werden kann nach dem auslesen.
* Dies wird **Symbolic** oder **SoftLink**

**mounting**
Bezeichnet den Prozess die root node von einem NameSpace zu finden und zu "mounten" (=Aufsteigen oder in dem Fall benutzen) um zugang zu den Sub-Nodes zu erhalten.
Um in einem **Verteilten System** (anderenfall nicht) einen fremden NameSpace zu mounten wird folgende Information benötigt:
* name des Access Protocols
* name des servers
* name des mounting points im fremden NameSpace

Jeder dieser Namen muss aufgelöst werden.
#### Ausarbeitung POL
**alias**
* **Another name for the same entity**
* Strongly related to name resolution
* **Hard links:** Allow **multiple absolute pathnames** to refer to the same node
* **Soft/Symbolic Link:** Representing an entity by a **leaf node**. But instead of storing the address or state of the entity the **node stores an absolute pathname**. New pathname needs to be resolved then.


**Mounting**
* Name resolution can be used to **merge different name spaces** in a transparent way
* lets us´access other name spaces
* **Mounted local file system** Corresponds to a directory node storing the identifier of a directory node from a different name space
* **Mount point:** Directory node storing the node identifier
* **Mouning point** Directory node in the foreign name space

Wir haben **mehrere Namespaces (NS)** die verteilt sind auf verschiedene Server, die auf unterschiedlichen Maschinen laufen. Wollen wir nun einen NS2 in einen NS1 mountain, muss **über das Netzwerk kommuniziert** werden, wofür zumindest folgende Informationen nötig sind:
* Name des Zugriffsprotokolls
* Name des Servers
* Name des Mounting Points im anderen Namespace

In nicht-verteilten Systemen sind keine dieser Infos notwendig. Die **Namen** können **als URL dargestellt** werden. Aber jeder einzelne Name muss aufgelöst werden:
* Der anem vom Access Protocol muss aufgelöst werden, für die Implementierung eines Protokolls, über das mit dem fremnden Namespace kommuniziert werden kann
* Der Servername muss zur Adress aufgelöst werden, über die der Server erreicht werden kann
* Der Name des Mounting Point muss in sinen Identifier im entfernten Namespace aufgelöst werden
* das übernimmt der Server, auf dem sich der Mounting Point befindet

**Alternative zum Mounting:** Einen Merging point machen, d.h. einen neuen root Knoten, der die beiden Namespaces verbindet. Evt. Cloud computing group possible remote folders evt. load remote namespeace

### 4. Erklären Sie die Schichten der Verteilung von Name Spaces.
* Global Layer: "highest level nodes" Root node und directory nodes die logisch nahe dran liegen
* Stabil -> selten verändert
* Administational Layer: Durch Directory nodes welche innerhalb einzelner Organisationen zusammenhängen
* repräsentieren Gruppen von Entitäten von der gleichen Organisation
* veränderungen passieren auch eher selten -> caching von Lookups kann effektiv sein (bessere Performance)
*
* Managerial Layer: Besteht aus Nodes welche sich öfter Verändern. Zb.:
* Hosts in a LAN
* Files von Libraries oder Binaries.
* Benutzerdefinierte Files und Directories
* Werden auch von den Endbenutzern verwaltet

### 5. Erläutern Sie verschiedene (hierarchische) Möglichkeiten der iterativen/rekursiven "name resolution".
**Iterativ**
* Name Resolver übergibt kompletten namen an den RootNameServer
* Adresse des RootServers muss bekannt sein
* Root löst Pfad soweit er kann auf und liefert das Ergebnis(die adresse des nächsten RootNameServers)
* Von diesem Ergebnis weg löst der neu gefundene RootNameServer weiter auf usw.

**Rekursiv**
Anstatt jedem RootNameServer erneut zu sagen wohin es gehen soll, gibt der vorherige Server seine Eingabe weiter und der neue Server sucht automatisch weiter.
Nur das Kontaktieren der Ziel-Node wird separat vom Client-Prozess ausgeführt.
Verbessert performance über Zeit da die Adressen anderer NameServer erlernt werden welche für bestimmte low level Nodes zuständig sind.
#### Ausarbeitung POL
Ein Name Space ist **hierarchisch strukturiert** und in **logische Schichten** unterteilt:
**GLOBAL LAYER:**
* **Von** den **Knoten** auf der **höchsten Ebene gebildet**
* Das sind der **Root-Knoten** und **andere Verzeichnisknoten**, die diesem **logisch nahe stehen** (zB Child-Knoten)
* Diese Knoten zeichnen sich durch ihre **Stabilität** aus, da ihre **Verzeichnistabellen** nur **selten geändert** werden.
* Solche Knoten können Organisationen oder Gruppen von Organisationen vertreten, für die Namen im Name Space gespeichert sind.
**ADMINISTRATIONSSCHICHT:**
* **Von Verzeichnisknoten gebildet**, die innerhalb **einer Organisation** verwaltet werden
* Ein charakteristisches Merkmal ist, dass sie eine **Gruppe von Entitäten** repräsentiern, die zur **selben Organisation** oder **Verwaltungseinheit** gehören (Bsp.: Verzeichnisknoten für jede Abteilung in einer Organisation).
* Die Knoten sind **relativ stabil**, obwohl Änderungen häufiger auftreten als in der globalen Schicht.
**MANAGEMENTSCHICHT:**
* Bestehen aus **Knoten**, die **regelmäßigen Änderungen** unterliegen
* Das sind zB Knoten, die **Hosts** im lokalen Netzwerk, benutzerdefinierte **Verzeichnisse** und **Dateien** oder gemeinsam genutzte Dateien abbilden.

Der Name Space ist in **überschneidungsfreie Abschnitte** eingeteilt, die in **DNS Zonen** genannt werden. Eine Zonde wird durch einen **eigenen Name Server** implementiert.

### 6. Erläutern Sie das Domain Name System DNS, v.a.den Aufbau des Name Space (Zones), sowie den prinzipiellen Ablauf bei der Namens-Auflösung anhand der DNS Database (Resource Records). Was ist reverse lookup?
DNS ist als hierarchischer Baum aufgebaut. Hat nur global und administrational layer. Managerial layer ist nicht teil von DNS und daher auch nicht davon verwaltet.
Der Sub-Baum einer Root-Node wird **domain** genannt und der Pfad welcher zu dieser Node führt **domain name**. (kann wie ein pfad Name absolut oder relativ sein)
Nur nodes die Zonen repräsentieren müssen NS-Records aufbewahren.
DNS unterscheidet zweischen alias und canonical names(CNAME) welche jeder host hat.

Jede Zone wird via einem NS implementiert welcher Zwecks Verfügbarkeit fast immer doppelt vorhanden ist.
Updates der Zonen werden vom primary NS gehandhabt und finden statt indem die DNS-DB lokal zum primären Server übertragen werden.
Sekundäre NS haben keinen direkten Zugriff zur DB sondern fragen beim primären um einen transfer an. Das nennt man **zone transfer**.
#### Ausarbeitung POL
Das Domain Name System (DNS) ist eines der **größten verteilten Namensdienste** und definiert einen **Benennungsstrandard für das Internet**. Es dient zum **Auflösen von Domain-Namen in IP-Addressen** und der Suche nach **Mail-Servern**.
The **root** is represented by a **dot**(root:[nl,vu,cs,flits] --> flits.cs.vu.nl.)

Der DNS Name Space ist als **hierarchische Baumstruktur** organisiert.
* A lable is a case-insensitive string made up of alphanumeric characters
* each node name space has one incoming edge (exp. root node)
* The lable attached to a node's incoming edge is also used as the name for that node
* Ein **Subtree** wird als **Domain** bezeichnet
* Der Pfadname zu seinem Root Element nennt man **Domain Name**

**ZONES**
* **Teil des Domänenbaums**, den **ein (primary) Nameserver verwaltet.**
* **Secondary Nameserver::** Gespiegelte zones zur Erhöhung der **Verfügbarkeit** bei Ausfällen (**Zone-transfer**)
* Besteht aus **Resource Records**, die in einer **Zonendatei gespeichert** sind (am primary/master)
* Bei **Updates** per **Zonentransfer** zu den Secondary / Slave übertragen
* Eine Zone kann eine gesamte Domain umfassen. Normalerweise werden Subdomänen aber durch eigene Zonen repräsentiert. NS Resource Records (NS-RR) verweisen dabei zu Sub-Zonen, die sich auf andere Nameservern befinden können.

The contents of a node is formed by a collection of resource records. A node in the DNS name space oftern will represent several (nonoverlapping) zones.

**LOOKUP**
Rechner X will eine Verbindung zu "de.wikipedia.org" (Rechner Y) aufbauen. Dazu braut er dessen IP-Addresse.
1. **Local lookup:** Der Rechner X sucht in seiner **Hosts-Datei**. Falls dem nicht so ist, fragt er beim DNS-Server nach
2. Die Anfrage wird bis zum zuständigen NS weitergereicht welcher dann mit dem passenden A record antowrtet

**REVERSE LOOKUP**
* IP-to-Domain lookup
* **eigenständige Domäne für inverse Zugriffe*
* Ein reverser Name enthält die IPv4 **Adresskomponente** in **umgekehrter Reihenfolge**

### 7. (F) Sie sind für den Domain Name Server NS-A der Domain A zuständig. Die Domain B ist eine Subdomain von A, jedoch als eigene Zone realisiert, für die der Nameserver NS-B zuständig ist. Um auf einen Knoten N in B zuzugreifen, ist es folglich notwendig, dass NS-B in NS-A spezifiziert ist. Wann genügt es in NS-A, einfach nur den Domainnamen von NS-B anzugeben und wann ist es unbedingt notwendig, zusätzlich auch den Adress-Record von NS-B einzutragen?

### 8. Was ist Directory Service bzw. "Attribute-based naming"? Beschreiben Sie den prinzipiellen Aufbau des X.500 Name Space sowie dessen LDAP Implementierung.
**DEFINITION:** Directory Services, auch **Attribute-Based Naming** Systeme genannnt, sind **Verzeichnisdienste**, bei denen **Entitäten über Attribute beschrieben** werden. Jede Entität besitzt (Attribute, Value)-Paare, über die die Suche stattfindet.
* **Add/remove** names to /form directory
* **Get** names from directory according to property description pattern (e.g. wildcards)
* Assign **access modes** to names (e.g. Read/write/execute)
* Enforce **access control (X500/LDAP) --> Directory access protocoll (DAP)
* Es ist ein implizierter Baum, jeder Knoten ist Content und Directory (DNS ist explizit)

**OSI X.500**
* Beschreibt den **Aufbau** eines **Globalen Verzeichnisdienstes**
* Ein Eintrag **besteht aus Attributen** und jedes Attribut hat **einen oder mehrere Values**
* Jeder Eintrag hat einen global **einzigartigen Namen**
* Zusammengesetzt aus **Relative Distinguished Names (RDNs)** und den RDNs seiner übergeordneten Einträge
* Dieser Standard wurde nie implementiert

**AUFBAU:**
* **Directory Information Tree(DIT):** Organisiert Einträge, die über einen oder mehrere DSA's verteilt sind, hierarchisch.
* **Directory Systen Agents(DSA):** Besitz Datenbank mit Einträgen
* **Directory User Agents (DUA):** Clients tauschen mit DSAs über das LDAP Informationen aus.
* **Directory Information Base (DIB):** Alle Verzeichniseinträge eines LDAP Verzeichnisdienstes heißen.

**LIGHTWEIGHT DIRECTORY ACCESS PROTOCOL(LDAP)**
* Basiert auf dem OSI X500 Directory Access Protocol
* Effizienter und einfacher ist, sowie auf TCP basiert

Ersten 5 Attirbute (RDNs) sind Namenskonventionen nach dem LDAP Standard:
* Globally unique names: **/C=NL/O=VrijeUniversiteit/OU=Comp.Sc.**
* Analog zum DNS Namen **nl.vu.cs**

### 9. Wie funktioniert in flachen Namensräumen das Location Service? Geben Sie das Grundprinzip möglicher Lösungen an und gehen Sie dabei auch auf die Begriffe Mobility und Discovery ein.
**FLAT NAMING** Identifiers sind random bit strings (**ad hoc or spontaneous networks**)
**Location service:** Maps identifier to address

Ein Location Service kann dazu benutzt werden, Services zu registrieren und aufzufinden. Dadurch wird ein hoher Grad an **Mobility** erreicht, da ein Host nicht mehr über eine **fixe Adresse(IP)** angesprochen wird. Location Services unterscheiden sich von NS und Dir. Services durch die Anforderung, dass sie sich oft/schnell ändern. Also kurz gesagt: Ändern sich die Anforderungen bei Location Services oft und schnell.

**DISCOVERY SERVICE:**
* **When** do we need a discovery service?
* In **ad hoc or spontaneous networks** hosts decide to **share resources and services that change dynamically**
* Nodes **appear and disappear often in a large scale system**
* **Mobility** has to be supported
* **Principles:**
* Hosts must have the **ability to announce and discover** available **resources and services**
* TTL is important in these networks: e.g., lease

**EFFECT OF MOBILITY**
* Hosts on a network are no **longer permanently fixed** in one (topological) **location**
* Laptops, personal digital assistants, and their contents move from one location in the network and join in other points
* In general, objects and resources are **not stationary**
* **Note:** IP addresses refer to fixed locations within the network topology

**NAMING VS. LOCATING ENTITIES**
* Traditional **naming systems are not well suited** for supporting name-to-address **mappings that change often**:
* global and administational layer are assumed to be stable --> caching, replication
* updates are usually restricted to a single name server
* Two immediate solutions
* **change** address **record** (non-local lookup/update)
* **add** symbolic **link**(chain of links)

a. Direct, single level mapping between names and addresses.
b. 2-level mapping (e.g., using identities). Location service maps identifier to address.

**SIMPLE SOLUTIONS:**
* **Boradcasting:**(e.g. ARP)
* Bandwidth?/ Nbr. of hosts interrupted?
* **Multicasting:** restricted group of hosts
* **Multicast address** as general location service
* Locate the nearest replica
* **Forwarding Pointers**
* Wenn eine Entität seinen **Ort ändert, lässt sie eine Referenz** zurück, welche auf ihren neuen Ort zeigt.
* Simple, BUT: long chain, many intermediate locations, vulnerability to broken link, ...
* 
* **Goal of a&b** keep chains relatively short!
* Redirecting of forwarding pointer, by **storing a shortcut** in a proxy
* Skeleton that is no longer referred to can be removed

**HOME-BASED APPROACHES:**
* **Mobility** in large Networks
* Brodcasing and forwarding pointers impose scalability problems
* **Home location keeps track of current location**(highly dependable)
* **Mobile IP:** (placement WAN)
* **Home agent at fixed address** (placement LAN) where host originates from
* Mobile host **registers temporary care-of-address** with the home agent **when changing the network**
* Packets are **tunneled** if host is not in LAN, sender is informed
* **Mobile telephony (GSM) - two-tiered scheme:
* first, check local Visitor Location Register (VLR)
* then, contact Home Location Register (HLR) to find current location
* Drawbacks:
* Communication latency
* **Fixed home location:** availability; permanent migration, register home location with traditional naming service and let client first lookup the home (relatively stable, can be effectively cached)

**HIERARCHICAL APPROACHES**
* Hierarchical **organization of a location service** into domains, sub domains, and leaf domains, each having an associated directory node.
* Entity is represented by location record: In the directory node of a leaf domain it contains an address, else it contains a pointer to the respective sub-domain

## SYN: Clocks and Agreement
### 1. Wozu braucht man Uhrensynchronisation? Erläutern Sie das NTP.
In einem **zentralisierten** System ist die **Zeit eindeutig** (Prozess > Systemaufruf > Kernel > Antwort >: current timestamp). In einem **verteilten System** ist es **nicht trivial**. Ziel: Einigkeit über die Zeit zu erzielen.
* Uhrensynchronisation braucht man für die **Festlegung der Reihenfolge von Operationen in verteilten Systemen.
* Korrektheit verteilter und zeitabhängiger Informationsverarbeitung
* Nicht synchrone clocks kann zu Fehlern bei der Ausfürhung von Programmen führen.

**Beispiel - das UNIX-Programm make: (OR UNISON)**
Begneb Sue abm dass die Objecktdatei output.o wie unten dargestellt den Zeitstempel 2144 hat und kurz danach die Quelldatei output.c vom Programmierer geändert wird, jedoch den Zeitstempel 2143 erhältm weil die Uhr auf diesem Rechner etwas nachgeht. -> Make ruft den Compiler nicht auf!

**NTP(NETWORK TIME PROTOCOL) - PASSIVE TIMESERVER - EXTERNE SYNCHRONISATION**
Ein verbreiteter **Ansatz für Uhrensynchronisation** besteht darin, dass **Clients** sich **mit einem Zeitserver verbinden.** Der Zeitserver kann die **genaue Zeit bereitstellen**, weil er zB mit einem **WWV-Empfänger** (empfängt die Weltzeit/Universal Coordinated Time (UTC)) oder einer **Atomuhr** ausgestattet ist.
Die gemeldete Zeit ist aufgrund der **Nachrichtenverzögerung** beim empfangen bereits veraltet. Der Trick besteht darin, eine gute **Schätzung** für diese **Verzögerung (delay)** zu finden.
In diesem Fall sender A eine Anfrage mit dem Zeitstempel T1 an B. B wiederum notiert die Empfangszeit T2 (seiner eigenen Uhr) und gibt eine mit T3 gestempelte Antwort zurück, die zusätzlich die zuvor protokollierte Zeit T2 enthält. Schließlich notiert A die Zeit T4, zu der die Antwort eintrifft.
Lasst uns nun **annehmen**, dass die Laufzeit von A nach B **ungefähr dieselbe** wie von B nach A ist, was bedeutet, dass T2-T1 = T4-T3. In diesem Fall kann A seine Abweichung relativ zu B wie folgt bestimmen:

* O<0 bedeutet, Uhr von **Client (A) ist zu schnell**
* Die Uhr darf jedoch **nicht zurückgestellt** werden
* Zeitstempel müssen nämlich **immer linear vorwärtsgehen**
* Eine Uhr wird auch nicht in einem Schritt, sondern **langsam korrigiert**
* Bsp.: statt 10ms, nur noch 9ms mit jedem Interrupt hinzufügen bis die Korrektheit erreicht wird.
* Weiters sollte auch nicht sprunghaft die Zeit nach vorne verstellt werden.

**Timer(Quartz Kristall)** oszilliert mit einer bekannten Frquenz +2 Register (counter, holding register). Der Timer zählt runter, bei 0 -> Interrupt und wird durch holding register neu geladen. Interrupt wird clock tick genannt. Der Timer (Quarz) erzeugt zB 100 interrupts pro Sekunde, was heißt dass alle 10ms ein Interrupt passiert und dieser dann auch 10ms zum Holding Register hinzuaddiert. Ist der ClientTimer nun schneller, und die Uhrzeit somit vorne, so wird für einen Zeitraum bei jedem 10ms Interrupt das Holding Register nur um 9ms erhöhrt

**Clock skew:** Denotes the extent to which the frequency differs from that of a perfect clock.
Berechnung der Schätzung für die Verzögerung:

Eigentlich darf man nur Differenzen und Summen bilden zwischen Zeiten der selben Uhr:

### 2. Eläutern Sie den Berkeley Algorithmus. Was ist die Problematik bei der Synchronisation von Physical Clocks?
**BERKELEY ALGORITHMUS: INTERNE SYNCHRONISATION - AKTIVER TIME DAEMON**
Bei **Berkeley Unix** ist der Time Server (=**Time Daemon** ) **aktiv**, der **Server fragt** die Clients von Zeit zu Zeit, wie spät es ist. Abhöngig von den Antowrten erreichnet der Server einen **Mittelwert** der Zeit und **propagiert** diese als die neue Zeit, genauer gesagt, sagt er jedem einzelnen Client wie er seine **Uhr beschleunigen/bremsen** muss.

Diese Variante ist geeignet für **Systeme** welche **keine** Maschine mit einer Verbindung zu einem **Stratum 0** haben oder **nicht** mit der **Außenwelt** kommunizieren müssen. Die **Zeit** am Time Server muss **periodisch manuell gesetzt** werden -> wird das nicht gemacht haben die Server im Netzwerk zwar dieselbe Zeit, aber sie leben "in ihrer eigenen Welt". Ist egal in manchen Anwendungen.
Alle Rechner nach Schritt c) haben sich auf eine **Zeit geeinigt**, es ist **nicht wichtig** ob diese auf mit der **realen Zeit übereinstimmt.** Es reicht, wenn die Rechner sich einigen (egal auf welche Zeit) solange sie mit **keinen externen Geräten kommunizieren** müssen!

**PROBLEMATIK BEI DER SYNCHRONISATION VON PHYSICAL CLOCKS**
**Phyisical clock:**
Durch Verwendung unterschiedlicher Quarzen kann es dazu kommen, dass nach einer Zeit die Uhrzeit in den verschiedenen Geräten nicht mehr übereinstimmt. Das Problem liegt daran, dass es keiner garantieren kann, dass die Kristalle von verschiedenen CPUs (die ihre eigene Uhren verwenden) alle genau mit derselben Frequenz osizillieren -> unterschiedliche Zeitwerte

Die Uhren der einzelnen Maschinen laufen unterschiedlich schnell, daher müssen diese permanent synchronisiert werden selbst bei keiner Nutzlast. Das führt zu permanenten Traffic.
**Timer/Quarz:** Crystl oszillator
* Battery backed CMOS RAM(initial setting)
* Clock offset, skew, defit (different definitions in literature!)
* Real-time systems need actual clock time
* synchronize with real-world time (external!)
* synchronize with each other (internal)
**GMT**(Erde dreht sich um Sonne usw. 24H) Solar Second

**Atomurh TAI** (International Atomic Time, läuft konstanter als GMT)

**UTC**(Universal Coordinated Time)
second=TAI second, but leap seconds kept UTC in phase with solar time (GMT)

**Probleme:** Kommunikationsaufwand, Intervall > nicht "echte" Zeit, tödlich Varianz in der Latenz

### 3. Was sind die Gründe für die Verwendung von Logical Clocks? Erklären Sie die Unterschiede zu den Physical Clocks. Was ist die "happened-before" Beziehung?
**GRÜNDE:**
Es ist **nicht immer wichtig** die genaue oder **reale Zeit** zu kennen bzw. die Uhren genau zu synchronisieren. **Es reicht die relative Zeit** dh die **Abfolge** in der etwas **passiert** (ist), zu kennen.
Wenn 2 Prozesse, deren Uhren nicht synchronisiert sind, nicht miteinander wechselwirken, ist die fehlende Synchronisation nicht beobachtbar und verursacht keine Probleme.

Bsp.: C-Programm: Wir haben die Source-Datei program.c und das kompilierte Programm program.o. Ist die aktuellste Version des Codes kompiliert? Dafür ist der genaue Erstellzeitpunkt der beiden Dateien irrelevant. Es reicht zu wissen, ob program.c neuer oder älter ist als program.o.

Eine Beschränkung auf logisch Uhren **erleichtert die Synchronisation** in Verteilten Systemen ungemein. Die Synchronisation wird dann nicht **Zeitgesteuert** (physical Clocks) sondern **Ereignisgesteuert** (logical Clocks) durgeführt.

**UNTERSCHIED ZU PHYSICAL CLOCKS:**
* **Physical** Clocks bilden die **reale Uhrzeit** ab (UTC)
* **Logical** Clocks bilden die **Reihenfolge von Ereignissen** ab.

**HAPPENS-BEFORE BEZIEHUNG:**
Wurde von **Lamport** definiert für die **Synchronisation von logical clocks**
(Some events are **ordered**. some are **"concurrent"(partial order)**)
[a->b](a passiert vor b) bedeutet, dass alle **Prozesse übereinstimmen** müssen, dass a vor b passiert ist. The happens-before relation can be observed in 2 situations:
1. **Events in one process are ordered** (local clock): Sind die Ereignisse **a** und **b** im **selben Prozess** und a tritt vor b ein, gilt a -> b. (Ereignisse nach lokaler Zeit geordnet)
2. **Messge send happens before message receive:** Is **a** das Ereignis, das bedeutet, dass eine **Nachricht** von einem Prozess **ausgesendet** wurde und **b** das Ereignis, das bedeutet, dass diese **Nachricht** von einem anderen Prozess **empfangen** wurde, dann gilt a -> b. Eine Nachricht kann nicht empfangen werden bevor sie gesendet wurde. Zwischen absenden und empfangen vergeht eine bestimmte endliche Zeit > 0

Die happens-before Relation is **transitiv** dh wenn a->b und b->c dann folgt a->c

**Concurrent (partial order)**: Zwei Ereignisse in **unterschiedlichen Prozessen**, welche **keine Nachricht** austauschen, oder Ereignisse die nicht geordnet sind.

### 4. Wie funktionieren die "Lamport-Timestamps"?
Lamport Algorithmus zum Zuweisen von Zeiten zu Events. Durch die **happen-before relation** benötigen wir die Möglichkeit zum **Messen der Zeit C(x):
* aus **a->b** muss die Beziehung **C(a)<C(b)** folgen
* Wenn **a** das Senden und **b** das Empfangen ist (bei untersch. Prozessen!), dann müssen alle Werte dem **C(a)<C(b)** zustimmen
* Die **Uhrzeit C** muss immer **anwachsen**, darf sich **niemals vermindern**,

Bsp.: 3 Prozesse auf **verschiedenen Rechnern** und **verschiedene Uhrzeiten** mit **unterschiedlichen Geschwinditkeitn**
* Die Prozesse haben unterschiedliche Takte (+6/+8/+10)
* Zum Zeitpunkt 6 sendet Prozess P1 eine Nachricht m1 an Prozess P2. Wie lange diese Nachricht bis zu Ankungt benötigt, hängt von der Uhr ab, der Sie glauben. Auf jeden Fall steht die Uhr in Prozess P2 bei der Ankunft auf 16. Wenn die Nachricht die Startzeit 6 mit sich führt, folgert P2, dass sie für die Reise zehn Takte benötigt hat. Dieser Wert ist sicherlich möglich. Nach dieser Argumentation benötigt die Nachricht m2 von P2 nach P3 16 Takte, was ebenfalls glaubhaft ist.
* Betrachten wir nun die Nachricht m3. Sie verlässt P3 zur Zeit 60 und kommt um 56 bei P2 an. Auf ähnliche Weise wird die Nachricht m4 von P2 nach P1 um 64 ausgesendet und kommt um 54 an. = Diese Werte sind offensichtlich unmöglich, sodass eine solche Situation verhindert werden muss.
Die **Lösung** von Lamport**folgt unmittelbar aus** der **Happens-Before-Relation**. Da m3 zum Zeitpunkt **x** abgeschicht wurde, muss sie um x+1 oder später eintreffen. Daher enthält jede Nachricht die **Absendezeit gemäß Uhr des Absenders**. Wenn die Nachricht eintrifft und die **Empfängeruhr einen früheren Wert anzeigt**, stellt der Empfänger seine Uhr schnell auf einen Einheit nach der Absendezeit vor. In Abbildung b sehen wir, dass m3 jetzt um 61 ankommt. Ebenso trifft m4 um 70 ein.

**Lamport clocks in middleware:**

**Implementierung der logischen Uhren von Lamport**
Um das zu tun unterhält **jeder Prozess a** einen **lokalen Zähler Ci.** Diese Zähler werden **wie folgt aktualisiert:**
1. **Bevor ein Ereignis ausgeführt** wird, führt **Pi** den Schirtt **Ci<-Ci+1** aus
2. Dann, wenn Prozess **Pi** eine Nachricht **m** an **Pj** sendet, setzt er den **Timestamp ts(m)** von m gleich **Ci**
3. Nach dem Empfang der Nachricht **m** stellt der Prozess **Pj** einen eigenen **lokalen Zähler** auf **Cj <- max{Cj, ts(m)}** ein, wonach er den **ersten Schritt ausführt** (Cj <- max{Cj, ts(m)}+1!!!) und die Nachricht an die Anwendung ausliefert.

In einigen Situationen ist eine **zusätzliche Anforderung** wünschenswert: Zwei Ereignisse treten **niemals zu genau derselben Zeit ein**. Um dieses Ziel zu erreichn, können wir die Nummer des Prozesses, in dem dieses Ereignis eintritt, mit einem Dezimalpunkt abgetrennt an die Zeit anhängen. Ein Ereignis zum Zeitpunkt 40 in einem Prozess Pi erhält den Zeitstempel 40i

Note that by assigning the event time C(a) Ci(a) if a happened at process Pi at time Ci(a), we have a distributed implementation of the global tiem value we were intially seeking for.

### 5. Welchen Nachteil haben die Lamport-Timestamps und wie kann dieser durch Vector-Timestamps überwunden werden?
Mit Lamport-Uhren kann durch **bloßes Vergleichen** der **Zeitwerte C(a) und C(b)** nichts zur **Beziehung zwischen den Ereignisen a und b** ausgesagt werden. Mit anderen WOrten wenn C(a)<C(b) gilt, folgt daras nicht notwendigerweise, dass a in der Tat vor b stattfindet.

Per Definition wissen wir, dass für jede Nachricht **Tsend(mi)<Treceive(mi)** gilt. Was kann man dann aus **Treceive(mi)<Tsend(mj)** folgern? Wenn man vom Prozess P2 ausgeht und sagt: m3 wurde gesendet, nachdem m1 empfangen wurde, also hängt m3 von m1 ab, dann kann man damit durchaus recht haben, da m1 warhaftig empfangen wurde, bevor m3 gesandt wurde. Aus der Grafik wissen wir jedoch auch, dass **Treicieve(m1)<Tsend(m2)** gilt. Doch das Senden von m2 hat nichts mit dem Empfangen von m1 zu tun.

Lamport-Uhren haben also **das Problem**, dass diese **keine Kausalität** (Beziehung zwischen Ursache und Wirkung) **berücksichtigen**. (Logical clocks order related events; nothing can be said about unrelated events). Dem lässt sich mithilfe von **Vektoruhren** abhelfen --> beachtet Kausalität

**EIGENSCHAFTEN EINER VERKTORUHR:**
Wenn **as** für ein Ereignis b ist, dann geht a dem Ergebnis b kausal (also in Beziehung zwischen Ursache und Wirkung) voraus.
Damit eine Vektoruhr funktionieren kann, muss **jeder Prozess Pi** einen **Vektor VCi** mit den folgenden 2 **Eigenschaften** haben:
a. **VCi[i]** ist die **Anzahl der Ereignisse**, die bisher in **Pi** eingetreten sind. Mit anderen Worten, **VCi[i] ist die logische Uhr im Prozess Pi**
b. Wenn **VCi[j]=k**, dann weiß **Pi** das **k-Ereignisse in Pj** eingetreten sind. Dies ist daher das **Wissen von Pi über die lokale Zeit im Prozess Pj**

The **first property** is maintained by **incrementing VCi[i]** at the occurence of **each new event** that happens at **process Pi**. The **second property** is maintained by **piggybacking vectors** along with messages that are sent. Im Einzelnen werden die folgenden Schritte durchgeführt:
1. **Bevor ein Ereignis** ausgeführt wird führt **Pi** den Schritt **VCi[i]** <- **VCi[i]+1** aus.
2. Wenn Prozess **Pi** eine **Nachricht m** an **Pj** sendet, setzt er den (Vektor-)Zeitstempel **ts(m) gleich VCi**
3. Nach dem **Empfang** der **Nachricht m** stellt der **Prozess Pj** seinen eigenen Vektor auf **VCj[k]<-max{VCj[k],ts(m)[k]} für jedes k** ein, wonach er den **ersten Schritt ausführt** (VCj[j]<-VCj[j]+1) und die Nachricht an die Anwendung ausliefert

Interessant zu erwähnen ist noch, dass bei diesem System, Nachrichten, welche nicht kausal zusammenhängen, nicht beachtet werden. Es ist für dieses System egal wann und in welcher Reihenfolge solche Nachrichten ankommen.
Not that if an event has timestamp **ts(a)**, then **ts(a)[i]-1** denotes the **number of events processed at Pi that causally precede a**. As consequence, when **Pj receives a message from Pi** with **timestamp ts(m)**, it **knows** about the **number of events that have occured at Pi that causally preceded the sending of m**. More important, however, is that **Pj is also told how many events at other processes have taken place before Pi sent message m**. In other words, **timestamp ts(m) tells the receiver how many events** in other processes have preceeded the sending of m, and **on which m may causally depend**.

Now, V(a)<V(b)=> a->b(and vice-versa)
**Disadvantage:** more storage and message payload;
Wenn all Werte des Vektors in der gleichn >/< Beziehung stehen waren die Ereignisse in einer happened-before Beziehung (z.B.: (1,2,3)&(2,4,5)) aber nicht ->(1,2,3)&(2,3,3)

### 6. Wie funktioniert Distributed Mutual Exclusion. Wie verhalten sich verschiedene Algorithmen hinsichtlich Skalierbarkeit und Fehlertoleranz? (Ohne 6.3.3 Decentralized!)
**Szenario:** mehrere **Prozesse** wollen zur **selben zeit** auf **dieselbe Ressource** zugreifen
**Problem:** die **Ressource** könnte **beschädigt** oder **inkonsistent** werden
**Lösung:** Mutual Exclusion Algorithmen -> immer nur ein einziger Prozess bekommt die Möglichkeit auf eine Ressource zuzugreifen. Beim **distributed Mutex** erfolgt die **Umsetzung** über das Versenden von **Nachrichten**. Zwei Kategorien:

**TOKEN-BASED**
* Um den Zugriff zu regeln, wird ein **Token**, d.h. eine **spezielle Nachricht**, zwischen den Prozessen übermittelt. **Wer den Token hat, darf auf die Ressourcen zugreifen**. Wird die Ressource nicht mehr benötigt, wird der Token dem nächsten Prozess übergeben. Falls dieser die Ressource nicht benötigt, gibt er den Token einfach weiter.
* **Problem:** es gibt nur **einen einzigen** Token. Und dieser **könnte verloren gehen** (z.B. wenn der Prozess, der ihn gerade hat, abstürzt)-> selbst wenn es im VS einen Prozess gibt, der einen neuen Token erstellen kann, existiert dann aber auch wieder nur einer.
**PERMISSION-BASED**
* Möchte ein Prozess auf eine **Ressource zugreifen**, braucht er die **Erlaubnis** anderer Prozesse.
* **Centralized Algorithm**
* Es existiert ein **koordinierender Prozess**, der die **Erlaubnis** für den **Zugriff** auf eine Ressource **erteilt, ablehnt oder aufschiebt**(b-2 ist blocked, 3 put request to its queue, Sends OK after Release)
* 
* Es ist systemabhängig, wie ein P3 auf einen P2 reagiert. Möglich ist auch ein **"permission denied"** zu senden, wodurch P2 **Nicht** in einen **blocked-Zustand** versetzt wird. P2 müsste dann **Polling** anwenden (wiederholte abfrage), um herauszufinden, dass die **Ressource frei geworden ist**.
* Diese Lösung ist einfach zu implementiern, zudem sind **nur 3 Nachrichten pro Zugriff** auf eine Ressource erforderlich: **request, grant, release**
* **Probleme:** Bricht der koordinierende Prozess zusammen, funktioniert nichts mehr (**point of failure =1**). Prozesse, die einen **Request gesendet** haben und auf eine Reply warten, verbleiben im **blocked-Zustand** oder sie interpretieren die nicht-Antwort als ein "permission denied".
* Gibt es in einem VS nur einen **einzigen Koordinator**, kann dieser Prozess außerdem zu einem **Flaschenhals** (bottle neck) werden.
* **Distributed Algorithm**
* **Ablauf:** Möchte ein Prozess auf eine Ressource zugreifen, muss er **allen anderen Prozessen (inkl. sich selbst) eine Nachricht schicken**, in der der **Name der Ressource**, seine **Prozessnummer**, und die **aktuelle (logische) Uhrzeit** enthalten sind. Er wartet so lange, bis von jedem Prozess ein OK zurücgekommen ist und bekommt damit Zugriff auf die Ressource.
* Ist ein Prozess der Empfänger einer solchen Nachricht, ist eins der 3 folgenden Szenarien möglich:
* Der **Empfänger hat werde aktuell Zugriff** auf die Ressource **noch** möchte er dies **künftig**. Also **sendet** er ein **OK**
* Der **Empfänger hat gerade die Ressource und antwortet daher nicht.** Die **Anfrage** stellt er stattdessen **in seine Queue**
* Der **Empfänger** möchte ebenfalls auf die **Resource zugreifen**
* Er **vergleicht** die **Timestamps** seiner eigenen versendeten Nachricht mit der empfangenen.Ist der **Timestamp** vom Anfragenden **niedriger, schickt** er diesm ein **OK**. Ist sein **eigener niedriger**, stellt er die **Anfrage** in seine **Queue** und **antwortet nicht**
* Wenn ein Prozess eine Ressource wieder **frei** gibt, **sendet** er **an alle Prozesse in seiner Queue** ein **OK** und **löscht** die **Queue**.
* 
* **GRAFIK**: P0 und P2 wollen zur gleichen Zeit auf dieselbe Ressource zugreifen.
* Beide senden allen Prozessen einen Request, P0 mit Timestamp=8 und P2 mit Timestamp=12
* P1 braucht die Ressource nicht und antwortet daher beiden mit OK
* P0 und P2 vergleichen anschließend Timestamps
* P2 sendet anschließend OK an P0, wlecher auf die Ressource zugreift und stellt die Anfrage von p2 in seine Queue
* **Probleme:**
* Point of failure = alle Prozesse
* Jeder Prozess muss alle anderen Prozesse der Gruppe kennen inkl. denen, die die Gruppe verlassen, neu hinzukommen oder abgestürzt sind -> entweder muss jeder eine Liste besitzen oder es muss ein multicast communication primitive verwendet werden (der Algorithmus funktioniert am besten, wenn er auf eine fest, sich nicht verändernde Gruppe angewandt wird)
* Hier kann erst recht ein Flaschenhals entstehen.
* **Token-Ring algorithm**
* Ein logischer Ring aus Prozessen, die über point-to-point Verbindungen miteinander verbunden sind. Die **Ordnung** ist **egal, wichtig ist nur**, dass jeder Prozess weiß, welcher in der **Reihe nach ihm** kommt.
* 
* Wenn der Ring initialisiert wird, erhält **Prozess0** einen **Token.** Dieser wandert **von Prozess zu Prozess**
* Sobald ein Prozess den Token erhalten hat, prüft er, ob er die **Ressource benötigt, falls ja,** greift er darauf zu, gibt sie anchließend wieder frei und gibt den **Token weiter**. Es ist **nicht erlaubt,** dass ein Prozess, statt den Token weiterzugeben, die Ressource **gleich nochmal verwendet**.
* Braucht ein Prozess die Ressource nicht, gibt er den **Token direkt weiter**.
* (Wenn kein Prozess den Token benötigt, kreist er high-speed den Ring entlang)
* **Probleme:** Geht der **Token verloren**, muss er wieder hergestellt werden. Das Problem ist aber festzustellen, dass er verloren gegangen ist. Denn ihn könnte auch gerade ein Prozess länger in Verwendung haben.
* Wenn ein Prozess zusammenbricht, ist es mit diesem Algorithmus leichter, damit umzugehen. Denn sobald ein Prozess versucht, diesem den Token zu übergeben, wird er feststellen, dass der Prozess nicht mehr läuft. Er kann somit entfernt werden und der Token an den darauffolgenden Prozess übergeben werden. -> dafür muss aber jeder Prozess die aktuelle Konfiguration des Rings besitzen.

**Info:** Wenn ein System fehlertolerant sein soll, sind keine der Algorithmen geeignet!

### 7. Vergleichen Sie den "Bully" und den "Ring"-Algorithmus für Election hinsichtlich Fehlertoleranz. Warum sind diese Algorithmen für ad-hoc oder large-scale Systeme weniger geeignet und welche grundsätzlichen Lösungsansätze verfolgt man daher dort?
Beide Algorithmen basieren auf der Idee, dass **jeder Prozess eine eindeutige ID** besitzt und der Prozess mit der **höchsten ID** als **Koordinator** fungiert.

**BULLY ALGORITHMUS ("BIGGEST GUY I KNOW IN TOWN ALWAYS WINS")**
* Wenn der **Koordinator ausgefallen** ist und es ein **Prozess bemerkt**, sendet er eine **ELECTION - Nachricht an alle Prozesse** mit einer höheren ID. (In Grafik, 4 Bemerkt das 7 ausgefallen ist -> sendet 5&6 eine Nachricht)
* Wenn er **keine Antwort** erhält, so ist **er neuer Koordinator** (informiert alle anderen Prozesse darüber)
* **Antwortet** einer der **anderen Prozesse**, so übernehmen diese die Kontrolle, wer neuer Koordinator wird. (in Grafik 5&6 Antowrten 4 und übernehmen damit den Election Prozess)
* Dieser **wiederholt den Vorgang**, bis der Prozess mit der höchsten ID bekannt ist und eine **COORDINATOR-Nachricht** ausgesendet und somit allen bescheid gibt, dass er der neue Coordinator ist.
* 

**RING ALGORITHMUS**
* Die Prozesse sind logisch in **Form eines Rings angeordnet**
* Bemerkt ein Prozess, dass ein **Koordinator ausgefallen** ist, so wird eine **ELECTION-Nachricht** an seinen Nachfolger gesendet. (wenn dieser nicht antwortet, dann an dessen Nachfolger, so lange bis einer antwortet)
* Jeder Prozess hängt seine eigene ID an.
* Die Nachricht zirkuliert so lange, bis sie wieder den Ausgangsprozess erreicht. (Der Ausgangsprozess erkennt das die Nachricht von ihm ist daran, dass seine eigene ID in der Nachricht vorhanden ist)
* Dieser prüft die Einträge und jener mit der höchsten ID wird zum Koordinator gewählt -> informiert alle anderen Prozesse über die ID des neuen Koordinators (COORDINATOR-Msg. wird im Kreis gesendet)
* Nachdem die COORDINATOR-Msg. wieder beim Initiator angelangt ist, wird sie entfernt.
* Falls mehrere Prozesse gleichzeitig den Ausfall des Koodrinators bemerken und eine ELECTION Nachricht aussenden, ändert es nichts am Ergebnis, es wird lediglich ein wenig zusätzlicher Traffic erzeugt. (In der Grafik bemerken 2&5 gleichzeit das 7 ausgefallen ist)

**VERGLEICH HINSICHTLICH FEHLERTOLERANZ**
Beide Algo. sind sehr Fehlertolerant, da immer wieder ein neuer Koordinator gewählt werden kann. Es besteht **KEIN SINGLE POITN OF FAILURE** Problem.
Man benötigt einen Koordinator für verschiedene Aufgaben wie zB **Zeitbestimmung**. Von der **Safety** (=es gibt immer nur einen Koordinator) her ist der Ring besser. Der Bully ist zwar schneller, es kann aber zeitweise 2 Koordinator geben.

**AD-HOC SYSTEME**
Bei ad-hoc-Netzwerken kann sich die **Topologie schnell ändern** und man kann **nicht** davon ausgehen dass die Kommunikation zuverlässig (**reliable**) ist. Der **Bully- und Ring-Algorithmus** sind daher für derartige Netzwerke **nicht geeignet**. Außerdem ist es durch die heterogene Struktur wichti, dass nicht irgendein Koordinator gewählt wird, sondern der best (anhand eines Kriteriums, zB Bandbreite).

**Lösung:** Bei der Auswahl sendet ein Knoten die ELECTION Nachricht an all seine Nachbarn. Empfängt ein Nachbar diese Nachricht setzt er den Sender als Parent und leitet die ELECTION Nachricht an alle Nachbarn außer den Parent weiter. Dadurch entsteht eine Baumstruktur. Jeder Parent wartet nun nach dem Weiterleiten auf die Response aller seiner Kinder. Die Response enthält die ID und den Scord (Bewertung) des besten Prozesses im Subtree. Hat ein Parent von allen Kindern eine Response erhalten, kann er wiederum eine Response (mit dem besten Prozess) an seinen Parent senden. Der Root-Prozess weiß daher welcher Prozess der geeignetste Leader ist.

Bekommt ein Node eine weitere Election Nachricht die nicht von seinem Parent ist Acknowledged er sie nur. In der Grafik ist das zum Bsp.: unter (c) impliziert. Der Node g hat den broadcast von b zuerst bekommen und somit b zu seinem Parent gemacht. Der Node j sendet g auch eine Election Nachricht, bekommt aber dann nur ein Ack zurück weil g bereits einen Parent hat. Da j keine weiteren Nachbarn hat bzw. auch keine weiteren Kinder von denen er die Antwort abwarten muss, schickt er den besten Node an seinen Parent zurück (in dem Fall sich selbst)

**LARGE-SCALE SYSTEM**
werden **Superpeers** ausgewählt, da **ein Koodrinator zu wenig** sein wird. Auswahl mehrerer ausgezeichneter Knoten, die sich jeweils um eine Anzahl anderer Knoten kümmern.
Dabei müssen **Superpeers** folgende Kriterien erfüllen:
* Superpeers sollten **geringe Latenzzeiten** gegenüber normalen Peers haben
* Superepper sollten im Netzwerk **gleichmäßig verteilt** sein
* Die Anzahl der Superpeers sollte eine definierte Anzahl relativ zur Anzahl normaler Knoten nicht unterschreiten
* Jeder Superpeer sollte nur eine gewisse Anzahl an Knoten bedinen.

**Lösung:** Es werden für n Superpeers n Token zufällig im Netz verteilt. Kein Knoten kann mehr als einen Token gleichzeitig haben. Außerdem wirken auf die Tokens so genannte Kräfte die sicherstellen sollen, dass sich Token voneinander abstoßen. Erfährt ein Knoten von ein oder mehrere Token in der Umgebung kann aufgrund der Richtung, in der die anderen Token liegen jene Richtung bestimmt werden in die sein Token weitergegebn wird. Hält ein Knoten einen Token für eine gewisse Zeit (Token haben sich stabilisiert) wird dieser zu einem Superpeer. Dieser Prozess erfordert, dass Knoten, die einen Token haben, die anderen Token kennen. Es kann ein Gossipporotkoll verwendet werden, um die Kraft der Tokens im Netzwerk zu verbeiten. Wenn ein Knoten feststellt, dass die auf ihn wirkende Gesamtkraft einen Schwellwert überschreitet, verschiebt er den Token in Richtung der resultierenden Kraft.

### 8. (F) Welche Probleme gibt es bei der Ermittlung des "Global State" und wie können diese überwunden werden? Geben Sie zumindest einen Algorithmus an.
**GLOBAL STATE** eines VS besteht aus (saved to a locally available storage):
* Die **lokalen Status ALLER Prozesse**
* Die **Nachrichten** die **gerade unterwegs** sind aber noch nicht am Ziel angelangt sind.

"What exactly the **local** state of a process is, depends on what we are interested in (Helary, 1989)"

**Analysing** the global state:
* **Example:** When **local computations** have **stopped** and there are **no more messages in transit, the system** has entered a **state** in which **no more progress** can be made.
* **Error detection:** Aussagen die man bezüglich des globalen state treffen kann:
* **Distributed DEADLOCK detection:** Ein Zyklus im "Warte auf"-Graphen
* **Distributed TERMINIERUNGS detection:** Terminierung eines verteilten Algorithmus erkennen
* **Distributed GARBAGE collection:** Ein Objekt ist "Müll", wenn es **keinerlei Verweise** mehr darauf gibt
* **Dirstibuted DEBUGGING**
* **GLOBAL PREDICATE EVALUATION:**
* A global state predicate is a function that maps from the global state of processes **p to {True, False}**
* **Safety: α** is an **undesirable predicate** of the system's global state (**e.g. being deadlocked**)
* **Safety(α)** at S0:α=fals for all states reachable from S0 -> (i.e. "bad" α will **never happen**)
* **Liveness:ß** is a **desireable property** (e.g. reach termination)
* **Liveness(ß)** at S0:ß=true for some state SL reachable from S0 -> (i.e. "good" ß will **eventually happen**)
* **Error recovery** After a process or system failure -> **recovery line:** load most recent snapshot

**NOTATION OF A GLOBAL STATE**
can be **graphically represented** by what is called a **cut:**
**Physical time cannot be perfectly synchronized** in a DS. Som it is not possible to gather the global state of the system at a particular time. Cuts provide the ability to "**assemble a meaningful global state from local states recorded at different times**".
a) A **consisten cut** is shown by means of the **dashed line crossing the time axis** of all processes and **represents** the **last event** that has been **recorded for each process**. All recorded message receipts have a corresponding recorded send event!!
b) Shows an **inconsistent cut** (Effect without cause) The receipt of a message has been recorded, but the snapshot contains no corresponding send event!!

**Probleme:**
* Es könnte ein **inkonsistenter "Cut"** durch das System gemacht werden.
* **Kein Process** hat eine **globale Sicht** aus das System.
* Es gibt **keine gemeinsame Zeit** für die **Aufzeichnung** ("Stichtag")

**Distributed Snapshot** (Lösung): Way for **recording the global state** of a distributed system:
* Reflects a **state** in which the distributed **system might habe been**
* Reflects a **consistent** global state. (all processes: **Happened-Before Relation**)

**Simplify** the explanation of the Algo. for taking a distributed snapshot, we assume that the distributed system can be represented as a **collection of processes connected to each other through unidirectional point-to-point communication channels.**
For **example**, processes may first set up **TCP connections** before any further communication takes place.

**DISTRIBUTED SNAPSHOT ALGORITHM:**
* **Ermittelt** den **globalen Zustand**, der in Teilen zu **verschiedenen realen Zeiten** stattgefunden hat
* Ist aber **auf jeden Fall konsistent!**
* **Any process may initiate the algorithm**. The initiating process, say P, **starts** by **recording** its **own local state**. Then, it **sends a marker** along each of its **outgoing channels**, indicating that the **receiver should participate in recording the global state**.
* When a process Q receives a marker through a channel C, its action depends **if it has already saved its local state**.
* If it has **not already done** so, it first **records its local state** and also **sends a marker along** each of its own **outgoing channels**
* If Q had **already recorded** its state, the marker on channel C is an indicator that Q should record the state of the channel. This state is formed by the **sequence of messages** that have been received by Q **since** the last time Q **recorded** its **own local state**, and before it received the marker.
(a) **Organization** of a process and channels for a distributed snapshot
(b) Process Q **receives a marker** for the first time and **records its local state**
(c) Q **records** all **incomming messages**
(d) Q **receives** a **marker** for its incoming channel and **finishes recording** the **state of the incoming channel**

A process is said to have **finished its part of the algorithm** when it has **received a marker** along **each** of its **incoming channels, and processed each one**. At that point, its **recorded local state**, as well as the **state it recorded for each incomming channel**, can be **collected and sent**, for example, to the process that initiated the snapshot. The latter can then subsequently **analyze** the **current state**. Note that, meanwhile, the distributed system as a whole can **continue to run normally**.

It should be noted that **because any process can initiate** the algorithm, the **construction of several snapshots** may be in progress at the **same time**. For this reason, a **marker is tagged** with the **identifier** (and possibly also a **version number**), of the **process that initiated** the snapshot. Only after a process has received that marker through each of its incoming channels, can it finish its part in the construction of the marker*s associated snapshot.

**Alternative:** (System termination)
What is needed is a snapshot in which **all channels are empty**. The following is a simple **modification** to the algorithm described above. When a process Q finished its part of the snapshot, it either returns a **DONE** message to its predecessor, **or** a **CONTINUE** message. A **DONE message** is returned only when the following two conditions are met:
1. All of Q's **successors** have **returned** a **DONE** message.
2. Q has **not received any message** between the point it recorded its state, and the point it had received the marker along each of its incoming channels.
In all **other cases** Q sends a **CONTINUE** message to its **predecessor**.

Eventually, the original initiator of the snapshot, say process P, will either receive a CONTINUE message, or only DONE messages from its successors. When **only DONE messages** are received, it is known that **no regular messages are in transit**, and thus that **computation has terminated. Otherwise,** process P initiates **another snapshot**, and continues to do so **unitl only DONE** messages are eventually returned.