Topological data analysis (TDA) is a powerful technique for extracting complex and valuable shape-related summaries of high-dimensional data. However, the computational demands of classical algorithms for computing TDA are exorbitant, and quickly become impractical for high-order characteristics. Quantum computers offer the potential of achieving significant speedup for certain computational problems. Indeed, TDA has been purported to be one such problem, yet, quantum computing algorithms proposed for the problem, such as the original Quantum TDA (QTDA) formulation by Lloyd, Garnerone and Zanardi, require fault-tolerance qualifications that are currently unavailable. In this study, we present NISQ-TDA, a fully implemented end-to-end quantum machine learning algorithm needing only a short circuit-depth, that is applicable to high-dimensional classical data, and with provable asymptotic speedup for certain classes of problems. The algorithm neither suffers from the data-loading problem nor does it need to store the input data on the quantum computer explicitly. The algorithm was successfully executed on quantum computing devices, as well as on noisy quantum simulators, applied to small datasets. Preliminary empirical results suggest that the algorithm is robust to noise.

We study the problem of transfer learning, observing that previous efforts to understand its information-theoretic limits do not fully exploit the geometric structure of the source and target domains. In contrast, our study first illustrates the benefits of incorporating a natural geometric structure within a linear regression model, which corresponds to the generalized eigenvalue problem formed by the Gram matrices of both domains. We next establish a finite-sample minimax lower bound, propose a refined model interpolation estimator that enjoys a matching upper bound, and then extend our framework to multiple source domains and generalized linear models. Surprisingly, as long as information is available on the distance between the source and target parameters, negative-transfer does not occur. Simulation studies show that our proposed interpolation estimator outperforms state-of-the-art transfer learning methods in both moderate- and high-dimensional settings.

Decentralized optimization with multiple networked clients/learners has advanced machine learning significantly over the past few years. When data distributions at different nodes/locations are heterogeneous, consensus-based decentralized algorithms ignore distinctive features of local data samples. In this paper, we propose a decentralized client adaptation strategy for personalized learning by taking local client data structures into account. It turns out that optimizing the model parameters can be formulated as a decentralized bilevel programming problem. Motivated by this application, we propose a stochastic primal-dual framework for solving decentralized bilevel nonconvex problems and show that the devised algorithm achieves the Karush–Kuhn–Tucker (KKT) points for this class of problems at a rate of $\mathcal{O}(1/\sqrt {nT} )$, where n denotes the number of total learners and T the total number of iterations. Multiple experiments show the superiority of our proposed method compared to state-of-the-art methods in terms of both training speed and testing accuracy for decentralized learning problems on real datasets.

Bilevel optimization has been shown to be a powerful framework for formulating multi-task machine learning problems, e.g., reinforcement learning (RL) and meta-learning, where the decision variables are coupled in both levels of the minimization problems. In practice, the learning tasks would be located at different computing resource environments, and thus there is a need for deploying a decentralized training framework to implement multi-agent and multi-task learning. We develop a stochastic linearized augmented Lagrangian method (SLAM) for solving general nonconvex bilevel optimization problems over a graph, where both upper and lower optimization variables are able to achieve a consensus. We also establish that the theoretical convergence rate of the proposed SLAM to the Karush-Kuhn-Tucker (KKT) points of this class of problems is on the same order as the one achieved by the classical distributed stochastic gradient descent for only single-level nonconvex minimization problems. Numerical results tested on multi-agent RL problems showcase the superiority of SLAM compared with the benchmarks.

Distributionally robust learning (DRL) is increasingly seen as a viable method to train machine learning models for improved model generalization. These min-max formulations, however, are more difficult to solve. We provide a new stochastic gradient descent algorithm to efficiently solve this DRL formulation. Our approach applies gradient descent to the outer minimization formulation and estimates the gradient of the inner maximization based on a sample average approximation. The latter uses a subset of the data sampled without replacement in each iteration, progressively increasing the subset size to ensure convergence. We rigorously establish convergence to a near-optimal solution under standard regularity assumptions and, for strongly convex losses, match the best known $O(\epsilon{ −1})$ rate of convergence up to a known threshold. Empirical results demonstrate the significant benefits of our approach over previous work in improving learning for model generalization.

