CEPAGE Research team

Algorithmics for computationally intensive applications over wide scale distributed platforms

Team presentation

The recent evolutions in computer networks technology, as well as their diversification, yield a tremendous change in the use of these networks: applications and systems can now be designed at a much larger scale than before. This scaling evolution is dealing with the amount of data, the number of computers, the number of users, and the geographical diversity of these users. The goal of CEPAGE is to design high level distributed algorithms and data structures to help programming these large scale distributed platforms.

The main strength of the team is to gather researchers having various expertises in distributed data structures, routing, distributed, parallel and randomized algorithms, graph decompositions and graph algorithms. We believe that all these expertises are necessary to propose efficient overlay networks and high level services for large scale distributed platforms.

Research themes

Firstly, we aim both at building strong foundations for distributed algorithms (graph exploration, black-hole search,...) and distributed data structures (routing, efficient query, compact labeling...) to understand how to explore large scale networks in the context of failures and how to disseminate data so as to answer quickly to specific queries. Secondly, we aim at building simple (based on local estimations without centralized knowledge), realistic models to represent accurately resource performance and to build a realistic view of the topology of the network (based on network coordinates, geometric spanners, $\delta$-hyperbolic spaces). Then, we aim at proving that these models are tractable by providing low complexity distributed and randomized approximation algorithms for a set a basic scheduling problems (independent tasks scheduling, broadcasting, data dissemination,...) and associated overlay networks. At last, our goal is to prove the validity of our approach through softwares dedicated to several applications (molecular dynamics simulations, continuous integration) as well as more general tools related to the model we propose (AlNEM for automatic topology discovery, SimGRID for simulations at large scale).

International and industrial relations

  • Industrial relations and national collaborations:
    ALCATEL, 4SH - Xoocode, Yahoo!, ANR Alpage, ANR Aladdin, ADT "Aladdin", ANR "USS SimGrid"
  • International relations:
    EPSRC travel grant with King's College London and the University of Liverpool, Royal Society Grant with King's College London, European COST Action 293 GRAAL, European Cost 295 DYNAMO, European COST Action ComplexHPC, UCSD, San Diego, United States (L. Carter, J. Ferrante), University of Hawai`i at Manoa, United States (H. Casanova), ETH Zurich, Switzerland (J. Hromkovic), Gdansk University of Technology, Poland (A. Kosowski), King's College London (C. Cooper, T. Radzik), RWTH Aachen, Germany (B. Vocking, W. Unger), The University of Liverpool, UK (L. Gasieniec, M. Zito), Universit\'e du Qu\'ebec en Outaouai, Canada (A. Pelc, J. Czyzowicz), University of L'Aquila, Italy (M. Flammini), University of Paderborn, Germany (R. Elsasser), University of Perugia, Italy (A. Navarra), Wroclaw University of Technology, Poland (M. Korzeniowski), Waseda University (A. Ghatpande, H. Nakazato, H. Watanabe).

Keywords: Distributed Algorithms Large Scale Networks Randomized Algorithms Routing Compact Data Structures Mobile Agents Scheduling

Research teams of the same theme :

Inria Headquarters and research centres

Direct links

Social