Distributed On-the-Fly Equivalence Checking

AbstractOn-the-fly equivalence checking consists in comparing two Labeled Transition Systems (Ltss) modulo a given equivalence relation by exploring them in a demand-driven way. Since it avoids the explicit construction of Ltss, this method is able to detect errors even in systems that are too large to fit in the memory of a computer. In this paper, we aim at further improving the performance of on-the-fly equivalence checking using several machines connected by a network. We propose DSolve, a new algorithm for distributed on-the-fly resolution of Boolean Equation Systems (Bess), which enables equivalence checking modulo various relations characterized in terms of Bess. DSolve serves as verification engine for the distributed version of Bisimulator, an on-the-fly equivalence checker developed within the Cadp verification toolbox using the Open/Cæsar environment. Our experimental measures show quasi-linear speedups and a good scalability of the distributed version of Bisimulator w.r.t. its sequential version