Alternating polynomial-time Turing machines, as introduced by Chandra, Kozen, and Stockmeyer [1], are polynomial-time machines that can alternate between universal blocks (in which a node accepts if all its children accept) and existential blocks (in which a node accepts if at least one of its children accepts). Chandra, Kozen, and Stockmeyer showed that these machines capture the essence of many complexity classes. For example, alternating polynomial time is exactly PSPACE, and the levels of the polynomial hierarchy--NP, coNP, NP^NP, coNP^NP, and so on--can be precisely characterized via alternating machines.

This paper introduces a restriction to the alternating machine model--a synchronization primitive. Described informally, the primitive works as follows. A computation path may execute a command WAIT( I ), where I is one of a finite set of integers. The computation path is then suspended until all processes are either completed or are also waiting for the same I, in which cases the path continues. If two paths suspend themselves waiting for different events, however, we have a synchronization fault, and the entire machine by definition rejects the inputs.

The motivation for adding this synchronization primitive is to model some degree of communication between paths. The model seems relatively natural (though the synchronization rules in some sense cut across alternation blocks--how would one intuitively motivate this?), and the body of the paper is a detailed study of this model and its relationship to earlier models of computation (see also the other references cited in the paper). The particular relationships explored are fundamental automata-theoretic issues, such as the effects of the number of tapes, the number of heads, one-way versus two-way input, the number of reversals, the time used, and the space used. For example, any two-way (one-way) k-head t-tape synchronized alternating machine can be simulated relatively efficiently in terms of time, space, and degree of parallelism by a two-way (one-way) k-head ( t + 1 )-tape alternating machine whose last tape is an auxiliary pushdown store using only one reversal. Intuitively, the stack-like tape is used to store a nondeterministic guess of the sequence of WAIT(&dundot;) events; this is the general flavor of many of the proofs. The paper presents a thought-provoking model for which interesting results have been obtained in this paper and in the other papers cited therein.