Research interests :
  • Service discovery in computational grids
  • Peer-to-peer systems
  • Self-stabilization

Advisors :

 Projects :
Research Activity :

     Motivation :

Within computational grids, some services (software components, linear algebra libraries, etc.) are made available by some servers to some clients. In spite of the growing popularity of such grids, several factors still hinder their deployment over completely decentralized platforms. Among them, service discovery, although efficient in many cases, does not reach several requirements, mainly in terms of flexibility and efficiency on wide-area dynamic platforms. Therefore, it has become crucial to propose new tools coping with such platforms. Emerging peer-to-peer technologies provide scalable and fault-tolerant concepts and tools for the distribution and retrieval of data items at large scale. That's why it became a field of investigation for the design of future grids.

     A preliminary work :

Among recently proposed solutions for peer-to-peer resource discovery, a new kind of overlay has appeared, based on tries, also known as lexicographic, or prefix trees. These overlays provide an efficient way of solving range queries, supporting searches on partial string. Moreover they are easy to extend for multi-attribute queries. In this class of tools, we developed the DLPT (Distributed Lexicographic Placement Table) approach, a service discovery solution based on a prefix tree indexing grid services dynamically as they are registered by servers in a fully distributed way. It supports exact match requests, partial search strings, and multi-attribute range queries. Each node of this tree is run on a peer of the physical network, nodes being distributed among peers through a DHT. Facing the dynamic nature of the platform, we provided distributed algorithm of replication of the tree. Finally, a distributed greedy heuristic periodically computes an efficient spanning tree of the replicated tree to provide some topology awareness [2].

     Some efficiency issues: mapping and load balancing

The basic design may lead to several causes of inefficiency, dealing with load balancing and maintenance cost. We thus developed a self-contained architecture avoiding the need for an underlying DHT, designed new heuristics for load balancing and adapted existing ones to our cases. Simulations showed the liveness and efficiency of this architecture [5].

     An alternative to replication:

One drawback of using tries is their inherent poor robustness in a dynamic environment, leading to the split of the tree into a forest, and the impossibility to route requests. In most trie-based approaches, the fault-tolerance is handled by replication, which can be very costly in terms of computing and storage resources. We proposed a fault-tolerance protocol that reconnects subtrees a posteriori, after crashes, to have a connected graph and then reorders the nodes to build a consistent prefix tree [3].

     Snap-stabilization :

We proved the previous approach to repair disconnected trees and reorder them in a unique tree only if the initial trees are valid. In other words, this first protocol is not self-stabilizing i.e., able to recover from any initial configuration. We thus developed a protocol maintaining prefix trees, which we proved to have the snap-stabilization property. This means that this protocol is optimal in terms of stabilization time [4].

     Practical self-stabilization :

The drawback of this snap-stabilization solution is that it was written in a coarse-grain theoretical model and works with restricted initial configurations. To overcome these problems and make a self-stabilization protocol that can be implemented in actual networks, we developed another solution that we proved to be self-stabilizing in a message passing environment whatever the initial configuration of the system is [6].
Publications :

     International journal or book chapter :

[2] Eddy Caron, Frédéric Desprez, Franck Petit, and Cédric Tedeschi. Handbook of Research on P2P and Grid Systems for Service-Oriented Computing: Models, Methodologies and Applications, chapter DLPT: A P2P tool for Service Discovery in Grid Computing. IGI Global, 2009. To appear. [ bib ]
[1] Eddy Caron, Frédéric Desprez, and Cédric Tedeschi. Enhancing Computational Grids with Peer-to-Peer technology for Large Scale Service Discovery. Journal of Grid Computing, 5(3):337-360, September 2007. [ bib | .pdf ]

     International conferences :

