_*
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.
*Context*
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
information:
* 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.
*
*
*References
*
**[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.
|
