\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{tikz}
\usetheme{Boadilla}
\usecolortheme{beaver}
\usepackage{listings}
\lstdefinelanguage{pseudo}
  {morekeywords={if, then, else, end, let, and, or, for, in, while}}
\lstset{escapechar=?, mathescape=true, language=pseudo, basicstyle=\tiny, keywordstyle=\bfseries}
\renewcommand{\lstlistingname}{Spec.}



\title[Pacemaker]{Pacemaker : preuves de présence dans les réseaux pair-à-pair}
\author{Thibaut Horel}
\institute[stage INRIA Saclay]{Stage de MPRI sous la direction de Fabrice Le Fessant}
\setbeamercovered{transparent}
\begin{document}

\begin{frame}
\maketitle
\end{frame}

\begin{frame}{Plan}
\tableofcontents
\end{frame}

\section{Cadre d'étude}

\begin{frame}{Objectifs}
\begin{enumerate}
\item Disponibilité
\begin{block}{Définition}
Fraction du temps passé par le pair sur le réseau.
\end{block}
\alert{Quelle utilité ?}
\begin{itemize}
\item<2-> structurer le réseau, super-pairs
\item<3-> prédire le comportement futur
\item<4-> inciter les pairs à coopérer
\end{itemize}
\item<5-> Horodatage de documents (brevets)
\end{enumerate}
\end{frame}

\begin{frame}{Hypothèses}
On suppose donné un \alert{réseau} :
\begin{itemize}
\item pair-à-pair, connaissance partielle
\item asynchrone, communication de nœud à nœud  
\item pannes, déconnexions, perte de paquets
\item potentiellement beaucoup d'utilisateurs
\end{itemize}
\vfill
\alert{Sécurité} :
\begin{itemize}
\item communications sûres,  cryptographie asymétrique
\item les pairs n'échangent pas leur clé privée
\end{itemize}
\end{frame}

%\begin{frame}{Critères}
%\alert{Protocole} :
%\begin{itemize}
%\item passage à l'échelle
%\item résistant à la collusion
%\item peu coûteux (bande passante, calcul)
%\end{itemize}
%
%\vfill
%
%\alert{Information} :
%\begin{itemize}
%\item précise
%\item non-falsifiable
%\item durable dans le temps
%\end{itemize}
%\end{frame}

%\begin{frame}{Disponibilité : profil}
%\begin{center}
%\begin{figure}
%\includegraphics[scale=0.42]{avail.eps}
%\caption{Répartition de la disponibilité de 1469 pairs sur Overnet}
%\end{figure}
%\end{center}
%\end{frame}

\section{Le protocole}

\begin{frame}{Principe}
Système de \alert{preuve} :
\begin{itemize}
\item Le pair reçoit une preuve de sa présence et la stocke
\item Le pair peut fournit la preuve ultérieurement
\end{itemize}
Fonctionnement par \alert{ronde} :
\begin{itemize}
\item Le pair reçoit une preuve à intervalles réguliers
\item La preuve certifie la présence au cours de la ronde
\item Un pair particulier : le \alert{serveur}, pour initier la ronde
\end{itemize}
\begin{columns}

\begin{column}{0.45\textwidth}
\begin{block}{Avantages}<2->
\begin{itemize}
\item passage à l'échelle
\item durabilité temporelle
\end{itemize}
\end{block}
\end{column}

\begin{column}{0.45\textwidth}
\begin{block}{Attention}<3->
\begin{itemize}
\item collusion
\item falsification
\end{itemize}
\end{block}
\end{column}
\end{columns}
\end{frame}

\begin{frame}[fragile]{Fonctionnement}
\begin{columns}

\begin{column}{0.44\textwidth}
\only<1-4>{\textbf{Phase 1 : Semaille}
\begin{itemize}
\item<2-> $1$ choisit et diffuse une graine $S$
\item<3-> $i$ calcule H$_i$ = hash(sign(S,K$_i$))
\end{itemize}
}

\only<5-11>{\textbf{Phase 2 : Récolte}
\begin{itemize}
\item À intervalle régulier, chaque pair :
\begin{itemize}
\item hache son tableau
\item le transmet à ses voisins
\end{itemize}
\item<7-11> À la réception : on stocke
\end{itemize}
}

\only<12->{
\textbf{Phase 3 : Pulsation}
\begin{itemize}
\item la racine signe le hash de son tableau : S$_{pulse}$
\item transmission de la pulsation et du tableau
\end{itemize}
}
\end{column}

\begin{column}{0.55\textwidth}

\begin{tikzpicture}
\node[matrix,circle,row sep=1cm](mesh) at (0,0)
{
\node[draw,double] (1) {1}; &[0.5cm] \visible<7-10>{\node[draw,rectangle]{\alert<7>{H$^{'}_2$}};}\visible<11->{\node[draw,rectangle]{\alert<11>{H$^{''}_2$}};} &&[0.5cm] \visible<12>{\node{\alert{S$_{pulse}$}};}\\
\node[draw] (2) {2}; &[0.5cm] \visible<3->{\node[draw,rectangle,minimum height=0.72cm] {H$_2$};}& \visible<9->{\node[draw,rectangle]{\alert<9>{H$^{'}_3$}};}&[0.5cm] \visible<6-9>{\node{H$^{'}_2$};} \visible<10->{\node{\alert<10>{H$^{''}_2$}};}\\
\node[draw] (3) {3}; &[0.5cm] \visible<4->{\node[draw,rectangle,minimum height=0.72cm] {H$_3$};}& \visible<7-10>{\node[draw,rectangle]{\alert<7>{H$^{'}_2$}};}\visible<11->{\node[draw,rectangle]{\alert<11>{H$^{''}_2$}};} &[0.5cm]\visible<8->{\node{\alert<8>{H$^{'}_3$}};}\\
};
\draw (1) -- (2);
\draw (2) -- (3);
\visible<2-3>{\draw (1) to[bend left,->] (2) node[midway,right] {S};}
\visible<4>{\draw (2) to[bend left,->] (3) node[midway,right] {S};}
\visible<6-7>{
\draw (2) to[bend left,->] (3) node[midway,right] {H$^{'}_2$};
\draw (2) to[bend right,->] (1) node[midway,right] {H$^{'}_2$};
}
\visible<8-9>
{
\draw (3) to[bend right,->] (2) node[midway,right] {\alert<8>{H$^{'}_3$}};
}
\visible<10-11>
{
\draw (2) to[bend left,->] (3) node[midway,right] {H$^{''}_2$};
\draw (2) to[bend right,->] (1) node[midway,right] {H$^{''}_2$};
}
\visible<12>
{
\draw (1) to[bend left,->] (2) node[midway, right] {\alert{S$_{pulse}$}};
}
\end{tikzpicture}

\end{column}
\end{columns}
\end{frame}

%\begin{frame}{Fonctionnement (suite)}
%À FAIRE
%\end{frame}

\begin{frame}[fragile]{Spécification}
\begin{columns}[t]
\begin{column}{0.48\textwidth}

\begin{block}{\tiny{Serveur au début de la ronde $i$}}
\begin{lstlisting}
  let phase$^i$ = SEEDING;
  let seed$^i$ = random_seed();
  let S$^i_{seed}$ = sign($\langle$$i$|seed$^i$|$T^i$$\rangle$, KS$_{priv}$);
  let M$^i_{seed}$ = Seed($i$, seed$^i$, $T^i$, S$^i_{seed}$);
  let map$^i$ = $\emptyset$;
  $\forall q \in$ NS$_{server}$, send($q$, M$^i_{seed}$);

  wait $T^i$;
\end{lstlisting}
\end{block}

\begin{block}{\tiny{Toutes les $\Delta << T^i$ secondes chez le pair $p$}}
\begin{lstlisting}
  if phase$^i$ = SEEDING then
    let H$^i$ = hash(map$^i$);
    let M$^i_{seedreply}$ = SeedReply($i$, H$^i$);
    nreplies$^i$ = nreplies$^i+1$;
    replies$^i$[nreplies$^i$] = (H$^i$, map$^i$);
    $\forall q \in$ NS$_p$, send($q$, M$^i_{seedreply}$);    
  end if
\end{lstlisting}
\end{block}
\end{column}

\begin{column}{0.48\textwidth}
\begin{block}{\tiny{Pair $p$ à la réception de \textsf{Seed($i$, seed$^i$, $T^i$, S$^i_{seed}$)}}}
\begin{lstlisting}
  if
    verify(S$^i_{seed}$, $\langle$$i$|seed$^i$|$T^i$$\rangle$, KS$_{pub}$)
  then
    $\forall q \in$ NS$_p$, send($q$, M$^i_{seed}$);    
    let S$^i_p$ = sign($\langle$$i$|seed$^i$$\rangle$, K$^p_{priv}$);
    let map$^i$ = {$p \rightarrow$hash(S$^i_p$)};
    let nreplies$^i$ = 0;
    let replies$^i$ = $\emptyset$;
    let included$^i$ = $\bot$;
    let duration$^i$ = $T^i$;
    let phase$^i$ = SEEDING;
  end if
\end{lstlisting}
\end{block}

\begin{block}{\tiny{Réception de \textsf{SeedReply($i$, X$_q$)} depuis le pair $q$}}
\begin{lstlisting}
  if phase$^i$ = SEEDING then
    map$^i$ = $\{ q \rightarrow $X$_q \} \oplus$map$^i$;
  end if
\end{lstlisting}
\end{block}
\end{column}
\end{columns}
\end{frame}

\begin{frame}[fragile]{Spécification (suite)}
\begin{columns}[t]
\begin{column}{0.43\textwidth}
\begin{block}{\tiny{Serveur après avoir attendu pendant $T^i$}}
\begin{lstlisting}
phase$^i$ = PULSE;
let H$^i$ = hash(map$^i$);
let branch$^i$ = $\emptyset$;
branch$^i$[0] = map$^i$;
let S$^i_{pulse}$ = sign($\langle$$i$|seed$^i$|H$^i$$\rangle$, KS$_{priv}$);
let M$^i_{pulse}$ = Pulse($i$,seed$^i$,branch$^i$,S$^i_{pulse}$); 
$\forall q \in$ NS$_{server}$, send($q$, M$^i_{pulse}$);
\end{lstlisting}
\end{block}
\end{column}

\begin{column}{0.54\textwidth}
\begin{block}{\tiny{Réception de \textsf{Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$)}}}
\begin{lstlisting}
if 
  verify(S$^i_{pulse}$,$\langle$$i$|seed$^i$|hash(branch$^i$[0])$\rangle$,KS$_{pub}$) and
  phase$^i$ = SEEDING or phase$^i$ = PULSE  
then
   phase$^i$ = PULSE;
   let level = length(branch$^i$)-1;
   if
     $\exists$ {$p$ $\rightarrow$ H$^i$} $\in$ branch$^i$[level] and
     $\exists\; n\; |$replies[$n$] = (H$^i$, oldmap$^i$) and
     included$^i < n$ and
     $\forall n\in$[1..level],hash(branch$^i$[n])$\in$branch$^i$[n-1]
   then
     branch$^i$[level+1] = oldmap$^i$;
     let M$^i_{pulse}$ = Pulse($i$, seed$^i$, branch'$^i$, S$^i_{pulse}$);
     History[$i$] = ($i$, seed$^i$, branch'$^i$, S$^i_p$, S$^i_{pulse}$);
     included$^i$ = $n$;
     $\forall q \in$ NS$_p$, send($q$, M$^i_{pulse}$);
  end if
end if
\end{lstlisting}

\end{block}
\end{column}
\end{columns}
\end{frame}

%\begin{frame}{Utilisation du protocole}
%\begin{itemize}
%\item mesure de disponibilité :
%\begin{itemize}
%\item chaque pair garde l'historique des preuves reçues
%\item système de requête/réponse pour contrôler les pairs
%\end{itemize}
%\vfill
%\item horodatage :
%\begin{itemize}
%\item on prouve la présence sur le réseau en ajoutant un nœud dans un arbre
%\item le nœud peut également contenir des informations ! 
%\end{itemize}
%\end{itemize}
%\end{frame}

\begin{frame}{Étude du protocole}

\begin{itemize}
\item Non falsifiabilité
\vfill
\item Précision et passage à l'échelle
\begin{itemize}
\item simulation
\item déploiement sur un réseau réel
\end{itemize}
\end{itemize}
\end{frame}
\section{Résultats}

%\begin{frame}{Non falsifiabilité}
%À FAIRE
%\end{frame}

\begin{frame}{Simulateur}
Fonctionnement par étapes. À chaque étape :
\begin{itemize}
\item connexions et déconnexions des pairs
\item réception et envoi des messages
\end{itemize}
\onslide<2->
\vfill
Approximation de l'asynchronisme :
\begin{itemize}
\item ordre d'exécution aléatoire
\item délai d'une étape entre l'envoi et la réception
\item une étape représente 30 secondes de temps réel
\end{itemize}
\end{frame}

\begin{frame}{Obtention de la topologie du réseau}
Topologie du réseau, selon les applications. \alert{Ici} :
\begin{itemize}
\item degré constant égal à \alert{10}
\item recherche de voisins depuis la racine en descendant progressivement
%\item on stoppe la recherche à \alert{8} voisins
\end{itemize}

On fait tourner sur le simulateur :
\begin{itemize}
\item le protocole pacemaker
\item le protocole de construction de la topologie
\end{itemize}
\onslide<2->
\begin{block}{}
simulateur + pacemaker + topologie $\simeq$ \alert{800} lignes en OCaml
\end{block}
\end{frame}

\begin{frame}{Simulation (résultats)}
\begin{center}
\begin{figure}
\includegraphics[scale=0.42]{test.eps}
\caption{Fonction de répartition de l'erreur relative (40\,000 nœuds, 10 jours)}
\end{figure}
\end{center}
\end{frame}

\begin{frame}{PlanetLab}
\begin{center}
\includegraphics[scale=0.2]{logo.eps}
\end{center}
\begin{block}{}
``PlanetLab is a group of computers available as a testbed for computer networking and distributed systems research.''
\end{block}
\onslide<2->
En pratique :
\begin{itemize}
\item \alert{167} ordinateurs à travers le monde
%\item machines surchargées (virtualisation)
%\item perte de nombreux paquets réseaux
\end{itemize}
\onslide<3->
Implémentation :
\begin{itemize}
\item sans la cryptographie asymétrique
\item communication en UDP
\item même topologie que dans le simulateur
\end{itemize}

\onslide<4->
\begin{block}{}
$\simeq$ \alert{800} lignes en OCaml
\end{block}
\end{frame}

\begin{frame}{PlanetLab (résultats)}
\begin{center}
\begin{figure}
\includegraphics[scale=0.42]{pl.eps}
\caption{Fonction de répartition de l'erreur relative (167 nœuds, 1 mois)}
\end{figure}
\end{center}
\end{frame}
\section*{Conclusion}

\begin{frame}{Conclusion}
Robustesse :
\begin{itemize}
\item testé jusqu'à 40\,000 nœuds
\item l'instabilité pourrait pénaliser les pairs éloignés
\end{itemize}
\alert{Solution :} utiliser plusieurs serveurs
\onslide<2->
\vfill
Perspectives : 
\begin{itemize}
\item essayer d'autres topologies (Chord, \ldots)
\item tester le protocole sur un réseau réel
\item empêcher la racine de réécrire l'histoire en chaînant les graines
\end{itemize}


\end{frame}
\end{document}