Section: Overall Objectives

General Objectives

CEPAGE project was launched (as a team) in 2006, when the development of interconnection networks had led to the emergence of new types of computing platforms, characterized by the heterogeneity of both their processing and communication resources, their geographical dispersion, the absence of centralized control, and their instability in terms of the number and performance of participating resources. At the same time, P2P file exchange systems and Volunteer Computing platforms were developing, reinforcing the idea that big platforms could be built by aggregating a large set of small distributed resources. In the context of intensive computations, the solutions were less sophisticated than in the context of file exchanges, and mostly relied on the client-server model (SETI@home, folding@home), with centralized knowledge and control of the platform, and no direct communications between peers. In this context, the general goal of CEPAGE was to come up with new strategies in order to extend the set of computation-intensive applications that could be run on large scale distributed platforms, by gathering researchers with expertize in scheduling of tasks and collective communications, graph theory, design of overlay networks, modeling of network topologies, small world networks, distributed algorithms, compact data structures, routing and randomized algorithms, later extended to include mobile agents and databases.

Objectives for the evaluation period

The above context lead us to identify the following research axes (extracted from the project proposal).

1. Models

   1. At a low level, to understand the underlying physical topology and to obtain realistic models whose parameters can be instantiated at runtime.

   2. At a higher level, to derive models of the dynamism of targeted platforms, both in terms of participating resources and resource performance.

2. Overlays and distributed algorithms:

   1. To understand how to augment the logical topology in order to achieve good properties of P2P systems.

   2. To build overlays dedicated to specific applications and services that achieve good performance.

   3. To understand how to dynamically adapt scheduling algorithms (in particular collective communication schemes) to changes in network performance and topology, using randomized algorithms.

3. Compact and distributed data structures:

   1. To understand how to dynamically adapt compact data structures to changes in network performance and topology.

   2. To design sophisticated labeling schemes in order to answer complex predicates using local labels only.

Regarding the 2007-2011 objectives of the projects (1)-(3), the vast majority of them has been fulfilled as shown in Sections  4.1 ,  4.2 and  4.3 .

Nevertheless, during the last four years, several adjustments were made with respect to the initial objectives.

• First, we under-evaluated in our project proposal the importance of issues related to security and anonymity, by saying that we would rely on external mechanisms provided by distributed systems to ensure them. It turned out that the question was harder to solve and a necessary condition in order to deploy our algorithms at a large scale. Therefore, we spent a lot of effort to work on these issues using the behavior and capacities of mobile agents under adversarial models. The recruitments of David Ilcinkas (CR CNRS, 2007) and Adrian Kosowski (CR Inria, 2010) have strongly reinforced this axis.

• The picture changed due to the coming of Cloud Computing as a mean to "renting" external resources rather than aggregating and sharing privately-owned ones. This solution is particularly appealing in the context of computing-intensive applications. Our efforts to develop widely used distributed codes for molecular dynamics simulations and continuous integration were made unsuccessful by this new context. We are moving toward this direction, in particular by considering stability of resource allocation problems, reliability, and stochastic optimization issues.