Speaker: Corto Mascle, LaBRI.
Tuesday 12 April 2022, 11:00, (room 1Z71 ENS Paris-Saclay and online)
Abstract: We consider the distributed control problem for systems with locks. We introduce a model in which some processes running in parallel cannot communicate directly, but may acquire or release some shared locks. The goal is to find local controllers so that the global system does not deadlock. With no restriction this problem is undecidable, but in this talk we will focus on systems in which each process can access at most two locks. The problem then becomes complete for the second level of the polynomial hierarchy, and even in PTIME under some additional assumptions. The dining philosophers problem satisfies these assumptions.