Scalable Multi-Input–Multi-Output Queues With Application to Variation-Tolerant Architectures

A queue typically connects a producer and a consumer and improves the overall performance by smoothening irregular production and consumption over time. In this paper, we introduce so-called multiple-input–multiple-output (MIMO) queues, connecting $N_{P}$ producers with $N_{C}$ consumers, that are symmetric, scalable, and have a high throughput. MIMO queues can be used to perform fine-grained load balancing and are proposed as key building blocks for variation-tolerant architectures. We present and analyze a family of asynchronous MIMO queues.      

Repeated use of codes which detect deception (Corresp.)

A senderAwants to sendNmessagesx_{i} = 1 , ldots ,N, chosen from a set containingMdifferent possible messages,M > N, to a receiverB. Everyx_{i}has to pass through the hands of a dishonest messengerC. ThereforeAandBagree on a mathematical transformationfand a secret parameter, or keyk, that will be used to produce the authenticatory_{i} = f(x_{i} , k ), which is sent together withx. The key is chosen at random from a set ofLelements.Cknowsfand can find all elements in the setG(x_{i},y_{i}) = {k|f(x_{i}, k) = y_{i}}given enough time and computer resources.Cwants to changex_{i} into x^{prime}withoutBsuspecting. This means thatCmust find the new anthenticatory^{prime} = f(x^{prime} , k). SinceG(x_{i},y_{i})can be found for any(x_{i},y_{i}), it is obvious thatCwill always succeed unlessG(x_{i},y_{i})contains more than one element. Here it is proved that the average probability of success forCis minimized if (a)G(x_{i}, y_{i})containsL^{(N-1)/N}elements and (b) each new known pair(x_{j}, y_{j})will diminish this set of solutions by a factor ofL^{-l/N}. The minimum average probability will then beL^{-l/N}.     

Some periodic convolutional codes better than any fixed code (Corresp.)

Some(n_{o}=2; k_{o}=1)noncatastrophic periodic convolutional codes with memoryM=4are given that have the same free distance,d_{infty}, as the best fixed code but have both a smaller number of paths of weightd_{infty}per time instant and a smaller average number of information bit errors per such path for periodsT=2, 3, 4, and5. It is also shown that an(n_{0}, k_{0})code of periodTis equivalent to a fixed code with parameters(Tn_{0}, Tk_{0}).     

On the capacity of infinite population multiple access protocols

We present bounds on the maximum channel utilization (with finite average delay) of synchronous multiple access communications protocols serving an infinite population of homogeneous stations. Messages arrive to the system as a series of independent Bernoulli trials in discrete time, with probability p of an arrival at each arrival point (the Poisson limit is explicitly included) and are then randomly distributed among the stations. Pippenger showed that the channel utilization cannot exceedxi_{p}, wherexi_{l}=1andlim_{p rightarrow 0} xi_{p} approx 0.744. Using a "helpful genie" argument, we find the exact capacity for allp geq 0.568(where we find optimal protocols that obey first-come first-served); for smaller values of p, we present an improved upper bound that decreases monotonically toapprox 0.6731in the Poisson limit asp rightarrow 0.     

Computation of packet response time via Lagrange series expansion

Packets are processed in bulk at the nodes of a computer communication network. A complete analytical solution of the packet response time in a node processor is derived. The node processor is modelled as an M/M^[K]/1 queue. In this queue, the packets arrive according to a Poisson process, and the service times are exponentially distributed. In each service period the number of packets served is the minimum of K and the number of packets present in the queue. In existing literature it is assumed implicitly that a root of a polynomial equation, lying in the interval (0, 1), will be evaluated numerically. A Lagrange series expansion of a root of this polynomial equation of degree (K+1) is derived. The proposed solution technique can be used for evaluating analytically other Markovian bulk service queues, and also the E_r/M/1 queue     

Further classifications of codes meeting the Griesmer bound (Corresp.)

For any(n, k, d)binary linear code, the Griesmer bound says thatn geq sum_{i=0}^{k-1} lceil d/2^{i} rceil, wherelceil x rceildenotes the smallest integergeq x. We consider codes meeting the Griesmer bound with equality. These codes have parametersleft( s(2^{k} - 1) - sum_{i=1}^{p} (2^{u_{i}} - 1), k, s2^{k-1} - sum_{i=1}^{p} 2^{u_{i} -1} right), wherek > u_{1} > cdots > u_{p} geq 1. We characterize all such codes whenp = 2oru_{i-1}-u_{i} geq 2for2 leq i leq p.     

