We consider the distributed control synthesis problem for systems with locks. The goal is to find local controllers so that the global system does not deadlock. With no restriction this problem is undecidable even for three processes each using a fixed number of locks. We propose two restrictions that make distributed control decidable. The first one is to allow each process to use at most two locks. The problem then becomes Sigma2P-complete, and even in PTIME under some additional assumptions. The dining philosophers problem satisfies these assumptions. The second restriction is a nested usage of locks. In this case the synthesis problem is NEXPTIME-complete. The drinking philosophers problem falls in this case.
翻译:我们考虑有锁系统的分布式控制合成问题。 目标是找到本地控制器, 使全球系统不陷入僵局。 即使使用固定数目的锁, 这个问题也是无法避免的。 我们建议了两种限制, 使分配式控制可以调整。 第一个是允许每个程序在大多数两个锁中使用。 问题随后变成Sigma2P- 完成, 甚至在PTIME 中, 还有一些假设。 餐饮哲学家的问题满足了这些假设。 第二个限制是嵌套式使用锁。 在这种情况下, 合成问题就是 NEXPTIME 完成。 饮酒哲学家的问题就在这个例子中出现。