\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\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 et mesures de disponibilité 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}

\AtBeginSection[]
{
\begin{frame}
\frametitle{Plan}
\tableofcontents[currentsection]
\end{frame}
}


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

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

\section{Cadre d'étude}
\begin{frame}{Réseau}

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éconnexion
\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}{Disponibilité}
\begin{block}{Définition : \alert{disponibilité}}
Fraction du temps passé par le pair sur le réseau.
\end{block}
\vfill
\alert{Quelle utilité ?}
\begin{itemize}
\item<2-> structurer le réseau, super-pairs
\item<3-> prédire le comportement futur
\item<4-> obliger les pairs à coopérer (donnant-donnant)
\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}

\begin{frame}{Objectif}
\alert{Protocole} :
\begin{itemize}
\item décentralisé : nécessaire pour le passage à l'échelle
\item résistant à la collusion
\item simple (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}

\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 La preuve est fournie plus tard à la demande
\end{itemize}
Fonctionement 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 décentralisation
\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}{Fonctionnement}
\begin{columns}[t]

\begin{column}{0.4\textwidth}
\textbf{Phase 1 : Semaille}

$1$ choisit un secret $S$ et le diffuse.
\end{column}

\begin{column}{0.55\textwidth}

À FAIRE

%\begin{tikzpicture}
%\matrix [nodes=draw,circle,ampersand replacement=\&,row sep=1cm]
%{
%\node (a) {1}; \\
%\node (b) {2}; \\
%\node (c) {3}; \\
%};
%\draw [->] (a.south);
%\end{tikzpicture}

\end{column}
\end{columns}
\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}

\section{Résultats}

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

\begin{frame}{Simulation}
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->
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}
\onslide<3->
Structure 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}
\onslide<4->
\begin{block}{}
$\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\ldots
\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 structure du réseau 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 jusqu'à 40\,000 nœuds
\item au-delà ? l'instabilité du réseau pénalise les pairs éloignés
\end{itemize}
\alert{Solution :} utiliser plusieurs serveurs
\onslide<2->
\vfill
Application : 
\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}
\onslide<3->

\begin{block}{}
$\Rightarrow$ Certification temporelle de documents (brevets)
\end{block}

\end{frame}
\end{document}