Knowledge Compilation for Feature Models


Feature tree, knowledge compilation, d-DNNF, software variability


Recently, fog computing has become a major trend in the area of large-scale distributed systems. This paradigm promotes the seamless integration of cloud computing services and IoT devices, resulting in a highly configurable environment where services and devices interact together and evolve over time. The benefits are obvious: by leveraging the strengths of both sides, a fog environment can provide huge computational capabilities from the cloud, combined with context-awareness of IoT devices. But such systems are likely to be distributed across different application domains and geographical locations, creating hidden dependencies across domains, platforms and services, making them difficult to configure. Capturing and reasoning on the configurations of such a variable, distributed and heterogeneous environment in a systematic and automated way is a complex, heavy and challenging task.


Feature trees are massively used to describe highly variable environments and define their configuration space, i.e. the set of possible configurations. A configuration is a combination of features, that is, a set of selected nodes in the tree which complies with the constraints related to the tree (e.g., a selected node implies the selection of another one). Various operations can be executed on the tree, such as counting/listing all configurations, detect unused nodes, check the validity of a configuration, etc. However, when dealing with large-scale variable software such as fog ones, these operations can be difficult or impossible to execute due to the combinatorial explosion resulting from the size of the tree and the set of constraints. Existing approaches based on BDD or SAT solvers cannot scale. The objective of this position is to explore recent techniques from the area of knowledge compilation to tackle configuration issues. Specifically, the hired candidate will investigate the best-suited d-DNNF representation for each reasoning operation, and will provide new variability modeling mechanisms (e.g., dimensions, priorities and scopes) required in a fog context as well as the related software tooling.


  • R. Mahmud, R. Kotagiri, R. Buyya. Fog Computing: A Taxonomy, Survey and Future Directions. Internet of Everything, pp 103-130, Springer, 2018.
  • C. Quinton, D. Romero, L. Duchien. SALOON: a platform for selecting and configuring cloud environments. Software: Practice and Experience vol. 46, 2016.
  • J. A. Galindo Duarte, M. Acher, J. M. Tirado, C. Vidal, B. Baudry, et al. Exploiting the Enumeration of All Feature Model Configurations: A New Perspective with Distributed Computing. International Software Product Line Conference, SPLC 2016.
  • J. García-Galán, J. M. García, P. Trinidad, and P. Fernández. Modelling and Analysing Highly-Configurable Services. International Software Product Line Conference, SPLC 2017.


The postdoc will be hosted in the Spirals team. Spirals is a joint team between Inria Lille – Nord Europe and CRIStAL (computer science laboratory of the University of Lille) and is located on Lille University’s scientific campus in Villeneuve d’Ascq.


  40 Avenue Halley,
59650 Villeneuve d’Ascq

  +33 359 358 770