We consider the problem of estimating the Wasserstein distance between the empirical measure and a set of probability measures whose expectations over a class of functions (hypothesis class) are constrained. If this class is sufficiently rich to characterize a particular distribution (e.g., all Lipschitz functions), then our formulation recovers the Wasserstein distance to such a distribution. We establish a strong duality result that generalizes the celebrated Kantorovich-Rubinstein duality. We also show that our formulation can be used to beat the curse of dimensionality, which is well known to affect the rates of statistical convergence of the empirical Wasserstein distance. In particular, examples of infinite-dimensional hypothesis classes are presented, informed by a complex correlation structure, for which it is shown that the empirical Wasserstein distance to such classes converges to zero at the standard parametric rate. Our formulation provides insights that help clarify why, despite the curse of dimensionality, the Wasserstein distance enjoys favorable empirical performance across a wide range of statistical applications.

We propose a novel framework PROVEN to \textbf{PRO}babilistically \textbf{VE}rify \textbf{N}eural network’s robustness with statistical guarantees. PROVEN provides probability certificates of neural network robustness when the input perturbation follow distributional characterization. Notably, PROVEN is derived from current state-of-the-art worst-case neural network robustness verification frameworks, and therefore it can provide probability certificates with little computational overhead on top of existing methods such as Fast-Lin, CROWN and CNN-Cert. Experiments on small and large MNIST and CIFAR neural network models demonstrate our probabilistic approach can tighten up robustness certificate to around $1.8 \times$ and $3.5 \times$ with at least a $99.99%$ confidence compared with the worst-case robustness certificate by CROWN and CNN-Cert.

We consider a new family of stochastic operators for reinforcement learning with the goal of alleviating negative effects and becoming more robust to approximation or estimation errors. Various theoretical results are established, which include showing that our family of operators preserve optimality and increase the action gap in a stochastic sense. Our empirical results illustrate the strong benefits of our robust stochastic operators, significantly outperforming the classical Bellman operator and recently proposed operators.

Worldwide interest in the delivery of computing and storage capacity as a service continues to grow at a rapid pace. The complexities of such cloud computing centers require advanced resource management solutions that are capable of dynamically adapting the cloud platform while providing continuous service and performance guarantees. The goal of this paper is to devise resource allocation policies for virtualized cloud environments that satisfy performance and availability guarantees and minimize energy costs in very large cloud service centers. We present a scalable distributed hierarchical framework based on a mixed-integer nonlinear optimization of resource management acting at multiple timescales. Extensive experiments across a wide variety of configurations demonstrate the efficiency and effectiveness of our approach.

This paper investigates fundamental properties of throughput and energy cost in large wireless linear networks with very limited local resources that do not grow with the size of the network. The maximum throughput of the network is derived and the arrival process that maximizes throughput, given a fixed arrival rate, is established. An asymptotically critical loading regime is identified such that the probability of an arbitrary packet being lost is strictly within (0, 1) as the network size increases. Such a regime delivers throughput comparable to the maximum at a reasonable energy cost.

This paper considers structural and algorithmic problems in stochastic loss networks. The very popular Erlang approximation can be shown to provide relatively poor performance estimates, especially for loss networks in the critically loaded regime. This paper proposes a novel algorithm for estimating the stationary loss probabilities in stochastic loss networks based on structural properties of the exact stationary distribution, which is shown to always converge, exponentially fast, to the asymptotically exact results. Using a variational characterization of the stationary distribution, an alternative proof is provided for an important result due to Kelly, which is simpler and may be of interest in its own right. This paper also determines structural properties of the inverse Erlang function characterizing the region of capacities that ensures offered traffic is served within a set of loss probabilities. Numerical experiments investigate various issues of both theoretical and practical interest.

We consider a capacity planning optimization problem in a general theoretical framework that extends the classical Erlang loss modeland related stochastic loss networks to support time-varying workloads. The time horizon consists of a sequence of coarse time intervals, each of which involves a stochastic loss network under a fixed multi-class workload that can change in a general manner from one interval to the next. The optimization problem consists of determining the capacities for each time interval that maximize a utility function over the entire time horizon, finite or infinite, where rewards gained from servicing customers are offset by penalties associated with deploying capacities in an interval and with changing capacities among intervals. We derive a state-dependent optimal policy within the context of a particular limiting regime of the optimization problem, and we prove this solution to be a symptotically optimal. Then, under fairly mild conditions, we prove that a similar structural property holds for the optimal solution of the original stochastic optimization problem, and we show how the optimal capacities comprising this solution can be efficiently computed.

Abstract—This paper investigates the existence of scalable protocols that can achieve the capacity limit of per source-destination pair in a large wireless network of nodes when the buffer space of each node does not grow with the size of the network. It is shown that there is no end-to-end protocol capable of carrying out the limiting throughput of with nodes that have constant buffer space. In other words, this limit is achievable only with devices whose buffers grow with the size of the network. On the other hand, the paper establishes that there exists a protocol which realizes a slightly smaller throughput of log when devices have constant buffer space. Furthermore, it is shown that the required buffer space can be very small, capable of storing just a few packets. This is particularly important for wireless sensor networks where devices have limited resources. Finally, from a mathematical perspective, the paper furthers our understanding of the difficult problem of analyzing large queueing networks with finite buffers for which, in general, no explicit solutions are available. Index Terms—Ad hoc wireless networks, finite-buffer queueing networks, large-scale networks, local cooperation, scaling laws, wireless sensor networks. I.

The growing complexity of hardware and software mandates the recognition of fault occurrence in system deployment and management. While there are several techniques to prevent and/or handle faults, there continues to be a growing need for an in-depth understanding of system errors and failures and their empirical and statistical properties. This understanding can help evaluate the effectiveness of different techniques for improving system availability, in addition to developing new solutions. In this paper, we analyze the empirical and statistical properties of system errors and failures from a network of nearly 400 heterogeneous servers running a diverse workload over a year. While improvements in system robustness continue to limit the number of actual failures to a very small fraction of the recorded errors, the failure rates are significant and highly variable. Our results also show that the system error and failure patterns are comprised of time-varying behavior containing long stationary intervals. These stationary intervals exhibit various strong correlation structures and periodic patterns, which impact performance but also can be exploited to address such performance issues.

We present architectures and algorithms for efficiently serving dynamic data at highly accessed Web sites together with the results of an analysis motivating our design and quantifying its performance benefits. This includes algorithms for keeping cached data consistent so that dynamic pages can be cached at the Web server and dynamic content can be served at the performance level of static content. We show that our system design is able to achieve cache hit ratios close to 100% for cached data which is almost never obsolete by more than a few seconds, if at all. Our architectures and algorithms provide more than an order of magnitude improvement in performance using an order of magnitude fewer servers over that obtained under conventional methods.

We consider the problem of task assignment in a distributed server system, where short jobs are separated from long jobs, but short jobs may be run in the long job partition if it is idle (cycle stealing). Jobs are assumed to be nonpreemptible, where short and long jobs have generally distributed service requirements, and arrivals are Poisson. We consider two variants of this problem: a central queue model and an immediate dispatch model. This paper presents the first analysis of cycle stealing under the central-queue model. (Cycle stealing under the immediate dispatch model is analyzed in [9]). The analysis uses a technique which we refer to as busy period transitions. Results show that cycle stealing can reduce mean response time for short jobs by orders of magnitude, while long jobs are only slightly penalized. Furthermore using a central queue yields significant performance improvement over immediate dispatch, both from the perspective of the benefit to short jobs and the penalty to long jobs.

We consider the practical problem of task assignment in a server farm, where each arriving job is immediately dispatched to a server in the farm. We look at the benefit of cycle stealing at the point of the dispatcher, where jobs normally destined for one machine may be routed to a different machine if it is idle. The analysis uses a technique which we refer to as dimensionality reduction via busy period transitions. Our analysis is approximate, but can be made as close to exact as desired, and is validated via simulation. Results show that the beneficiaries of the idle cycles can benefit unboundedly, due to an increase in their stability region, while the donors are only slightly penalized. These results still hold even when there is only one donor server and 20 beneficiary servers stealing its idle cycles.

With the growing popularity of Web applications, there is a considerable increase in the importance of managing Web sites to deliver high levels of performance and scalability to accommodate future growth and evolution. One of the key issues in this regard concerns a better understanding of the traffic patterns at multiple levels, such as the levels of requests, pages and sessions. This paper presents a detailed analysis of measurement data from various sources pertaining to a specific multi-tiered, geographically distributed architecture that has been used to host the Web sites for a number of recent, popular sporting events. Our analysis of the request-level and page-level patterns demonstrate differences among the Web sites depending upon the type of event and the breadth of interests of the user community. Some of these patterns are consistent with commercial Web sites, while others are significantly different These results further illustrate geographical differences in the request-level and page-level patterns. Our analysis also investigates in detail session-level characteristics. This includes an analysis of the session durations, the think time distributions, the dependence structure of the session arrival process, and the page views comprising each session.

