Explanations for over-constrained problems using QuickXPlain with speculative executions

Conflict detection is used in various scenarios ranging from interactive decision making (e.g., knowledge-based configuration) to the diagnosis of potentially faulty models (e.g., using knowledge base analysis operations). Conflicts can be regarded as sets of restrictions (constraints) causing an inconsistency. Junker’s QuickXPlain is a divide-and-conquer based algorithm for the detection of preferred minimal conflicts. In this article, we present a novel approach to the detection of such conflicts which is based on speculative programming. We introduce a parallelization of QuickXPlain and empirically evaluate this approach on the basis of synthesized knowledge bases representing feature models. The results of this evaluation show significant performance improvements in the parallelized QuickXPlain version.