An algorithm for maximizing expected log investment return

Let the random (stock market) vectorX geq 0be drawn according to a known distribution functionF(x), x in R^{m}. A log-optimal portfoliob^{ast}is any portfoliobachieving maximal expectedlogreturnW^{ast}=sup_{b} E ln b^{t}X, where the supremum is over the simplexb geq 0, sum_{i=1}^{m} b_{i} = 1. An algorithm is presented for findingb^{ast}. The algorithm consists of replacing the portfoliobby the expected portfoliob^{'}, b_{i}^{'} = E(b_{i}X_{i}/b^{t}X), corresponding to the expected proportion of holdings in each stock after one market period. The improvement inW(b)after each iteration is lower-bounded by the Kullback-Leibler information numberD(b^{'}|b)between the current and updated portfolios. Thus the algorithm monotonically improves the returnW. An upper bound onW^{ast}is given in terms of the current portfolio and the gradient, and the convergence of the algorithm is established.     

When does the modular distance induce a metric in the binary case? (Corresp.)

The modular distance induces a metric if and only if the nonadjacent form of the modulusMhas one of the following forms:1) 2^{n}+2^{n-2} pm 2^{i}, wheren-igeq 4; 2) 2^{n} - 2^{j} pm 2^{i}, where2 leq n -j leq 5andj-igeq 2; 3) 2^{n} pm 2^{j}, wheren -j geq 2; 4) 2^{n}.     

Higher dimensional orthogonal designs and applications

The concept of orthogonal design is extended to higher dimensions. A properg-dimensional design[d_{ijk cdots upsilon}]is defined as one in which all parallel(g-1)-dimensional layers, in any orientation parallel to a hyper plane, are uncorrelated. This is equivalent to the requirement thatd_{ijk cdots upsilon} in {0, pm x_{1}, cdots , pm x_{t} }, wherex_{1}, cdots , x_{t}are commuting variables, and thatsum_{p} sum_{q} sum_{r} cdots sum_{y} d_{pqr cdots ya} d_{pqr cdots yb} = left( sum_{t} s_{i}x_{i}^{2} right)^{g-1} delta ab,where(s{1}, cdots , s{t})are integers giving the occurrences ofpm x_{1}, cdots , pm x_{t}in each row and column (this is called the type(s_{1}, cdot ,s_{t})^{g-1})and(pqr cdots yz)represents all permutations of(ijk cdots upsilon). This extends an idea of Paul J. Shlichta, whose higher dimensional Hadamard matrices are special cases withx_{1}, cdots , x_{t} in {1,- 1}, (s_{1}, cdots, s_{t})=(g), and(sum_{t}s_{i}x_{i}^{2})=g. Another special case is higher dimensional weighing matrices of type(k)^{g}, which havex_{1}, cdots , x_{t} in {0,1,- 1}, (s_{1}, cdots, s_{t})=(k), and(sum_{t}s_{i}x_{i}^{2})=k. Shlichta found properg-dimensional Hadamard matrices of size(2^{t})^{g}. Proper orthogonal designs of type     

A proof of the data compression theorem of Slepian and Wolf for ergodic sources (Corresp.)

If{(X_i, Y_i)}_{i=1}^{infty}is a sequence of independent identically distributed discrete random pairs with(X_i, Y_i) ~ p(x,y), Slepian and Wolf have shown that theXprocess and theYprocess can be separately described to a common receiver at ratesR_XandR_Yhits per symbol ifR_X + R_Y > H(X,Y), R_X > H(XmidY), R_Y > H(YmidX). A simpler proof of this result will be given. As a consequence it is established that the Slepian-Wolf theorem is true without change for arbitrary ergodic processes{(X_i,Y_i)}_{i=1}^{infty}and countably infinite alphabets. The extension to an arbitrary number of processes is immediate.     

Dual product constructions of Reed - Muller type codes (Corresp.)

