We study the verification of distributed systems where processes are finite automata with access to a shared pool of locks. We consider objectives that are boolean combinations of local regular constraints. We show that the problem, PSPACE-complete in general, falls in NP with the right assumptions on the system. We use restrictions on the number of locks a process can access and the order in which locks can be released. We provide tight complexity bounds, as well as a subcase of interest that can be solved in PTIME.

翻译：我们研究对分布式系统的核查,在分布式系统中,流程是有限的自动化系统,可进入共享的锁群。我们考虑的目标是当地常规制约的布林组合。我们发现,问题(一般而言,PSPACE已经完成)在NP中,有正确的系统假设。我们使用对一个流程可以进入的锁数的限制,以及释放锁的顺序。我们提供了紧凑的复杂界限,以及可在PTIME中解决的次级利益。