Communicating Processes, Scheduling, and the Complexity of Nondeterminism.
Journal
Mathematical Systems Theory
Journal Volume
23
Journal Issue
1
Pages
33-59
Date Issued
1990
Author(s)
Abstract
In this paper we study the computational complexity of the nontermination problem for systems of communicating processes with respect to five types of scheduling schemes, namely, round-robin, random, priority, first-come-first-served, and equifair schedules. We show that the problem is undecidable (Π1-complete) with respect to round-robin, first-come-first-served, and priority scheduling; whereas it is decidable with respect to random and equifair scheduling. (Here Π1 denotes the set of languages whose complements are recursively enumerable.) For a restricted class of systems in which the communication channels between processes are of unit capacity, we show that the nontermination problem is solvable in O(k2 log n) nondeterministic space for round-robin, random, priority, and first-come-first-served scheduling, and in no(k2) nondeterministic time for equifair scheduling, where k is the number of processes and n is the size of the maximal process. We are also able to establish a lower bound of Ω((k-59)/20*log n) nondeterministic space for all five types of scheduling schemes. © 1990 Springer-Verlag New York Inc.
SDGs
Type
journal article