TARGET in asynchronous shared-memory systems
An asynchronous shared-memory system is composed of processes that interact by reading from and writing to a shared memory. This shared memory is composed of registers, each containing one symbol at a time from the finite alphabet . All processes are anonymous and identical; they are described by the same finite automaton, called protocol. The transitions of the automaton are labelled by actions of the form or with and . A step of the execution corresponds to some process taking a transition of the automaton and, doing so, reading from or writing to some register. In the initial configuration of size , all processes are on state while all registers have initial value . TARGET asks whether there exists such that, from the initial configuration of size , there is an execution that puts all processes on some distinguished state . This problem is known to be NP-complete in the general case, and in PTIME when . Questions: Is TARGET XP with respect to , i.e., is it solvable in polynomial time when is fixed? Is it FPT with respect to , i.e., can it be solved in time with a polynomial and the protocol? We have established during Autoboz that the problem is in fct W[2]-hard with respect to r. Remain open questions are: is it FPT with respect to ? is it in XP with respect to ? in particular, is in in PTIME for ?
