Search

Sex Transm Infect 2004;80:68-71. doi: 10.1136/sti.2003.006239 Objective: Development of a rapid, sensitive, and accurate assay for confirmation of Neisseria gonorrhoeae in clinical samples. Method: Two real time polymerase chain reaction [...]

Results are summarized from an empirical study directed at the measurement of program operating behavior in those multiprogramming systems in which programs are organized into fixed length pages. The data collected from the interpretive execution of a number of paged programs are used to describe the frequency of page faults, i.e. the frequency of those instants at which an executing program requires a page of data or instructions not in main (core) memory. These data are used also for the evaluation of page replacement algorithms and for assessing the effects on performance of changes in the amount of storage allocated to executing programs. [ABSTRACT FROM AUTHOR]

In his (2004), Randolph Clarke assesses an important version of an influential argument against libertarianism about metaphysical freedom. Clarke calls the anti‐libertarian argument he evaluates the Contrast Argument. It targets the following claim: there could be an undetermined free act done by S such that S would have freely done something else had S not done the act in question. This modal claim will be endorsed not only by proponents of main brands of libertarianism, but also by action theorists of other stripes – including many compatibilists. Clarke aims to defend the Contrast Argument from a prominent objection by developing a novel case for the premise under attack. I show that Clarke's attempted defense of the Contrast Argument fails, thereby protecting the relevant libertarian and compatibilist positions. In brief, Clarke's argument depends on an ambiguous principle, each available reading of which leaves some or other premise of his argument unjustified.

In this paper, I consider some issues involving a certain closure principle for Structural Justification, a relation between a cognitive subject and a proposition that’s expressed by locutions like ‘S has a source of justification for p’ and ‘p is justifiable for S’. I begin by summarizing recent work by Peter Klein that advances the thesis that the indicated closure principle is plausible but lacks Skeptical utility. I then assess objections to Klein’s thesis based on work by Robert Audi and Anthony Brueckner. One finding is that the typical statement of the relevant closure principle can express a number of different closure principles, and that recognizing this helps to resolve certain disputes.In this paper, I consider some issues involving a certain closure principle for Structural Justification, a relation between a cognitive subject and a proposition that’s expressed by locutions like ‘S has a source of justification for p’ and ‘p is justifiable for S’. I begin by summarizing recent work by Peter Klein that advances the thesis that the indicated closure principle is plausible but lacks Skeptical utility. I then assess objections to Klein’s thesis based on work by Robert Audi and Anthony Brueckner. One finding is that the typical statement of the relevant closure principle can express a number of different closure principles, and that recognizing this helps to resolve certain disputes.

In a variation of bin packing called extensible bin packing, the number of bins is specified as part of the input, and bins may be extended to hold more than the usual unit capacity. The cost of a bin is 1 if it is not extended, and the size if it is extended. The goal is to pack a set of items of given sizes into the specified number of bins so as to minimize the total cost. Adapting ideas Grötschel et al. (1981), Grötschel et al. (1988), Karmarkar and Karp (1982), Murgolo (1987), we give a fully polynomial time asymptotic approximation scheme (FPTAAS) for extensible bin packing. We close with comments on the complexity of obtaining stronger results.

Natural systems excel in directing the synthesis of inorganic materials for various functional purposes. One of the best-studied systems is silica synthesis, as occurs in diatoms and marine sponges. Various biological and synthetic polymers have been shown to template and catalyze silica formation from silicic acid precursors. Here, we describe the use of poly-l-lysine to promote the synthesis of silica in neutral, aqueous solution and when immobilized onto a silicon support structure under similar conditions. Either reagent jetting or conventional photolithography techniques can be used to pattern the templating polymer. Spots created by reagent jetting led to the creation of silica structures in the shape of a ring that may be a result of the spotting process. Photolithographically defined poly-l-lysine spots led to thin laminate structures after exposure to a dilute aqueous silicic acid solution. The laminate structures were nanostructured and highly interconnected. Photolithographic patterning of (3-aminopropyl)trimethoxysilane, a reagent that mimics the lysine functional group, led to similar silica coatings even though low-molecular-weight materials do not rapidly promote silica synthesis in solution. This result highlights the importance of functional-group arrangement for templating and promoting the synthesis of inorganic materials. The described surface-patterning techniques offer a route to integrate conventional silicon-patterning technologies with biologically based material synthesis. Such combined fabrication techniques enable controlled assembly over multiple length scales and an approach to understanding interfacial silica synthesis, as occurs in natural systems.

