Let ${\cal G}_d (n)$ be the set of d-regular simple graphs with n vertices, and for $G = (V,E)$ in ${\cal G}_d (n)$ let $f: V \to \{1,2, \ldots, n \}$ be a bijective coloring of the vertices of G. Also let $\alpha$ denote an interference parameter in $\{0,1, \ldots, n-1 \}$, and define the interference number of f with respect to G and $\alpha$ as the number of edges $\{u,v\}$ in E for which $\min \{ | f(u) - f(v) |$, $n- | f(u) - f(v) | \} \le \alpha$. We consider two interference number problems for feasible $(n, \alpha, d)$. The first is to specify a $G \in {\cal G}_d (n)$ and an f for which the interference number is as small as possible. The second is to determine a $G \in {\cal G}_d (n)$ whose minimum interference number over all f is as large as possible. A previous paper completely solves both problems for d = 2. The present paper solves the first problem for all $d \ge 3$ and obtains partial results for the second problem for $d \ge 3$ that focus on interference-minimizing f's when G consists of disjoint copies of $K_{d+1}$.

Communications problems that involve frequency interference, such as the channel assignment problem in the design of cellular telephone networks, can be cast as graph coloring problems in which the frequencies (colors) assigned to an edge's vertices interfere if they are too similar. The paper considers situations modeled by vertex-coloring d-regular graphs with n vertices using a color set 1, 2,..., n, where colors i and j are said to interfere if their circular distance $\min \{ | i-j | , n- | i-j | \}$ does not exceed a given threshold value $\alpha$. Given a d-regular graph G and threshold $\alpha$, an interference-minimizing coloring is a coloring of vertices that minimizes the number of edges that interfere. Let $I_\alpha (G)$ denote the minimum number of interfering edges in such a coloring of G. For most triples $(n, \alpha ,d),$ we determine the minimum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain it. In determining when this minimum value is 0, we prove that for $r \geq 3$ there exists a d-regular graph G on n vertices that is r-colorable whenever $d \leq (1- \frac{1}{r}) n-1$ and nd is even. We also study the maximum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain this maximum in many cases.

We consider schemes for reuse-efficient packet access in wireless data networks. We show that computing the maximum ergodic packet arrival rate is NP-hard. We give an upper bound on the maximum ergodic throughput in terms of the eigenvalues of matrices related to the path-gain matrix. We present simple, practical heuristic algorithms which exhibit good throughput and packet delay and report on results of preliminary simulations. More sophisticated algorithms that yield optimal throughput are also presented. A recent result of McKeown, Anantharam and Walrand (1996) on scheduling of input-queued switches is obtained as a by-product.

A double-loop network with hop constants h1, h2, DL(n, h1, h2) may be represented as a directed graph with n nodes 0, 1, …, n − 1 and 2n links of the form i → i + h1mod n and i → i + h2mod n (referred to as h1-links and h2-links). They have been proposed as architectures for local area networks and for data alignment in SIMD processors, among other applications. Three reliability models of double-loop networks have been studied in the literature. In the link model, nodes always work and each link fails independently with probability p. Hwang and Li showed that for p small DL(n, 1, 1 + n/2) is most reliable for n even, and DL(n, 1, 2) is most reliable for n odd. In the node model, links always work and each node fails independently with probability p. Hu et al. showed that for p small DL(n, 1, 1 + ⌈n/2⌉) is the most reliable. However, no nonenumerative algorithms were given to compute the reliabilities of these most reliable networks except DL(n, 1, 1 + n/2) for even n under the node model. Recently, Hwang and Wright proposed a novel approach to compute the reliabilities of double-loop networks under the uniform model that each node fails with probability p, each h1-link with probability p1, and each h2-link with probability p2, and the failures are independent. In particular, they obtained the reliabilities for DL(n, 1, 2). In this paper, we applied their approach to compute the reliabilities of DL(n, 1, 1 + ⌈n/2⌉) under the uniform model, except that for n odd we need the assumption that h1-links always work. Note that even under this additional assumption our reliability model is more general than is the node model, the original model under which DL(n, 1, 1 + ⌈n/2⌉) is found to be most reliable for n odd. We also used this approach to obtain the reliabilities of DL(n, 1, n − 2), known as the daisy chain in the literature. © 1997 John Wiley & Sons, Inc. Networks 30: 81–90, 1997

