2026-08-07T10:23:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16466 2024-03-06T10:57:33Z ddc:004 open_access

Distributed Controller Synthesis for Deadlock Avoidance Gimbert, Hugo Mascle, Corto Muscholl, Anca Walukiewicz, Igor Distributed Synthesis Concurrency Lock Synchronisation Deadlock Avoidance 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 complete for the second level of the polynomial time hierarchy, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo Gimbert and Corto Mascle and Anca Muscholl and Igor Walukiewicz 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.125 urn:nbn:de:0030-drops-164668 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.125 eng https://creativecommons.org/licenses/by/4.0/legalcode