VS.tex

\documentclass[ngerman,a4paper]{report}
\usepackage[english,ngerman]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{geometry}
\usepackage{caption}
\usepackage{hyperref}
\usepackage{MyriadPro}
%\usepackage{MinionPro}
\usepackage{graphicx}
%\geometry{verbose,tmargin=3cm,bmargin=3cm,lmargin=3cm,rmargin=3cm}
\usepackage{listings}
\usepackage{paralist}
\usepackage{stmaryrd}
\usepackage{color}
%\usepackage{floatflt}
\usepackage{amsmath}
%\usepackage{amssymb}
\usepackage{float}
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
\lstset{language=C,
numbers=left,
numberstyle=\tiny\color{gray},
stepnumber=1,
numbersep=5pt,
%basicstyle=\tiny,
%frame = single,
tabsize =2,
breaklines = true,
breakatwhitespace = false,
keywordstyle=\color{blue},          % keyword style
commentstyle=\color{dkgreen},       % comment style
stringstyle=\color{mauve},         % string literal style
literate=%
{Ö}{{\"O}}1
{Ä}{{\"A}}1
{Ü}{{\"U}}1
{ß}{{\ss}}2
{ü}{{\"u}}1
{ä}{{\"a}}1
{ö}{{\"o}}1
}

\selectlanguage{english}

\renewcommand{\familydefault}{\sfdefault}


\author{Hinnerk van Bruinehsen\\Tobias Höppner\\Tobias Famulla\\Johannes Dillmann\\Julian Dobmann\\Jens Fischer}
\title{Lecture Notes\\\Huge{Distributed System}}
\date{SoSe 2013}

\begin{document}
\maketitle
\tableofcontents

\chapter{Verteilte Systeme/Distributed Systems}
\section{Orga}
VL Di 10-12 (nicht am 23.04.)\\
Ue Do 10-12\\

\subsection{Elektisches}
\begin{compactitem}
\item (kvv)
\item Website AG
\item Sakai
\end{compactitem}

\subsection{Übungen}

\begin{compactitem}
\item ca. 5 Übungsblätter, 14-tägig
\item Vorträge in Gruppen über \glqq verteilte Systeme\grqq
\end{compactitem}

\subsection{Material/Inhalt}
\begin{compactitem}
\item[1. Hälfte] Distributed Systems (Tanenbaum, van Steen)
	\begin{compactitem}
	\item Architektur
	\item Prozesse
	\item Kommunikation
	\item Namen
	\item Synchronisation
	\item Konsistenz
	\item Replikation
	\item Fehlertoleranz
	\end{compactitem}
\item[2. Hälfte] Distributed Algorithms (Nancy Lynch)
	\begin{compactitem}
	\item synchronous network algorithms
	\item network models (leader election, shortest path, distributed consensus, byzantine agreement)
	\item asynchronous network algorithms (shared memory, mutual exclusion, resource allocation, consensus)
	\item timing
	\item network resource allocation
	\item failure detectors
	\end{compactitem}
\end{compactitem}

\chapter{Distributed Systems}
\textbf{Def:} A distributed System is a collection of independent computers that appears to it's users as a single coherent system.

Characteristics:
\begin{compactitem}
\item autonomous components
\item appears as single system
\item communication is hidden
\item organisation is hidden \\(could be high-performance mainframe or sensor net)
\item heterogenous system offers homogenous look/interface
\end{compactitem}
\ \\
\ \\
There are 4 goals of distributed systems:
\begin{compactenum}
\item Making Resources Accessible
\item Distribution Transparency
\item Openness
\item Scalability
\end{compactenum}

\section{Making Resources Accessible}

\begin{compactitem}
\item provide users (and applications) access to remote resources (printer, storage, computing)
\item share ressources in a controlled efficient way
\end{compactitem}

\section{Distribution Transparency}
Hide the fact that processes and resources are physically distributed. A distributed system that is able to present itself to users and applications as if it were only a single computer system is said to be transparent.
\begin{compactitem}
\item transparancy is desireable, but not always perfectly possible
\item tradeoff between transparancy and complexity, maintainablility and performance
\end{compactitem}

\pagebreak
\textbf{Types of transparancy:}
\begin{compactitem}
\item[\textbf{access}] hide differences in data representation and how a resource is accessed
\item[\textbf{location}] hide where a resource is located
\item[\textbf{migration}] hide that a resource may move to another location
\item[\textbf{relocation}] hide that a resource may be moved to another location while in use
\item[\textbf{replication}] hide that a resource is replicated
\item[\textbf{concurrency}] hide that a resource may be shared by serveral competitive users
\item[\textbf{failure}] hide the failure and recovery of a resource
\end{compactitem}

\section{Openness}
\begin{compactitem}
\item An open distributed system is a system that offers services according to standard rules that describe the syntax and semantics of those services
\item service interfaces (syntax) specified using Interface Definition Language (IDL)
\item service specification (semantics) as text
\end{compactitem}

\section{Scalability} 
is an important property, distributed systems should be scalable in \\
\begin{compactitem}
\item[\textbf{size}] number of nodes, users, resources
\item[\textbf{geographic spread}] geographical distribution of users and resources (may lie far apart)
\item[\textbf{administration}] manageability, even if even if it spans many independent administrative organizations
\end{compactitem}

\subsection{Scaling in size}
If more users or resources need to be supported, we are often confronted with the limitations of centralized services, data, and algorithms. Scalability in size is limitated by:
\begin{compactitem}
\item [\textbf{centralized services}] A single server for all users (bottleneck)
\item [\textbf{centralized data}] A single on-line telephone book or non-distributed DNS
\item [\textbf{centralized algorithms}] Doing routing based on \emph{complete} information
\end{compactitem}
\subsection{Geographical Scalability}
\begin{compactitem}
\item existing distributed systems were designed for LANs
\item $\rightarrow$ LAN-based systems often use synchronous communication 
\item $\rightarrow$ LAN-based systems provide relatively reliable communication
\item $\rightarrow$ in LAN-based systems broadcasting is possible
\item all of this is not possible in WAN $\Rightarrow$ problems in geographical scalability
\end{compactitem}
\subsection{Scalability in administration}
how to scale a distributed system across multiple, independent administrative domains. Important security questions arise:
\begin{compactitem}
\item [\textbf{selfprotection}] from malicious attacks from the new domain
\item [\textbf{domainprotection}] the domain protects itself from attacks from a new domain
\end{compactitem}

\subsection{Scaling techiques}
\begin{compactitem}
\item [\textbf{hiding communication latencies}] use only asynchronous communication
\item [\textbf{distribution}] split components into smaller parts :)
\item [\textbf{replication}] of components, chaching, enables load balancing
\end{compactitem}

\section{Pitfalls}
False assumptions that everyone makes when developing a distributed application for the first time:
\begin{compactenum}
\item The network is reliable.
\item The network is secure.
\item The network is homogeneous.
\item The topology does not change.
\item Latency is zero.
\item Bandwidth is infinite.
\item Transport cost is zero.
\item There is one administrator.
\end{compactenum}

\section{Types of distributed systems}

\subsection{Distributed Computing Systems}

\subsubsection{Cluster Computing Systems}

\begin{compactitem}
\item the underlying hardware consists of a collection of similar workstations or PCs
\item these closely connected by means of a high speed local-area network
\item each node runs the same operating system
\item used for instance for the building of supercomputers using off-the-shelf technology by hooking up a collection of relatively simple computers in a high-speed network
\end{compactitem}

\begin{figure}[h]
	\centering
	\includegraphics[width=200px]{gfx/cluster_computing.png}
	\caption{cluster computing}
	\label{img:cluster_comp}
\end{figure}

\subsubsection{Grid Computing Systems}

\begin{compactitem}
\item grid computing systems have a high degree of heterogeneity: no assumptions are made concerning hardware, operating systems, networks, administrative domains, secu- rity policies, etc.
\item virtual organization: resources from different organizations are brought together to allow the collaboration of a group of people or institutions
\item geographically distributed
\end{compactitem}

\subsection{Distributed Information Systems}

\subsubsection{Transaction Processing Systems}
A distributed system for processing transactions, e.g. a (distributed) database. 
Transactions are defined through fulfilling the \textbf{ACID} (atomicity, consistency, isolation, durability) properties:
\begin{compactdesc}
\item[Atomic] To the outside world, the transaction, happens indivisibly
\item[Consistens] The transaction does not violate system invariants
\item[Isolated] Concurrent transactions do not interfere with each other
\item[Duarble] Once a transaction commits, the changes are permanent
\end{compactdesc}

\subsubsection{Enterprise Application Integration}

\begin{compactitem}
\item the more applications became decoupled from the databases they were built upon, the more evident it became that facilities were needed to integrate applications independent from their databases
\item application components should be able to communicate directly with each other and not mere- ly by means of the request/reply behavior that was supported by transaction processing systems
\item main idea was that existing applications could directly exchange information via communication middleware
\item see RPC
\end{compactitem}

\subsubsection{Distributed Pervasive Systems}
\begin{compactitem}
\item The distributed systems we have been discussing so far are largely characterized by their stability: nodes are fixed and have a more or less permanent and high-quality connection to a network
\item in distributed pervasive systems, instability is the default behavior
\item often small, wireless, adhoc, no administration
\item Examples: Home automation, Health systems, Sensor Networks
\end{compactitem}



\chapter{Architectures 1: Architectural styles}

\begin{compactitem}
\item how to split software into components\\
$\Rightarrow$ Software architecture (aka architectural styles)
\item how to build a system out of the components\\
$\Rightarrow$ System architecture
\end{compactitem}
\ \\
Middleware can  help to create distribution transparency

\section{Layered architecture}

\begin{compactitem}
	\item components are organized in a layered fashion
	\item a component at layer $L_n$ is allowed to call (request) components at the underlying layer $L_{n-1}$, but not the other way around
	\item control flows from layer to layer
	\item request down, reply up
	\item widely adopted in network stack
\end{compactitem}

\section{Object-based architectures}

\begin{compactitem}
	\item interaction between components
	\item components are connected through a (remote) procedure call mechanism
	\item associated with client-server system architecture
\end{compactitem}


\begin{figure}[h]
	\centering
	\includegraphics[width=300px]{gfx/layeres_and_objects.png}
	\caption{The (a) layered and (b) object-based architectural style.}
	\label{img:layeres_and_objects}
\end{figure}


\section{Data-centered architectures}

\begin{compactitem}
	\item processes communicate through a common (passive or active) repository
	\item Example: networked applications with shared distributed file system in which all communication takes place through files
	\item Example: Web-based distributed system: processes communicate through the use of shared database
	\item Example: distributed database
\end{compactitem}

\section{Event-based architecture}

\begin{figure}[h]
	\centering
	\includegraphics[width=150px]{gfx/pub_sub.png}
	\caption{publish subsribe system}
	\label{img:publish_subscribe}
\end{figure}

\begin{compactitem}
	\item aka publish-subscribe systems
	\item processes essentially through the propagation of events
	\item publisher announces events at broker
	\item only those processes that subscribed will receive the events
	\item $\Rightarrow$ loose coupling (publisher and subscriber need not to know each other), decoupled in space\\
	\item $\Rightarrow$ scalability better than client-server, parallel processing, caching\\
\end{compactitem}

\section{Shared data spaces}

Event-based and data-based can be combined $\Rightarrow$ shared Data space
\begin{figure}[h]
	\centering
	\includegraphics[width=150px]{gfx/shared_data_space.png}
	\caption{shared data space}
	\label{img:shared_data_space}
\end{figure}

\chapter{Architectures 2: System architectures}

\begin{compactitem}
\item \textbf{vertical distribution} (layering, multitiered architectures)
	\begin{compactitem}
		\item placing logically different components on different machines\\
		$\Rightarrow$ centralized architectures / client-server
	\end{compactitem}
	\item \textbf{horizontal distribution}
	\begin{compactitem}
		\item replicated client/server operating on different data (different parts of the data)
		\item all the machines fulfill in principal the same role\\
		$\Rightarrow$ peer-to-peer systems
	\end{compactitem}
\end{compactitem}

\section{Centralized architectures}

\subsection{Client - server}

\begin{figure}[h]
	\centering
	\includegraphics[width=200px]{gfx/cs_simple_wait.png}
	\caption{client server simple waiting situation}
	\label{img:cs_simple_wait}
\end{figure}

\begin{compactitem}
	\item processes in a distributed system are divided into two (possibly overlapping) groups
	\item \textbf{server:} a process implementing a specific service, for example, a file system service or a database service
	\item \textbf{client:} a process that requests a service from a server by sending it a request and subsequently waiting for the server's 
	\item problems:
	\begin{compactitem}
		\item single point of failure
		\item performance (server is bottleneck)
		\item can request be repeated without harm? only if request is idempotent
	\end{compactitem}
\end{compactitem}

\subsubsection{Application layering}

\begin{compactenum}
	\item User interface
	\begin{compactitem}
		\item all that is necessary to directly interface with the user, such as display management
		\item clients typically implement the user-interface level
	\end{compactitem}
	\item processing level
	\begin{compactitem}
		\item contains the core functionality of an application
	\end{compactitem}	
	\item data level
	\begin{compactitem}
		\item contains the programs that maintain the actual data on which the applications operate
	\end{compactitem}	
\end{compactenum}

\subsubsection{Multitiered Architectures}

\begin{compactitem}
	\item physically distribute a client-server application across several machines
	\item direct consequence of dividing applications into a user-interface, processing components, and a data level
	\item different tiers correspond directly with the logical organization of applications
	\item three-tiered architecture: split user-interface, application server and database server
	\item Example: Website
	\begin{compactitem}
		\item Web server acts as an entry point to a site
		\item requests are passed to an application server where the actual processing takes place
		\item the application server interacts with a database server
	\end{compactitem}
\end{compactitem}
$\Rightarrow$ a lot of waiting\\
$\Rightarrow$ does not scale\\


\begin{figure}[h]
	\centering
	\includegraphics[width=\linewidth]{gfx/server_as_client.png}
	\caption{Application layering: example of a server acting as client.}
	\label{img:cs_app_layer}
\end{figure}

\section{Decentralized architectures}

\begin{compactitem}
	\item processes that constitute a peer-to-peer system are (in principal) all equal
	\item functions that need to be carried out are represented by every process
	\item interaction between processes is symmetric: each process will act as a client and a server at the same time
	\item how to organize the processes in an \textbf{overlay network}
	\begin{compactitem}
		\item a network in which the nodes are formed by the processes and the links represent the possible communication channels 
		\item hide physical structure by adding logical structure
	\end{compactitem}
\end{compactitem}
	


\subsection{Structured P2P architectures}

\begin{compactitem}
	\item the overlay network is constructed using a deterministic procedure
	\item most-used procedure is distributed hash table (DHT)	
\end{compactitem}


\subsubsection{DHT / Chrod}

\begin{figure}[h]
	\centering
	\includegraphics[width=280px]{gfx/chord_mapping.png}
	\caption{The mapping of data items onto nodes in Chord}
	\label{img:chord_mapping}
\end{figure}

\begin{compactitem}
	\item randomly 128 bit or 160 bit ke for data and nodes. Two or more duplicate keys are extremely unlikely
	\item efficient and deterministic scheme that uniquely maps the key of a data item to the identifier of a node
	\item when looking up a data item, the network address of the node responsible for that data item is returned
	\item Chord system arranges items in a ring
	\item data item $k$ is assigned to node with smallest identifier $id \geq k$
	\begin{compactitem}
		\item item 1 belongs to node 1 (see \ref{img:chord_mapping}
		\item item 2 belongs to node 4 (see \ref{img:chord_mapping}		
	\end{compactitem}		
	\item \textbf{succ(k)} for each item $k_i$ $succ(k)=id$ returns  the name of the node $k$ is assigned to
	\item \textbf{lookaup(k)} to find data item $k$ the function $lookup(k)$ returns the adress of $succ(k)$ in $\mathcal{O}(log(N))$
	\item \textbf{membership management}
	\begin{compactitem}
		\item join
		\begin{compactitem}
			\item create SHA1 identifier $id$
			\item $lookup(id)$  will return $succ(id)$
			\item contact $succ(id)$ and $pred(id)$ and insert itself in between
		\end{compactitem}
		\item leave
		\begin{compactitem}
			\item node id informs $succ(id)$ and $pred(id)$ and assigns it's data to $succ(id)$
		\end{compactitem}
	\end{compactitem}
\end{compactitem}


\subsubsection{Content adressable network (CAN)}

\begin{figure}[h]
	\centering
	\includegraphics[width=350px]{gfx/CAN.png}
	\caption{(a) The mapping of data items onto nodes in CAN. (b) Splitting a region when a node joins.}
	\label{img:CAN}
\end{figure}

\begin{compactitem}
\item d-dimensional cartesian space
\item every node draws random number
\item space is divided among nodes
\item every data draws identifier (coodinates) which assigns a node

\item join\begin{compactitem}
\item select random point
\item half the square in which id falls
\item assign item to centers
\end{compactitem}
\item leave\begin{compactitem}
\item one node takes the rectangle\\
$\Rightarrow$ reassign rectangles periodically
\end{compactitem}
\end{compactitem}

\subsection{Unstructured P2P Network}

\begin{compactitem}
	\item rely on randomized algorithms for constructing an overlay network
	\item  the goals of many unstructured peer-to-peer systems is to construct an overlay network that resembles a random graph
	\item  basic model 
	\begin{compactitem}
		\item each node maintains a list of $c$ neighbors
		\item each neighbor represents a randomly chosen \emph{live} node from the current set of nodes
		\item list of neighbors is also referred to as a \emph{partial view}
		\item nodes regularly exchange entries from their partial view
		\item an entry identifies another node in the network
		\item an has an associated age (indicates how old the reference is)
	\end{compactitem}
\end{compactitem}

\subsubsection{Basic algorithm for overlay construction}

\begin{compactdesc}
	\item[Active thread] Select peer from partial view
	\begin{compactitem}
		\item[PUSH] \ 
		\begin{compactitem}
			\item select c/2 youngest entries+myself
			\item send to peer
		\end{compactitem}
		\item[PULL] \ 	
		\begin{compactitem}
			\item receive peer buffer
			\item construct new partial view
			\item increment age \\
		\end{compactitem}			
	\end{compactitem}
	\item[Passive Thread] Receive buffer from peer
	\begin{compactitem}
		\item[PULL] \ 	
		\begin{compactitem}
			\item select c/2
			\item send to peer
			\item construct new partial view
			\item increment age
		\end{compactitem}			
	\end{compactitem}	
\end{compactdesc}

\input{chapter/peersim.tex}

\input{chapter/proc.tex}

\chapter{Communication}

\begin{compactitem}
	\item Communication in distributed systems is always based on low-level message passing as offered by the underlying network
	\item message passing is harder than using primitives based on shared memory, as in nondistributed systems
	\item low-level communication facilities of computer networks are in many ways not suitable due to their lack of distribution transparency.
\end{compactitem}

\section{RPC - Remote Procedure Call}
%ordinary procedure call, e.g. count = read(fd,buf,nbytes)

\begin{compactitem}
	\item allow programs to call procedures located on other machines
	\item When a process on machine A calls' a procedure on machine B, the calling process on A is suspended, and execution of the called procedure takes place on B.
	\item Remote procedure call uses stubs to pack parameters in message
	\item client stub: packs the parameters into a message and requests that message to be sent to the server
	\item server stub: transforms requests coming in over the network into local procedure calls
	\item No message passing at all is visible to the programmer
	\item neither client nor server need to be aware of the intermediate steps or the existence of the network
\end{compactitem}

\subsection*{A remote procedure call occurs in the following steps:}

\begin{compactenum}
	\item The client procedure calls the client stub in the normal way.
	\item The client stub builds a message and calls the local operating system.
	\item The client's operating system sends the message to the remote operating system.
	\item The remote operating system gives the message to the server stub.
	\item The server stub unpacks the parameters and calls the server.
	\item The server does the work and returns the result to the stub.
	\item The server stub packs it in a message and calls its local operating system.
	\item The server's as sends the message to the client's operating system.
	\item The client's operating system gives the message to the client stub.
	\item The stub unpacks the result and returns to the client.
\end{compactenum}

\subsection*{Parameter Marshaling}

parameter marshaling: packing parameters into a message is called


\subsubsection*{Passing Value Parameters}

\begin{compactitem}
	\item values are packed into messages (client) and unpacked from messages (server)
	\item transfered byte-by-byte
	\item as long as the client and server machines are identical this model works fine
	\item in a large distributed system, it is common that multiple machine types are present
	\item $\Rightarrow$ problems because of different character encoding (EBCDIC vs ASCII), represetation of integers (one's complement vs two's complement) or endianness (little endian vs. big endian)
\end{compactitem}

\subsubsection*{Passing Reference Parameters}
\begin{compactitem}
	\item extremly difficult
	\item pointers are meaningful only within the address space of the process in which it is being used
	\item replace with copy/restore: copy the datastructure, send it to the server, work on it, send it back, restore at the client
\end{compactitem}



\section{Asynchronous RPC}

\begin{figure}[h]
	\centering
	\includegraphics[width=400px]{gfx/rpc.png}
	\caption{a: synchronous b: asynchronous RPC}
	\label{img:rpc}
\end{figure}

\begin{compactitem}
	\item in conventional procedure calls, when a client calls a remote procedure, the client will block until a reply is returned
	\item asynchronous RPCs: the server immediately sends a reply back to the client the moment the RPC request is received. Reply acts as an acknowledgment.
	\item client will continue without further blocking as soon as it has received the server's acknowledgment
	\item Examples: transferring money from one account to another, adding entries into a database, starting remote services, batch processing...
	\item Asynchronous RPCs can also be useful when a reply will be returned but the client doesn't need to wait for it and can do nothing in the meantime
	\item One-Way RPCs: the client does not wait for an acknowledgment from the server
	\item deferred synchronous RPC: organize the communication between the client and server through two asynchronous RPCs
\end{compactitem}

\begin{compactitem}
	\item foo
\end{compactitem}

\section{Message oriented communication}

General Idea: avoid synchronous communication which blocks sender (RPC)

\subsection{Message-Oriented Transient Communication}

transient: flüchtig, vorrübergehend

\subsubsection{Berkeley Sockets}

A socket is a communication end point to which an application can write data that are to be sent out over the underlying network, and from which incoming data can be read. A socket forms an abstraction over the actual communication end point that is used by the local operating system for a specific transport protocol.

\begin{figure}[h]
	\centering
	\includegraphics[width=400px]{gfx/sockets.png}
	\caption{Connection-oriented communication pattern using sockets}
	\label{img:sockets}
\end{figure}

\begin{compactitem}
	\item socket: create a new communication end point
	\item bind: attach a local addres to a socket
	\item listen: announce willingness to accept connections
	\item accept: block caller until a connection request arrives
	\item connect: actively attemt to establish a connection
	\item send: send some data over the connection
	\item receive: receive some data over the connection
	\item close: release the connection
\end{compactitem}

\subsubsection{Message-passing-interface (MPI)}
\begin{compactitem}
	\item standad for message passing
	\item designed for parallel applications
	\item communication within groups of processes
	\item A $(groupID, processID)$ pair uniquely identifies the source or destination of a message (used instead of a transport-level address)
\end{compactitem}

\subsection{Message-Oriented Persistent Communication}

aka Message-queuing-system, Message-oriented-middleware (MoM) \\

\begin{figure}[h]
	\centering
	\includegraphics[width=400px]{gfx/mom.png}
	\caption{general organization of a message-queuing system with routers}
	\label{img:mom}
\end{figure}

\begin{compactitem}
	\item asynchronous persistent communication
	\item offer intermediate-term storage capacity for messages, without requiring either the sender or receiver to be active during message transmission
	\item transfer may take minutes, not milliseconds
	\item applications communicate by inserting messages into queues
	\item messages are only put into and read from local queues
	\item the message-queuing system takes care that messages are transferred from their source to their destination queue
	\item message carries destination address
	\item queue managers
	\begin{compactitem}
		\item a queue manager interacts directly with the application that is sending or receiving a message
		\item also special queue managers that operate as routers, or relays: they forward incoming messages to other queue managers
	\end{compactitem}
	\item message brokers transform type A into type B, using a set of rules
		\begin{compactitem}
		\item application-level gateway in a message-queuing system
		\item convert incoming messages so that they can be understood by the destination application
		\item transform messages of type A into type B, using a set of rules
	\end{compactitem}
	\item Examples: Email, workflow, batch processing, queries accross several databases
\end{compactitem}

\section{Stream Oriented Communication}

\begin{figure}[h]
	\centering
	\includegraphics[width=400px]{gfx/streams.png}
	\caption{A general architecture for streaming stored multimedia data over a network}
	\label{img:streams}
\end{figure}

\begin{compactitem}
	\item form of communication in which timing plays a crucial role
	\item in continuous media, the temporal relationships between different data items are fundamental to correctly interpreting what the data actually means
	\item multimedia data will need to be compressed substantially in order to reduce the required network capacity
	\item simple stream: consists of only a single sequence of data
	\item complex stream: consists of several related (often time dependent) simple streams (substreams)
	\item QoS
		\begin{compactenum}
			\item The required bit rate at which data should be transported. 
			\item The maximum delay until a session has been set up (i.e., when an application can start sending data). 
			\item The maximum end-to-end delay (i.e., how long it will take until a data unit makes it to a recipient). 
			\item The maximum delay variance, or jitter. 
			\item The maximum round-trip delay.		
		\end{compactenum}

	\item synchronisation of streams
	\begin{compactitem}
		\item Synchronization of streams deals with maintaining temporal relations between streams
		\item Synchronization takes place at the level of the data units of which a stream is made up
		\item In other words, we can synchronize two streams only between data units
		\item Example: Playing a movie in which the video stream needs to be synchronized with the audio
	\end{compactitem}
	
\end{compactitem}


\section{Multicast communication}

\subsection{Application Level Multicasting}

\begin{compactitem}
	\item sending data to multiple receivers
	\item For many years, this topic has belonged to the domain of network protocol
	\item With the advent of peer-to-peer technology various application-level multicasting techniques have been introduced
	\item The basic idea in application-level multicasting is that nodes organize into an overlay network, which is then used to disseminate information to its members
	\item connections between nodes in the overlay network may cross several physical links, and as such, routing messages within the overlay may not be optimal in comparison to what could have been achieved by network-level routing
\end{compactitem} 


\subsubsection*{Approaches to building the overlay}
\begin{compactitem}
	\item tree: nodes may organize themselves directly into a tree, meaning that there is a unique (overlay) path between every pair of nodes
	\item mesh network: nodes organize into a mesh network in which every node will have multiple neighbors and, in general, there exist multiple paths between every pair of nodes
	\item mesh network generally provides higher robustness
\end{compactitem}

\

\subsubsection*{Example: Construct overlay tree for chord}  
\begin{compactitem}
	\item node that wants to start multicast generates key 128bit/160bit (mid) randomly
	\item lookup of succ(mid) finds node responsible for key mid\\
		$\Rightarrow$ succ(mid) becomes root of tree
	\item join multicast: lookup (mid) creates lookup message with join request routed from P to succ(mid)
	\item request is forwarded by Q (first time forward), Q becomes forwarder\\
		$\Rightarrow$ P child of Q
	\item request is then forwarded by R, R becomes forwarder\\
		$\Rightarrow$ Q becomes child of R
	\item if Q or R is already forwarder: no forward\\
		$\Rightarrow$ Q becomes child of R	
	\item multicast: lookup(mid) sends message to the root\\
		multicast from root
\end{compactitem}

\begin{figure}[h]
	\centering
	\includegraphics[width=250px]{gfx/overlay_example.png}
	\caption{The relation between links in an overlay and actual network-level routes}
	\label{img:ovrlnt}
\end{figure}


\subsubsection*{Efficiency}

\begin{compactitem}
	\item building a tree is not difficult once we have organized the nodes into an overlay
	\item building an efficient tree may be difficult
	\item The quality of an application-level multicast tree is generally measured by three different metrics
	\begin{compactenum}
		\item Link stress: defined per link and counts how often a packet crosses the same link
		\item Stretch / Relative Delay Penalty (RDP)\\
			ratio in the delay between two nodes in the overlay, and the delay that those two nodes would experience in the underlying network: 
			$\frac{\text{transmission time in overlay}}{\text{transmission time in delay/network}}$ \\
			$\Rightarrow$ minimize aggregated stretch, average RDP over all note pairs
		\item tree cost: global metric, generally related to minimizing the aggregated link costs \\
			link cost = cost between end points\\
				$\Rightarrow$ find minimal spanning tree	
	\end{compactenum}
\end{compactitem}

\subsection{Gossip-based-communication}
\begin{compactitem}
	\item epidemic behaviour: model information dissemination in a (large) distributed system after the spreading of infectious diseases
	\item infected node: a node that holds data that it is willing to spread 
	\item susceptible: a node does not yet have the new data
	\item removed: an updated node that is not willing or able to spread its data 
	\item we assume we can distinguish old from new data, for example, because it has been timestamped or versioned
\end{compactitem}

\subsubsection*{Anti-entropy-model}

A node P picks another node Q at random, and subsequently exchanges updates with Q.
There are three approaches to exchanging updates:
\begin{compactenum}

	\item P only pushes its own updates to Q
	\begin{compactitem}
		\item updates can be propagated only by infected nodes
		\item if many nodes are infected, the probability of each one selecting a susceptible node is relatively small
		\item $\Rightarrow$ chances are that a particular node remains susceptible for a long period simply because it is not selected by an infected node
	\end{compactitem}

	\item P only pulls in new updates from Q
	\begin{compactitem}		
		\item spreading updates is essentially triggered by susceptible nodes
		\item high probability to to contact an infected node and pull in the updates
		\item $\Rightarrow$ pull-based approach works much better when many nodes are infected
	\end{compactitem}

	\item P and Q send updates to each other (i.e., a push-pull approach)
	\begin{compactitem}
		\item if only one node is infected push/pull is best
	\end{compactitem}
\end{compactenum}

\

\begin{compactitem}
	\item Round is period in which each node at least once selects a neighbor
	\item number of rounds needed to spread  $\approx \mathcal{O}(\log(N)), N$ is number of nodes
\end{compactitem}

\subsubsection*{Rumor spreading, gossiping}
\begin{compactitem}
	\item if node P has just been updated for data item x, it contacts an arbitrary other node Q and tries to push the update to Q
	\item if Q was already updated by another node, P may lose (with some probability) interest in spreading the update any further
	\item P then becomes removed\item
	\item Fraction of nodes that never obtain data: $s=e^{-(k+1)(1-s)}$\\
		e.g. $k=4, ln(s) = 4,97$\\
		$\Rightarrow s = 0,007$\\
		less than $0,7\%$ remain without data\\
\end{compactitem}


\subsubsection*{Removing Data}
\begin{compactitem}
	\item problem: deletion of a data item destroys all information on that item\\
		$\Rightarrow$ when a data item is simply removed from a node, that node will eventually receive old copies of the data item and interpret those as updates on something it did not have before
	\item $\Rightarrow$ record the deletion of a data item as just another update, and keep a record of that deletion
\end{compactitem}


\chapter{CHORD: Distributed Hash Tables}

Chapter in the Book:
\begin{compactitem}
\item Naming
\begin{compactitem}
\item Flat naming
\begin{compactitem}
\item Distributed Hash Tables
\end{compactitem}
\end{compactitem}
\end{compactitem}
\ \\
%krasse büld von de hipster tobi
\begin{compactitem}
\item Chord uses an m-bit identifier space (128 or 160 Bit) to assign randomly-chosen identifiers to nodes as well as keys to specific entities
\item An entity with key k falls under the jurisdiction of the node with the smallest identifier id $\geq$ k (referred to as succ(k)
\end{compactitem}

\section{Joining}
\begin{compactitem}
\item node $p$ wants to join
\item $p$ requests lookup for $succ(p)$  
\begin{compactitem}
\item actually, $p$ creates SHA1 identifier $id$, e.g. from its IP, which is then looked up
\end{compactitem}
\item contact $succ(id)$ and $pred(id)$ to join ring
\item create finger table for $p$ either by calculating all the entries or by copying the finger table of $succ(p)$ an let the stabilization protocol do the rest
\end{compactitem}

\section{Leaving}
\begin{compactitem}
\item node $p$ informs $succ(p)$ and $pred(p$)
\item $p's$ data is assigned to $succ(p)$
\end{compactitem}

\section{Routing}
\begin{compactitem}
\item searching, lookung
\item Resolve key $k$ to address of $succ(k)$
\end{compactitem}

\subsection{Option 1: Naive Approach (Linear search)}

\begin{compactitem}
\item each node p keeps succ(p+1) and pred(p)
\item each node forwards request for key k to a neighbor
\item if pred(p) < k $\leq$ p, return(p)\\
$\Rightarrow$ not scalable
\end{compactitem}

\subsection{Option 2: Finger-table based lookup}
\begin{compactitem}

\item better solution: each Chord node maintains \underline{finger table} of lenght m\\

$ \forall \  1 \leq i \leq m :	FT[i] = succ(p+2^{i-1}) \mod 2^m $ \\

\item the $i$-th entry points to the first node succeeding $p$ by at least $2^{i-1}$ 
\item Example: Node 1: FT[$1$]=succ($p+2^{i-1}$) = succ($1+2^{1-1}$) = succ($1+1$) = succ($2$) \\ (smallest id, sucht that id $\geq$ 2)
\item to lookup key $k$, node $p$ forwards request to node $q$ with index $j$ in $p's$ finger table:\\
$q = FT_p[j] \leq k \leq FT_p[j+1]$
\item lookup generally requires $O(log(N))$ steps, N nodes in system
\end{compactitem}

\section{Stabilization}
\begin{compactitem}
\item goals:
\begin{compactitem}
\item keep the finger tables up to date
\item make new nodes known to the rest of the network
\item preserve the structure of the ring
\end{compactitem}
\item two tasks, periodically run at each node
\begin{compactenum}
\item \lstinline$fix_fingers$
\begin{compactitem}
\item check (li.e. lookup) one, some or all entries in the the finger table
\item update the finger table accordingly
\end{compactitem}
\item \lstinline$stabilize$
\begin{compactitem}
\item lookup $pred(succ(p))$ (should be $p$)
\item otherwise: update successor and predecessor information in $p$ and the neighbors
\end{compactitem}
\end{compactenum}
\end{compactitem}

\subsubsection{Example 1: Routing}
The example refers to Figure 5.4, p. 190, Tanenbaum.\\
Resolve k = 26 from node 1 \\
$k=26 > FT_1[5] \Rightarrow$ forward request to node\\
$18 = FT_1[5]$
\begin{compactitem}
\item node $18$ selects node $20 FT_{18}[2] \leq k < FT_{18}[3]$
\item node $20$ selects node $21 \Rightarrow 28 $ which is responsible for key $26$
\end{compactitem}
\ \\

\subsubsection{Example 2: Superpeers}
Assume a system for which k bits of an m-bit identifier space have been reserved for assigning to superpeers. If identifiers are randomly assigned, how many superpeers can one expect to have in an N-node system? \\
Superpeers: $2^k$, therefore $2^{m-k}$ normal nodes.\\
Probability that a node is a supernode: $n\cdot \frac{2^k}{2^m} = 2^{k-m} \cdot n$, with $m$ number of bits, $k$ is number of bits that mark superpeers, $n$ is number of nodes (not maximum possible but the actual number).\\
Number of superpeers to be expected: $E(x)= n\cdot p$\\

%\item example2:\\
%\begin{figure}[h]
%	\centering
%	\includegraphics[width=250px]{gfx/Chord_Fingertable.png}
%	\caption{Ring and Fingertable for Node 30}
%	\label{img:ring}
%\end{figure}
%\begin{tabular}{|l|l|}
%\hline
%30 & \\
%\hline
%1 & 37\\
%\hline
%2 & 37\\
%\hline
%3 & 37\\
%\hline
%4 & 38\\
%\hline
%5 & 45\\
%\hline
%6 & 0\\
%\hline
%\end{tabular}





\chapter{Synchronistation}
\section{Clock synchronisation algorithms}
System model: each machine has timer that causes H interrupts per second
\begin{compactitem}
	\item clock $C$ adds up ticks (interrupts)
	\item $C_p(t)$ is clock time on machine $p$
	\item perfect clock: $\forall \  p, t : C_p(t) = t $ \\
	$\Longleftrightarrow C_p'(t) = \frac{d C_p(t)}{dt} = 1$\\
	$\mathrel{\widehat{=}}$ frequency of clock $C_p$ at time $t$

\begin{figure}[h]
	\centering
	\includegraphics[width=400px]{gfx/clock-drift.png}
	\caption{fast, slow \& perfect clock}
	\label{img:clock-drift}
\end{figure}

	\item $C_p'(t) - 1 \mathrel{\widehat{=}}$ skew of p's clock, difference to perfect clock.
	\item $C_p(t)-t \mathrel{\widehat{=}}$ offset
	\item real timers do not interrupt exactly H times per second
	\item maximum drift $\rho$ is a constant guaranteed/specified by the vendor \\
	$1-\rho \leq \frac{d C_p(t)}{dt} \leq 1 + \rho$

	\item at time $\Delta t$ after two clocks were synchronized the drift can be max: \\
	$|C_2(\Delta t) - C_1(\Delta t) | \leq 2 \rho \Delta t$
	\item if the difference should never exceed $\delta$ then synchronisation every $\frac {\delta}{2 \rho}$ seconds is needed
	\item time always moves forward.
\end{compactitem}

\textbf{example:} given values for $C_1$ and $C_2$:\\
$C_1 = \rho = 0.001$\\
$C_2 = \rho = 0.001$\\
$\frac{dC}{dt} = \frac {1}{2 * 0.001} = \frac{1}{0.002} = \frac{1}{2} * 10^{3}$\\
Clocks $C_1$ and $C_2$ need to be synchronized every $500s$ to keep time in the same second.\\

\section{Network Time Protcol (NTP)}
\begin{compactitem}
\item nodes contact time server that has an accurate clock
\item time server passive\\

\begin{figure}[h]
	\centering
	\includegraphics[width=200px]{gfx/ntp.png}
	\caption{ntp}
	\label{img:ntp}
\end{figure}

A estimates its offset to B as\\
$\Theta = \frac{(T_2 - T_1) + (T_4 - T_3)}{2}$\\
assuming communication time is symmetric\\
delay:\\
$\delta = (T_4 - T_1) - (T_3 - T_2) =  (T_2 - T_1) + (T_4 - T_3)$
\item A probes B, B probes A
\item NTP stores 8 pairs $(\Theta, \delta)$ per node pair using min($\delta$) for smallest delay
\item either A or B can be more stable
\item reference node has \underline{stratum  1} (clock has stratum 0) (stratum = \# Servers to a reference clock)
\item lower stratrum level is better, will be used.
\end{compactitem}

\section{Berkeley algorithm}

\begin{figure}[h]
	\centering
	\includegraphics[width=200px]{gfx/berkeley.png}
	\caption{Berkley Clocks: (a) The time daemon asks all the other machines for their clock values (b) The machines anwer.  (c) The time daemon tells everyone how to adjust their clock.}
	\label{img:berkeley}
\end{figure}

\begin{compactitem}
\item assumes no node has 'good' time
\item time server polls all nodes for their time
\item takes average and adjusts speed of nodes correspondingly
\item all nodes agree on time, which may not be correct
\end{compactitem}



\section{Lamports Logical Clocks}

\begin{figure}[h]
	\centering
	\includegraphics[width=300px]{gfx/lamport.png}
	\caption{Lamport's clock}
	\label{img:lamport}
\end{figure}

\begin{compactitem}
\item logical time need not correct in real time.
\item needs 'happens before' relation a $\rightarrow$ b

\begin{compactenum}
\item if a,b are events in the same process and a happens before b, than a $\rightarrow$ b is true
\item if a denotes the event of sending a message and b the event of receiving this message by another process then a $\rightarrow$ b is true
\end{compactenum}

\item happens before is transitive:\\
$a \rightarrow b \land b \rightarrow c \Rightarrow a \rightarrow c$
\item concurrency:\\
if $x, y$ happen in different processes and neither $x \rightarrow y$ nor $y \rightarrow x$, then $x, y$ are concurrent\\
(which means, it is not known which one comes first)
\item $\forall$ events a, we can assign it a time $C(a)$ on which all processes aggree.
\item if $a \rightarrow b$ then $C(a) < C(b)$ \\
    if $C(a) < C(b)$ then not $a \xrightarrow{?} b$\\
    if $C(a) \not < C(b)$ then $ a \not \rightarrow b$\\

\item 4 properties of logical time
\begin{compactenum}
\item No two events get assigned the same time.
\item Logical times of events in each process are strictly increasing
\item logical time of send event is strictly smaller than receive event for the same message
\item for any $t \in T$ only finitely many events get assigned logical times smaller then  t.
\end{compactenum}
\end{compactitem}

\textbf{Algorithm} \\
 $C_i =$ local counter of process $P_i$

\begin{compactenum}
\item Before executing an event (sending a msg over the network, delivering a msg to an app, some internal events) $P_i$ executes $C_i \leftarrow C_i + 1$
\item When process $P_i$ sends message $m$ to $P_j$ it sets the timestamp $ts(m)$ of $m$ to the current time $ts(m) \leftarrow C$.
\item upon receipt of a message $m$ process $P_j$ adjust its time to $C_j \leftarrow \max \left({C_j, ts(m)+1}\right)$
\end{compactenum}

\subsection{Totally ordered multicast}

\begin{figure}[h]
	\centering
	\includegraphics[width=300px]{gfx/TotallyOrderedMulticast.png}
	\caption{Totally Ordered Multicast}
	\label{img:TotallyOrderedMulticast}
\end{figure}

\subsubsection{Example}

Consider a bank with two data centers A and B, that need to be kept consistent. Each request uses the nearest copy. \\
Assume a customer has \$1000,- in his bank account and decides to add \$100,- using copy A. At the same time 1\% interest is added to copy B. What happens? How can we solve the problem?

%Bild

\subsubsection{Algorithm}
\begin{compactitem}
	\item  every message is sent to all receivers+itself with timestamp
	\item Assumption 1: messages from the same sender are received in the order they were sent, and that no messages are lost
	\item Assumption 2: no two events get assigned the same time
	\item When msg is received
	\begin{compactenum}
		\item put it into a local priority queue ordered to the msgs timestamp
		\item multicast an acknowledgment to all other processes ( following Lamport $\Rightarrow ts(msg) < ts(ack)$ )
	\end{compactenum}
	\item eventually all queues are identical $\Rightarrow$ total order
	\item Process delivers a queued msg to the app only when
	\begin{compactenum}
		\item msg is at head of queue
		\item ack received from every process
	\end{compactenum}

%Bild!!! :D

\end{compactitem}

\section{Vector Clocks}
\begin{compactitem}
	\item Problem with Lamport: does not capture causality
	\item By construction, we know that for each message $T_{sent}(m_i) < T_{recv} (m_i)$. But what can we conclude in general from$ T_{recv} (m_i) < T_{sent} (m_j)$ [Lamport]

\begin{figure}[h]
	\centering
	\includegraphics[width=300px]{gfx/lamport-concurrent.png}
	\label{img:lamport-concurrent}
\end{figure}

	\item
		In the case $m_i=m_1$ and $m_j = m_3$ we know at $P_2$  that $m_j$ was sent after $m_i$ was received. This \emph{may} indicate that sending of $m_j$ has something to do with the receiving of $m_i$

	\item Vector Clocks: \\
		$VC(a) < VC(b)$ means, that event a is known to causally precede event b.
	\item Each process $P_i$ maintains a Vector $VC_i$ with the following properties:
		\begin{compactenum}
			\item $VC_i[i]$ is the number of events that occured so far at $P_i$ \\
				$VC_i[i]$ is the logial clock at $P_i$
			\item if $VC_i[j]=k$ then $P_i$ knows, that $k$ events have occured at $P_j$. It is thus $P_i$'s knowledge of the local time at $P_j$
				%Bild
		\end{compactenum}
 	\item To maintain properties:
 			\begin{compactenum}
 			\item Before executing an event (i.e., sending a message over the network, delivering a message to an application, or some other internal event), $P_i$ executes $VC_i[i] = VC_i[i] + 1$
 			\item When process $P_i$ sends a message m to $P_j$, it sets m's (vector) timestamp $ts(m)$ equal to $VC_i$ after having executed the previous step
 			\item Upon the receipt of a message m, process $P_j$ adjusts its own vector by setting $VC_j[k] = max(VC_j[k], ts(m)[k])$ for each k, after which it executes the first step and delivers the message to the application.
		\end{compactenum}
		\item timestamp $ts (m)$ tells the receiver how many events in other processes have preceded the sending of m, and on which m may causally depend.
\end{compactitem}
\subsection{Causally-ordered multicast}
\begin{compactitem}
    \item Causally-ordered mulsticast is weaker than totally ordered multicast
    \item delivery of message m from $P_i$ to $P_j$ to application layer will be delayed until:
	\begin{compactenum}
		\item $ts(m)[i] = VC_j[i]+1$ \\
		= m is the next message that $P_j$ was expecting from process $P_i$
		\item $ts(m)[k] \leq VC_j[k] \ \ \forall \ k \neq i$ \\
		= $P_j$ has seen all the messages that have been seen by $P_i$ when it sent message m

	\end{compactenum}
	\item Better to be implemented on application layer, because the app knows which messages are causally related.
\end{compactitem}

\begin{figure}[h]
	\centering
	\includegraphics[width=300px]{gfx/vector-clock.png}
	\label{img:vector-clock}
\end{figure}

\subsection{Thoughts on causality and ordering}
\begin{compactitem}
\item causal ordering and (total) ordering are not the same
\item causal ordering asks, which causal relationship the ordered items have
\item lamport clocks and vector clocks both implement partial causal ordering
\item vector clocks implement a stronger form of partial causal ordering (Tanenbaum p. 248 speaks here of total ordering, WP speaks of partial ordering)
\item both can be forced to adhere to total ordering of events by implementing a mechanism deciding the ordering of concurrent events (if you do so, the total ordering then does not necessarily imply a causal ordering)
\end{compactitem}

\chapter{Mutual Exclusion}
Access to shared resources\\
2 types of algorithms: token-based and permission-based
\begin{compactitem}
	\item token is simple, reliability problem (lost token)
	\item permission difficult in distributed systems
\end{compactitem}

\section{Centralized algorithm}
\begin{figure}[h]
	\centering
	\includegraphics[width=300px]{gfx/mutex-centralized.png}
	\label{img:mutex-centralized}
\end{figure}

\subsection*{Algorithm}
\begin{compactitem}
	\item one process is coordinator
	\item when process wants access, it sends request to the coordinator
	\item coordinator allows access only to one process
	\item blocks competing processes by not replying and stores request in queue
	\item when process is finished, it sends a message to the coordinator
	\item coordinator takes the first item off the queue of deferred requests and sends that process a grant message
\end{compactitem}

\subsection*{Properties}
\begin{compactitem}
	\item simple
	\item fair, requests are processed in order of arrival
	\item no starvation: no process ever waits forever
	\item efficient: requires only three mes- sages per use of resource (request, grant, release)
	\item easy to implement
\end{compactitem}

\subsection*{Problems}

\begin{compactitem}
	\item coordinator is single point of failure
	\item processes cannot distinguish a dead coordinator from "permission denied" ($\rightarrow$ use non-blocking scheme with "permission denied" messages instead of blocking ungranted requests
	\item handle message loss with ack
\end{compactitem}

\section{Decentralized algorithm}
\begin{compactitem}
	\item voting algorithm that can be executed using a DHT-based system
\end{compactitem}


%\subsection*{Algorithm: Highlevel view from Tanenbaum}
%
%\begin{compactitem}
%	\item each resource is replicated $n$ times
%	\item every replica has its own coordinator for controlling the access by concurrent processes
%	\item whenever a process wants to access the resource, it will simply need to get a majority vote from $m>n/2$ coordinators
%	\item when a coordinator does not give permission, it will tell the requester
%\end{compactitem}
%
%\subsection*{Algorithm: From lecture}
%\begin{compactitem}
%	\item Let $m$ be the count of the coordinators, that answered and allowed entry to the critical section
%	\item Each resource is replicated n times , rname\_i is the name of the replica
%	\item each replica has it's own controller, the name is a hash of the rname\_i
%	\item if rname is known, each process can generate the address of the controllers
%	\item access to resource when $m>n/2$ controllers grant it
%	\item If permission to the resource is denied (i.e., a process gets less than $m$ votes), it is assumed that it will back off for a randomly chosen time, and make a next attempt later.
%\end{compactitem}


\subsection*{Algorithm}

\begin{compactitem}
	\item resource is known under its unique name $rname$
	\item each resource is assumed to be replicated $n$ times
	\item $rname_i$ is the unique name of the i-th replication of $rname$
	\item every replica has its own coordinator for controlling the access, reachable under $hash(rname_i)$
	\item given a resource's name, a process can generate the necessary $n$ keys, lookup each coordinator and request permission
	\item permission to access the resource is granted, when a majority vote is acquired, i.e. $m>n/2$ permission messages  from  coordinators are received
	\item when a coordinator does not give permission, it will tell the requester
	\item If permission to the resource is denied (i.e., a process gets less than $m$ votes), it is assumed that it will back off for a randomly chosen time, and make a next attempt later.	
\end{compactitem}

\subsection*{Properties}

\begin{compactitem}
	\item makes the original centralized solution less vulnerable to failures of a single coordinator
	\item when a coordinator crashes, it recovers quickly but will have forgotten any vote it gave before it crashed
	\item coordinator may reset itself (i.e. crash) at arbitrary moments
	\item risk: reset will make the coordinator forget that it had previously granted permission to some process 
	\item may incorrectly grant this permission again to another process after its recovery=
	\item Let $p$ probability that a coordinator resets during $\Delta t$
	\item the probability $P[k]$ that $k$ out of $m$ coordinators reset during this $\Delta t$ is:\\
		$P[k]= \left( \binom{m}{k}\right) p^k (1-p)^{m-k}$
	\item at least $2m-n\geq n+2-n=2$ coordinators need to reset in order to violate the voting. This happens with probability $\sum\limits_{k=2m-n}^n P[k]$\\
	\item Example: \\  $\Delta t = 10s, n=32, m=0,75n$ \\ Probability of violation is $10^{-40}$
\end{compactitem}
	
\subsection*{Problems}
\begin{compactitem}
	\item heavy load $\Rightarrow$ drop in utilization
	\item there are so many nodes competing to get access that eventually no one is able to get enough votes leaving the resource unused 	\item according to Tanenbaum/van Steen solvable, but no solution given
\end{compactitem}

\section{A distributed algorithm aka Ricart and Agrawala's Algorithm}

\begin{compactitem}
	\item deterministic
	\item uses total ordering of events
	\item assumption: no message loss
\end{compactitem}


\begin{compactitem}
	
	\item process that wants to access a resource sends out message containing (resourcename, process no, current localtime) to all other processes and itself
	\item process receives a message. Either:
		\begin{compactenum}
			\item if receiver does not want the resource: reply OK 
			\item if it has resource: no reply, queues request
			\item if receiver wants resource too, compares time stamps
			\begin{compactitem}
				\item if time stamp from remote request < time stamp from own request $\rightarrow$ reply OK
				\item else queue request, no reply
			\end{compactitem}	
			\item As soon as all the permissions are in, process can access resource 
			\item When finished, process sends OK messages to all processes in queue and empties queue		
		\end{compactenum}
\end{compactitem}

\begin{figure}[h]
	\centering
	\includegraphics[width=300px]{gfx/mutex-distributed.png}
	\label{img:mutex-distributed}
\end{figure}

\subsection*{Properties}
\begin{compactitem}
	\item grants mutual exclusion without deadlocks or starvation
\end{compactitem}
\subsection*{Problems}
\begin{compactitem}
	\item node failure: single point of failure has been replaced by n points of failure. Any process crashes $\rightarrow$ no access granted
    \item load, all processes take part in decisions (needs 2(n-1) messages for n processes)
	\item algorithm is slower, more complicated, more expensive, less robust than centralized algorithm $\rightarrow$ not a good algorithm
\end{compactitem}

\section{Token Ring Algorithm}

%\begin{figure}[h]
%	\centering
%	\includegraphics[width=300px]{gfx/mutex-token.png}
%	\label{img:mutex-token}
%\end{figure}
\subsection*{Algorithm}
\begin{compactitem}
	\item processes form a logical ring
	\item token continuously circulates around the ring
	\item owner of token can access resource, passes token when finished (not allowed to immediately enter resource again)
\end{compactitem}
\subsection*{Properties}
\begin{compactitem}
	\item simple and efficient
	\item no starvation (once a process needs resource, at worst it will have to wait for every other process to use the resource once).
\end{compactitem}
\subsection*{Problems}
\begin{compactitem}
	\item If the token is ever lost, it must be regenerated
	\item detecting token loss is is difficult, since the amount of time between appearances of the token is unbounded
	\item crashing nodes pose problem, but recovery is easier than in the other cases (dead node detection via acks of token delivery)
	\item not fair under heavy load (according to Wolter, not Tanenbaum)
\end{compactitem}

\section{Comparison}

\begin{tabular} {l|l|l|l}
Algorithm&messages per entry/exit&Delay before access&Problems\\
\hline
Centralised& 3& 2&coordinator crash\\
Decentralised&$3mk$&$2m$&starvation, low efficiency\\
Distributed&$2(n-1)$&$2(n-1)$&crash of any process\\
Token Ring& 1 to $\infty$&$0$ to $\infty$&lost token, process crash, fairness?
\end{tabular}
\ \\
\begin{compactdesc}
	\item[messages per entry/exit] the number of messages required for a process to access and release a shared resource
	\item[Delay before access] the delay (in message times) before access can occur (assuming messages are passed sequentially over a network)
\end{compactdesc}

\begin{compactitem}
	\item all algorithms except the decentralized one suffer badly in the event of crashes
	\item the distributed algorithms are even more sensitive to crashes than the centralized one
	\item The decentralized algorithm is less sensitive to crashes, but processes may suffer from starvation and special measures are needed to guarantee efficiency
\end{compactitem}

\input{chapter/leader.tex}

\input{chapter/consistency.tex}

\chapter{Tips Exam}
1. Aufgabe: Terminiologie (wichtige Konzepte, erklären, vergleichen, bla,bla)
dann durch die Themen des Semsters, übungszettel, gerne ausrechnen (Fingertable, Metriken von overlaynetzen, komplexität von protokollen (wie viele nachrichten braucht ein protokoll), logische uhren (stellen oder so)), erklären, Peersimaufgabe(n) (programm angucken, was macht das programm?, überblick, wie modifizieren für fkt x, cycle driven vs event driven (was wofür)), last auf dem netz, kein gnuplot programm auf papier!!!
Hilfsmittel: mitbringen, was man will, außer internet, telefon, freunde usw...

\end{document}