For a given k= 1, subintervals of a given interval [0, X] arrive at random and are accepted (allocated) so long as they overlap fewer than ksubintervals already accepted. Subintervals not accepted are cleared, while accepted subintervals remain allocated for random retention times before they are released and made available to subsequent arrivals. Thus, the system operates as a generalized many-server queue under a loss protocol. We study a discretized version of this model that appears in reference theories for a number of applications, including communication networks, surface adsorption-desorption processes, and reservation systems. Our primary interest is in steady-state estimates of the vacant space, i.e. the total length of available subintervals kX- ?li, where the liare the lengths of the subintervals currently allocated. We obtain explicit results for k= 1 and for general kwith all subinterval lengths equal to 2, the classical dimercase of chemical applications. Our focus is on the asymptotic regime of large retention times.

Robots are deployed by a Web search engine for collecting information from different Web servers in order to maintain the currency of its data base of Web pages. In this paper, we investigate the number of robots to be used by a search engine so as to maximize the currency of the data base without putting an unnecessary load on the network. We adopt a finite-buffer queueing model to represent the system. The arrivals to the queueing system are Web pages brought by the robots; service corresponds to the indexing of these pages. Good performance requires that the number of robots, and thus the arrival rate of the queueing system, be chosen so that the indexing queue is rarely starved or saturated. Thus, we formulate a multi-criteria stochastic optimization problem with the loss rate and empty-buffer probability being the criteria. We take the common approach of reducing the problem to one with a single objective that is a linear function of the given criteria. Both static and dynamic policies can be considered. In the static setting the number of robots is held fixed; in the dynamic setting robots may be re-activated/de-activated as a function of the state. Under the assumption that arrivals form a Poisson process and that service times are independent and exponentially distributed random variables, we determine an optimal decision rule for the dynamic setting, i.e., a rule that varies the number of robots in such a way as to minimize a given linear function of the loss rate and empty-buffer probability. Our results are compared with known results for the static case. A numerical study indicates that substantial gains can be achieved by dynamically controlling the activity of the robots.

Abstract: We model a server that allocates varying amounts of bandwidth to “customers” during service. Customers could be computer jobs with demands for storage bandwidth or they could be calls with demands for transmission bandwidth on a network link. Service times are constants, each normalized to 1 time unit, and the system operates in discrete time, with packing (scheduling) decisions made only at integer times. Demands for bandwidths are for fractions of the total available and are limited to the discrete set {1/k, 2/k, …, 1} wherek is a given parameter. More than one customer can be served at a time, but the total bandwidth allocated to the customers in service must be at most the total available. Customers arrive ink flows and join a queue. Thejth flow has rate λ j and contains just those customers with bandwidth demandsj/k. We study the performance of the two packing algorithms First Fit and Best Fit, both allocating bandwidth by a greedy rule, the first scanning the queue in arrival order and the second scanning the queue in decreasing order of bandwidth demand. We determine necessary and sufficient conditions for stability of the system under the two packing rules. The average total bandwidth demand of the arrivals in a time slot must be less than 1 for stability under any packing rule, i.e., the condition

