% A Readymade beamer presentation template
% Version 1.1
% Relase date: May 2, 2010
% Released at http://www.stattler.com
% by Rifat Jahan

\documentclass{beamer}
%\usecolortheme[named=green]{structure}
\mode<presentation> {
%\usetheme{Madrid} % My favorite!
%\usetheme{Boadilla} % Pretty neat, soft color.
%\usetheme{default}
%\usetheme{Warsaw}
%\usetheme{Bergen} % This template has nagivation on the left
\usetheme{Frankfurt} % Similar to the default with an extra region at the top.
%\usecolortheme{seahorse} % Simple and clean template
%\usetheme{Darmstadt} % not so good
% Uncomment the following line if you want page numbers and using Warsaw theme
% \setbeamertemplate{footline}[page number]
%\setbeamercovered{transparent}
\setbeamercovered{invisible}
% To remove the navigation symbols from the bottom of slides%
\setbeamertemplate{navigation symbols}{}
}

\usepackage{xcolor,colortbl}
\definecolor{mycolor1}{RGB}{181,165,243}
\definecolor{mycolor2}{RGB}{105,125,241}
\newcommand{\done}{\cellcolor{teal}done}  %{0.9}
\newcommand{\hcyan}[1]{{\color{teal} #1}}
\usepackage{wrapfig}
\usepackage{subfig}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{etex}
\usepackage[style=numeric-comp]{biblatex}
\usepackage[lined,boxed,commentsnumbered,ruled,vlined,
linesnumbered]{algorithm2e }
\usepackage{slashbox}

\usepackage{graphicx}
%\usepackage{bm} 
% For typesetting bold math (not \mathbold)
%\logo{\includegraphics[height=0.6cm]{yourlogo.eps}}
%
\title[Concurrency Control and Awareness Support for Multi-synchronous
Collaborative Editing]{Concurrency Control and Awareness Support for
Multi-synchronous Collaborative Editing}
%
\author[Mehdi Ahmed-Nacer]{Mehdi Ahmed-Nacer, Valter Balegas,\\ Pascal Urso
and Nuno Preguiça}
\institute[LORIA]
{
University of Lorraine - LORIA Laboratory - France \\
Nova de Lisboa - Portugal \\
\medskip
{\emph{mehdi.ahmed-nacer@loria.fr}} \\
\medskip
{This work is
partially funded by the french national research programs {\sc ConcoRDanT.}} \\
% \medskip
% {ICDAR 2013}
}
\date{}

% logo of my university
\titlegraphic{
\includegraphics[width=1.5cm]{images/ul.png}\hspace*{1.2cm}~%
\includegraphics[width=1.5cm]{images/nova_lisboa.png}\hspace*{1.2cm}~%
\includegraphics[width=1.5cm]{images/loria.jpg}\hspace*{1.2cm}~%
\includegraphics[width=1.5cm]{images/Logo-ANR.jpg}
}

\begin{document}
%
\begin{frame}
\titlepage
\end{frame}

%==================================================================
%==================================================================
%==================================================================
\section{Introduction}

\subsection{Collaborative editing applications}
\begin{frame}
\frametitle{Collaborative editing applications}

\begin{itemize}
\item Synchronous collaboration
\begin{itemize}
  \item Changes observed immediately
  \item Merge concurrent updates by \underline{operations}
  \end{itemize}

\item Asynchronous Collaboration
\begin{itemize}
  \item Changes observed after commit 
  \item Merge concurrent updates by \underline{states}
  \end{itemize}

\item Synchronous application supports disconnected collaboration
\begin{itemize}
\item Multi-synchronous applications
\end{itemize}
\item Satisfy users intention during concurrent updates
\item Keep awareness information to show to users the concurrent modifications

\end{itemize}


\end{frame}
%==================================================================
\subsection{Limitations of existing Solutions}
 \begin{frame}
\frametitle{Limitations of existing Solutions\\
1- Google Drive}


\begin{columns}[t]
 
 \begin{column}{7cm}
\begin{itemize}
   \item Merge updates after disconnected periods
\begin{itemize}
 \item Semantic errors
 \item Violatation of user intention
\end{itemize}
\end{itemize}
  \end{column}

 \begin{column}{3cm}
\begin{figure}[H]
  \includegraphics[width=3cm]{images/logo-google.jpg}
\end{figure}

  \end{column}
\end{columns}

\begin{itemize}
\item Different problems can occur
\begin{itemize}
 \item Concurrent updates on the same sentence
\item Typographic errors
  \item Cursor position
  \item Update loss
  
\end{itemize}
\item Limitations: 
\begin{itemize}

\item Mechanism provides less awareness information
\begin{itemize}
\item Linearisation of the history
\end{itemize}

\item Keep $only$ the previous revisions of the documents
\end{itemize}
\end{itemize}

  \end{frame}

%==================================================================
\subsection{Limitations of existing Solutions}
 \begin{frame}
\frametitle{Limitations of existing Solutions\\
2- Microsoft SkyDrive}

\begin{itemize}
 \item Users are forced to synchronize their documents explicitly
 \item Send the document to the server
 \item Solve conflicts manually if there were conflicting update
 \item Limitation: 
\begin{itemize}
 \item Weak awareness and no synchronous update
\end{itemize}
\end{itemize}

\begin{center}
 \includegraphics[width=4cm]{images/Microsoft-Skydrive.jpg}
\end{center}

  \end{frame}
%==================================================================
\subsection{Solution and idea}
 \begin{frame}
\frametitle{Solution and idea}

\begin{block}{Goal}
 \begin{itemize}
  \item Improve multi-synchronous collaborative editing application
  \begin{itemize}
   \item Integrate concurrency control mechanisms
   \item Keep more awareness information
  \item Respect user intentions
  \end{itemize}
\end{itemize}
\end{block}

\begin{block}{How ?}
 \begin{itemize}
  \item Propose policies for handling  conflicting operations	
  \item Offer new operations
  \begin{itemize}
  \item update and move
  \end{itemize}
  \item Verify if the policies preserve the user intention 
  %\item Propose an algorithm to improve the merge results
 \end{itemize}

\end{block}

  \end{frame}
%==================================================================
%==================================================================
%==================================================================
\section{Solution for managing Shared document}
\subsection{Conflict-free Replicated Data Types (CRDT)}
\begin{frame}
\frametitle{Conflict-free Replicated Data Types (CRDT)}
\begin{itemize}
 \item Class of distributed data type
 \item Modifications without coordination 
 \item Replica converge to the same value when all updates are propagated
 \item Two types of CRDT:
  \begin{enumerate}
   \item $Operation-based$: modifications are propagated as operations 
   \item $State-based$: modifications are propagated as states 
  \end{enumerate}
  \item $Operation-based$ CRDT more adapted to synchronous collaboration
\end{itemize}

\end{frame}

%------------------------------------------------
\subsection{System Model}
\begin{frame}
\frametitle{System Model}
\begin{itemize}
 \item Each node maintains a replica of the shared document
  \item Updates are propagated to all replica nodes
  \item Interface of document CRDT includes: insert, delete, update and move
%   \item granularity = line
  \item Updates are delivered in causal order
  \item Deployment in any architecture
% \begin{itemize}
% \item Distributed version control systems such as $git$
% \item Cloud-based  
% \end{itemize}

\end{itemize}

\begin{center}
 \includegraphics[width=6cm]{images/architecture-small.pdf}
\end{center}

\end{frame}
%==================================================================
\subsection{Policy for Handling Conflicting Operations}
\begin{frame}
\frametitle{Policy for Handling Conflicting Operations}

\begin{table}
{\centering
\small
\begin{tabular}{|c|c|c|c|c|}
\hline 
 & insert & update & delete & move \\ 
\hline 
\hline 
insert & keep two & not possible & not possible & not possible \\ 
 & elements & &  &  \\ 
 \cline{2-5}
 & highlight & - & - & - \\
 & new elems. &  &  &  \\
\hline 
\hline 
update & - & create  & delete & move the \\ 
 &  &  versions & element & updated version \\ 
 \cline{2-5}
 & - & show both & show del. & highlight \\
 &  & versions & element &  \\
\hline 
\hline 
delete & - & - & delete & delete  \\ 
 & & &  & element \\ 
 \cline{2-5}
 & - & - & nothing & show del. \\
 &  &  & needed & element \\
\hline 
\hline 
move & - & - & - & create clones \\ 
 \cline{2-5}
 & - & - & - & highlight \\
 &  & - & -  & clones \\
\hline 
\end{tabular}}
\caption{\tiny Handling of concurrent updates to the same element
and associated awareness solution}
\end{table}

\end{frame}

\subsection{Structure}
\begin{frame}
\frametitle{Structure}

\only<1>
{
\centering\includegraphics[width=10cm]{image2/structure.pdf}
 }
\only<2>
{
\centering\includegraphics[width=10cm]{image2/structure-pdt.pdf}
}
\only<3>
{
\centering\includegraphics[width=10cm]{image2/structure-mv.pdf}
}
\only<4>
{
\centering\includegraphics[width=10cm]{image2/structure-mv2.pdf}
}
\only<5>
{
\centering\includegraphics[width=10cm]{image2/structure-del.pdf}
}

\end{frame}
%==================================================================

% \subsection{Document Specification}
% \begin{frame}
% \frametitle{Document Specification}
% 
% \begin{itemize}
%  \item Consider 4 operations: insert, delete, update and move
%  \item granularity = line
%  \item Transform each operation into 4-tuple: \\
% (oldPosition, oldValue, newPosition, newValue)
% \begin{itemize}
% \item POS $\rightarrow$ (id, position)
% \item VAL $\rightarrow$ ((id, ts), value)
% \end{itemize}
% \item Insert $\rightarrow$ new position and new value
% \item Delete $\rightarrow$ remove position and all the existing value
% \item Update $\rightarrow$ new value and remove the existing one
% \item Move $\rightarrow$ new position and remove the old one
% \item Document is an ordered list of visible position
% \item Position is visible if it is associated to at least one value
% \end{itemize}
% 
% \end{frame}

%==================================================================
%==================================================================
%==================================================================
\section{Evaluation}

\subsection{Evaluation Method}
\begin{frame}
\frametitle{Evaluation Method}
\begin{itemize}
\item Replays the history of Git repositories
  \begin{itemize}
  \item By different op-based algorithms
  \end{itemize}
\item Transforms the state of the document to the set of operations
\item Detects update and move operations
\item Compare the number of modifications using our solution and another
op-based algorithm
\end{itemize}

\end{frame}


\subsection{Operation Detection}
\begin{frame}
\frametitle{Operation Detection}
\begin{itemize}
 \item Compute distance of editions $\delta_{i,j}$ for each line
  \item Define Threshold Update ($Tu$) and Threshold Move($Tm$)
 \begin{itemize}
  \item $\delta_{i,j}<$Tu $\rightarrow$ update operation
  \item $\delta_{i,j}<$Tm $\rightarrow$ move operation
  \end{itemize}

\includegraphics[width=11cm]{images/operation-detection.pdf}
\end{itemize}

\end{frame}

\subsection{Experiment}
\begin{frame}
\frametitle{Experiment}
\begin{itemize}
 \item Estimate the adequate $Tu$ and $Tm$
\begin{enumerate}
 \item Execute the algorithm in git/git repository
 \item Vary (Tu, Tm) from 0\% to 100\% in steps of 10\% 
\end{enumerate}
  \item Compute the difference between user merges and automated merges
computed by our algorithm 
  \item Treedoc\footnote{Nuno P et al. A Commutative Replicated Data Type for
Cooperative Editing} is used as reference and compared with move/update
algorithm 
\end{itemize}

\end{frame}

\subsection{Results}
\begin{frame}

\begin{columns}[t]
  \begin{column}{6cm}
   \includegraphics[width=6cm]{images/treedoc2.pdf}
  \end{column}

\begin{column}{6cm}
   \includegraphics[width=6cm]{images/move2.pdf}
  \end{column}
\end{columns}


\begin{itemize}
 \item Best performance is obtained with Tu=0.9 and Tm=0.2 
 \item Gain is 18\% in git/git repository 
 \item More results, see the paper !
\end{itemize}

\frametitle{Results}
\end{frame}


%==================================================================
\section{Conclusion and perspectives}

\subsection{Conclusion and perspectives}
\begin{frame}
\frametitle{Conclusion and perspectives}

\begin{block}{Conclusion}
 \begin{itemize}
 \item Solution for supporting multi-synchronous
collaborative editing
\item Extend the traditional interface of document
\begin{itemize}
\item Different granularity
\item Support move and update operations 
\end{itemize}
\item Keep more awareness information than traditional applications
 \end{itemize}
\end{block}

\begin{block}{Perspectives}
 \begin{itemize}
  \item Introduce undo/redo mechanism
  \item Integrate our algorithm in a cloud-based web editing
tool that supports geo-replication.
 \end{itemize}

\end{block}
\end{frame}

\subsection{}
\begin{frame}
\frametitle{}
\begin{center}
 {Thank you for your attention}
\end{center}


\end{frame}

% End of slides
\end{document} 