Introduction

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

1 files changed, 35 insertions, 20 deletions

diff --git a/stage/article.tex b/stage/article.tex
index cb6fb18..f11d190 100644
--- a/stage/article.tex
+++ b/stage/article.tex
@@ -16,48 +16,63 @@ basicstyle=\small, keywordstyle=\bfseries, captionpos=b}
 \theoremstyle{remark}
 \newtheorem*{rem}{Remark}
 
-\title{Pacemaker}
-
+\title{Pacemaker : un protocole de mesure de disponibilité dans les réseaux pair-à-pair}
+\date{Sujet proposé et supervisé par Fabrice Le Fessant}
 \begin{document}
 
 \maketitle
 
 \section{Introduction}
-Tous les réseaux pair-à-pair ont en commun d'avoir un dynamique complexe : naissances, morts, arrivées, départs, indisponibilité temporaires peuvent survenir à tout instant. Ainsi, la \emph{disponibilité} d'un noeud est une caractérisitique importante pour déterminer l'impact d'un nœud sur le réseau. La \emph{disponibilité} d'un nœud est définie comme étant la fraction du temps passée par le nœud sur le réseau.
+Tous les réseaux pair-à-pair ont en commun d'avoir un dynamique complexe : naissances, morts, arrivées, départs, indisponibilité temporaires peuvent survenir à tout instant. Ainsi, la \emph{disponibilité} d'un nœud, c'est à dire la fraction du temps passée par ce nœud sur le réseau, est une propriété importante pour déterminer l'impact de ce nœud sur le réseau.
 
-C'est pourquoi de nombreux protocoles de réseaux pair-à-pair s'appuient sur la disponibilité des nœuds. Deux utilisations différentes de cette information sont à distinguer:
+C'est pourquoi de nombreux protocoles de réseaux pair-à-pair s'appuient sur la disponibilité des nœuds. Deux utilisations différentes de cette information sont à distinguer :
 \begin{itemize}
 \item la structuration du réseau, ou bien par l'élection de super-peer (cf. ...) ou dans la sélection des voisins (cf. backup)
 \item assurer une plus grande justice dans la répartition d'un service : faire en sorte que les gens qui ont la plus grande disponibilité aient plus d'avantages sur le réseau.
 \end{itemize}
 
-Malheureusement, la plupart de ces stratégies s'appuyant sur la disponibilité s'appuient sur un oracle qui leur fournirait cette information. Il existe deux approches fondamentalement opposées pour construire un tel oracle
+Malheureusement, la plupart de ces stratégies supposent donné un oracle qui fournirait cette information de disponibilité. Plusieurs approches permettent d'obtenir cet orcale :
+\begin{itemize}
+\item de façon individuelle : chaque nœud est en charge de surveiller et de stocker sa propre disponibilité
+\item l'évaluation par les pairs : à chaque nœud est associé un ensemble de pairs chargés de surveiller sa disponibilité
+\item de façon centralisée : un nœud s'occupant de surveiller le réseau et de stocker la disponibilité de l'ensemble des nœuds du réseau
+\end{itemize}
+Chacune de ces approches présente une limite manifeste :
 \begin{itemize}
-\item de façon centralisée
-\item peer-review
+\item l'approche individuelle autorise les nœuds à mentir sur leur propre disponibilité, pour obtenir par exemple plus d'avantages sur le réseau. Ceci met donc en défaut une des principales utilisation de l'information de disponibilité.
+\item l'évaluation par les pairs résout le problème de passage à l'échelle, mais est très sensible à la collusion : des groupes de nœuds peuvent choisir de coopérer en se choisissant mutuellement comme évaluateurs et ainsi mentir collectivement sur leur disponibilité. Le protocole AVMON qui utilise ce procédé contourne le problème de la collusion en imposant que les évaluateurs soient choisis de façon semi-aléatoire, mais cette méthode impose malheureusement une limite inférieure sur la taille du réseau. De plus, l'évluation par les pairs n'assure pas la durabilité des informations de disponibilités : l'ensemble des mes évaluateurs à un instant donné sera-t-il toujours présent sur le réseau dans plusieurs mois ?
+\item l'approche centralisée n'est pas passable à l'échelle : quand le nombre de pairs dans le réseau devient trop grand, le nœud en charge de la surveillance ne peut ni garder une vision globale du réseau ni répondre à toutes les requêtes de pairs cherchant à s'informer sur la disponibilité d'autres pairs.
 \end{itemize}