Various linear and nonlinearR(r,m)codes having parameters(2^{m}, 2^{k}, 2^{m-r})withk=sum_{i=0}^{r}left(^{m}_{i}right)are constructed fromR(r,q)andR(r,p)codes,m=p+q. A dual construction forR(m-r,m)codes fromR(p-r,p)andR(q-r,q)codes is also presented,m=p+q. As a simple corollary we have that the number of nonequivalentR(r,m)codes is at least exponential in the length (forr>1). ForR(m-r,m)codes, the lower bound is doubly exponential in the length (forr>1).     

The imperfectly conducting cylindrical transmitting antenna: Numerical results

The complex wave number, the distribution of current, the admittance, and the radiating efficiency of cylindrical antennas made of imperfect conductors are evaluated numerically from a previously derived theory[1]. The quantity2lambda r^{i}/zeta_{0}(wherer^{i}is the resistance per unit length,lambdais the free-space wavelength, andzeta_{0} = 377ohms) is used as the parameter in a range that extends from zero to 200. Extensive graphs and tables are given.     

Some equivalences between Shannon entropy and Kolmogorov complexity

It is known that the expected codeword lengthL_{UD}of the best uniquely decodable (UD) code satisfiesH(X)leqL_{UD}. LetXbe a random variable which can take on n values. Then it is shown that the average codeword lengthL_{1:1}for the best one-to-one (not necessarily uniquely decodable) code forXis shorter than the average codeword lengthL_{UD}for the best uniquely decodable code by no more than(log_{2} log_{2} n)+ 3. LetYbe a random variable taking on a finite or countable number of values and having entropyH. Then it is proved thatL_{1:1}geq H-log_{2}(H + 1)-log_{2}log_{2}(H + 1 )-cdots -6. Some relations are established among the Kolmogorov, Chaitin, and extension complexities. Finally it is shown that, for all computable probability distributions, the universal prefix codes associated with the conditional Chaitin complexity have expected codeword length within a constant of the Shannon entropy.     

Performance of the biased square-law sequential detector in the absence of signal

G. E. Albert's general sequential test for making one of r distinct decisions about a distribution functionF(x_{i}|x_{i-1})by observing a sequence ofx_{i}'s is presented, and his results, which give the performance of this test as the solutions of integral equations, are stated. This test is more general than the usual sequential probability ratio test of Wald, and includes nonoptimum, as well as Wald's optimum, sequential tests. Albert's equations are used to treat the incoherent detection of a sine wave in Gaussian noise by a biased square-law detector. This is the detector which uses samplesy_{i}of the envelope of the received waveform to calculate the sumsx_{i} = k sum_{j=1}^{i} (yj^{2} -bias), i = 1, 2, cdots, and sequentially compares thex_{i}to two thresholds until anx_{i}is found which is less than the lower thresholdB, or greater than the upper thresholdA. Then ifx_{i} leq B, it is decided that the signal is not present (dismissal), and ifA leq x_{i}it is decided that the signal is present (alarm). Though this is not the optimum detector for a sine wave in Gaussian noise (unless the SNR is very small), it is a convenient test to implement and is of considerable interest in its own right. Fory_{i}having the Rayleigh probability distributionf(y) = y exp{-y^{2}/2}, i.e., for the received waveform consisting of Gaussian noise alone, {em exact} solutions are obtained for the probability of (false) alarm and for the average test duration. These results are unique in that they are valid without restrictions on either the design input SNR or on the thresholds A and B. Curves of the probability of false alarm vs. the upper threshold A, and of the average test duration vs. the expected input SNR are presented, and are compared to similar results of Wald.     

On certain projective geometry codes (Corresp.)

LetVbe an(n, k, d)binary projective geometry code withn = (q^{m}-1)/(q - 1), q = 2^{s}, andd geq [(q^{m-r}-1)/(q - 1)] + 1. This code isr-step majority-logic decodable. With reference to the GF(q^{m}) = {0, 1, alpha , alpha^{2} , cdots , alpha^{n(q-1)-1} }, the generator polynomialg(X), ofV, hasalpha^{nu}as a root if and only ifnuhas the formnu = i(q - 1)andmax_{0 leq l < s} W_{q}(2^{l} nu) leq (m - r - 1)(q - 1), whereW_{q}(x)indicates the weight of the radix-qrepresentation of the numberx. LetSbe the set of nonzero numbersnu, such thatalpha^{nu}is a root ofg(X). LetC_{1}, C_{2}, cdots, C_{nu}be the cyclotomic cosets such thatSis the union of these cosets. It is clear that the process of findingg(X)becomes simpler if we can find a representative from eachC_{i}, since we can then refer to a table, of irreducible factors, as given by, say, Peterson and Weldon. In this correspondence it was determined that the coset representatives for the cases ofm-r = 2, withs = 2, 3, andm-r=3, withs=2.     

