Section: Overall Objectives

Goal and Context

General Context

The first set of questions that we consider is related to distributed computations, where the Internet is the underlying network. Since the topology of the underlying network is unknown, the use of logical networks (overlays) is required. In turn, the choice of the overlay will have an impact on the complexity of the algorithms. In this context, only the performance of the whole chain is meaningful, which requires to collect raw data and then to propose network models and algorithms based on these models, such that the performance of the resulting algorithm is good on raw data. This also requires studying the influence of the topology of the overlay network (the underlying graph) on the complexity of fundamental questions, such as graph exploration or black-hole search.

The second set of questions is related to distributed data structures. In general, the question is related to the compromise between the size of the data structure to be stored on each node and the time to answer a request (estimate the bandwidth between two nodes, compute the closest common ancestor of two nodes in a tree) or to perform a task (route a message in a network based on the information stored at the router nodes).

In order to study these questions, our research plan is based on the following goals. 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 accurately represent 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 of 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) and collections of datasets (Hubble for the continuous integration DAGs, Bedibe for latency and bandwidth measurements).

For the sake of the clarity of the presentation of our contributions during the last evaluation period, we decided to perform a synthesis, organizing our work into three main axes.

1. Resource Allocation and Scheduling (Section  4.1 ), with an emphasis on the interaction between network performance modeling and the design of efficient and guaranteed algorithms (covers axes 1(a), 2(a) and 2(b) of Section  2.1.1 );

2. Compact Routing (Section  4.2 ), with an emphasis on the design of specific strategies for restricted graph classes and the design of data structures resilient to resource failures (covers axes 1(b), 2(b), 2(c), 3(a), 3(b) of Section  2.1.1 );

3. Mobile Agents (Section  4.3 ), with en emphasis on the detection of dynamic faults and improvement of dissemination of information (covers axes 1(b), 2(b), 3(b) of Section  2.1.1 );.

Nevertheless, strong relationships and collaborations exist between these axes:

• the design and analysis of overlay networks is shared by Resource Allocation and Scheduling and Mobile Agents axes (see for example [61] , [85] , [54] , [101] , [77] ),

• the design of geometric spanners and geographic routing protocols is shared by Resource Allocation and Scheduling and Compact Routing axes (see for example [85] , [69] , [70] , [105] ),

• the use of specific graph classes (bounded tree-width, ...) is shared by Mobile Agents and Compact Routing axes (see for example [93] , [100] , [82] , [87] , [84] , [46] ).