[6] Eddy Caron, Ajoy K. Datta, Franck Petit, and Cédric Tedeschi. Self-Stabilization in Tree-Structured Peer-to-Peer Service Discovery Systems. In 27th International Symposium on Reliable Distributed Systems, SRDS2008, Napoli, Italy, October, 6-8 2008. IEEE. [ bib ]
[5] Eddy Caron, Frédéric Desprez, and Cédric Tedeschi. Efficiency of Tree-Structured Peer-to-Peer Service Discovery Systems. In 5th International Workshop on Hot Topics in Peer-to-Peer Systems, Hot-P2P 2008, in conjunction with IPDPS 2008, Miami, USA, April, 14-18 2008. IEEE. [ bib | .pdf ]
[4] Eddy Caron, Frédéric Desprez, Franck Petit, and Cédric Tedeschi. Snap-stabilizing Prefix Tree for Peer-to-peer Systems. In Toshimitsu Masuzawa and Sébastien Tixeuil, editors, 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS2007, volume 4838 of LNCS, pages 82-96, Paris, France, November, 14-16 2007. Springer Verlag Berlin Heidelberg. [ bib | .pdf ]
[3] Eddy Caron, Frédéric Desprez, Charles Fourdrignier, Franck Petit, and Cédric Tedeschi. A Repair Mechanism for Fault-Tolerance for Tree-Structured Peer-to-Peer Systems. In Yves Robert, Manish Parashar, Ramamurthy Badrinath, and Viktor K. Prasanna, editors, 12th International Conference on High Performance Computing, HiPC2006, volume 4297 of LNCS, pages 171-182, Bangalore, India, December, 18-21 2006. Springer-Verlag Berlin Heidelberg. [ bib | .pdf ]
[2] Eddy Caron, Frédéric Desprez, and Cédric Tedeschi. A Dynamic Prefix Tree for the Service Discovery Within Large Scale Grids. In Alberto Montresor, Adam Wierzbicki, and Nahid Shahmehri, editors, 6th International Conference on Peer-to-Peer Computing, P2P2006, pages 106-113, Cambridge, UK, September, 6-8 2006. IEEE. [ bib | .pdf ]
[1] Eddy Caron, Frédéric Desprez, Franck Petit, and Cédric Tedeschi. A Peer-to-Peer Extension of Network-Enabled Server Systems. In 1st International Conference on e-Science and Grid Computing, e-Science 2005, pages 430-437, Melbourne, Australia, December, 5-8 2005. IEEE. [ bib | .pdf ]

     National conferences :

[3] Cédric Tedeschi. Arbre de préfixes auto-stable pour les systèmes pair-à-pair. In Fribourg'2008 - Conférences conjointes RenPar'18 / SympA'2008 / CFSE'6, Fribourg, Suisse, February, 11-13 2008. [ bib ]
[2] Eddy Caron, Charles Fourdrignier, Franck Petit, and Cédric Tedeschi. Mécanisme de réparations pour un système p2p de découverte de services. In Perpi'2006 - Conférences conjointes RenPar'17 / SympA'2006 / CFSE'5 / JC'2006, pages 252-259, Canet en Roussillon, France, October, 4-6 2006. [ bib ]
[1] Cédric Tedeschi. Découverte de services pour les grilles de calcul dynamiques large échelle. In Perpi'2006 - Conférences conjointes RenPar'17 / SympA'2006 / CFSE'5 / JC'2006, pages 52-59, Canet en Roussillon, France, October, 4-6 2006. [ bib ]

     Research reports :

