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.