Bent-function sequences

In this paper we construct a new family of nonlinear binary signal sets which achieve Welch's lower bound on simultaneous cross correlation and autocorrelation magnitudes. Given a parameternwithn=0 pmod{4}, the period of the sequences is2^{n}-1, the number of sequences in the set is2^{n/2}, and the cross/auto correlation function has three values with magnitudesleq 2^{n/2}+1. The equivalent linear span of the codes is bound above bysum_{i=1}^{n/4}left(stackrel{n}{i} right). These new signal sets have the same size and correlation properties as the small set of Kasami codes, but they have important advantages for use in spread spectrum multiple access communications systems. First, the sequences are "balances," which represents only a slight advantage. Second, the sequence generators are easy to randomly initialize into any assigned code and hence can be rapidly "hopped" from sequence to sequence for code division multiple access operation. Most importantly, the codes are nonlinear in that the order of the linear difference equation satisfied by the sequence can be orders of magnitude larger than the number of memory elements in the generator that produced it. This high equivalent linear span assures that the code sequence cannot be readily analyzed by a sophisticated enemy and then used to neutralize the advantages of the spread spectrum processing.     

Input Versus Output Queueing on a Space-Division Packet Switch

Two simple models of queueing on anN times Nspace-division packet switch are examined. The switch operates synchronously with fixed-length packets; during each time slot, packets may arrive on any inputs addressed to any outputs. Because packet arrivals to the switch are unscheduled, more than one packet may arrive for the same output during the same time slot, making queueing unavoidable. Mean queue lengths are always greater for queueing on inputs than for queueing on outputs, and the output queues saturate only as the utilization approaches unity. Input queues, on the other hand, saturate at a utilization that depends onN, but is approximately(2 -sqrt{2}) = 0.586whenNis large. If output trunk utilization is the primary consideration, it is possible to slightly increase utilization of the output trunks-upto(1 - e^{-1}) = 0.632asN rightarrow infty-by dropping interfering packets at the end of each time slot, rather than storing them in the input queues. This improvement is possible, however, only when the utilization of the input trunks exceeds a second critical threshold-approximatelyln (1 +sqrt{2}) = 0.881for largeN.     

An approximation to the weight distribution of binary primitive BCH codes with designed distances 9 and 11 (Corresp.)

Recently Kasami {em et al.} presented a linear programming approach to the weight distribution of binary linear codes [2]. Their approach to compute upper and lower bounds on the weight distribution of binary primitive BCH codes of length2^{m} - 1withm geq 8and designed distance2t + 1with4 leq t leq 5is improved. From these results, the relative deviation of the number of codewords of weightjleq 2^{m-1}from the binomial distribution2^{-mt} left( stackrel{2^{m}-1}{j} right)is shown to be less than 1 percent for the following cases: (1)t = 4, j geq 2t + 1andm geq 16; (2)t = 4, j geq 2t + 3and10 leq m leq 15; (3)t=4, j geq 2t+5and8 leq m leq 9; (4)t=5,j geq 2t+ 1andm geq 20; (5)t=5, j geq 2t+ 3and12 leq m leq 19; (6)t=5, j geq 2t+ 5and10 leq m leq 11; (7)t=5, j geq 2t + 7andm=9; (8)t= 5, j geq 2t+ 9andm = 8.     

On the Probability Density Function of the Squared Envelope of a Sum of Random Phase Vectors

A recursive solution is presented for the probability density function of the sum ofNindependent, random phase vectors. The recursion parameter isN, the number of vectors in the sum. This approach allows one to rapidly compute a complete set of these density functions for values ofN = 2, 3, ..., N_{max}, where Nmaxtypically corresponds to the total number of system users in a multiuser FHMA/MFSK application, or one plus the total number of jamming tones in an FH/MFSK spread-spectrum application. Such evaluations are necessary for exact calculation of the average error probability performance of such systems.