\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{\TOFIX}[1]{\textcolor{orange}{#1}}
\newcommand{\TODO}[1]{\textcolor{red}{#1}}
\newcommand{\ELEM}[1]{\textcolor{blue}{#1}}
\newcommand{\NAME}[0]{\textit{h}-LSEQ}

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

\title{Concurrency Effects Over Variable-size Identifiers 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 I}
%\begin{figure}
%  \includegraphics[width=\textwidth]{./img/gdoc.png}
%\end{figure}
%\end{frame}

\setbeamercovered{transparent}
\begin{frame}{LSEQ, an allocation strategy for variable-size CRDTs}
  \textbf{All is about the insert operation}
  \begin{itemize}
    \item insert($id_p$, element, $id_q$) $\Rightarrow$ \textbf{alloc}($id_p$,
    $id_q$) $\Rightarrow$ $id_{element}$ such as $id_p<id_{element}<id_q$
  \end{itemize}

  \textbf{\textit{Allocation strategy before}}\\
  \begin{itemize}
  \item \textit{linear}
  \item \textit{editing behaviour dependant} $\Rightarrow$ design for
    end-editing
  \end{itemize}
  
  \begin{center}
  \input{endeditingexample.tex}
  \end{center}

  \textbf{LSEQ allocation strategy}
  \begin{itemize}
    \item lowered the space complexity: linear $\Rightarrow$ polylogarithmic
    \item any editing behaviour
      \begin{itemize}
      \item[$\Rightarrow$] variable-size CRDTs safe
      \item[$\Rightarrow$] avoids additional protocol
      \item[$\Rightarrow$] ready to use in editors?
    \end{itemize}
  \end{itemize}
\end{frame}


\begin{frame}{Not yet\ldots}
  left open in LSEQ perspectives: the \textbf{concurrency effects}
  \begin{itemize}
  \item how the LSEQ \textbf{alloc} function behaves when
    \begin{enumerate}
    \item varying number of users
    \item varying latency
    \end{enumerate}
  \end{itemize}
  \ \\ \ \\
  \begin{table}[h]
    \begin{center}
      \begin{tabular}{|l|r|r|r|r|r|}
        \cline{2-6}
        \multicolumn{1}{c|}{} & \multicolumn{5}{c|}{\textbf{\#insert
            operations}}
        \\
        %% \cline{2-6}
        \multicolumn{1}{c|}{} & \textbf{10} & \textbf{100} & \textbf{200}
        & \textbf{500} & \textbf{1000} \\
        \hline
        1 user (bit/id) & 6.5 & 26.8 & 32.7 & 56.0 & 64.2 \\
        \hline
        10 users (bit/id) & 9.5 & \TODO{125.8} & \TODO{377.0} & \TODO{1962.1} &
        \TODO{5468.0} \\
        \hline
      \end{tabular}
    \end{center}
  \end{table}
  \ \\
  \begin{itemize}
    \item expectation: sub-linear behaviour
    \item reality: quadratic growth
  \end{itemize}
  \begin{itemize}
  \item[$\Rightarrow$] only \TODO{partially} improves variable-size identifiers
  \end{itemize}

\end{frame}

%% %%% % %% % %% % % % % % %% % % % %%

\begin{frame}{Objective}
  \begin{itemize}
  \item Solve the limitation of LSEQ in context involving concurrency
    \begin{itemize}
    \item \textbf{Extends} sub-linear upper-bound of single user to
      \textbf{multiple users}
    \item \textbf{Study} the effect of \textbf{latency} over the size of
      identifiers
    \end{itemize}
  \end{itemize}

  \begin{itemize}
    \item[]
    \begin{itemize}
    \item [$\Rightarrow$] No costly additional protocol
    \item [$\Rightarrow$] I can build a Distributed Collaborative Editor based
      on variable-size CRDTs
      \begin{itemize}
      \item Decentralized
      \item Simple algorithms
      \item Tiny metadata
      \end{itemize}
    \end{itemize}
\end{itemize}
\end{frame}

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

\textbf{Similar to LSEQ}
\begin{itemize}
  \item exponential tree model 
  \item multiple sub allocation strategies
    \begin{itemize}
      \item designed for end-editing
      \item designed for front-editing
    \end{itemize}
\end{itemize}
\ \\
\textbf{Different}
\begin{itemize}
\item strategy choice
\end{itemize}
\ \\
\begin{table}[h]
  \begin{center}
    \begin{tabular}{|c|c|c|}
      \cline{2-3}
      \multicolumn{1}{c|}{} & local & different \\
      \hline
      LSEQ & random & different \\
      \hline
      \NAME{} & random & \textbf{similar} \\
      \hline
    \end{tabular}
  \end{center}
\end{table}

\ \\
\begin{block}{Intuition}
  The shared hash function provide an \emph{a priori} \textbf{agreement} over
  participants on which strategy to employ. This agreement \textbf{avoids} the
  possibility of \textbf{antagonist choices} which would have led to a bad
  global allocation of identifiers.
\end{block}
\end{frame}

\begin{frame}{LSEQ vs \NAME{}: example}

\begin{figure}[width=\textwidth]
  \begin{center}
    \input{hashexample.tex}
  \end{center}
\end{figure}

\begin{columns}[onlytextwidth]
\begin{column}{0.5\textwidth}
  \begin{enumerate}
  \item <2-> user1: insert(B,a,E)
    \begin{itemize}
    \item[$\Rightarrow$] lvl 1 $\rightarrow$ End-editing
      \begin{itemize}
      \item[$\Rightarrow$] [9]
      \end{itemize}
    \end{itemize}
  \item <3-> user2: insert(a,b,E)
    \begin{itemize}
    \item[$\Rightarrow$] lvl 1 $\rightarrow$ Front-editing
      \begin{itemize}
      \item[$\Rightarrow$] [30]
      \end{itemize}
    \end{itemize}
  \item <5-> repeat 1 x: depth increases
  \item <5-> repeat n x: quadratic growth
  \end{enumerate}
\end{column}
\begin{column}{0.5\textwidth}
  \begin{enumerate}
  \item <6->user1: insert(B,a,E)
    \begin{itemize}
    \item[$\Rightarrow$] lvl1 $\rightarrow$ End-editing
      \begin{itemize}
      \item[$\Rightarrow$] [9]
      \end{itemize}
    \end{itemize}
  \item <7->user2: insert(a,b,E)
    \begin{itemize}
    \item[$\Rightarrow$] lvl1 $\rightarrow$ End-editing
      \begin{itemize}
      \item[$\Rightarrow$] [10]
      \end{itemize}
    \end{itemize}
  \item <8->repeat 1 x: stay lvl 1
  \item <8->repeat n x: sub-linear behaviour
  \end{enumerate}
\end{column}
\end{columns}


\end{frame}

\begin{frame}{Experiments}
\begin{enumerate}
  \itemsep 10pt
\item Evaluation of LSEQ and \NAME{} on a collaboration involving
  \textbf{multiple users}
  \begin{itemize}
  \item[$\Rightarrow$] Synthetic documents (100 lines)
  \item[$\Rightarrow$] 10 users (10 op/each)
  \item[$\Rightarrow$] Editing behaviour: end editing
  \item[$\Rightarrow$] Instant delivery of messages ($\approx$ LAN)
  \item[Expect:] 
    \begin{enumerate}
      \item LSEQ $\Rightarrow$ quick growth of identifiers
      \item \NAME{} $\Rightarrow$ quick stabilization $\Rightarrow$ sub-linear
        upper-bound
      \end{enumerate}
  \end{itemize}
\item Evaluation of LSEQ and \NAME{} with \textbf{varying latency}
  \begin{itemize}
  \item[$\Rightarrow$] Synthetic documents (100 lines)
  \item[$\Rightarrow$] 10 users (10 op/each)
  \item[$\Rightarrow$] Editing behaviour: end editing
  \item[Expect:] 
    \begin{enumerate}
    \item no latency: worst-case
    \item latency $\nearrow$ then avg(id.size) $\searrow$
    \end{enumerate}
  \end{itemize}
\end{enumerate}
\end{frame}

\begin{frame}{\NAME{} scales in term of users}

  \begin{figure}
    \begin{center}
      \includegraphics[width=0.9\textwidth]{./img/tenusers.eps}
    \end{center}
  \end{figure}
\end{frame}

\begin{frame}{Latency does not badly impact variable-size CRDTs}

  \begin{figure}
    \begin{center}
      \includegraphics[width=0.9\textwidth]{./img/stats.eps}
    \end{center}
  \end{figure}
\end{frame}

\begin{frame}{Synthesis: experiments}
  \begin{enumerate}
    \itemsep 10pt
  \item \NAME{} $\Rightarrow$ hash-based choice strategy $\Rightarrow$ global
    agreement on employed strategies
    \begin{itemize}
    \item[$\Rightarrow$] No additionnal cost (only a shared seed within the
      document)
    \item[$\Rightarrow$] Generalize the space complexity from single user to
      multiple users
    \end{itemize}
  \item Latency:
    \begin{itemize}
    \item No bad impact on size of identifiers
    \item No latency $\Rightarrow$ upper-bound on the size of identifiers
    \end{itemize}
  \item[$\Rightarrow$] \NAME{} supports concurrency
  \end{enumerate}
\end{frame}


\begin{frame}{Conclusion}

\NAME{} handles concurrency
\begin{itemize}
  \item[$\Rightarrow$] limitation solved
\end{itemize}
\ \\
With \NAME{}:
\begin{itemize}
\item  Distributed Collaborative Editors
  \begin{itemize}
  \item Decentralized
  \item Very simple algorithms
  \item tiny metadata
  \end{itemize}
\end{itemize}

\ \\
\emph{CRDT-based distributed collaborative editors using \NAME{} constitutes a
  good alternative to trending editors such as Google Docs, Etherpad\ldots with
  better scalability.}
\end{frame}

\begin{frame}{Future works}

\begin{enumerate}
  \item Develop the Distributed Collaborative Editor
  \item Proof
    \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 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}
\end{frame}

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

%%\setbeamertemplate{footline}{}
%%\section{Références}
%%\begin{frame}[allowframebreaks]{Références}
%%  \def\newblock{\hskip .11em plus .33em minus .07em}
%%  \bibliographystyle{plainnat}
%%  \bibliography{bibliographie}
%%\end{frame}

\end{document}
