← All problems
Unverified

TARGET in asynchronous shared-memory systems

An asynchronous shared-memory system is composed of nn processes that interact by reading from and writing to a shared memory. This shared memory is composed of rr registers, each containing one symbol at a time from the finite alphabet DD. 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 readi(d)read_i(d) or writei(d)write_i(d) with i∈{1,…,r}i \in \{1,\dots,r\} and d∈Dd \in D. 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 nn, all nn processes are on state q0q_0 while all registers have initial value d0d_0. TARGET asks whether there exists n≥1n \geq 1 such that, from the initial configuration of size nn, there is an execution that puts all processes on some distinguished state qfq_f. This problem is known to be NP-complete in the general case, and in PTIME when r=1r=1. Questions: Is TARGET XP with respect to rr, i.e., is it solvable in polynomial time when rr is fixed? Is it FPT with respect to rr, i.e., can it be solved in time O(f(r)p(∣P∣))O(f(r) p(|P|)) with pp a polynomial and PP 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 r+∣D∣r + |D|? is it in XP with respect to rr? in particular, is in in PTIME for r=2r = 2?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu