% Based on generic-ornate-15min-45min.en.tex by Till Tantau <tantau@users.sourceforge.net>.
% Ilari Nieminen, 2007. No rights reserved.
% http://www.tcs.hut.fi/Studies/T-79.4001/
% T-79.4001 Seminar on Theoretical Computer Science

% Original copyright notice:

%% Copyright 2004 by Till Tantau <tantau@users.sourceforge.net>.
%%
%% In principle, this file can be redistributed and/or modified under
%% the terms of the GNU Public License, version 2.
%%
%% However, this file is supposed to be a template to be modified
%% for your own needs. For this reason, if you use this file as a
%% template and not specifically distribute it as part of a another
%% package/program, I grant the extra permission to freely copy and
%% modify this file as you see fit and even to delete this copyright
%% notice.

% http://latex-beamer.sourceforge.net
% http://www.lirmm.fr/~fiorio/AlgorithmSty/ (Place algorithm2e.sty in your working directory)

\documentclass{beamer}
\usepackage[]{algorithm2e}

% A few keywords to use in pseudocode
% You should also probably read the algorithm2e -documentation more than I did.

\SetKw{Send}{send}
\SetKw{To}{to}
\SetKw{Othera}{other}
\SetKw{Become}{become}

\mode<presentation>
{
   \usetheme{Malmoe}
   \setbeamercovered{transparent}
   \definecolor{beamer@tkkblue}{HTML}{0041AD}
   \setbeamercolor{structure}{fg=beamer@tkkblue}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\title
{Election in Trees and Rings}
\subtitle
{T-79.4001 Seminar on Theoretical Computer Science}
\author
{Ilari Nieminen}
\date
{21.02.2007}

\AtBeginSection[]
{
  \begin{frame}<beamer>
    \frametitle{Outline}
    \tableofcontents[currentsection]
  \end{frame}
}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents
\end{frame}

\section{Leader Election}

\subsection[Election]{Election}

\begin{frame}
  \frametitle{Notation}
  \begin{itemize}
  \item
    $n$ is the number of nodes, $m$ is the number of edges
  \item
    Standard set of restrictions \newline
    \textbf{R} = $\{$\emph{Bidirectional Links}, \emph{Connectivity}, \emph{Total Reliability}$\}$
  \item
    N($x$) is the set of neighbours of $x$
  \item
    $\textbf{M}\left[P\right]$ is the number of messages needed in protocol $P$
  \item
    $\textbf{T}\left[P\right]$ is the time required in protocol $P$
  \item
    $\textbf{B}\left[P\right]$ is the number of bits needed in protocol $P$
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Election}

Leader Election (\textbf{Elect})
  \begin{itemize}
  \item
    In the initial configuration all entities are in the same state (``available'')
  \item
    In the goal configuration all but one are in the same state (``follower'')
  \item
    Can be thought as enforcing restriction \emph{Unique Initiator}
  \end{itemize}

\end{frame}

\subsection{Impossibility Result}

\begin{frame}
  \frametitle{Impossibility Result}

  \begin{itemize}
  \item
    Problem \textbf{Elect} is \emph{deterministically unsolvable} under \textbf{R}
  \item
    Means that there is no protocol that will terminate correctly in finite time
  \item
    Easy to prove with two entities when communication delays are unitary
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Election's Standard Set of Restrictions}
  Restriction \emph{Initial Distinct Values} (ID) is chosen to break the symmetry between entities.
  Set \textbf{IR} $=$ \textbf{R} $\cup \{\mathrm{ID}\}$ is called the \emph{standard set for election}.
  id($x$) is used to denote the distinct value of entity $x$.
  
\end{frame}

\subsection{Solution Strategies}
\begin{frame}
  \frametitle{Elect Minimum}
  
  \begin{enumerate}
  \item
    Find the smallest value id($x$)
  \item
    Elect the entity with that value as a leader
  \end{enumerate}

  This strategy also solves \textbf{Min}.

\end{frame}

\begin{frame}
  \frametitle{Elect Minimum Initiator}
  
  \begin{enumerate}
  \item
    Find the smallest value id($x$) among initiators
  \item
    Elect the entity with that value as a leader
  \end{enumerate}

  Does not solve \textbf{Min}.

\end{frame}

\begin{frame}
  \frametitle{Elect Root}

  \begin{enumerate}
  \item
    Construct a rooted spanning tree
  \item
    Elect the root of the tree as the leader
  \end{enumerate}

\end{frame}

\section{Election in Trees}

\subsection{Elect Minimum and Elect Root}

