Abstract: Various properties related with the safe, correct, and efficient operation of Cyber-Physical Systems (CPS) can be expressed via formal languages and checked at runtime or offline by appropriate verification tools. Such tools operate on monitoring data about the CPS state and functionality, typically collected from IoT devices. A specific approach involves modeling CPS state or operations using Satisfiability Modulo Theories (SMT) formalisms, and using solver software to check whether given CPS properties are satisfied or to derive satisfiable CPS configurations. The computational requirements of this process can however be significant, which challenges its timely execution on IoT/edge devices where input date originate. To address this challenge, we present an architecture that allows the distributed execution of SMT problem solving workloads over the computing continuum as a service. Our design supports arbitrary hierarchies of solver nodes running anywhere from the IoT device to the cloud, each independently executing decision-making logic as to whether to solve an SMT problem instance locally or to recursively offload the task to other nodes in the continuum. We demonstrate the benefits of offloading by implementing and quantitatively evaluating different reinforcement learning-based decision-making strategies addressing latency minimization and energy efficiency goals, and showcase the practicability of our scheme in a fog robotics proof-of-concept. Note: © Authors 2023. This is the authors' version of the work. The definitive version is published in the proceedings of ICDCN 2024, https://doi.org/10.1145/3631461.3631562. ACM Reference Format: Stefan Holzer, Pantelis Frangoudis, Christos Tsigkanos, and Schahram Dustdar. 2024. SMT-as-a-Service for Fog-Supported Cyber-Physical Systems. In 25th International Conference on Distributed Computing and Networking (ICDCN '24), January 04--07, 2024, Chennai, India. ACM, New York, NY, USA 10 Pages. https://doi.org/10.1145/3631461.3631562