PODC Archives

ACM PODC Participants List


Options: Use Classic View

Use Monospaced Font
Show HTML Part by Default
Show All Mail Headers

Topic: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Franck Petit <[log in to unmask]>
Mon, 16 Apr 2018 16:50:57 +0200
text/plain (4 kB) , text/html (5 kB)
Service Problems within Highly Dynamic Distributed Systems *_

A PhD grant is available at INRIA / Sorbonne University. Located on the 
Pierre and Marie Curie Campus (4, place Jussieu, Paris), the position is 
open for three years starting in autumn 2018.


The availability of wireless networks has drastically increased in 
recent years and establish new needs and applications. Humans, agents, 
devices, robots, and applications interact together through more and 
more heterogeneous infrastructures, such as mobile ad hoc networks 
(MANET), vehicular networks (VANET), (mobile) sensor and actuator 
networks (SAN), body area networks (BAN), as well as always evolving 
network infrastructures on the Internet. In such networks, items (users, 
links, equipments, etc.) may join, leave, or move inside the system at 
unforeseeable times.

The dynamics of such systems, the heterogeneity of devices, usages, and 
participants, and often the unprecedented scale to consider, make the 
design of such infrastructures extremely challenging. For a vast 
majority of them, the dynamics are also unpredictable. Furthermore, 
designing applications on top of such networks requires to deal with the 
lack (or weakness) of infrastructures and numerous topological changes.

Therefore, it becomes necessary to define and to develop new accurate 
models capturing the features of the considered objects: users' 
mobility, system instability, dynamics of applications, etc. Recently, 
numerous models (refer to [1,2,3], [4] for a survey) for these harsh 
environments have been gathered in a general framework: the Time-Varying 
Graphs (TVGs) [5]. Based on this framework, DELYS team recently proposed 
a quite thoroughgoing study of fixed point problems (like maximal 
matching, minimal dominating set, maximal dominating set, etc.) in 
highly dynamic systems, i.e., systems in which the network topology 
changes very fast [6,7,8]. In particular, some necessary and sufficient 
topological conditions are exhibited for these problems.

*Research Project*

The main goal of the thesis is to provide a similar study about problems 
without fixed point in HDDS. Such problems refer to service tasks that 
are unpredictably triggered on demand by some participants. We propose 
to focus on one of the following fundamental problems: Mutual Exclusion, 
Token Circulation, or Propagation of Information with Feedback. All this 
problems received great attention in static systems but have barely been 
considered in the context of (highly) dynamic systems.

The scientific agenda is mainly threefold:

  * First, studying service problems with the goal to provide
    specifications that makes sense in the context of HDDS;
  * Producing necessary and sufficient conditions on the system (e.g.,
    network dynamic, network topology, etc.) to enable existence of
    solutions to this specification in highly dynamic environments;
  * The design of distributed algorithms that meet these necessary and
    sufficient conditions in order to obtain optimal solutions.

*Application *

The position is offered to students who hold a Master degree in Computer 
science, and are interested in theory of distributed computing. A solid 
knowledge in algorithms, synchronization, concurrency, and 
fault-tolerance will be appreciated.

To apply, please use the following link: 
https://jobs.inria.fr/public/classic/en/offres/2018-00672, and click on 
the "Apply" button on the top right. Please provide the following 

  *      A resume or Curriculum Vitae
  *      A list of courses and grades of the last two years of study
  *      Names and contact details of three references (people who can
    recommend you), whom we will contact directly.



**[1] A. Ferreira. Building a reference combinatorial model for manets. 
Network, 18(5):24–29, 2004.
[2] F. Kuhn, N. A. Lynch, and R. Oshman. Distributed computation in 
dynamic networks. In Proceedings of the 42nd ACM Symposium on Theory of 
Computing, STOC 2010, pages 513–522, 2010.
[3] B. Xuan, A. Ferreira, and A. Jarry. Computing shortest, fastest, and 
foremost journeys in dynamic networks. IJFCS, 14(02):267–285, 2003.
[4] A. Casteigts and P. Flocchini. Deterministic algorithms in dynamic 
networks: Problems, analysis, and algorithmic tools. Technical report, 
DRDC 2013-020, 2013.
[5] A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. 
Time-varying graphs and dynamic networks. IJPEDS, 27(5):387–408, 2012.
[6] S. Dubois, M-H. Kaaouachi, and F. Petit. Enabling minimal dominating 
set in highly dynamic distributed systems. In SSS 2015, pages 51–66, 2015.
[7] N. Braud-Santoni, S. Dubois, M-H. Kaaouachi, and F. Petit. The next 
700 impossibility results in time-varying graphs. IJNC, 6(1):27–41, 2016.
[8] A. Casteigts, S. Dubois, F. Petit, and John Michael Robson. 
Robustness in highly dynamic networks. CoRR, abs/1703.03190, 2017.