2-generals-talk/talk.tex

% Copyright (C) 2017 Koz Ross <koz.ross@retro-freedom.nz>
% Copyright (C) 2008 Karta24

% This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 
% International License. To view a copy of this license, visit 
% http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to Creative 
% Commons, PO Box 1866, Mountain View, CA 94042, USA.

% Karta's attribution applies to the image '2-generals-dead-messenger.svg', per
% the requirements of the CC-BY-SA license.

\documentclass[style=fyma]{powerdot}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage[font={itshape},begintext={``},endtext={''}]{quoting}

\newtheorem*{theorem}{Theorem}
\newtheorem*{observation}{Observation}

\pdsetup{theslide=,
  palette=gray}

\begin{document}

\begin{slide}[toc=]{}
  \begin{center}
    {\LARGE \textbf{The Two Generals Problem} \par}
    {\Large Or: Why distributed systems are Nintendo Hard \par}
    \vspace{1cm}    
    \includegraphics[scale=0.75]{logo.eps}
    \vspace{1cm}
    \linebreak
    Koz Ross

    \medskip

    March 16, 2017

  \end{center}
\end{slide}

\begin{slide}[toc=]{Overview}
  \tableofcontents[content=sections]
\end{slide}

\section{Introduction to distributed systems}

\begin{slide}{What is a distributed system?}
  A system is {\em distributed\/} if it has: \pause{}
  \begin{itemize}
    \item Multiple processing units (so we can do things `at the same time')\pause{}
    \item Independent failure (one unit failing shouldn't bring down the whole
      system)\pause{}
    \item Unreliable communication (information about other units is limited and
      uncertain, connections between units can fail unpredictably)\pause{}
  \end{itemize}

  Systems which are not distributed are called otherwise,  {\em singular\/} (or 
  {\em centralized\/} in some contexts).
\end{slide}

\begin{slide}{Examples of distributed systems}
  {\bf Example 1:} Social networks (like Facebook, Twitter, etc)\pause{}
  \medskip
  \begin{itemize}
    \item Multiple processing units (client apps, web browsers, servers)\pause{}
    \item Independent failure (if your computer catches fire, everyone else can
      still tell each other what they had for breakfast today)\pause{}
    \item Unreliable communication (timelines can go out of sync, trending posts
      can vary, updates might be lost or take a long time)
  \end{itemize}
\end{slide}

\begin{slide}[toc=]{Examples of distributed systems}
  {\bf Example 2:} Torrents (legitimate or otherwise)\pause{}
  \medskip
  \begin{itemize}
    \item Multiple processing units (everyone can seed or download different
      things, or parts of them, independently, at the same time)\pause{}
    \item Independent failure (if a single peer disconnects or runs slowly,
      everyone else can still download or seed)\pause{}
    \item Unreliable communication (peers randomly join and leave, network 
      failure to particular peers, slow connections$\ldots$)
  \end{itemize}
\end{slide}

\begin{slide}[toc=]{Examples of distributed systems}
  {\bf Example 3:} Human society (at any scale)\pause{}
  \medskip
  \begin{itemize}
    \item Multiple processing units (me teaching a class at 10am happens whether
      or not you care or show up)\pause{}
    \item Independent failure (society doesn't stop because one person gets sick
      or dies)\pause{}
    \item Unreliable communication (every sitcom ever$\ldots$)\pause{}
  \end{itemize}

  This shows that distributed systems don't just apply to computing!
\end{slide}

\begin{slide}{Why do we care?}
  \pause{}
  \begin{itemize}
    \item Distributed systems are {\em useful\/}\pause{}
    \item Distributed systems are {\em everywhere\/}\pause{}
    \item Distributed systems are {\em weird\/} (and thus, Nintendo Hard)
      \pause{}
  \end{itemize}

  Whatever you plan to do, distributed systems, their creation, maintenance and
  use {\em will\/} be {\em your\/} problem.\pause{} Understanding their
  weirdness is essential to making them behave and do what you want.\pause{} 
  
  \medskip

  The alternative to understanding distributed systems is {\em awful\/} (look at AWS 
  and Github, and that's just recently!).
\end{slide}

\section{The Two Generals Problem}

\begin{slide}{Problem overview}

  \begin{center}
  \includegraphics[scale=0.4]{2-generals.eps}
  \end{center}
  \pause{}
  \vspace{1cm}

  Both generals {\em must\/} attack at the same time if they want to take the
  city.\pause{} However, they haven't agreed on a time before they set up camp.

\end{slide}

\begin{slide}[toc=]{Problem overview}

  \begin{center}
  \includegraphics[scale=0.4]{2-generals-messenger.eps}
  \end{center}
  \vspace{1cm}

  The only way the generals can communicate with each other is by sending
  messengers between their camps.\pause{} In order for the messengers to get
  there in a timely manner, they must run through the city.

\end{slide}

\begin{slide}[toc=]{Problem overview}

  \begin{center}
  \includegraphics[scale=0.4]{2-generals-dead-messenger.eps}
  \end{center}
  \vspace{1cm}

  Some messengers won't make it.\pause{} Thus, neither general knows which of
  their messages got delivered, or what the chance of any given message getting
  delivered is.

\end{slide}

\begin{slide}[toc=]{Problem overview}

  \begin{center}
  \includegraphics[scale=0.4]{2-generals-dead-messenger.eps}
  \end{center}
  \vspace{1cm}

  {\bf Question:} Is it possible for both generals to agree on an attack time
  with {\em total\/} certainty?\pause{} {\em No.}
\end{slide}

\begin{slide}{Preliminaries}
  A {\em message\/} is some $x \in \mathbb{N}$.\pause{} An {\em outbox\/} is a list
  of sent messages, in the order they were sent.\pause{} 
 
  \medskip

  Each general $G$ has an outbox $\mathrm{out}(G)$, and a {\em decision\/}
  $d(G)$, where $d(G) \in \mathbb{N} \cup \{\mathrm{undef}\}$.\pause{}
  Initially, any general $G$ has $\mathrm{out}(G) = \emptyset$ and $d(G) =
  \mathrm{undef}$.\pause{} Each general is only aware of their own outbox and
  decision at any given time.\pause{}

  \medskip

  We also define a {\em success probability\/} $P \in (0, 1)$.\pause{} This 
  can change as messages get sent.\pause{} Neither of the generals know anything 
  about $P$ beyond these two facts.\pause{}

  \medskip

  We will refer to our generals as $C$ and $L$ (for no particular reason
  whatsoever).
\end{slide}

\begin{slide}[toc=]{Preliminaries}
  A general $G$ can send a message $m$ to another general $G^{\prime}$. To do
  this, we add $m$ to the end of $\mathrm{out}(G)$.\pause{} Then, we generate 
  a random $p \in (0,1)$ and compare it to $P$: if $p \leq P$, then the 
  message {\em arrives}, otherwise, it is {\em lost}.\pause{}

  \medskip

  If $m$ arrives, we set $d(G^{\prime}) = m$ (the generals are genuine and
  don't want to sabotage each other).\pause{}

  \medskip

  We say that our generals have {\em reached agreement\/} if:

  \begin{itemize}
    \item $d(C) \neq \mathrm{undef}$ and $d(L) \neq \mathrm{undef}$; and
    \item $d(C) = d(L)$
  \end{itemize}
\end{slide}

\begin{slide}{Problem statement}
  \begin{theorem}
    There is no $\mathrm{out}(C),\mathrm{out}(L)$ such that $C, L$ are
    guaranteed to reach agreement with probability 1.
  \end{theorem}\pause{}

  \bigskip

  Note that this does {\em not\/} claim that we cannot {\em ever\/} reach
  agreement --- only that we can't be certain that we will, given only the
  outboxes of both generals. 
\end{slide}

\begin{slide}{Proof}
  \begin{observation}
    If $\mathrm{out}(C) = \mathrm{out}(L) = \emptyset$, then we cannot have  
    reached agreement.
  \end{observation}\pause{}

  This is intentional: if nobody's sent any messages, clearly nobody's made any
  decisions, and thus, nobody's agreed to anything.
\end{slide}

\begin{slide}[toc=]{Proof}
  \begin{proof}
    Suppose for the sake of a contradiction that there exist some
    $\mathrm{out}(C), \mathrm{out}(L)$ such that we can guarantee $C,L$ reaching
    agreement with probability 1. Consider some message $m$ in either outbox, as
    well as $P$ at the time $m$ was sent.\pause{}

    \medskip

    As $P \neq 1$, the probability that $m$ was lost is $1 - P \neq 0$.\pause{} As 
    after sending each message in $\mathrm{out}(C), \mathrm{out}(L)$, we are 
    guaranteed to reach agreement with probability 1, $m$ arriving cannot have
    been essential for reaching agreement.\pause{} Thus, even if we don't send $m$, 
    we will still reach agreement with probability 1.\pause{}

    \medskip

    As $m$ is an arbitrary message, it follows that we can reach agreement when
    $\mathrm{out}(C) = \mathrm{out}(L) = \emptyset$.\pause{} However, this is a
    contradiction, as by definition, this is impossible. Thus, no such
    $\mathrm{out}(C), \mathrm{out}(L)$ can exist.
  \end{proof}
\end{slide}

\section{Consequences}

\begin{slide}{For computer scientists}
  \begin{itemize}
    \item Whenever we need {\em any\/} agreement on state between components in
      a distributed system, we are going to have a bad time.\pause{}
    \item Even something as simple as {\em shared clocks\/} become an
      issue!\pause{}
    \item Directly leads to two famous results: the FLP impossibility theorem
      (Fischer, Lynch and Paterson, 1985) and the CAP theorem (Brewer,
      1998).\pause{}
    \item A lot of work on singular systems is next-to-worthless for distributed
      ones.\pause{}
    \item There are lots of ways to obtain coherency and agreement in
      distributed systems, but {\em none\/} will be as perfect as a singular one
      (although you might not care in some cases).
  \end{itemize}
\end{slide}

\begin{slide}{For practitioners}
  \begin{itemize}
    \item When we need agreement or synchronization, there {\em will\/} be serious
      costs that have to be considered.\pause{}
    \item If you see (or need to be involved with) any distributed system with heavy 
      amounts of global information that must be kept coherent, {\em
      run}.\pause{}
    \item Know your tradeoffs --- if you can avoid needing a lot of
      synchronization or information sharing, definitely avoid it, or at least
      limit its impact.\pause{}
    \item Understand what the computer scientists have said about distributed
      systems --- it's not nearly as theoretical as you think, and it might save
      your job one day.
  \end{itemize}
\end{slide}

\begin{slide}{A final thought}
  \vspace{1cm}
  \begin{quoting}
    You know you have a distributed system when the crash of a computer you've
    never heard of stops you from getting any work done.
  \end{quoting}
  Leslie Lamport
\end{slide}

\section{Questions}

\end{document}