\begin{frame}
  \frametitle{Elect Minimum in Trees}
  Tree:Elect\_Min
  \begin{itemize}
  \item
    Using saturation, find the smallest value
  \item
    $\textbf{M}\left[Tree:Elect\_Min\right] = 3n + k_* - 4 \leq 4n - 4$
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Elect Root}

  \begin{itemize}
  \item
    \emph{Full Saturation} selects two saturated nodes
  \item
    \emph{Tree:Elect\_Root} compares the identities of the saturated nodes
  \item
    $\textbf{M}\left[Tree:Elect\_Root\right] = 3n + k_* - 2 \leq 4n - 2$

  \end{itemize}

\end{frame}

\begin{frame}[fragile]
  \frametitle{Tree:Elect\_Root}


\SetAlFnt{\scriptsize}
\dontprintsemicolon
\begin{algorithm}[H]
\begin{columns}
\column[T]{6cm}

SATURATED\;
\Indp
  Receiving(Election, id)\;
  \Begin{
    \eIf{id(x) < id} {
    become LEADER\;
    }{
    become FOLLOWER\;
    }
  \Send(Termination) \To N($x$)-\{parent\}\;
  }
\BlankLine
\Indm
PROCESSING\;
\Indp
  Receiving(Termination)\;
  \Begin{
    become FOLLOWER\;
    \Send(Termination) \To N($x$)-\{parent\}\;
  }

\column[T]{6cm}

\Indm
\BlankLine
Procedure Resolve\;
  \Begin{
   \Send(Election,id(x)) \To parent\;
    become SATURATED\;
  }

\end{columns}
\end{algorithm}
\end{frame}

\subsection{Performance}

\begin{frame}
  \frametitle{Bit Complexity}
  \begin{itemize}
  \item
    Tree:Elect\_Root sends two more messages than Tree:Elect\_Min
  \item
    Number of bits needed is lower for Tree:Elect\_Root
  \item
    $\textbf{B}\left[Tree:Elect\_Min\right] = n(c + \log \mathrm{id}) + c(2n + k_* - 2)$ % Should possibly be -4.
  \item
    $\textbf{B}\left[Tree:Elect\_Root\right] = 2(c + \log \mathrm{id}) + c(3n + k_* - 2)$
  \end{itemize}
  where $c = O(1)$ denotes the number of bits needed to distinguish between messages.

\end{frame}

\section{Election in Rings}

\subsection{General}

\begin{frame}
  \frametitle{Rings}
  \begin{itemize}
  
  \item
    A ring consists of a single cycle of length $n$
  \item
    Each entity has exactly two neighbours, whose ports are called ``right'' and ``left''
  \item
    It is important to note that this labeling might be inconsistent between entities
  \item
    Notation: \textbf{other} is used to denote N($x$)-sender
  \item
    Any protocol that elects a leader in a ring can be made to find the minimum value with $n$ additional messages
  
  \end{itemize}
\end{frame}

\subsection{All the Way}

\begin{frame}
  \frametitle{All the Way}
  \begin{itemize}
  \item
    On becoming awake entity sends a message to one of its neighbours containing its id
  \item
    On receiving a message it forwards the message and keeps note of the smallest id seen 
  \item
    Because the \emph{Message Ordering} restriction is not used, an entity won't know that the election is finished when it receives its value back
  \item
    To calculate the size of the ring, a counter is added to the message
  \item
    Does not actually need the \emph{Bidirectional Links} restriction
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{All the Way Protocol}

\SetAlFnt{\tiny}
\dontprintsemicolon
\begin{algorithm}[H]
\begin{columns}
\column[T]{6cm}
States: $S$ = \{ASLEEP, AWAKE, FOLLOWER, LEADER\}\;
$S_{INIT}$ = \{ASLEEP\}\;
$S_{TERM}$ = \{FOLLOWER, LEADER\}\;
\BlankLine
\BlankLine
ASLEEP\;
\Indp
  \emph{Spontaneously}\;
  \Begin{
      INITIALIZE\;
      become AWAKE\;
  }
\BlankLine
  \emph{Receiving}(``Election'', value$^*$, counter$^*$)\;  
  \Begin{
      INITIALIZE\;
      \Send(``Election'', value$^*$, counter$^*$+1) \textbf{to other}\;
      count := count+1\;
      min := Min\{min, value$^*$\}\;
      \textbf{become} AWAKE\;
      }