Scheduling in large-scale parallel systems has been and continues to be an important and challenging research problem. Several key factors, including the increasing use of off-the-shelf clusters of workstations to build such parallel systems, have resulted in the emergence of a new class of scheduling strategies, broadly referred to as dynamic coscheduling. Unfortunately, the size of both the design and performance spaces of these emerging scheduling strategies is quite large, due in part to the numerous dynamic interactions among the different components of the parallel computing environment as well as the wide range of applications and systems that can comprise the parallel environment. This in turn makes it difficult to fully explore the benefits and limitations of the various proposed dynamic coscheduling approaches for large-scale systems solely with the use of simulation and/or experimentation.To gain a better understanding of the fundamental properties of different dynamic coscheduling methods, we formulate a general mathematical model of this class of scheduling strategies within a unified framework that allows us to investigate a wide range of parallel environments. We derive a matrix-analytic analysis based on a stochastic decomposition and a fixed-point iteration. A large number of numerical experiments are performed in part to examine the accuracy of our approach. These numerical results are in excellent agreement with detailed simulation results. Our mathematical model and analysis is then used to explore several fundamental design and performance tradeoffs associated with the class of dynamic coscheduling policies across a broad spectrum of parallel computing environments.

Web Search Engines employ multiple so-called crawlers to maintain local copies of web pages. But these web pages are frequently updated by their owners, and therefore the crawlers must regularly revisit the web pages to maintain the freshness of their local copies. In this paper, we propose a two-part scheme to optimize this crawling process. One goal might be the minimization of the average level of staleness over all web pages, and the scheme we propose can solve this problem. Alternatively, the same basic scheme could be used to minimize a possibly more important search engine embarrassment level metric: The frequency with which a client makes a search engine query and then clicks on a returned url only to find that the result is incorrect. The first part our scheme determines the (nearly) optimal crawling frequencies, as well as the theoretically optimal times to crawl each web page. It does so within an extremely general stochastic framework, one which supports a wide range of complex update patterns found in practice. It uses techniques from probability theory and the theory of resource allocation problems which are highly computationally efficient -- crucial for practicality because the size of the problem in the web environment is immense. The second part employs these crawling frequencies and ideal crawl times as input, and creates an optimal achievable schedule for the crawlers. Our solution, based on network flow theory, is exact as well as highly efficient. An analysis of the update patterns from a highly accessed and highly dynamic web site is used to gain some insights into the properties of page updates in practice. Then, based on this analysis, we perform a set of detailed simulation experiments to demonstrate the quality and speed of our approach.

A fundamental understanding of the interplay between computation and I/O activities in parallel applications that manipulate huge amounts of data is critical to achieving good application performance, as well as correctly characterizing the workloads of large-scale high-performance parallel systems. We present a formal model of the behavior of CPU and I/O interactions in scientific applications, from which we derive various formulas that characterize application performance. Our model captures the I/O and CPU activity at different levels of granularity, where results from the model are shown to be in excellent agreement with measurement data from a set of I/O-intensive applications. Using the formulas from our model, which explicitly take I/O activity into account, we also present examples of possible applications of the model.

We present a methodology for maximizing profits in a general class of e-commerce environments. The cost model is based on revenues that are generated when Quality-of-Service (QoS) guarantees are satisfied and on penalties that are incurred otherwise. The corresponding QoS criteria are derived from multiclass Service-Level-Agreements (SLAs) between service providers and their clients, which include the tail distributions of the per-class delays in addition to more standard QoS metrics such as throughput and mean delays. Our approach consists of formulating the optimization problem as a network flow model with a separable set of concave objective functions based on queueing-theoretic formulas, where the SLA classes are taken into account in both the constraints and the objective function. This problem is then solved via a fixed-point iteration. Numerous experiments illustrate the benefits of our approach.

