Scalable Model-Based Diagnosis with FastDiag: A Dataset and Parallel Benchmark Framework

Abstract

FastDiag is a widely used algorithm for model-based diagnosis, computing minimal subsets of constraints whose removal restores consistency in knowledge-based systems. As applications grow in complexity, researchers have proposed parallel extensions such as Java-version FastDiagP and FastDiagP++ to accelerate diagnosis through speculative and multiprocessing strategies. This paper presents a reproducible and extensible framework for evaluating FastDiag and its parallel variants across a benchmark suite of feature models and ontology-like constraints. We analyze each variant in terms of recursion structure, runtime performance, and diagnostic correctness. Tracking mechanisms and structured logs enable the fine-grained comparison of recursive behavior and branching strategies. Technical validation confirms that parallel execution preserves minimality and structural soundness, while benchmark results show runtime improvements of up to 4× with FastDiagP++. The accompanying dataset, available as open source, supports educational use, algorithmic benchmarking, and integration into interactive configuration environments. The framework is primarily intended for reproducible benchmarking and teaching with open-source implementations that facilitate analysis and extension. © 2025 by the authors.