2026-07-22T16:01:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13278 2024-03-06T10:52:00Z ddc:004 open_access

Parameterized Complexity of Safety of Threshold Automata Balasubramanian, A. R. Threshold automata distributed algorithms parameterized complexity Threshold automata are a formalism for modeling fault-tolerant distributed algorithms. In this paper, we study the parameterized complexity of reachability of threshold automata. As a first result, we show that the problem becomes W[1]-hard even when parameterized by parameters which are quite small in practice. We then consider two restricted cases which arise in practice and provide fixed-parameter tractable algorithms for both these cases. Finally, we report on experimental results conducted on some protocols taken from the literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik A. R. Balasubramanian 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.37 urn:nbn:de:0030-drops-132787 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.37 eng https://creativecommons.org/licenses/by/3.0/legalcode