We provide scheduling algorithms that attempt to maximize the profits of a broadcast-based electronic delivery service for digital products purchased, for example, at e-commerce sites on the World Wide Web. Examples of such products include multimedia objects such as CDs and DVDs. Other examples include software and, with increasing popularity, electronic books as well. We consider two separate alternatives, depending in part on the sophistication of the set-top box receiving the product at the customer end. The first, more restrictive option, assumes that the atomic unit of transmission of the product is the entire object, which must be transmitted in order from start to finish. We provide a solution based in part on a transportation problem formulation for this so-called noncyclic scheduling problem. The second alternative, which is less restrictive, assumes that the product may be transmitted cyclically in smaller segments, starting from an arbitrary point in the object. Three heuristics are provided for this difficult cyclic scheduling problem. Both scenarios assume that the broadcasts of the same digital product to multiple customers can be "batched." We examine the effectiveness of these algorithms via simulation experiments under varying parametric assumptions. Each of the three cyclic scheduling algorithms perform better than the noncyclic algorithm. Moreover, one of the cyclic scheduling algorithms emerges as the clear winner.

Studies the effects of correlations between the inter-arrival times of different service classes. An analysis of distributed information systems reveals that such inter-class correlations exist, in part as a result of the interactions between the server and its clients. To gain insight into the performance implications of these correlations, we formulate a general stochastic model that explicitly captures client-server interactions, and we derive a matrix analysis of a specific instance of the model. Our results illustrate and quantify the impact that such inter-class correlations can have on system performance.

In this paper we consider the problem of scheduling different classes of customers on multiple distributed servers to minimize an objective function based on per-class mean response times.This problem arises in a wide range of distributed systems, networks and applications.Within the context of our model, we observe that the optimal sequencing strategy at each of the servers is a simple static priority policy.Using this observation, we argue that the globally optimal scheduling problem reduces to finding an optimal routing matrix under this sequencing policy.We formulate the latter problem as a nonlinear programming problem and show that any interior local minimum is a global minimum, which significantly simplifies the solution of the optimization problem.In the case of Poisson arrivals, we provide an optimal scheduling strategy that also tends to minimize a function of the per-class response time variances.Applying our analysis to various static instances of the general problem leads us to rederive many results, yielding simple approximation algorithms whose guarantees match the best known results.

We develop a general methodology for characterizing Web server access patterns based on a spectral analysis of finite collections of observed data from real systems. Our approach is used together with the access logs from the IBM Web site for the 1996 Olympic Games to demonstrate some of its advantages over previous methods and to analyze certain aspects of large-scale Web server performance.

In this paper we systematically examine various performance issues involved in the coordinated allocation of processor and disk resources in large-scale parallel computer systems. Models are formulated to investigate the I/O and computation behavior of parallel programs and workloads, and to analyze parallel scheduling policies under such workloads. These models are parameterized by measurements of parallel programs, and they are solved via analytic methods and simulation. Our results provide important insights into the performance of parallel applications and resource management strategies when I/O demands are not negligible.

Advanced general purpose parallel systems should be able to support diverse applications with different resource requirements without compromising effectiveness and efficiency. We present a resource management model for cluster computing that allows multiple scheduling policies to co-exist dynamically. In particular, we have built Octopus, an extensible and distributed hierarchical scheduler that implements new space sharing, gang scheduling and load sharing strategies. A series of experiments performed on an IBM SP2 suggest that Octopus can effectively match application requirements to available resources, and improve the performance of a variety of parallel applications within a cluster.

The evaluation of pipeline performance and the analysis of different design alternatives and cost/performance tradeoffs are a fundamental aspect of high-performance computer system design. This performance evaluation process requires accurate models of both the pipeline organization and the characteristics of the workload being executed. We derive general mathematical models and analyses of workload behavior and pipeline performance that can provide measures as accurate as detailed trace-driven simulations with the computational efficiency of analytic methods.

As memory speeds grow at a considerably slower rate than processor speeds, memory accesses are starting to dominate the execution time of processors, and this will likely continue into the future. This trend will be exacerbated by growing miss rates due to commercial applications, object-oriented programming and micro-kernel based operating systems. We examine the use of coarse-grained multithreading to address this important problem in uniprocessor on-line transaction processing environments where there is a natural, coarse-grained parallelism between the tasks resulting from transactions being executed concurrently, with no application software modifications required. Our results suggest that multithreading can provide significant performance improvements for uniprocessor commercial computing environments.

Gang scheduling is a resource management scheme for paralder to maximize its performance on each hardware platform.1

No abstract available.

