\documentclass{beamer}

\usepackage[english,francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{natbib}
\usepackage{multirow}

\usepackage{hyperref}
\hypersetup{
  colorlinks,
  citecolor=black,
  filecolor=black,
  linkcolor=black,
  urlcolor=black
}
\usepackage[labelformat=empty]{caption}
\usepackage{url}
\usepackage{epstopdf}
\usepackage{epsfig}
\usepackage{tikz}
\usepackage{graphicx}
\usepackage{transparent}

\usetikzlibrary{trees}
\definecolor{light-gray}{gray}{0.65}
\tikzset{fade on/.code={\only<#1>{\color{light-gray}}}}
\tikzset{hide on/.code={\only<#1>{\color{white}}}}
\tikzset{bold on/.code={\only<#1>{\bfseries}}}
\usetikzlibrary{plotmarks,shapes}
\usepackage{subcaption}

\newcommand{\NAME}[0]{LSEQ}
\newcommand{\TODO}[1]{\textcolor{red}{#1}}

\usetheme{Boadilla}
\setbeamertemplate{sections/subsections in toc}[square]
\setbeamertemplate{blocks}[rounded][shadow=false]
\setbeamertemplate{footline}{\vskip2pt}
\setbeamertemplate{items}[square]
\beamertemplatenavigationsymbolsempty

\input{data/indexdata.tex}

\title{\NAME{}: an Adaptive Structure for Sequences\\ in Distributed
  Collaborative Editing}

\subtitle{ConcoRDanT}

\titlegraphic{
  \begin{center}
    \includegraphics[width=2cm]{logos/univ_nantes.eps}\hspace*{0.05\textwidth}
    \includegraphics[width=2cm]{logos/lina.eps}\hspace*{0.05\textwidth}
  \end{center}
}

\date{}

\author{Brice Nédelec\\ \and Pascal Molli \and Achour Mostefaoui \and Emmanuel
  Desmontils}

\institute{LINA, 2 rue de la Houssinière\\
  BP02208, 44322 Nantes Cedex 03\\
  \url{first.last@univ-nantes.fr}}

\begin{document}
  \renewcommand*{\theenumii}{\alph{enumii}}
  \renewcommand*{\theenumiii}{\roman{enumiii}}

%%% TITLE %%%
\begin{frame}
  \titlepage
\end{frame}
\setbeamertemplate{footline}{\hfill\insertframenumber{\ \ }\vskip2pt}
\setcounter{framenumber}{0}

\begin{frame}{Distributed Collaborative Editors}
  \begin{columns}
    \begin{column}{0.47\textwidth}
      \begin{itemize}
      \item DCE allow to \textbf{distribute the work} across \textbf{space,
          time, organizations.}
      \item \textit{example: Google Docs, Google Wave, Etherpad, Git,
          Subversion, Wikipedia, CoVim\ldots}
      \end{itemize}
    \end{column}
    \begin{column}{0.5\textwidth}
      \begin{figure}
        \includegraphics[scale=0.15]{img/gdoc.png}
      \end{figure}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}{Current editors are not entirely satisfying}
  \begin{itemize}
  \item \textbf{Single point of failure}: the server is down, I cannot work on
    my document anymore\ldots
  \item \textbf{Privacy concern}: the owner of the server owns the data\ldots
    He can sell it to third-party company. (\textit{e.g. advertisement
      company})
  \end{itemize}
  \ \\
  \begin{itemize}
  \item[$\Rightarrow$] \textbf{As a user, I don't want my editor got any of
      these!}
    \begin{itemize}
    \item[$\Rightarrow$] Deny the enslavement to a coordination provider!
    \item[$\Rightarrow$] I still want something as appealing as Google Docs
      though\ldots
    \end{itemize}
  \end{itemize}
\end{frame}

\setbeamercovered{transparent}
\begin{frame}{Benefits of the optimistic replication}
  \begin{itemize}
  \item <1-> most editors relies on the optimistic replication approach.
    \begin{itemize}
    \item high \textbf{availability} of data: each user has its own local
      replica
    \item \textbf{two phases} operations:
      \begin{enumerate}
      \item \textbf{locally} prepare the result of the operation and send it
      \item integrate the result of the \textbf{remote} operations to the data
      \end{enumerate}
    \end{itemize}
  \item <2-> when the data is a document $\rightarrow$ modifications are
    \textbf{insert} or \textbf{delete} an element
      \begin{itemize}
      \item[$\Rightarrow$] element: character, line, paragraph\ldots
      \end{itemize}
  \end{itemize}

  \begin{itemize}
  \item <3-> modifications of the document must ensure the 3 properties (CCI):
    \begin{enumerate}
    \item \textbf{Convergence}: all replicas eventually reach an identical
      state
    \item \textbf{Causality}: any operation needs to reflect the operations
      that occurred causally before it
    \item \textbf{Intention}: the effect of an operation needs to meet the
      intention of the user that ordered it
    \end{enumerate}
  \end{itemize}

  \begin{itemize}
  \item[$\Rightarrow$] <4-> a \textbf{very efficient} approach that belongs to
    optimistic replication 
    \begin{itemize}
    \item[$\Rightarrow$] \textbf{Conflict-free Replicated Data Types}
      \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[t]{CRDTs for sequences}

\framesubtitle{Conflict-free Replicated Data Types}

  \begin{itemize}
  \item simple abstract type for sequences that can model documents
  \item optimistic replication: convergent, two phases operations \ldots
  \item avoids the difficult task of sovling conflicts
  \item 2 commutative operations: insert and delete
    \begin{itemize}
    \item[$\Rightarrow$] ins/ins, ins/del, del/del
    \item[$\Rightarrow$] except: ins(a)/del(a) $\Rightarrow$ require causality
      : ins(a) $\rightarrow$ del(a)
    \end{itemize}
  \end{itemize}
  
\ \\
  
  \begin{itemize}
  \item <2-> 1 identifier for each element in sequence
    \begin{itemize}
    \item document $\rightarrow$ character, line, paragraph\ldots
    \item unique, non mutable identifier
    \item totally ordered
    \item the order on ids makes the sequence
    \end{itemize}
  \item <2-> [$\Rightarrow$] delete($id_{element}$)
  \item <2-> [$\Rightarrow$] insert($id_p$, element, $id_q$) $\Rightarrow$ \textbf{alloc}
    ($id_p$, $id_q$) $\Rightarrow$ $id_p < id_{element} < id_q$
  \end{itemize}
\end{frame}

\begin{frame}{Allocation of identifiers matters}
\input{sequence.tex}

\begin{itemize}
\item <11-> linearly growing ids
  \begin{itemize}
  \item document with 1000 lines $\Rightarrow$  $max(id.size)=1000$
  \end{itemize}
\end{itemize}

\end{frame}


\begin{frame}{Problem: lowering the size of identifiers}

\begin{columns}[onlytextwidth]

\begin{column}{0.4\textwidth}
\begin{block}{Variable-size identifier}
  A variable-size identifier $id$ is a sequence of numbers $id=[p_1.p_2\ldots
    p_n]$ which can designate a path in a tree.
\end{block}
\begin{itemize}
  \item <2-> $Id_D = [10]$
  \item <4-> $Id_O = [10.13]$
\end{itemize}
\end{column}
\begin{column}{0.6\textwidth}
\flushright
\begin{center}
\begin{tikzpicture}[scale=0.85]
\tiny


  \draw (0,0) -- node[anchor=south east]{0}  (-85pt, -50pt);
  \draw (0,0) -- node[anchor=south west]{99} ( 85pt, -50pt);

  \draw[hide on=-1, bold on=2] (0,0) -- node[anchor=east]{10} (-40pt, -50pt);
  \draw[hide on=-2] (0,0) -- node[anchor=east]{11} (  0pt, -50pt);
  \draw[hide on=-2] (0,0) -- node[anchor=east]{14} ( 30pt, -50pt);

  \draw[fill=white] (0,0) circle (1pt);

\small
  \draw[fill=white] (-85pt, -50pt) node[anchor=north]{Begin} circle (1pt);
  \draw[fill=white] ( 85pt, -50pt) node[anchor=north]{End} circle (1pt);

\tiny
  \draw[hide on=-3, bold on=3] (-40pt,-50pt) --
  node[anchor=east]{13} (-34.8pt, -100pt);

  \draw[hide on=-4] (-40pt,-50pt) -- node[anchor=west]{42} (-23.2pt, -100pt);
  \draw[hide on=-4] (-40pt,-50pt) -- node[anchor=west]{92}(- 3.2pt, -100pt);

\small
  \draw[hide on=-1,bold on=2,fill=white] (-40pt, -50pt)
  node[anchor=east]{D} circle (1pt);
  \draw[hide on=-2,bold on=3, fill=white]
  (0pt, -50pt) node[anchor= north]{N} circle (1pt);
  \draw[hide on=-2,bold on=3, fill=white] ( 30pt, -50pt)
  node[anchor= north]{G} circle (1pt);


  \draw[hide on=-3,bold on=4,fill=white](-34.8pt, -100pt)
  node[anchor= north]{O} circle (1pt);

  \draw[hide on=-4,bold on=5,fill=white](-23.2pt, -100pt)
  node[anchor= north]{C} circle (1pt);

  \draw[hide on=-4,bold on=5,fill=white](- 3.2pt, -100pt)
  node[anchor= north]{E} circle (1pt);

\end{tikzpicture} 
\end{center}

\end{column}
\end{columns}


\begin{block}{\textbf{Problem statement}}
Let $\mathcal{D}$ a document on which $n$ insert operations have been
performed.  Let $\mathcal{I}(\mathcal{D})= \{id |
(\_,id)\in{\mathcal{D}}\}$. The function $alloc(id_p,id_q)$ should provide
identifiers such as:
\begin{center}
$\sum\limits_{id \in \mathcal{I}} { {|id|_2}\over{n}}$ $< O(n)$
\end{center}
\end{block}
\begin{itemize}
  \item[$\Rightarrow$] \textbf{No cleaning of the structure required!}
\end{itemize} 
\end{frame}

\begin{frame}{Proposal: \textbf{\NAME{}}}

\NAME{} relies on \textbf{3} components:
\begin{itemize}
\item \textbf{exponential tree}: we assume that when $\nearrow$ depth, it means
  that a lot of insertions were done and more are probably upcoming. We need
  more available nodes
\item \textbf{multiple allocation strategies}: a strategy designed for
  end-editing is not sufficient to handle any editing behaviour
\item \textbf{random strategy choice}: I have multiple sub allocation
  strategies. Which one should I choose? 
\end{itemize}
\ \\
\begin{block}{Intuition}
As it is complex to predict the editing behaviour, some depths of the tree on a
given path can be lost if the reward \textbf{compensates} the loss.

In other terms, even if \NAME{} chooses the wrong strategy at a given time, it
will eventually choose the good one, and that choice will \textbf{amortize} the
cost of all previous lost depths.
\end{block}
\end{frame}


\begin{frame}{Example: use case DNG? Wait... DOCENG!}

Three components:
\begin{itemize}
  \item <2->Exponential tree
    \begin{itemize}
    \item[$\Rightarrow$] 32 nodes maximum at depth-1, 64 nodes maximum at
      depth-2\ldots
    \end{itemize}
  \item <3->Two allocation strategies
    \begin{itemize}
      \item[$\Rightarrow$]: designed for end-editing
      \item[$\Rightarrow$]: designed for front-editing
    \end{itemize}
  \item <4->Random strategy choice
\end{itemize}

\begin{columns}
  \begin{column}{0.68\textwidth}
    \input{lseqtreeexampleP1.tex}
  \end{column}
  \begin{column}{0.35\textwidth}
    \begin{enumerate}
      \item <5-> insert(Begin,D,End)
      \item <6-> insert(D,N,End)
      \item <7-> insert(N,G,End)
      \item <8-> insert(D,E,N)
        \begin{itemize}
          \item[$\Rightarrow$] no room
          \item[$\Rightarrow$] randomize strat
          \item[$\Rightarrow$] front-editing
        \end{itemize}
        \item <9-> insert(D,C,E)
        \item <10-> insert(D,O,C)
    \end{enumerate}
  \end{column}
\end{columns}
\end{frame}



\begin{frame}{Back in time: Our baseline}
  \begin{center}
    \input{dimlogexperiment.tex}
  \end{center}
  \begin{itemize}
  \item random: logarithmic $\Rightarrow$ very good
  \item front and end: linear $\Rightarrow$ bad
  \item editing behaviour dependant $\Rightarrow$ bad
  \end{itemize}

\end{frame}

\begin{frame}{Exponential tree}
  \framesubtitle{\textbf{lower the space-complexity} but still \textbf{editing
      behaviour dependant}}
  
  \begin{columns}
    \begin{column}{0.47\textwidth}
      Each node has twice more children than its parent
      \begin{itemize}
      \item[$\Rightarrow$] exponential $\nearrow$ number of nodes when depth
        $\nearrow$
      \end{itemize}
      \ \\ \ \\
      Each number in the id costs 1 more bit to encode
      \ \\ \ \\
      $\textbf{+\,1}$ bit $\Rightarrow$ \textbf{x2} identifiers
      
    \end{column}
    \begin{column}{0.53\textwidth}
      \input{doubleexperiment.tex}
    \end{column}
  \end{columns}
  \begin{block}{Intuition}
    If the number of insert operations is \textbf{low}, the id bit-length can
    stay \textbf{small}. On the other hand, when the number of insertions
    \textbf{increases}, it is profitable to allocate \textbf{larger}
    identifiers.
  \end{block}
\end{frame}

\begin{frame}{Multiple allocation strategies \& Random strategy choice}
  \framesubtitle{\textbf{solve the editing behaviour dependency} but still
    \textbf{linear}}

\begin{columns}
  \begin{column}{0.47\textwidth}
    Two sub allocation strategy:
    \begin{itemize}
    \item[$\Rightarrow$] 1 designed for end-editing
    \item[$\Rightarrow$] 1 designed for front-editing
    \end{itemize}
    Allocation strategy chosen:
    \begin{itemize}
    \item[$\Rightarrow$] randomly
    \item[$\Rightarrow$] when id size increases
    \end{itemize}
  \end{column}
  \begin{column}{0.53\textwidth}
    \input{roundrobinexperiment.tex}
  \end{column}
\end{columns}

\begin{block}{Intuition: Why}
  The end-editing allocation strategy is \textbf{not sufficient} to be
  employed as a safe allocation strategy. However, by using its antagonist
  strategy, each strategy \textbf{cancels} the \textbf{deficiency} of the
  other.
\end{block}

\begin{block}{Intuition: Which}
Since it is impossible to know \emph{a priori} the editing behaviour, the
strategy choice should \textbf{not favorize any behaviour}.
\end{block}

\end{frame}

\begin{frame}{\NAME{} solves everything!}
  \framesubtitle{\NAME{} = exponential tree + two sub allocation strategies + 
  random strategy choice}

  \begin{center}
    \input{lseqexperiment.tex}
  \end{center}
  \begin{itemize}
    \item front and end: sub-linear behaviour
    \item random: logarithmic
  \end{itemize}
\end{frame}


\begin{frame}{\NAME{} outperforms variable-size CRDT on real documents}
\framesubtitle{extracted from the English Wikipedia}
\begin{figure}
\centering
\begin{subfigure}{0.47\textwidth}
  \includegraphics[width=\textwidth]{img/poste.eps}
\end{subfigure}
\begin{subfigure}{0.47\textwidth}
  \includegraphics[width=\textwidth]{img/didyouknow.eps}
\end{subfigure}
\end{figure}

\begin{columns}
  \begin{column}{0.5\textwidth}

    \begin{table}[h]
      \scriptsize
      \begin{center}
        \begin{tabular}{|c|c|r|r|}
          \cline{3-4}
          \multicolumn{2}{c|}{} &\textbf{L}ogoot &\textbf{\NAME{}}\\
          \hline
          \multirow{2}{*}{id-bit-length} & avg & $169.7$ & \textbf{61.24}\\
          \cline{2-4}
          & max & $256$ & $150$ \\
          \hline
        \end{tabular}
        \caption{Page mostly end-edited.}
        \label{tab:queuePage}
      \end{center}
    \end{table}
    \end{column}
    \begin{column}{0.5\textwidth}
      \begin{table}[h]
        \scriptsize
        \begin{center}
          \begin{tabular}{|c|c|r|r|}
            \cline{3-4}
            \multicolumn{2}{c|}{} &\textbf{L}ogoot &\textbf{\NAME{}}\\
            \hline
            \multirow{2}{*}{id-bit-length} & avg & $172.25$ & \textbf{51.99}\\
            \cline{2-4}
            & max & $320$ & $84$ \\
            \hline
          \end{tabular}
          \caption{Page mostly front-edited.}
          \label{tab:didyouknow}
        \end{center}
      \end{table}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}{Conclusion}

\textbf{\NAME{}}:
\begin{itemize}

  \item Allocation strategy for variable-size CRDTs for sequences
    \begin{itemize}
    \item[$\Rightarrow$] reusable (\emph{Example: Treedoc})
    \end{itemize}
  \item With 3 components:
    \begin{itemize}
      \item exponential tree
      \item 2 strategies: \emph{boundary+} and \emph{boundary--}
      \item random strategy choice
    \end{itemize}
\end{itemize}
\ \\ \ \\
\textbf{Experiments show}:
\begin{itemize}
  \item \NAME{} has a sub-linear behaviour
    \begin{itemize}
    \item under the assumption that it works in context involving concurrency
    \item[$\Rightarrow$] No additionnal rebalance protocol required
    \item[$\Rightarrow$] safely usable: large open distributed network with
      churn
    \end{itemize}
  \item Better performance over Logoot:
    \begin{itemize}
      \item good case of Logoot -- end editing
      \item bad case of Logoot -- front editing
    \end{itemize}
\end{itemize}


\end{frame}

\begin{frame}{Distributed Collaborative Editor $\not\Rightarrow$  single
    point of failure}
  
  \begin{itemize}
  \item LSEQ is not safe when \textbf{multiple users} are involved due to
    different strategy choices. It has been improved by a shared hash function.
    \begin{itemize}
    \item [$\Rightarrow$] upcoming talk\ldots 
    \end{itemize}
  \end{itemize}

  \begin{itemize}
  \item \textbf{Goal}: create Distributed Collaborative Editors which is
    \begin{enumerate}
    \item decentralized (privacy, availability, repartition of charge\ldots)
    \item scalable and simple
    \item short overhead
    \end{enumerate}
  \end{itemize}
\end{frame}

\begin{frame}{Future works}
\begin{enumerate}
  \item Proof on space complexity
    \begin{itemize}
      \item $n$ operations: uniform distribution $\Rightarrow
        O((log\,log\,n)^2)$
      \item $n$ operations: monotononic $\Rightarrow O((log\,n)^2)$
      \item $n$ operations: worst-case $\Rightarrow O(n^2)$
    \end{itemize}
  \item Proof: worst-case happens with a negligible probability
  \item Concurrency effect: Latency, multiple-users ?
  \item Causality tracking (still an issue in distributed systems with churn)
    \begin{itemize}
    \item does not scale in term of user
    \item or does not provide exact causality
    \item[$\Rightarrow$] CRDTs for sequences require causality\ldots
    \end{itemize}
\end{enumerate}
\ \\
\begin{enumerate}
\setcounter{enumi}{4} 
\item Develop the distributed collaborative editor
\end{enumerate}
\end{frame}

\begin{frame}[c]
\begin{center}
\textbf{Thank you!}
\end{center}
\end{frame}

\end{document}
