Dear all,

the following postdoc position is available with start

date in a couple of months (the time needed to accomplish

all the administrative formalities).

TITLE: Distributed Optimization in Dynamic Wireless Networks

CANDIDATE’S BACKGROUND:

The candidate should have a solid background on probability,

graph theory and optimization and good programming skills.

CONTEXT:

The applicant will be part of INRIA Maestro team and will

work in the framework of INRIA and Alcatel-Lucent Bell Labs

joint laboratory.

MAESTRO is an INRIA project-team (created on October 1st,

2003) whose permanent members are located in Sophia

Antipolis, in Avignon and in Montpellier.

The ambition of MAESTRO is to provide the community with

methods and tools for the performance evaluation,

optimization and control of networks. More precisely, the

objectives of MAESTRO are:

* to develop mathematical and software tools for

evaluating the performance, optimizing and controlling

discrete-event systems, including networks and their

applications;

* to evaluate the performance and to control

communication networks (protocols, architectures,

applications) and, primarily, IP networks.

http://www-sop.inria.fr/maestro/

SALARY:

25600 euros net per year

DURATION:

One year

CONTACT:

Giovanni Neglia, giovanni.neglia@inria.fr,

http://www-sop.inria.fr/members/Giovanni.Neglia/

TOPIC DESCRIPTION:

Future wireless networks may require autonomic operation

features in order to cope with a high number of users and a

fast changing scenario. In fact, the time a central

authority would need to discover network operation

conditions and enforce particular behaviours at the nodes

would be in many application scenarios much longer than the

network dynamics timescales. Then, nodes need to be able to

derive local policies in oder to achieve a global desired

performance.

This problem can be considered as a distributed stochastic

optimal control problem or a team theory problem: we have

multiple controllers (the nodes) with a common objective.

The challenge arises from the fact that nodes in general do

not have an exact knowledge of the status of the system

because this is distributed, large and because the spreading

of information may be significantly limited by intermittent

connectivity. Hence each node can only rely on some belief

about the status of the system to take its decisions. In

such a context, optimal policies may be identified only for

specific structures of the information available at the

agent (full, sampled, delayed…) and their complexities

depend on the information structure too. Moreover, not only

the current state of the system, but also the network

scenario itself (e.g. the total number of nodes, their

connectivity, the consequences of each action) can be

unknown to the nodes. In such cases it is needed that nodes

learn online about the dynamic environment through

trial-and-error interactions.

We want to address the problem of distributed optimization

in such a scenario. We start considering the case when the

nodes collaborate to minimize the sum of local objective

functions, depending in general on some parameters or

actions of all the nodes in the network. If the local

objective functions are convex, it can be adopted a recently

proposed computation framework that relies on local

sub-gradient methods and consensus algorithms to average

each node information [Nedic2009]. For example the

dissemination of dynamic content in a Delay Tolerant Network

falls in this scenario [Iaonnidis2009].

Existing convergence results for this framework can be

applied only in the case of synchronous node operation and

simple network dynamics without memory. We will address both

these issues studying the convergence to the optimal

solution for a more general class of dynamics and under

asynchronous operation. Some preliminary results are in

[Masiero2010].

Moreover, we want to investigate also the speed of

convergence of this distributed optimization approach, that

is determined by its two components: the consensus algorithm

and the gradient algorithm.

A third research direction is to determine if the local

sub-gradient can be replaced by local derivative-free

approaches [Conn2009] in the cases when the performance

metric to optimize is unknown, so that it is not possible to

calculate a gradient or even a sub-gradient.

[Ioannidis2009] S. Ioannidis, A. Chaintreau, and L.

Massoulie, “Optimal and Scalable Distribution of Content

Updates over a Mobile Social Network,” in proceedings of

IEEE INFOCOM 2009, Rio de Janeiro, Brazil, Apr. 2009, pp.

1422–1430.

[Nedic2009] A. Nedic and A. Ozdaglar, “Distributed

Subgradient Methods for Multi-agent Optimization,” LIDS

report 2755, IEEE Transactions on Automatic Control, vol.

54, no. 1, pp. 48-61, 2009.

[Masiero2010] R. Masiero, G. Neglia, Distributed

Sub-gradient Method for Delay Tolerant Networks, in

proceedings of IEEE INFOCOM 2010 (Miniconf), Shangai, China,

April 2010.

[Conn2009] A. R. Conn, K. Scheinberg, L. N. Vicente,

Introduction to Derivative-Free Optimization, Society for

Industrial and Applied Mathematics. 2009