[13] Eddy Caron, Frédéric Desprez, and Cédric Tedeschi. Efficiency of Tree-Structured Peer-to-Peer Service Discovery Systems. Technical Report RR2008-18, Laboratoire de l'Informatique du Parallélisme (LIP), April 2008. Also available as INRIA Research Report 6557. [ bib | .pdf ]
[12] Eddy Caron, Frédéric Desprez, and Cédric Tedeschi. Efficiency of Tree-Structured Peer-to-Peer Service Discovery Systems. Research Report RR-6557, INRIA, April 2008. Also available as LIP Research Report 2008-18. [ bib | http ]
[11] Eddy Caron, Frédéric Desprez, Franck Petit, and Cédric Tedeschi. Snap-stabilizing Prefix Tree for Peer-to-peer Systems. Technical Report RR2007-39, Laboratoire de l'Informatique du Parallélisme (LIP), September 2007. Also available as INRIA Research Report 6297. [ bib | .pdf ]
[10] Eddy Caron, Frédéric Desprez, Franck Petit, and Cédric Tedeschi. Snap-stabilizing Prefix Tree for Peer-to-peer Systems. Research Report RR-6297, INRIA, September 2007. Also available as LIP Research Report 2007-39. [ bib | http ]
[9] Cédric Tedeschi. Découverte de services pour les grilles de calcul dynamiques large ćhelle. Technical Report RR2006-44, Laboratoire de l'Informatique du Parallélisme (LIP), November 2006. Also available as INRIA Research Report 6035. [ bib | .pdf ]
[8] Cédric Tedeschi. Découverte de services pour les grilles de calcul dynamiques large échelle. Technical Report RR-6035, Institut National de Recherche en Informatique et en Automatique (INRIA), November 2006. Also available as LIP Research Report 2006-44. [ bib | http ]
[7] Eddy Caron, Frédéric Desprez, Charles Fourdrignier, Franck Petit, and Cédric Tedeschi. A Repair Mechanism for Fault-Tolerance for Tree-Structured Peer-to-Peer Systems. Technical Report RR6029, Institut National de Recherche en Informatique et en Automatique (INRIA), October 2006. Also available as LIP Research Report 2006-34. [ bib | http ]
[6] Eddy Caron, Frédéric Desprez, Charles Fourdrignier, Franck Petit, and Cédric Tedeschi. A Repair Mechanism for Fault-Tolerance for Tree-Structured Peer-to-Peer Systems. Technical Report RR2006-34, Laboratoire de l'Informatique du Parallélisme (LIP), October 2006. Also available as INRIA Research Report 6029. [ bib | .pdf ]
[5] Eddy Caron, Frédéric Desprez, and Cédric Tedeschi. A Dynamic Prefix Tree for the Service Discovery Within Large Scale Grids. Technical Report RR2006-33, Laboratoire de l'Informatique du Parallélisme (LIP), October 2006. Also available as INRIA Research Report 6028. [ bib | .pdf ]
[4] Eddy Caron, Frédéric Desprez, and Cédric Tedeschi. A Dynamic Prefix Tree for the Service Discovery Within Large Scale Grids. Technical Report RR-6028, Institut National de Recherche en Informatique et en Automatique (INRIA), October 2006. Also available as LIP Research Report 2006-33. [ bib | http ]
[3] Cédric Tedeschi. Service discovery in a peer-to-peer environment for computational grids. Technical Report RR2005-42, Laboratoire de l'Informatique du Parallélisme (LIP), September 2006. Also available as INRIA Research Report 5679. [ bib | .pdf ]
[2] Cédric Tedeschi. Service Discovery in a Peer-to-peer Environment for Computational Grids. Technical Report RR-5679, Institut National de Recherche en Informatique et en Automatique (INRIA), September 2005. Also available as LIP Research Report 2005-42. [ bib | http ]
[1] Eddy Caron, Frédéric Desprez, Franck Petit, and Cédric Tedeschi. Resource localization using peer-to-peer technology for network enabled servers. Research report 2004-55, Laboratoire de l'Informatique du Parallélisme (LIP), December 2004. [ bib | .pdf ]

     Thesis :

[1] Cédric Tedeschi. Peer-to-Peer Prefix Tree for Large Scale Service Discovery. PhD thesis, École normale supérieure de Lyon, October 2008.
[ bib | .pdf ]
Talks :

     HotP2P 2008 (Miami, USA) --- Efficiency of Tree-Structured Peer-to-Peer Service Discovery Systems --- Slides (pdf)
     SSS 2007 (Paris, France) Snap-stabilizing Prefix Tree for Peer-to-peer Systems --- Slides (pdf)
     HiPC 2006 (Bangalore, India) A Repair Mechanism for Tree-structured Peer-to-peer Systems --- Slides (pdf)
     P2P 2006 (Cambridge, UK) A Dynamic Prefix Tree for the Service Discovery within Large Scale Grids --- Slides (pdf)
     E-Science 2005 (Melbourne, Australia) A Peer-to-Peer Extension of Network-Enabled Server Systems --- Slides (pdf)