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:


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:, and click on the "Apply" button on the top right. Please provide the following information:


[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.