We consider the problem of scheduling packets of different lengths via k directed parallel communication links. The links are prone to simultaneous errors --- if an error occurs, all links are affected. Dynamic packet arrivals and errors are modelled by a worst-case adversary. The goal is to optimize competitive throughput of online scheduling algorithms. Two types of failures are considered: jamming, when currently scheduled packets are simply not delivered, and crashes, when additionally the channel scheduler crashes losing its current state. For the former, milder type of failures, we prove an upper bound on competitive throughput of 3/4 - 1/(4k) for odd values of k, and 3/4 - 1/(4k+4) for even values of k. On constructive side, we design an online algorithm that, for packets of two different lengths, matches the upper bound on competitive throughput. To compare, scheduling on independent channels, that is, when adversary could cause errors on each channel independently, reaches throughput of 1/2. This shows that scheduling under simultaneous jamming is provably more efficient than scheduling under channel-independent jamming. In the setting with crash failures we prove a general upper bound for competitive throughput of (√5-1)/2 and design an algorithm achieving it for packets of two different lengths. This result has two interesting implications. First, simultaneous crashes are significantly stronger than simultaneous jamming. Second, due to the above mentioned upper bound of 1/2 on throughput under channel-independenterrors, scheduling under simultaneous crashes is significantly stronger than channel-independent crashes, similarly as in the case of jamming errors.

The sizes of permutation networks and planar permutation networks for special sets of permutations are investigated. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are established here. The two main results are as follows: A consequence of our results is the construction of a 4-degree network which can simulate each communication step of any hypercube algorithm using edges from at most a constant number of different dimensions in one communication step in $O(\log\log N)$ communication steps. An essential improvement of gossiping in vertex-disjoint path mode in bounded-degree networks follows.

We consider comparator networks M that are used repeatedly: while the output produced by M is not sorted, it is fed again into M . Sorting algorithms working in this way are called periodic . The number of parallel steps performed during a single run of M is called its period , the sorting time of M is the total number of parallel steps that are necessary to sort in the worst case. Periodic sorting networks have the advantage that they need little hardware (control logic, wiring, area) and that they are adaptive. We are interested in comparator networks of a constant period, due to their potential applications in hardware design. Previously, very little was known on such networks. The fastest solutions required time O(n ε ) where the depth was roughly 1/ε. We introduce a general method called periodification scheme that converts automatically an arbitrary sorting network that sorts n items in time T(n ) and that has layout area A(n ) into a sorting network that has period 5, sorts ***( n • T ( n ) items in time O(T( )• log n ), and has layout area O(A(n) ) • T(n )). In particular, applying this scheme to Batcher's algorithms, we get practical period 5 comparator networks that sort in time O (log 3 n ). For theoretical interest, one may use the AKS netork resulting in a period 5 comparator network with runtime O (log 2 n ).

A periodic comparator network has depth (or period) k, if for every t>k, the compare-exchange operations performed at step t are executed between exactly the same registers as at step t-k. We introduce a general method that converts an arbitrary comparator network that sorts n items in time T(n) and that has layout area A into a periodic sorting network of depth 5 that sorts /spl Theta/(n/spl middot/T(n)) items in time O(T(n)/spl middot/log n) and has layout area O(A/spl middot/T(n)). This scheme applied to the AKS network yields a depth 5 periodic comparator network that sorts in time O(log/sup 2/ n). More practical networks with runtime O(log/sup 3/ n) can be obtained from Batcher's networks. Developing the techniques for the main result, we improve some previous results: Let us fix a d/spl isin/N. Then we can construct a network of depth 3 based on a d-dimensional mesh sorting n items in time O(n/sup 1/d//spl middot/log/sup O(d/) n).>

Alternating Turing machines (ATMs) with bounded number of reversals are considered. It is proved that the machines making fewer than $\log ^{*} n$ reversals can recognize only regular languages. On the other hand, the class of languages that can be recognized by ATMs using $\log ^{*} n$ reversals is very wide. The authors prove that above this limit even a slight increase of the number of reversals leads to a considerably larger class of languages. It is also proved that every $T(n)$-time bounded ATM may be replaced by an equivalent machine working in the same time and making no more than $\log ^{*} (T(n))$ reversals.

Every single-tape Turing machine (TM) of time complexity $T(n) \geqq n^{2}$ can be simulated by a single-tape TM in space $T^{{1 / 2}}(n)$. It is shown that the time of the simulation can be bounded by $T^{3/2}(n)$ in the case of deterministic TMs and by $T(n)$ in the case of nondeterministic ones. Similar results are shown for off-line machines and for machines with multidimensional tape.

The reversal complexity of alternating Turing machines (ATM) is investigated. The strict lower bounds on reversals for recognizing nonregular languages by Sigma /sub k/ machines are settled. Some results relating reversal and space complexities are obtained.>