Three of the most well known double-loop networks are the distributed double-loop computer network (DDLCN), the daisy chain, and the braided ring. We compute the exact reliabilities of all three networks. We also extend the results on double-loop networks to directed chordal rings.

The nonpreemptive scheduling of $n \geqslant 1$ stochastic jobs is considered to minimize the expected number of parallel machines needed to meet given waiting-time constraints. The number of machines available is unlimited. The running times of the jobs are denoted $T_1 , \ldots ,T_n $ and are taken to be independent samples of an exponentially distributed random variable T with mean 1. Job waiting times are to be bounded stochastically by a nonnegative random variable W, independent of $T_1 , \ldots ,T_n $. At time zero, a timer is started with an initial value W, and job scheduling begins. When the timer expires, all jobs still waiting for a machine are assigned to available machines. Only the distributions of W and the job durations $T_1 , \ldots ,T_n $ are known to the scheduler in advance. A scheduling policy is defined which is proven to be optimal when W has an exponential distribution, and is asymptotically optimal as $n \to \infty $, when W is a constant (hard-deadline). In the exponential case, an explicit formula for the cost function is derived. The uniqueness question is also resolved. The paper concludes with a partial analysis of the general hard-deadline problem, which leads to a policy that we think is optimal. A proof of optimality, however, remains an open problem.

This paper provides an examination of an abstract moving-server system that models several computer applications, including software debugging and accessing compressed data. In this model, the server moves on the unit interval $[0,1]$, serving requests where they are encountered. The locations of successive requests are not known in advance, but they are known to be independent samples from a given distribution F on $[0,1]$. Before serving a request, the server must be moved to a reset point to the left of the request. There is a choice of two reset points, one fixed at 0 and one, called the checkpoint, that can be moved in the course of serving requests. The cost of serving a request is proportional to the distance moved to the request from the chosen reset point. This paper formulates a stochastic optimization problem whose solution, for a wide class of distributions F, yields a policy for deciding the successive locations of the checkpoint so as to minimize the expected total cost of serving a sequence of requests. Results for both finite and infinite-horizon variations of the problem are presented, along with the properties required of the distribution F.

We analyze the concurrent-read exclusive-write protocol for access to a shared resource, such as occurs in database and distributed operating systems. Readers arrive according to a Poisson process and acquire shareable i.e., non-exclusive, locks which, once granted, are released after a generally distributed random period. Writers arrive according to an arbitrary renewal process and acquire exclusive locks which, once granted, are held for a random time which is also generally distributed. Locks are granted in the order in which requests are received.We derive necessary and sufficient conditions under which the queue is stable i.e., the Iatencies for reader/writer lock acquisition have a limiting distribution. In the unstable case, the delays of successive readers/writers become unbounded. The stability condition is sensitive to the interarrival-time distribution of the writers and the lock holding-time distribution of the readers but depends only on the mean lock holding-time of the writers.Distributional and moment bounds are given for the latencies of read/write requests.

A simple model of master/slave processors is presented, along with two simple, practical scheduling algorithms. An approximate analysis of the model yields simple formulas for performance measures in terms of the hardware and workload parameters, and gives insight into the power and the limitations of master/slave systems. In particular, formulae are obtained for the maximal processing power (throughput) of the system, a quantity that remains bounded as the number of slave processors increases. This analysis is applicable to symmetric multiprocessors, where performance considerations such as cache performance may dictate asymmetric assignment of system tasks to the processors.>