We consider an important tradeoff between processor and memory allocation in distributed parallel processing systems. To study this tradeoff, we formulate stochastic models of parallel program behavior, distributed parallel processing environments and memory overheads incurred by parallel programs as a function of their processor allocation. A mathematical analysis of the models is developed, which includes the effects of contention for shared resources caused by paging activity. We conduct a detailed analysis of real large-scale scientific applications and use these results to parameterize our models. Our results show that memory overhead resulting from processor allocation decisions can have a significant effect on system performance in distributed parallel environments, strongly suggesting that memory considerations must be incorporated in the resource allocation policies for parallel systems. We also demonstrate the importance of the inter-locality miss ratio, which is introduced in this paper and analyzed for the first time.

A main objective of scheduling independent jobs composed of multiple sequential tasks in shared-memory and distributed-memory multiprocessor computer systems is the assignment of these tasks to processors in a manner that ensures efficient operation of the system. Achieving this objective requires the analysis of a fundamental tradeoff between maximizing parallel execution, suggesting that the tasks of a job be spread across all system processors, and minimizing synchronization and communication overheads, suggesting that the job's tasks be executed on a single processor. The authors consider a class of scheduling policies that represent the essential aspects of this processor allocation tradeoff, and model the system as a distributed fork-join queueing system. They derive an approximation for the expected job response time, which includes the important effects of various parallel processing overheads (such as task synchronization and communication) induced by the processor allocation policy.>

The authors analyze three general classes of scheduling policies under a workload typical of large-scale scientific computing. These policies differ in the manner in which processors are partitioned among the jobs as well as the way in which jobs are prioritized for execution on the partitions. The results indicate that existing static schemes to not perform well under varying workloads. Adaptive policies tend to make better scheduling decisions, but their ability to adjust to workload changes is limited. Dynamic partitioning policies, on the other hand, yield the best performance and can be tuned to provide desired performance differences among jobs with varying resource demands.

Multicomputers, consisting of many processing nodes connected through a high speed interconnection network, have become an important and common platform for a large body of scientific computations. These parallel systems have traditionally executed programs in batch mode, or have at most space-shared the processors among multiple programs using a static partitioning policy. This, however, can result in relatively low system utilization and throughput for important classes of scientific applications.In this paper we consider "a class of scheduling policies that attempt to increase processor utilization and system throughput by timesharing a partition of processors among multiple programs. We compare the system performance under this multiprogramming policy with that of static partitioning for a variety of workloads via both analytic and simulation modeling. Our results show that timesharing a partition can provide significant improvements in performance, particularly at moderate to heavy loads. The performance gains of the multiprogrammed policy depend upon the inherent efficiency of the parallel programs that comprise the workload, decreasing with increasing program efficiency. Our analysis also provides the regions over which one scheduling policy outperforms the other, as a function of system load.

In a shared-memory multiprocessor system, it may be more efficient to schedule a task on one processor than on another if relevant data already reside in a particular processor's cache. The effects of this type of processor affinity are examined. It is observed that tasks continuously alternate between executing at a processor and releasing this processor due to I/O, synchronization, quantum expiration, or preemption. Queuing network models of different abstract scheduling policies are formulated, spanning the range from ignoring affinity to fixing tasks on processors. These models are solved via mean value analysis, where possible, and by simulation otherwise. An analytic cache model is developed and used in these scheduling models to include the effects of an initial burst of cache misses experienced by tasks when they return to a processor for execution. A mean-value technique is also developed and used in the scheduling models to include the effects of increased bus traffic due to these bursts of cache misses. Only a small amount of affinity information needs to be maintained for each task. The importance of having a policy that adapts its behavior to changes in system load is demonstrated.>

In shared-memory multiprocessor systems it may be more efficient to schedule a task on one processor than on mother. Due to the inevitability of idle processors in these environments, there exists an important tradeoff between keeping the workload balanced and scheduling tasks where they run most efficiently. The purpose of an adaptive task migration policy is to determine the appropriate balance between the extremes of this load sharing tradeoff.We make the observation that there are considerable differences between this load sharing problem in distributed and shared-memory multiprocessor systems, and we formulate a queueing theoretic model of task migration to study the problem. A detailed mathematical analysis of the model is developed, which includes the effects of increased contention for system resources induced by the task migration policy. Our objective is to provide a better understanding of task migration in shared-memory multiprocessor environments. In particular, we illustrate the potential for significant improvements in system performance, and we show that even when migration costs are large it may still be beneficial to migrate waiting tasks to idle processors. We further demonstrate the potential for unstable behavior under migratory scheduling policies, and we provide optimal policy thresholds that yield the best performance and avoid this form of processor thrashing.