Diagrams showing the functioning of the protocol

git-svn-id: https://scm.gforge.inria.fr/svn/pacemaker@77 30fcff6e-8de6-41c7-acce-77ff6d1dd07b

1 files changed, 104 insertions, 61 deletions

diff --git a/stage/slides.tex b/stage/slides.tex
index 4ce1f2d..6efd99a 100644
--- a/stage/slides.tex
+++ b/stage/slides.tex
@@ -1,6 +1,8 @@
 \documentclass{beamer}
 \usepackage[utf8]{inputenc}
 \usepackage[french]{babel}
+\usepackage[T1]{fontenc}
+\usepackage{lmodern}
 \usepackage{amsmath}
 \usepackage{graphicx}
 \usepackage{tikz}
@@ -40,7 +42,7 @@ Fraction du temps passé par le pair sur le réseau.
 \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)
+\item<4-> inciter les pairs à coopérer
 \end{itemize}
 \item<5-> Horodatage de documents (brevets)
 \end{enumerate}
@@ -51,7 +53,7 @@ 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, perte de paquets
+\item pannes, déconnexions, perte de paquets
 \item potentiellement beaucoup d'utilisateurs
 \end{itemize}
 \vfill
@@ -62,32 +64,32 @@ On suppose donné un \alert{réseau} :
 \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
+%\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}
 
-\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}
+%\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}
 
@@ -126,34 +128,75 @@ Fonctionnement par \alert{ronde} :
 \end{frame}
 
 \begin{frame}[fragile]{Fonctionnement}
-\begin{columns}[t]
+\begin{columns}
 
-\begin{column}{0.4\textwidth}
-\textbf{Phase 1 : Semaille}
+\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}
+}
 
-$1$ choisit un secret $S$ et le diffuse.
+\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,nodes=draw,circle,row sep=1cm](mesh) at (0,0)
+\node[matrix,circle,row sep=1cm](mesh) at (0,0)
 {
-\node (1) {1}; \\
-\node (2) {2}; \\
-\node (3) {3}; \\
+\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);
-\onslide<2->\draw (2) -- (3);
+\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}{Fonctionnement (suite)}
+%À FAIRE
+%\end{frame}
 
 \begin{frame}[fragile]{Spécification}
 \begin{columns}[t]
@@ -259,21 +302,21 @@ end if
 \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}{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}
 
@@ -289,9 +332,9 @@ end if
 \end{frame}
 \section{Résultats}
 
-\begin{frame}{Non falsifiabilité}
-À FAIRE
-\end{frame}
+%\begin{frame}{Non falsifiabilité}
+%À FAIRE
+%\end{frame}
 
 \begin{frame}{Simulateur}
 Fonctionnement par étapes. À chaque étape :
@@ -314,7 +357,7 @@ 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
+%\item on stoppe la recherche à \alert{8} voisins
 \end{itemize}
 
 On fait tourner sur le simulateur :
@@ -322,7 +365,7 @@ On fait tourner sur le simulateur :
 \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}
@@ -348,8 +391,8 @@ simulateur + pacemaker + topologie $\simeq$ \alert{800} lignes en OCaml
 En pratique :
 \begin{itemize}
 \item \alert{167} ordinateurs à travers le monde
-\item machines surchargées (virtualisation)
-\item perte de nombreux paquets réseaux
+%\item machines surchargées (virtualisation)
+%\item perte de nombreux paquets réseaux
 \end{itemize}
 \onslide<3->
 Implémentation :