-Chacune de ces deux approches présente un défaut, 
 
+Le but du présent rapport est donc de présenter et d'étudier le protocole \emph{Pacemaker}\footnote{Le nom provient du fonctionnement du protocole ; celui-ci est basé sur la propagation de pulsations dans le réseau, présentant ainsi une certaine analogie avec les stimulateurs cardiaques.}. Le protocole devra assurer les propriétés suivantes :
+\begin{itemize}
+\item \textbf{passage à l'échelle :} la complexité temporelle et spatiale doit être au plus logarithmique en le nombre de nœuds du réseau
+\item \textbf{précision :} l'erreur entre la disponibilité mesurée par le protocole et la disponibilité réelle doit être négligeable
+\item \textbf{non falsifiabilité :} un pair ne doit pas pouvoir mentir au sujet de sa propre disponibilité
+\item \textbf{résistance à la collusion :} les pairs ne doivent pas pouvoir coopérer pour mentir sur leur disponibilité
+\item \textbf{faible impact sur le réseau :} la quantité de données échangées sur le réseau doit être limitée
+\item \textbf{répartition de charge :} le travail effectué par le protocole est réparti de façon homogène sur le réseau
+\item \textbf{durabilité temporelle :} l'historique de disponibilité d'un nœud doit être préservé dans le temps
+\end{itemize}
+
+La section 2. présente le modèle et les hypothèses sur lesquels repose Pacemaker, la section 3. contient la spéficiation complète du protocole, les sections suivantes s'attachent à l'analyse théorique et expérimentale du protocole, à travers une simulation et un déploiement sur PlanetLab\footnote{PlanetLab est un réseau constitués d'ordinateurs fournis par diverses entreprises et universités à travers le monde et mis à la disposition de l'ensemble des membres du réseau.}.
 
+\section{Modèle et notations}
 
-\section{Model}
+\subsection{Réseau}
 
-\section{Protocol}
 
-\subsection{Assumptions and notations}
 
-It is assumed that each peer $p$ has a pair of public/private key
-\textsf{(K$^p_{pub}$, K$^p_{priv}$)} and has access to the 3
-following cryptographic primitives:
+\subsection{Cryptographie}
+On suppose que chaque pair $p$ possède une pair de clé publique/privée \textsf{(K$^p_{pub}$, K$^p_{priv}$)} donnant accés aux primitives cryptographiques suivantes : 
 \begin{itemize}
- \item{\sf sign(data, K$_{priv}$):} Returns a signature for \textsf{data} 
- using the private key \textsf{K$_{priv}$}.
- \item{\sf verify(S, data, K$_{pub}$):} Verifies that \textsf{S} is a
- signature for \textsf{data} that was created using the private key
- \textsf{K$_{priv}$} associated with \textsf{K$_{pub}$}.
- \item{\sf hash(data):} Returns the hash of \textsf{data}.
+ \item{\sf sign(data, K$_{priv}$) :} renvoie une signature pour \textsf{data} en utilisant la clé privée \textsf{K$_{priv}$}.
+ \item{\sf verify(S, data, K$_{pub}$) :} vérifie que \textsf{S} est une signature pour \textsf{data} créée avec la clé privée \textsf{K$_{priv}$} associée à la clé publique \textsf{K$_{pub}$}.
+ \item{\sf hash(data) :} renvoie un hash de \textsf{data}.
 \end{itemize}
 
+On considére donc que les pairs connaissent toujours l'expéditeur des messages qu'ils recoivent, ceux-ci étant identifiés de façon unique par leur clé publique. Les attaques cryptographiques usuelles ne sont pas étudiées ici, et les primitives ci-dessus sont considérés comme sûres. De même. la fonction de hachage ci-dessus est considérée comme résistante aux attaques par collision (au moins sur la durée caractéristique d'utilisation du protocole).
+
 The key pair of the server will be denoted by \textsf{(KS$_{pub}$,
 KS$_{priv}$)}. \textsf{KS$_{pub}$} is assumed to be known by every peer.