2024/10/06 by Adsul, Bharat, Jain, Nehul
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2410.04420
We propose a new model of a distributed game, called an ATS game, which is played on a non-deterministic asynchronous transition system -- a natural distributed finite-state device working on Mazurkiewicz traces. This new partial-information game is played between an environment and a distributed system comprising multiple processes. A distributed strategy uses causal past to make the next move. The key algorithmic question is to solve the game, that is, to decide the existence of a distributed winning strategy. It turns out ATS games are equivalent to asynchronous games, which are known to be undecidable. We prove that ATS games are undecidable in this article.