logo EDITE Samuel BERNARD
Identité
Samuel BERNARD
État académique
Thèse soutenue le 2010-12-10
Sujet: Algorithmique répartie : vaincre les contraintes des réseaux modernes
Direction de thèse:
Encadrement de thèse:
Laboratoire:
Voisinage
Ellipse bleue: doctorant, ellipse jaune: docteur, rectangle vert: permanent, rectangle jaune: HDR. Trait vert: encadrant de thèse, trait bleu: directeur de thèse, pointillé: jury d'évaluation à mi-parcours ou jury de thèse.
Productions scientifiques
http://arxiv.org/abs/0805.0851
Probabilistic Self-stabilizing Vertex Coloring in Unidirectional Anonymous Networks
A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external intervention in finite time. Unidirectional networks preclude many common techniques in self-stabilization from being used, such as preserving local predicates. The focus of this work is on the classical vertex coloring problem, that is a basic building block for many resource allocation problems arising in wireless sensor networks. In this paper, we investigate the gain in complexity that can be obtained through randomization. We present a probabilistically self-stabilizing algorithm that uses k states per process, where k is a parameter of the algorithm. When k=Delta+1, the algorithm recovers in expected O(Delta n) actions. When k may grow arbitrarily, the algorithm recovers in expected O(n) actions in total. Thus, our algorithm can be made optimal with respect to space or time complexity. Our case study hints that randomization could help filling the complexity gap between bidirectionnal and unidirectionnal networks.
Proceedings of ICDCN 2010, Kolkata, India 2010
http://fabrice.lefessant.net/papers/damap2009.pdf
Optimizing Peer-to-Peer Backup using Lifetime Estimations
In this paper, we study the viability of a peer-to-peer backup
International Workshop on Data Management in Peer-to-Peer Systems (Damap'09) 2009
http://hal.inria.fr/inria-00384649
Sur le Coloriage Auto-stabilisant dans les Reseaux Unidirectionnels Anonymes
Nous considerons des reseaux unidirectionnels anonymes. Nous demontrons que contrairement aux reseaux bidirectionnels, l'auto-stabilisation de taches locales peut y etre aussi difficile que l'auto-stabilisation de taches globales. Pour ce faire, nous prenons comme exemple le probl`eme du coloriage des noeuds d'un reseau. Plus precisement, nous demontrons que le coloriage auto-stabilisant est intrins`equement aussi difficile `a resoudre de mani`ere deterministe qu'une tache globale. Nous proposons ensuite une approche probabiliste pour retrouver une complexite locale.
Proceedings of Algotel 2009 2009
http://dx.doi.org/10.1109/IPDPS.2009.5161053
Optimal Deterministic Self-stabilizing Vertex Coloring in Unidirectional Anonymous Networks
A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the systems recovers from this catastrophic situation without external intervention in finite time. Unidirectional networks preclude many common techniques in self-stabilization from being used, such as preserving local predicates. In this paper, we investigate the intrinsic complexity of achieving
Proceedings of the IEEE International Conference on Parallel and Distributed Processing Systems (IPDPS 2009), Rome, Italy 2009
edite:1298823148570
Optimal probabilistic self-stabilizing vertex coloring in unidirectional anonymous networks
2009
edite:1298823148571
Optimal deterministic self-stabilizing vertex coloring in unidirectional anonymous networks
IPDPS 2009
edite:1298823148599
Probabilistic Self-stabilizing Vertex Coloring in Unidirectional Anonymous Networks
ICDCN 2010
edite:1298823148607
A Framework for Secure and Private P2P Publish/Subscribe
12th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS 2010
http://hal.inria.fr/inria-00384649
Sur le Coloriage Auto-stabilisant dans les Réseaux Unidirectionnels Anonymes
Nous considérons des réseaux unidirectionnels anonymes. Nous démontrons que contrairement aux réseaux bidirectionnels, l'auto-stabilisation de taches locales peut y etre aussi difficile que l'auto-stabilisation de taches globales. Pour ce faire, nous prenons comme exemple le probl`eme du coloriage des noeuds d'un réseau. Plus précisément, nous démontrons que le coloriage auto-stabilisant est intrins`equement aussi difficile `a résoudre de mani`ere déterministe qu'une tache globale. Nous proposons ensuite une approche probabiliste pour retrouver une complexité locale.
Proceedings of Algotel 2009 2009
Soutenance
Thèse: Algorithmique répartie : vaincre les contraintes des réseaux modernes
Soutenance: 2010-12-10
Rapporteurs: Bertrand DUCOURTHIAL    Eddy CARON