On the Complexity of Partial Order Trace Model Checking∗

The design of a distributed system is known to be a difficult task which can be eased by various techniques including validation and debugging. The model-based design abstracts the actions the system can do into events which change its global state. Depending on the various assumptions the designer can make, the model can be either centralized, providing a global observation and contro