We study call admission rates in a linear communication network with each call identified by an arrival time, duration, bandwidth requirement, and origin-destination pair. Network links all have the same bandwidth capacity, and a call can be admitted only if there is sufficient bandwidth available on every link along the call's path. Calls not admitted are held in a queue, in contrast to the protocol of loss networks. We determine maximum admission rates (capacities) under greedy call allocation rules such as First Fit and Best Fit for several baseline models and prove that the natural necessary condition for stability is sufficient. We establish the close connections between our new problems and the classic problems of bin packing and interval packing. In view of these connections, it is surprising to find that Best Fit allocation policies are inferior to First Fit policies in the models studied.

Since callers encountering busy signals often want to redial, modern communication networks have been designed to provide automatic redialing. Redialing services commonly have two parameters: a maximum number n of retries and a total duration τ over which retries are to be made. Typically, retries are made at evenly spaced time intervals of length τ/n until either the call succeeds or n retries have failed. This rule has an obvious intuitive appeal; indeed, among the main results of this paper are proofs that τ/n-spacing is optimal in certain basic models of called-number behavior. However, it is easy to find situations where τ/n-spacing is not optimal, as the paper verifies. All of our models assume Poisson arrivals, but different assumptions are studied for the call durations; for a given mean, these are allowed to have the relatively high-variance exponential distribution or the zero-variance distribution concentrated at a point. We approximate the probability of success for the Erlang loss model with c > 1 trunks, and we calculate exact probabilities of success for the c = 1 Erlang model and the model with one trunk and constant call durations. For the latter model, we present two intriguing conjectures, one about the optimal choice of τ when n = 1 and one about the optimality of the τ/n-spacing policy. In spite of their apparent simplicity, these conjectures seem difficult to resolve. Finally, we study policies that continue redialing until they succeed, balancing a short mean wait against a small mean number of retries to success.

A single server moves with speed ? on a line interval (or a circle) of length (circumference)L. Customers, requiring service of constant durationb, arrive on the interval (or circle) at random at mean rate ? customers per unit length per unit time. A customer's mean wait for service depends partly on the rules governing the server's motion. We compare two different servers: thepolling server and thegreedy server. Without knowing the locations of waiting customers, a polling server scans endlessly back and forth across the interval (or clockwise around the circle), stopping only where it encounters a waiting customer. Knowing where customers are waiting, a greedy server always travels toward the current nearest one. Except for certain extreme values of ?,L, b, and?, the polling and greedy servers are roughly equally effective. Indeed, the simpler polling server is often the better. Theoretical results show, in most cases, that the polling server has a high probability of moving toward the nearest customer, i.e. moving as a greedy server would. The greedy server is difficult to analyze, but was simulated on a computer.

Queueing theory has occupied an important role in the analysis of computer storage structures and algorithms. In this survey we focus on secondary or auxiliary storage devices, which often comprise the principal bottleneck in the overall performance of computer systems. We begin with descriptions of the more important devices, such as disks and drums, and a general discussion of related queueing models. Server motion and dependent successive services are salient features of these models. Widely used, generic results are presented and then applied to specific devices. The paper concludes with a discussion of open problems.

Considerable effort has been invested in devising and analyzing sequencing rules for multiprogrammed or time-shared systems. A much studied discipline of this kind is the so-called system with feedback to lower priority queues. This discipline contains many parameters, in general, which must be fixed in order to achieve the desired waiting-time performance of the discipline. In this paper the problem of synthesizing a system of the above type is solved, by setting parameter values so that prespecified waiting time criteria are satisfied, assuming Poisson arrival and general service time parameters are known.

In the bin packing problem, a list Lof nitems is to be packed into a sequence of unit capacity bins with the goal of minimizing the number of bins used. First Fit (FF) is one of the most natural on‐line algorithms for this problem, based on the simple rule that each successive item is packed into the first bin of the sequence that currently has room for it. We present an average‐case analysis of FF in the discrete uniform model: The item sizes are drawn independently and uniformly at random from the set {1/k,…,(k‐ 1)/k}, for some k> 1. Let WFF(L) denote the wasted space in the FF packing of L, i.e., the total space still available in the occupied bins. We prove that $E[W^{FF}(L)]=O(\sqrt{nk})$, i.e., there exists a constant c> 0 such that $E[W^{FF}(L)] \leq c \sqrt{nk}$for all n, ksufficiently large. By a complementary lower bound argument, we prove that this result is sharp, unless kis allowed to grow with nat a rate faster than n1/3in which case E[WFF(L)] = θ(n2/3). Finally, we show that this last result carries over to the continuous uniform model, where item sizes are chosen uniformly from [0, 1]. The O(n2/3) upper bound for the continuous model is new and solves a problem posed a decade ago. The proofs of many of these results require extensions to the theory of stochastic planar matching. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 69–101 (1997)

We consider a variant of the classical one-dimensional bin-packing problem: The number of bins is fixed and the object is to maximize the number of pieces packed from some given set. Both problems have applications in processor and storage allocation in computer systems in addition to a broad application in operations research.

Cody and Coffman have studied the problem of distributing a set of a equal-size records among the sectors of a drum-like storage device so as to minimize the average rotational latency cost. This paper is an extension of that work. We employ the same model but a different latency delay function. Motivated by the NP-completeness of the general problem and the fact that an arbitrary assignment can have an expected latency cost almost twice that of an optimal assignment, we propose and analyze a fast heuristic whose performance compares favorably with that of an optimal algorithm.

New approximation algorithms for packing rectangles into a semi-infinite strip are introduced in this paper. Within a standard probability model, an asymptotic average-case analysis is given for the wasted space in the packings produced by these algorithms.

Abstract.: Starting at time 0, unit-length intervals arrive and are placed on the positive real line by a unit-intensity Poisson process in two dimensions; the probability of an interval arriving in the time interval [t,t+ t] with its left endpoint in [y,y+ y] is t y + o( t y ). Fix x 0. An arriving interval is accepted if and only if it is contained in [0,x] and overlaps no interval already accepted. We study the number N x (t) of intervals accepted during [0,t] . By Laplace-transform methods, we derive large-x estimates of EN x (t) and VarN x (t) with error terms exponentially small in x uniformly in t (0,T) , where T is any fixed positive constant. We prove that, as , EN x (t) , VarN x (t) , uniformly in t (0,T) , where and are given by explicit, albeit complicated formulas. Using these asymptotic estimates we show that N x (t) satisfies a central limit theorem, i.e., for any fixed t where (0,1) is a standard normal random variable, and denotes convergence in distribution. This stochastic, on-line interval packing problem generalizes the classical parking problem, the latter corresponding only to the absorbing states of the interval packing process, where successive packed intervals are separated by gaps less than 1 in length. We verify that, as , (t) and (t) converge to * = 0.748 . . . and * = 0.03815 . . ., the constants of Rényi and Mackenzie for the parking problem. Thus, by comparison with the parking analysis in a single space variable, ours is a transient analysis involving both a time and a space variable. Our interval packing problem has applications similar to those of the parking problem in the physical sciences, but the primary source of our interest is the modeling of reservation systems, especially those designed for multimedia communication systems to handle high-bandwidth, real-time demands.

This paper analyzes a stochastic model of data communication. Messages are entered in a buffer by a source, and removed by a sink, at rates that are allowed to differ. The source, following message entry, and the sink, following buffer depletion, leave the buffer for independent exponentially distributed periods of absence, with different rate parameters. Locking protocols are in effect, i.e., message entry and removal can not occur simultaneously. The decision of the source or sink arriving to find the buffer active can follow either the "wait" or "no wait" option, i.e., it can wait until the buffer is free, or it can leave on another period of absence.Earlier performance studies of this model have been limited chiefly to expected values. The focus here is on the deeper questions of distribution functions and time-dependent behavior. Specifically, renewal-theoretic arguments, especially those exploiting regenerative properties, are applied to derivations of transforms of buffer-height and busy-period distributions. These transforms lead to formulas for higher moments, and in certain cases they can be inverted to yield distribution functions explicitly. Examples are worked out to illustrate the results.

