A priority channel system (PCS) is a computational model where nondeterministic finite automata communicate over a faulty network.[1] They augment lossy channel systems with a new feature — agents which can mark certain messages as more important than others so they are less likely to be dropped. Initially defined by Christopher Haase et al. in 2014, they are notable in that certain LCS-related verification problems achieve a computational complexity of \(\mathbf{F}_{\varepsilon_0}\)-complete, using a complexity class analog of the fast-growing hierarchy.
Definition[]
The original paper contains a formal definition of PCS syntax and semantics. What follows here is a more intuitive and informal approach.
A level-\(d\) PCS has a set of \(m\) channels, a finite number of states, and a transition table. Each channel is a string consisting of numbers from 0 to d inclusive. Each number should be thought of as a message, and the value of the number is its priority. 0 is the lowest priority, and d is the highest.
The transition table contains a number of productions, which consist of the following:
- The initial state.
- The channel c to read or write from.
- An opcode, which can be either ? (read) or ! (write).
- The message a to be written or read.
- The successive state.
The transition table can be thought of as a directed multigraph where the nodes are states and the productions are edges, placed according to their initial and successive states.
Agents[]
PCS simulation is done with one or more nondeterministic agents. Multiple agents can run on a single PCS, in which any agent is chosen at each step. Concurrent agents share channels but otherwise do not interact.
A PCS agent has an internal state. It may either make a reliable step, where the agent receives or transmits messages, or an internal superseding step, which simulates the network dropping low-priority messages.
For a reliable step, the agent selects a production with a matching initial state. What it does next depends on the opcode:
- If the opcode is ?, the agent looks at the selected channel c and ensures that the first message is a. It then removes a from that channel. If the first message is not a, then the agent is not allowed to use this production.
- If the opcode is !, the agent appends a to channel c.
After executing the opcode, the agent moves on to the successive state of the production. Note that the read operation removes from the beginning of the string, and the write operation adds to the end of the string. In this way, channel strings can be thought of as first-in first-out stacks.
For an internal superseding step, the agent selects a channel containing two messages, a and b, with \(a \leq b\) and a coming immediately before b in the channel. The agent removes a from the channel and its state remains unchanged. For example, the channel [[1]] can be reduced repeatedly as follows: 015543521 → 01543521 → 0154521 → 054521 → 54521 → 5521 → 521.
A simulation is repeated application of PCS agent steps. A simulation is maximal iff it goes on infinitely or halts. Halting is defined as reaching a configuration where no further steps are possible (i.e. no internal superseding steps are possible and all matching productions are inapplicable read instructions).
Properties[]
Like LCSs, for PCSs, Boundedness and Recurrent Reachability are undecidable but Reachability and Inevitability are (see LCS properties). The latter two problems are so difficult that their complexity classes are googologically large. For \(\alpha \leq \varepsilon_0\), we define the class of functions \(\mathscr{F}_\alpha\) as
\[\mathscr{F}_\alpha = \bigcup_{c < \omega} \text{FDTIME}(f_\alpha^c(n))\]
and the complexity class \(\mathbf{F}_\alpha\) as
\[\mathbf{F}_\alpha = \bigcup_{p \in \mathscr{F}_{<\alpha}} \text{DTIME}(f_\alpha(p(n)))\]
where \(\mathscr{F}_{<\alpha}\) is a shorthand for \(\bigcup_{\beta < \alpha} \mathscr{F}_\alpha\). Here, \(f\) represents the fast-growing hierarchy. Haase et al. showed that the problems of Reachability and Inevitability are \(\mathbf{F}_{\varepsilon_0}\)-complete.
Priority channel systems are a variant of lossy channel systems (LCSs). LCSs do not have message prioritization, and network loss can cause any message to drop. The PCS computational model may seem more restrictive than that of LCSs, but in fact PCSs are stronger and can simulate any LCS, and even some higher-order LCS models.
Sources[]
See also[]
Bignum Bakeoff contestants: pete-3.c · pete-9.c · pete-8.c · harper.c · ioannis.c · chan-2.c · chan-3.c · pete-4.c · chan.c · pete-5.c · pete-6.c · pete-7.c · marxen.c · loader.c
Channel systems: lossy channel system · priority channel system
Concepts: Recursion