\BlankLine
\Indm
\column[T]{6cm}
AWAKE \;
\Indp
  \emph{Receiving}(``Election'', value$^*$, counter$^*$)\;
  \Begin{
      \eIf{value$^*$ $\neq$ id($x$)}{
	\Send(``Election'', value$^*$, counter$^*$+1) \textbf{to other}\;
        min := MIN\{min, value$^*$\}\;
        count := count+1\;
        \If{known}{CHECK\;}}{
	ringsize := counter$^*$\;
	known := true\;
	CHECK\;
}
    }

\end{columns}
\end{algorithm}


\end{frame}

\begin{frame}
  \frametitle{All the Way Procedures}

\SetAlFnt{\tiny}
\dontprintsemicolon
\begin{algorithm}[H]
\begin{columns}
\column[T]{6cm}

Procedure INITIALIZE\;
\Begin{
    count := 0\;
    size := 1\;
    known := false\;
    \Send(``Election'', id($x$), size) \To right;
    min := id($x$)\;
}
\BlankLine
Procedure CHECK
\Begin{
    \If{count = ringsize}{
      \eIf{min = id($x$)}{
	\Become LEADER\;
      }{
	\Become FOLLOWER\;
      }
    }
}


\column[T]{6cm}

\end{columns}
\end{algorithm}
\end{frame}

\begin{frame}
  \frametitle{All the Way and All the Way Minimum Initiator}

  \begin{itemize}
  \item
    The cost of \emph{All the Way} is easily seen
  \item
    $\textbf{M}\left[AlltheWay\right] = n^2$
  \item
    $\textbf{T}\left[AlltheWay\right] \leq 2n-1$
  \item
    By modifying the protocol to find the smallest value among the initiators number of messages can be reduced
  \item
    $\textbf{M}\left[AlltheWay:Minit\right] = nk_* + n$
  \item
    $\textbf{T}\left[AlltheWay:Minit\right] \leq 3n-1$
  \item
    The additional $n$ is required to inform the ring of termination.
  \end{itemize}

\end{frame}

\subsection{As Far As It Can}

\begin{frame}
  \frametitle{As Far As It Can}

  \begin{itemize}
  \item
    The drawback of \emph{All the Way} is that every message travels the whole ring
  \item
    \emph{All the Way} is modified so that an entity will only forward Election messages if the id in the message
    is smaller than than the smallest seen so far
  \item
    The message with the smallest id will travel the entire ring, so if an entity receives its own id, it knows it is the leader
  \item
    The leader notifies the ring to ensure termination

  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{As Far As It Can Message Complexity} 

  \begin{itemize}
  \item
    Worst case happens if the ring is ``ordered'' and all the messages
    are sent in the ``increasing'' direction 
  \item
    $\textbf{M}\left[AsFar\right] = n+\sum_{i=1}^{n}i = \frac{n(n+3)}{2}$
  \item
    Average case is harder. Let $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n}$
  \item
    $\textbf{M}\left[AsFar\right] = n H_n \approx .69n\log_2 n + O(n)$ on average in oriented (or unidirectional) rings\newline
    $\textbf{M}\left[AsFar\right] = \frac{\sqrt{2}}{2}n H_n \approx .49n\log_2 n + O(n)$ on average in unoriented rings (assuming half of the ``rights'' 
    correspond to the clockwise direction)
  \item
    $\textbf{T}\left[AsFar\right] = \textbf{T}\left[All the Way\right] + n-1$
  \end{itemize}

\end{frame}

\subsection{Controlled Distance}

\begin{frame}
  \frametitle{Controlled Distance}

  \begin{itemize}
  \item
    The downside with \emph{As Far As It Can} is that $O(n^2)$ performance is still possible
  \item
    \emph{Controlled Distance} has guaranteed $O(n \log n)$ message performance
  \item
    Idea is to limit the distance a message can travel and send multiple messages if necessary
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Controlled Distance Basics}
  
  \begin{enumerate}
  \item
    Entity $x$ sends a message with its own id, and the message will travel until it is terminated (by a smaller id) or until it reaches a distance $dis$.
  \item
    If the message is not terminated, it will be sent back to its originator. After receiving the returned message, it knows there are no smaller ids on
    that side of the ring within distance $dis$.
  \item
    To confirm that there are no smaller ids on either side, the entity will send the message in both directions. If they both come back, next time the
    message will be allowed to travel further.
    
  \end{enumerate}

\end{frame}

\begin{frame}
  \frametitle{Controlled Distance Basics (cont.)}
  
  \begin{enumerate}
  \setcounter{enumi}{3}
  \item
    If at any time an entity receives a message with a smaller id, it will stop trying to win the election
  \item
    If an entity receives its own message back from the other side, it knows it is the leader and notifies the ring 
  \end{enumerate}
\end{frame}


\begin{frame}
  \frametitle{Controlled Distance Correctness}

  \begin{itemize}
  \item
    The correctness can intuitively be understood through the following observations
  \item
    Messages containing the smallest id will always travel the maximum allocated distance.
  \item
    Every candidate that meets the messages will give up
  \item
    Allocated distance is increased monotonically, so at some point, a message with the minimum id will travel through the whole ring
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Protocol Control}

\SetAlFnt{\tiny}
\dontprintsemicolon
\begin{algorithm}[H]
\begin{columns}
\column[T]{6cm}

States: $S = \{ASLEEP, CANDIDATE, DEFEATED, FOLLOWER, LEADER\}$\;
$S_{INIT} = \{ASLEEP\}$\;
$S_{TERM} = \{FOLLOWER, LEADER\}$\;
\BlankLine

ASLEEP\;
\Indp
\emph{Spontaneously}\;
\Begin{
    INITIALIZE\;
    \Become CANDIDATE;
}
\BlankLine
\emph{Receiving}(``Forth'', id$^*$, stage$^*$, limit$^*$)\;
\Begin{
    \eIf{id$^*$ < id($x$)}{
      PROCESS-MESSAGE\;
      \Become DEFEATED\;}{
      INITIALIZE\;
      \Become CANDIDATE\;
    }
}

\BlankLine
\Indm

DEFEATED\;
\Indp
\emph{Receiving}(*)\;
\Begin{
    \Send(*) \To \Othera\;
    \If{* = ``Notify''}{\Become FOLLOWER}\;
}
\Indm
\column[T]{6cm}

CANDIDATE\;
\Indp
\emph{Receiving}(``Forth'', id$^*$, stage$^*$, limit$^*$)\;
\Begin{
    \eIf{id$^*$ < id($x$)}{
      PROCESS-MESSAGE\;
      \Become DEFEATED\;}{
      \If{id$^*$ = id($x$)}{NOTIFY\;}}
}
\BlankLine
\emph{Receiving}(``Back'', id$^*$)\;
\Begin{
    \If{id$^*$ = id($x$)}{CHECK\;}
}
\BlankLine
\emph{Receiving}(``Notify'') 
\Begin{
    \Send(``Notify'') \To \Othera\;
    \Become FOLLOWER\;
}      

\end{columns}
\end{algorithm}
\end{frame}

\begin{frame}
  \frametitle{Procedures of protocol Control}

\SetAlFnt{\tiny}
\dontprintsemicolon
\begin{algorithm}[H]
\begin{columns}
\column[T]{6cm}

Procedure INITIALIZE\;
\Begin{
stage := 1\;
limit := dis(stage)\;
count := 0\;
\Send(``Forth'', id($x$), stage, limit) \To N($x$)\;
}
\BlankLine

Procedure PROCESS-MESSAGE\;
\Begin{
limit$^*$ := limit$^*$-1\;
\eIf{limit$^*$ = 0}{
  \Send(``Back'', id$^*$, stage$^*$) \To \textbf{sender}\;
  }{
  \Send(``Forth'', id$^*$, stage$^*$, limit$^*$) \To \Othera\;
  }
}
\BlankLine

Procedure CHECK\;
\Begin{
count := count+1\;
\If{count = 2}{
  count := 0\;
  stage := stage+1\;
  limit := dis(stage)\;
  \Send(``Forth'', id($x$), stage, limit) \To N($x$)\;
}
}

\column[T]{6cm}

Procedure NOTIFY\;
\Begin{
    \Send(``Notify'') \To right\;
    \Become LEADER\;
}
  
\end{columns}
\end{algorithm}
\end{frame}

\begin{frame}
  \frametitle{Message Complexity of Control}
\begin{itemize}
  \item
    Performance depends on choice of dis(i)
  \item
    Let dis$^{-1}$($n$) denote smallest integer $k$ such that dis($k$) $\geq n$.
  \item
    $\textbf{M}\left[Control\right] \leq n \sum_{i=1}^{dis^{-1}(n)}\left(3\frac{dis(i)}{dis(i-1)}+1\right) + n$
  \item
    If distance is doubled at each stage
    $\textbf{M}\left[Control\right] \leq 7 n \log n + O(n)$
  \item
    $\textbf{T}\left[Control\right] \leq 2n + \sum_{i=1}^{dis^{-1}(n)}2dis(i)$

\end{itemize}
\end{frame}

\end{document}