\documentclass[a4paper,11pt]{article} \renewcommand{\b}[1]{\ensuremath{\mathbf{#1}}} \newcommand{\event}[1]{\stackrel{#1}{\longrightarrow}} \newcommand{\mi}[1]{\mathit{#1}} \newtheorem{lemma}{Lemma} \newtheorem{corollary}[lemma]{Corollary} \usepackage{a4wide} \begin{document} \title{Distributed Systems} \maketitle \section*{Books} \begin{itemize} \item \textit{Distributed Computing} -- H.~Attiya and J.~Welch -- McGraw-Hill, 1998, ch. 1 \item \textit{Concurrent Systems} -- J.~Bacon -- Addison-Wesley 1994, ch. 1 \item \textit{Distributed Systems} -- Coulouris et al. -- A-W 1993, ch. 1 \item \textit{Distributed Systems} -- Mullender (ed.) -- A-W 1993, ch. 1 and 2 \item \textit{Distributed Algorithms} -- N. Lynch -- Morgan Kaufman 1996, ch. 1 \end{itemize} \section*{Introduction} A distributed system is a system composed of several computers that are connected in some way and that together provide some service or achieve some goal, e.g. \begin{itemize} \item communication, e.g. cellphones, email \item process control, e.g. in aircraft \item information processing, e.g. financial transactions \item scientific computing, e.g. weather forecasting \end{itemize} The hardware of a distributed system may for instance be a VLSI chip, a shared-memory multiprocessor machine, a LAN of workstations or PCs, or a global network. In this course we study some ideas, concepts and techniques that are useful in understading, designing and implementing distributed systems. \section{A Mathematical Model} We begin by describing a mathematical model that can be used to express many distributed systems. \medskip Consider a finite connected graph $(\b{P}, \b{L})$. We call the nodes \emph{processes} and the edges \emph{links}. A link makes possible communication of data from a set \b{D} between the processes that it joins. \textbf{Example: } Suppose the graph has 12 processes $P_0,\ldots ,P_{11}$ connected in a ring, i.e. $\b{P} = \{P_0,\ldots ,P_{11}\}$ and $\b{L} = \{(P_i, P_{i+1}) | 0 \leq i < 12\}$ where arithmetic is mod 12. Let $\b{D} = \b{N} \cup \{$done$\}$. \medskip [Diagram goes here] \medskip The set \b{M} of messages is \b{P \times D \times P}. \textbf{Example: } The message $(P_3, $done$, P_4)$ is the datum \emph{done} set from $P_3$ to $P_4$. \medskip The \emph{state} of a process at a given moment is determined by the control state it is in, the data it is storing, and the arrived messages that have been delivered to it but not examined by it. \textbf{Example: } Suppose each $P_i$ has an associated name $n_i \in \b{N}$. Let the set \b{S} of states be $\b{Q} \times \b{N} \times \cal{F}(\b{M})$ where \b{Q} = \{init, active, leader, follower\} and $\cal{F}(\b{M})$ is the set of all finite multisets\footnote{I think a multiset (a.k.a. a bag) is like a normal set, but you can have multiple copies of the same thing in it.} of messages. A state of $P_2$ might be (active, 20, $\{(P_1, 0, P_2), (P_1, 10, P_2)\})$. \medskip A \emph{configuration} of a distributed system describes the state of each of its processes and the collection of messages that have been sent but not delivered. \textbf{Example: }The set \b{C} of configurations is $\b{S}^{12} \times \cal{F}(\b{M})$. \medskip Each process has a \emph{transition function} that determines what, if anything, it may do in a given state. Transition functions are sometimes described explicitly, as in the next example, and sometimes implicitly, by some text, pseudo-code, or program. \medskip \textbf{Example: } The transition function of $P_i$, for $0 \leq i < 12$, is ${\delta}_i : \b{S \to S} \times \cal{F}(\b{M})$ defined by: \begin{tabbing} ${\delta}_i$(init, n, in) = ((active, $n$, in), $\{(P_i, n, P_{i+1})\})$ \\ ${\delta}_i(q, n, $in$) = $\=$ ((q, n, \emptyset), \emptyset)$ \\ \> if $q$=leader or $q$=follower or ($q$=active and in=$\emptyset$) \\ ${\delta}_i($active$, n, $in$) =$ \\ wibble \= \+ \kill if done $\in$ data(in) then $(($follower$, n, \emptyset), \{(P_i, $done$, P_{i+1})\})$ \\ else if $n \in $data(in) then $(($leader$, n, \emptyset),\{(P_i, $done$, P_{i+1})\})$ \\ else if $n > $max(in) then $(($active$, n, \emptyset), \emptyset)$ \\ else if $n < $max(in) then $(($active$, n, \emptyset, \{(P_i, $max(in)$, P_{i+1})\})$ \\ jam \= \+ \kill where \=data(in) is the set of data in the message set \emph{in}, \\ and \> max(in) is the largest integer in that set (and in $\neq \emptyset$) \\ \end{tabbing} \pagebreak Very rough sketch of ${\delta}_i$: \begin{verbatim} /~\ | | | v init -> active -> leader <-\ | \__/ v follower <-\ [mmmm, ASCII] \__/ \end{verbatim} There are two kinds of event: \begin{itemize} \item \emph{Computation events}, where a process makes a transition \item \emph{Delivery events}, where a message is delived to a process \end{itemize} If an event $E$ is possible in a configuration $C$, it may occur and result in a configuration $C'$: $C \stackrel{e}{\longrightarrow} C'$. \subsubsection*{Example} \begin{enumerate} \item Suppose $C = (S_0,\ldots,S_{11},U)$ and ${\delta}_i(S_i) = (S_i', \mi{out})$. Then $C \event{\mi{comp}(i)} C' = (S_0, \ldots, S_i', \ldots, S_{11}, U \cup \mi{out})$. \item Suppose $C = (S_0, \ldots, S_{11}, U \cup \{m\})$ where $m = (P_j, d, P_i)$. Then $C \event{del(m)} C' = (S_0, \ldots, S_i, \ldots, S_{11}, U)$ where if $S_i = (q, n, \mi{in})$ then $S_i' = (q, n, in \cup \{m\})$. \end{enumerate} \bigskip \b{Q} has a nonempty subset $\b{Q}_{\mi{init}}$ of initial control states, and a subset $\b{Q}_{\mi{final}}$ of final control states. A state is \emph{initial} (\emph{final}) if its control state is. A configuration is \emph{initial} (\emph{final}) if the state of each of its processes is. \textbf{Example: } $\b{Q}_{\mi{init}} = \{\mi{init}\}$ and $\b{Q}_{\mi{final}} = \{\mi{leader}, \mi{follower}\}$. \noindent Also, $\b{S}_{\mi{init}} = \b{Q}_{\mi{init}} \times \b{N} \times \{\emptyset\}$ and $\b{S}_{\mi{final}} = \b{Q}_{\mi{final}} \times \b{N} \times \cal{F}(\b{M})$. \noindent Also, $\b{C}_{\mi{init}} = (\b{S}_{\mi{init}})^{12} \times \cal{F}(\b{M})$ and $\b{C}_{\mi{final}} = (\b{S}_{\mi{final}})^{12} \times \cal{F}(\b{M})$. \bigskip In general, if $\delta$ is a transition function, $S$ is a final state, and $\delta(S) = (S', \mi{out})$, then $S'$ is final. Hence, if C is final and $C \event{e} C'$, then $C'$ is final. An \emph{evolution} of a distributed system described by a configuration $C_0$ is of the form $C_0 \event{e_0} C_1 \event{e_1} C_2 \event{e_2} \ldots$. An evolution $C_0 \event{e_0} C_1 \event{e_1} \ldots$ is \emph{terminating} is there exists $j$ such that $C_j$ is final. If $C_0$ describes an \emph{asynchronous} system then an evolution $C_0 \event{e_0} C_1 \event{e_1} \ldots$ is \emph{admissible} if: \begin{enumerate} \item For each process $P_i$ there are infinitely many $j$ such that $e_j = \mi{comp}(i)$. \item If $e_j = \mi{comp}(i)$ and $m$ is created in $e_j$, then $e_k = \mi{del}(m)$ for some $k$. \end{enumerate} In an admissible evolution of an asynchronous system, each process performs infinitely many transitions, and every message that is created is delivered. There need be no finite upper bound on the number of events between two transitions of a process or between the creation and the delivery of a message. \bigskip If $C_0$ describes a \emph{synchronous} system then an evolution $C_0 \event{e_0} C_1 \event{e_1} \ldots$ is \emph{admissible} if it consists of a sequence of \emph{rounds}. In a round, \begin{enumerate} \item all outstanding messages are delivered, and then \item each process performs a computation step which results in at most one message being created, addressed to any given process. \end{enumerate} There is a fixed bound on the number of events between the creation and delivery of a message. \section{Leader Election} The \emph{leader election problem} is to design a process that stores just two data -- its name $n:\b{N}$ and its status $s:\{\mi{null}, \mi{leader}, \mi{follower}\}$ -- so that for any $k>1$, if $S$ is a system consisting of $k$ copies of $P$ -- that may differ only in storing different names -- connected in a ring, and in which there are initially no undelivered messages, then every admissible evolution of $S$ contains a final configuration in which the status of one $P$ is $\mi{leader}$, and the status of every other $P$ is $\mi{follower}$. \subsection*{A. The synchronous case} Fix $k>1$. Choose distinct $n_0, \ldots, n_{k-1}$. P has variables $s$, initially $\mi{null}$, and $n$, initially $n_i$ in $P_i$. $P$'s transitions are described as follows, where $c$ refers to the clockwise neighbour: \begin{eqnarray*} \mi{init} & = & c!n \to \mi{active} \\ \mi{leader} & = & ?\mi{in} \to \mi{leader} \\ \mi{follower} & = & ?\mi{in} \to \mi{follower} \\ \mi{active} & = & ?\mi{in} \to \mi{IF} ( \\ & & \mi{done} \in \mi{data}(\mi{in}): s:=\mi{follower} \to c?\mi{done} \to \mi{follower} \\ & & n \in \mi{data}(\mi{in}) : s:= \mi{leader} \to c!\mi{done} \to leader \\ & & n < \max(\mi{in}) : c!\max(\mi{in}) \to \mi{active} \\ & & n > \max(\mi{in}) : \mi{active}) \end{eqnarray*} [Notes: (1) The IF construct means ``if\ldots then\ldots elsif\ldots then\ldots elsif\ldots then\ldots'' and so on. (2) An empty set doesn't actually have a maximum, to the IF wouldn't appear to cover the case where $\mi{in}=\emptyset$. It works (I think) if you pretend that $\max(\emptyset) = -1$, or that the last branch will always be executed if $\mi{in}=\emptyset$.] Let $n* = \max{n_0, \ldots, n_{k-1}}$, and suppose $n* = n_m$. { \renewcommand{\labelenumi}{(\alph{enumi})} \renewcommand{\labelenumii}{(\roman{enumii})} \subsubsection*{Lemma 1} Suppose $0 \le r < k$. \begin{enumerate} \item In round $r$, \begin{enumerate} \item $P_{m+r}$ sends $n*$ \item If $j \ne m+r$ then $P_j$ does not send $n*$ \item No $P_j$ sends $\mi{done}$ \item If $j \ne m$ then no $P_i$ with $i \in [m\ldots j-1]$ sends $j$ \end{enumerate} \item \begin{enumerate} \item $P_j$ is in control state $\mi{active}$. \item $s_j = \mi{null}$ \end{enumerate} \end{enumerate} \subsubsection*{Lemma 2} Suppose $0 \le r < k$. \begin{enumerate} \item In round $k+r$, $P_{m+r}$ sends $\mi{done}$. \item At the end of round $k+r$, \begin{enumerate} \item $P_m$ is in control state $\mi{leader}$ and $s_m = \mi{leader}$ \item If $j \in (m,m+r]$ then $P_j$ is in control state $\mi{follower}$ and $s_j = \mi{follower}$ \item If $j \in (m+r, m)$ then $P_j$ is in control state $\mi{active}$ and $s_j = \mi{null}$ \end{enumerate} \end{enumerate} \subsubsection*{Corollary 3} At the end of round $2k-1$, \begin{enumerate} \item $s_m = \mi{leader}$ \item If $j \ne m$ then $s_j = \mi{follower}$ \end{enumerate} \subsubsection*{Message complexity} The number of messages created in the first $2k$ rounds is $O(k^2)$. \subsection*{B. The asynchronous case} Consider the system $S$, but now viewed as being asynchronous. \subsubsection*{Lemma 4} Suppose $C$ is a configuration in an admissible evolution of $S$. \begin{enumerate} \item $P_j$ is $\mi{leader}$ iff $s_j = \mi{leader}$. \item $P_j$ is $\mi{follower}$ iff $s_j = \mi{follower}$. \item $P_j$ is $\mi{init}$ or $\mi{active}$ iff $s_j = \mi{null}$. \item If $C$ contains $(P_i, n*, P_{i+1})$ then $P_m$ is active and $s_j = \mi{null}$ for $j \ne m$. \item $C$ contains at most one message of the form $(P_i, n*, P_{i+1})$. \item If $j \ne m$ and $i \in [m \ldots j-1]$, then $C$ does not contain $(P_i, n_j, P_{i+1})$. \item If $j \ne m$ then $s_j \ne leader$. \item If $C$ contains $(P_{m+j}, \mi{done}, P_{m+j+1})$, where $d \le j < k$, then $s_m = \mi{leader}$ and $s_i = \mi{follower}$ for $i \in (m, m+j]$ and $P_i$ is $\mi{active}$ for $i \in (m+j, m)$. \item $C$ contains at most one message of the form $(P_i, \mi{done}, P_{i+1})$. \end{enumerate} \subsubsection*{Lemma 5} Suppose $C_0 \event{e_0} C_1 \event{e_1} \ldots$ is an admissible evolution of $S$. \begin{enumerate} \item If $0 \le j