Titre : Calcul à grande échelle

Responsable(s) : C. Delporte-Gallet, H. Fauconnier

URL : cd

URL : hf

Nombre d’étudiants: 3

Descriptif : Sur des réseaux comme Internet de très nombreux sites sont connectés et n’utilisent pas leurs ressources, l’idée du calcul à grande échelle consiste à utiliser ces ressources pour effectuer des calculs complexes. De cette façon, plusieurs milliers voire plusieurs dizaines de milliers de sites sont amenés à coopérer pour ces calculs. Plusieurs systèmes de ce type sont actuellement en cours de développement.

De nombreux problèmes nouveaux se posent : déconnexions intempestives, problème d’échelle, sécurité, etc…

Le but de ce stage est de faire une étude sur ce sujet en commençant par faire un état des divers projets actuels de calcul à grande échelle et ensuite de déterminer dans quelle mesure le changement d’ordre de grandeur d’échelle changent les problèmes classiques d’algorithmique distribuée et parallèle.

Titre : Réseaux pair à pair (P2P)

Responsable(s) : C. Delporte-Gallet, H. Fauconnier

E-Mail : cd@liafa.jussieu.fr

E-Mail : hf@liafa.jussieu.fr

URL : cd

URL : hf

Nombre étudiants: 3

Descriptif : Contrairement au modèle client serveur classique, le modèle pair à pair permet un échange direct d’informations entre sites. De cette façon les sites peuvent partager leurs ressources. Les réseaux pair à pair ont connu de nombreux développements récents en particulier avec Kazaa , Napster, Gnutella ou autres.

Il s’agit pour ce stage de choisir un type de réseau pair à pair et d’étudier précisément son fonctionnement et de déterminer quels nouveaux problèmes ce type de réseaux pose. On pourra compléter cette étude par une tentative de classification de ces types de réseaux.

Titre : Table de Hachage Distribuée

Responsable(s) : C. Delporte-Gallet, H. Fauconnier

E-Mail : cd@liafa.jussieu.fr

E-Mail : hf@liafa.jussieu.fr

URL : cd

URL : hf

Nombre étudiants: 3

Descriptif : Dans un réseau pair à pair un problème important est de déterminer où se trouve l’information : si vous cherchez la dernière chanson de Madonna sur Kazaa, Kazaa vous fournit divers sites sur lesquels vous pouvez télécharger cette chanson. Sachant qu’il y a plusieurs centaines de milliers de site, il faut pouvoir faire cette recherche de façon efficace. Une solution pour cela est d’utiliser des tables de hachages distribuées.

Il existe plusieurs réalisations de ce type de tables. Le travail du stage sera de les étudier d’un point de vue théorique mais aussi de déterminer quelles méthodes sont utilisées dans les systèmes pair à pair.

Titre : Détecteurs de défaillances et surveillance réseau

Responsable(s) : C. Delporte-Gallet, H. Fauconnier

E-Mail : cd@liafa.jussieu.fr

E-Mail : hf@liafa.jussieu.fr

URL : cd

URL : hf

Nombre d'étudiants: 3

Descriptif : Pour ce stage, il s'agit de réaliser un service de détection de pannes dans un réseau. Ce service doit fournir aux processus qui le demandent des informations sur les éventuelles défaillances des autres processus.

Un travail théorique important existe concernant ce domaine avec, en particulier, une étude quantitative des performances de ce service.

Il existe déjà des implémentations de ce genre de service, le travail du stage sera (1) d'adapter ces implémentations et (2) de définir une console graphique qui permette de surveiller les divers processeurs.

Titre: Election ultime de leader en présence de pannes (1)

Responsable(s) : C. Delporte-Gallet, H. Fauconnier

E-Mail : cd@liafa.jussieu.fr

E-Mail : hf@liafa.jussieu.fr

URL : cd

URL : hf

Nombre d'étudiants: 3

Descriptif :

Dans une élection ultime de leader, tous les processus doivent de façon ultime se mettre d'accord sur l'identité d'un leader. Ce problème, simple s'il n'y a pas de pannes de processus, devient beaucoup plus difficile si certains processus peuvent tomber en pannes. Il s'agit  ici d'implémenter un algorithme récent d’élection de leader ultime

Ce stage devra implémenter cette élection de leader ultime en utilisant des détecteurs de défaillances qui seront fournis mais qui devront être adaptés localement.

Ce stage peut être complété par une étude des performances de l'algorithme réalisé.

Titre : Election de leader ultime (2)

Responsable(s) : C. Delporte-Gallet, H. Fauconnier

E-Mail : cd@liafa.jussieu.fr

E-Mail : hf@liafa.jussieu.fr

URL : cd

URL : hf

Nombre étudiants: 3

Descriptif :

Le sujet est identique au précédent mais au lieu d'utiliser des détecteurs de défaillances déjà implémentés, elle utilisera une implémentation directe (on utilisera deux algorithmes différents reposant sur des conditions différentes sur le système sous-jacent).

Titre : Groupe des processus corrects

Responsable(s) : C. Delporte-Gallet, H. Fauconnier

E-Mail : cd@liafa.jussieu.fr

E-Mail : hf@liafa.jussieu.fr

URL : cd

URL : hf

Nombre étudiants: 3

Descriptif : Le problème est ici d’implémenter un service distribué qui fournit à chaque processus la liste exacte (de façon ultime) des processus qui sont définitivement sans pannes.

Une solution directe et une solution basée sur une élection de leader sont demandées.

Titre : protocoles Zero-knowledge

Responsable(s) : C. Delporte-Gallet, H. Fauconnier

E-Mail : cd@liafa.jussieu.fr

E-Mail : hf@liafa.jussieu.fr

URL : cd

URL : hf

Nombre étudiants: 1 à 4

Descriptif :

Etude des principes et des protocoles "zero-knowledge". Ces protocoles servent en cryptographie. Le principe en est que durant le protocole aucune information ne doit être révélée.

Plus précisément, dans un protocole de ce type, il s'agit pour P (le prouveur) de prouver qu'il connaît un secret et  pour V (le vérificateur) de vérifier que P a bien ce secret. Dans la vérification, V ne doit rien apprendre sur le secret  lui-même (même s'il essaie de tricher), P ne doit pas pouvoir faire croire qu'il connaît  le secret si ce n'est pas le cas,  et V ne peut pas prétendre être P.

Le principal travail consiste en une recherche bibliographique et une synthèse.  Ce stage peut donner lieu à une implémentation.