We analyze a service system in which two servers move independently on the surface of the n-dimensional sphere. Requests for service arrive independently and uniformly over the surface. The ith request is to be served completely before service of the (i+1)st request begins. In an earlier paper the authors showed that the nearer server (NS) policy is optimal among all server selection policies in the sense that it minimizes the equilibrium expected angular distance E(D) which a server moves to process a request. In the present paper we obtain for all n the integral equation satisfied by the equilibrium measure for the angular distance Φ between servers under the NS policy. The equation is solved numerically. We also show that E(D)+E(Φ) = π, and unse this to compute E(D).

Computer users with very long computations run the risk of losing work because of machine failures. Such losses can often be reduced by scheduling saves on secure storage devices of work successfully done. In the model studied here, the user leaves the computation unattended for extended periods of time, after which he or she returns to check whether a machine failure occurs. When a check reveals a failure, the user resets the computation so that it resumes from the point of the last successful save.

Let S be a set of positive numbers and m an integer not less than 2. The problem is to partition S into m subsets such that the ratio of the largest subset sum to the smallest is as small as possible. Let ?g(S) be the value of this ratio using the greedy or largest-first rule and ?0(S) be the smallest possible value of this ratio, i.e., the optimal value. The authors prove that $$\frac{{\rho _g \left( S \right)}}{{\rho _0 \left( S \right)}}\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{ \leqslant } {7 \mathord{\left/ {\vphantom {7 5}} \right. \kern-\nulldelimiterspace} 5}$$ , and that this is a best possible bound for all m.

A robot is deployed by a Web search engine in order to maintain the currency of its data base of Web pages. This paper studies robot scheduling policies that minimize the fractions ri of time pages spend out-of-date, assuming independent Poisson page-change processes, and a general distribution for the page access time X. We show that, if X is decreased in the increasing convex ordering sense, then ri is decreased for all i under any scheduling policy, and that, in order to minimize expected total obsolescence time of any page, the accesses to that page should be as evenly spaced in time as possible. We then investigate the problem of scheduling to minimize the cost function ∑ciri, where the ci are given weights proportional to the page-change rates μi. We give a tight bound on the performance of such a policy and prove that the optimal frequency at which the robot should access page i is proportional to ln(hi)⁻¹, where hi:=Ee^−μiX. Note that this reduces to being proportional to μi when X is a constant, but not, as one might expect, when X has a general distribution. Next, we evaluate randomized accessing policies whereby the choices of page access are determined by independent random samples from the distribution {fi}. We show that when the weights ci in the cost function are proportional to μi, the minimum cost is achieved when fi is proportional to (hi)⁻¹−1. Finally, we present and analyze a heuristic policy that is especially suited to the asymptotic regime of large data bases. © 1998 John Wiley & Sons, Ltd.

This paper examines the problem of distributing a set of equal-size records among the sectors of a drum-like storage device in order to exploit known access frequencies and reduce the average access time. A simple catenated search model is defined for which, the problem is shown to be NP-complete. Heuristics are then defined and analyzed in terms of worst-case bounds. It is shown that easily implemented highest-access-frequency-first assignment rules provide an average access time very close to optimal.

In this note we derive a tight asymptotic bound on the relative performance of the Next-Fit-Decreasing approximation rule for classical one-dimensional bin-packing. The proof provides a novel application of certain well-known sequences of unit fractions. Potential applications are mentioned.

In a flexible manufacturing system stations are arranged along a common conveyor that brings items for processing to the stations and also carries away the processed items. At each station specialized robots automatically load and unload items on and off the conveyor. We examine here a single station in such a system. A new kind of queueing problem arises, with input-output dependencies that result because the same conveyor transports items both to and from the station. The paper analyzes two models of a station. Model 1 has one robot that cannot return a processed item to the conveyor while unloading a new item for processing. Model 2 has two robots to allow simultaneous loading and unloading of the conveyor. A principal goal of the analysis is the proper choice of the distance separating the two points at which items leave and rejoin the conveyor.

We model a selection process arising in certain storage problems. A sequence (X1, · ··, Xn) of non-negative, independent and identically distributed random variables is given. F(x) denotes the common distribution of the Xi's. With F(x) given we seek a decision rule for selecting a maximum number of the Xi's subject to the following constraints: (1) the sum of the elements selected must not exceed a given constant c> 0, and (2) the Xi's must be inspected in strict sequence with the decision to accept or reject an element being final at the time it is inspected.We prove first that there exists such a rule of threshold type, i.e. the ith element inspected is accepted if and only if it is no larger than a threshold which depends only on iand the sum of the elements already accepted. Next, we prove that if F(x) ~ Axaas x ?0 for some A, a> 0,then for fixed cthe expected number, En(c), selected by an optimal threshold is characterized by Asymptotics as c ? 8and n? 8with c/nheld fixed are derived, and connections with several closely related, well-known problems are brought out and discussed.

We study the problem of scheduling ngiven jobs on muniform processors to minimize expected makespan (maximum finishing time). Job execution times are not known in advance, but are known to be exponentially distributed, with identical rate parameters depending solely on the executing processor. For m= 2 and 3, we show that there exist optimal scheduling rules of a certain threshold type, and we show how the required thresholds can be easily determined. We conjecture that similar threshold rules suffice for m> 3 but are unable to prove this. However, for m> 3 we do obtain a general bound on problem size that permits Bellman equations to be used to construct an optimal scheduling rule for any given set of mrate parameters, with the memory required to represent that scheduling rule being independent of the number of remaining jobs.

We consider the NP-hard problem of packing into a specified rectangle a maximum number of squares from a given set. We define two related approximation algorithms and derive bounds on the worst case performance of the packings they produce.

Letnrandom intervalsI1, ...,Inbe chosen by selecting endpoints independently from the uniform distribution on [0.1]. Apackingis a pairwise disjoint subset of the intervals; itswasted spaceis the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this “best” packing has wasted space. It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizesof the best packings: about lognintervals in the unit interval case, but usually only one or two arcs in the circle case.

A ring of N cells rotates in discrete steps past N queues, moving customers from their queues of arrival to randomly chosen destinations. The model has applications in communication systems, processor interconnection networks, and flexible manufacturing. The arrivals to the queues are independent and stochastically identical. The total numbers of arrivals to the system during successive steps are independent, identically distributed random variables with mean λ and finite second and third moments. A greedy policy governs the insertion of customers on the ring: A customer waiting at the head of a queue enters the next unoccupied cell to appear at that queue. The customer then remains on the ring a random travel time d, leaves, and frees its cell for another customerA necessary condition for the system to be stable is [image omitted] . If no customer travels further than once around the ring [image omitted]  is sufficient for stability. Other results assume d to be stochastically bounded by an exponentially distributed travel time with mean [image omitted] . Then [image omitted]  is sufficient for stability. In the limit of large N, stable systems with fixed λ and μ have expected numbers [image omitted]  of waiting customers per queue; then a customer's wait in a queue is usually negligible compared with his travel time. Simulations suggest that the mean number waiting in a queue may even be [image omitted] .

The points of a graph Gwill form clusters as a result of a flow process. Initially, points iof Gown resources xiwhich are i.i.d. random real numbers. Afterwards, resources flow between points, but always from a point to a neighbor that has accumulated a larger total resource. Thus points with small resource tend to lose it and points with large resource tend to gain. Eventually the flow stops with only two kinds of points, nulls with no resource left and absorbers with such large resource that no neighbor can take it. The final resource at an absorber is a sum of certain initial resources xi, and the corresponding points iform one cluster. Analytical results are obtainable when Gis the chain of integer points on the line. Probability distributions are derived for the distance between consecutive absorbers and the size of a cluster. Indeed these distributions do not involve the given distribution for the xi.The Laplace transform of the distribution of final resources at absorbers is derived but the distribution itself is obtained by a simulation. For general graphs Gonly partial results are obtained.

The mean flow time of a schedule provides a measure of the average time that a task spends within a computer system, and also the average number of unfinished tasks in the system. The mean flow time of a schedule is defined to be the sum of the finishing times of all tasks in the system. On a system of identical processors O(nlog n) algorithms exist for determining minimal mean flow time schedules for nindependent tasks. In general, there will be a large class Cof schedules, of widely differing lengths, that all minimize mean flow time. The problem of finding the shortest schedule in Cis NP-complete. We give heuristics that find schedules in Cthat are no more than 25% longer than the shortest schedule in C. The advantage of a short schedule is that processor utilization is high.

The calculation of sojourn time distributions is an important problem of current interest in the analysis of queueing networks. The problem has proven to be quite difficult owing to the effects of overtaking, i.e. changes in the service order of jobs visiting the same two or more nodes of the network.Under exponential assumptions we analyze the simplest, non-trivial networks with overtaking: two-server tandem queues with processor-sharing at the first node. The major results of the analysis show that the calculation of sojourn time distributions can be reduced to the solution of boundary value problems.

A basic multiprocessor version of the makespan scheduling problem requires that n tasks be scheduled on m identical processors so as to minimize the latest task finishing time. In the standard probability model considered here, the task durations are i.i.d. random variables with a general distribution F having finite mean. Our main objective is to estimate the distribution of the makespan as a function of mn and F under the on-line greedy policy, i.e., where the tasks are put in sequence and assigned in order to processors whenever they become idle. Because of the difficulty of exact analysis, we concentrate on the asymptotic behavior as n→∞ or as both m→∞ and n→∞with m≥n. The focal point is the Markov chain giving the remaining processing times of the m - 1 tasks still running at task completion epochs. The theory of stationary marked point processes is used to show that the stationary distribution of this Markov chain coincides with the order statistics of m - 1 independent random variables having the equilibrium residual-life distribution associated with F. Convergence theory for general-state Markov chains is then applied to establish convergence results for the Markov chain of interest. Finally, central limit theorems are applied to show that what we can gain from a good list scheduling policy is asymptotically negligible compared to our degree of uncertainty about the makespan (i.e., its standard deviation)

Most operating systems for large computing facilities involve service disciplines which base, to some extent, the sequencing of object program executions on the amount of running time they require. It is the object of this paper to study mathematical models of such service disciplines applicable to both batch and time‐shared processing systems. In particular, Markov queueing models are defined and analyzed for round‐robin and foreground‐background service disciplines. With the round‐robin discipline, the service facility processes each program or job for a maximum of qseconds; if the program's service is completed during this quantum, it leaves the system, otherwise it returns to the end of the waiting line to await another quantum of service. With the foreground‐background discipline each new arrival joins the end of the foreground queue and awaits a single quantum of service. If it requires more it is subsequently placed at the end of the background queue which is allocated service only when the foreground queue is empty.

Despite the recognized potential of multiprocessing little is known concerning the general problem of finding efficient algorithms which compute minimallength schedules for given computations and m?2 processors. In this paper we formulate a general model of computation structures and exhibit an efficient algorithm for finding optimal nonpreemptive schedules for these structures on two-processor systems. We prove that the algorithm gives optimal solutions and discuss its application to preemptive scheduling disciplines.

This paper concerns the problem of obtaining predictions of the extent to which additional core storage would improve the performance of a given paging system based on information that could be obtained from monitoring the system whilst running its normal workload.

An important property of file structures is their behavior when the underlying distribution of access frequencies is non-uniform. In this note we consider methods for structuring files so that initially unknown but non-uniform access frequencies are exploited in a way that reduces mean search times. As a specific illustration a simple algorithm is applied to sequence search trees and shown to produce structures with mean search times that are significantly less than those produced by an algorithm creating tree structures independent of access frequencies. An analytic result is obtained for this improvement when access frequencies are uniform. Samples from the results of Monte Carlo simulations are used to illustrate this improvement when access frequencies are non-uniform.

We consider non-degradable hierarchical redundant systems having multiple working and failure modes with restoration time depending on failure type. We evaluate these systems using two measures: generalized uptime and traditional downtime. We define the Impact Weighted System Uptime (IWSU) and illustrate its usefulness in practical terms, viz., an IP router. Next, we provide an analysis that fits the downtimes by a heavy-tailed log PH distribution. For these downtime distributions, we study whether it is more cost effective to reduce failure rates or to speed up the response to failures The first option is a vendor problem, but the second is a service provider problem. A numerical example is given to help appreciate the tradeoff.

The localization problem of a wireless sensor network (WSN) is posed as a distributed computation performed by the sensors alone. A relatively small number of the nodes along the boundary of the WSN are initialized with their exact locations, which serve as reference coordinates that seed the computation. Our range-free, scalable localization protocol begins with a self-organizing, local-rule, distributed computation: In a converging sequence, each sensor periodically takes as its location estimate the average of its neighbors' estimates. These estimates are used to construct an instance of the Cauchy Integral Formula from which the final location estimates are produced. Our research is still in progress, but we are currently in position to argue the superiority over other range-free methods operating under similar minimalist constraints. Among the salient properties of our approach is a tolerance to variations in timing and sensor density, and to variations in the characteristics of individual sensors, such as computing speed and communication range.

This paper describes a self-assembling sleep-wake sensor system that is scalable, easily implemented, and energy conserving. Sensors actively detecting events form wave fronts that sweep the sensor field. An application of concepts from cellular automata theory accounts for much of its novelty. The system has additional, highly desirable properties such as a self-healing capability, fault tolerance, asynchronous operation, seamless accommodation of obstacles in the sensor field, and it is highly effective even in the case of intelligent intruders, i.e., those who know sensor design and sensor locations. System performance is a focus of the paper, and, as in the study of the emergent behavior of cellular automata, an instructive example of experimental mathematics. Related open questions in mathematical performance analysis are reviewed.

As the number of wavelengths in OBS systems increases, the utilization achievable for a given blocking probability can be made to approach 100%. This paper shows that this property applies to a wavelength allocation algorithm of greedy type. Another property of this rule, one shared by most other wavelength assignment algorithms, is that, since lost traffic tends to occur near destinations, where the resource usage wasted by such traffic is large, very low blocking probabilities are important for efficient operation. To help identify regions of low blocking probability, we derive an asymptotically exact condition for zero blocking probabilities; it has a form reminiscent of the stability condition of the M/G/1 queue.

We introduce a new paradigm in information transmission, the concept of SEAMLESS TRANSMISSION, whereby any client in a network requesting a file starts receiving it immediately, and experiences no delays throughout the remainder of the downloading time. This notion is based on the partial caching concept [2] which was introduced to overcome some of the disadvantages of traditional cache replacement algorithms such as LRU and LRU-threshold [1]. The main idea of partial caching is to store an initial part of the file in the cache and to obtain the rest of the file from the origin server. To achieve the maximal retrieval performance of seamless transmission, clients must be prepared to re-sequence segments of the files received out of order. With this caveat, seamless transmission can be viewed as a way to implement strict quality of service (QoS) guarantees to all clients of a network. This paper gives a provably correct technique for achieving seamlessness for a given file located at the root node in a tree structured network.

We study a version of the problem of searching peer-to-peer networks by means of floods, or expanding rings; when a network reduces to a path, then the term flood becomes the more familiar search term "scan," which is the focus of this paper.

No Abstract