Abstract

We consider a two-dimensional semimartingale reflecting Brownian motion (SRBM) in the nonnegative quadrant. Assume that the SRBM has a unique stationary distribution. We characterize the exact tail asymptotic of its marginal stationary distribution along each direction $c$ in the quadrant.

A key step in our analysis is to establish the convergence domain of the moment generating function of the two-dimensional stationary distribution. The line in direction $c$ intersects the boundary of the convergence domain at one point, and that point uniquely determines the decay rate $\alpha$ for the marginal stationary distribution. The one-dimensional moment generating function of the marginal distribution has a singularity at $\alpha$. Using analytic extension in complex analysis, we characterize the precise nature of the singularity there. Using that characterization and complex inversion techniques, we show that the tail distribution of the marginal stationary distribution has the exact asymptotic of the form $bx^\kappa \exp(-\alpha x)$ as $x$ goes to infinity, where $b$ is a positive constant and $\kappa$ takes one of the values $-3/2$, $ -1/2$, $0$, or $1$.

We will also review a variational problem (VP) that is associated with the SRBM and present a connection between the VP and the convergence domain. This talk is based on joint works with Masakio Miyazawa at Tokyo University of Science.

Abstract

We review belief propagation algorithms inspired by the study of phase transitions in combinatorial optimization problems. In particular, we present rigorous results on convergence of such algorithms for matching and associated bargaining problems on networks. We also present a belief propagation algorithm for the prize-collecting Steiner tree problem, for which rigorous convergence results are not yet known. Finally, we show how this algorithm can be used to discover pathways in cancer genomics, and to suggest possible drug targets for cancer therapy.

Abstract

Online privacy concerns prompt the following question: can a recommendation engine be accurate if end-users do not entrust it with their private data? To provide an answer, we study the problem of learning user ratings for items under so-called local or 'user-end' differential privacy, a formal notion of data privacy. Our first contribution is the obtention of lower bounds on learning complexity based on mutual information. These results highlight the role played by the amount of ratings performed by each user. In the information-rich regime (where each user rates at least a constant fraction of items), a spectral clustering approach is shown to achieve optimal sample complexity, as it matches our information-theoretic lower bounds. However the information-scarce regime (where each user only rates a vanishing fraction of the total item set) is found to require a different approach. We thus propose the so-called MaxSense algorithm, which achieves optimal sample complexity in the information-scarce regime. The techniques we develop for bounding mutual information may be of broader interest. To illustrate this, we show their applicability to (i) learning based on 1-bit sketches (in contrast to differentially private sketches), and (ii) interactive learning, where queries can be adapted based on answers to past queries.

Abstract

Referring to similarities between moderate-deviations-scale and diffusion-scale heavy traffic analysis, D. Wischik wrote in his 2001 paper, Moderate Deviations in Queueing Theory, "We conjecture that there is a similar control theory for queueing systems at the moderate deviations scale." In this talk I will discuss similarities that indeed occur between optimal control in the moderate deviations regime and in the diffusion regime. The former is also closely related to large-deviations-scale analysis, and this relation, and related ideas, will be described. This is joint work with Anup Biswas (Technion).

Abstract

Benes networks are constructed with simple switch modules and have many advantages, including small latency and requiring only an almost linear number of switch modules. As circuit-switches, Benes networks are rearrangeably non-blocking, which implies that they are full-throughput as packet switches, with suitable routing. Routing in Benes networks can be done by time-sharing permutations. However, this approach requires centralized control of the switch modules and statistical knowledge of the traffic arrivals. We propose a backpressure-based routing scheme for Benes networks, combined with end-to-end congestion control. This approach achieves the maximal utility of the network and requires only four queues per module, independently of the size of the network.

Abstract

Several classes of stochastic networks can be viewed as weakly interacting jump Markov processes. We establish large deviations principles for the scaled sequences of empirical measures associated with a large class of weakly interacting jump Markov processes, and discuss the implications for the design and performance of associated stochastic networks. The difficulty in establishing a large deviations principle arises from the fact that the processes do not satisfy the commonly assumed condition that the jump rates are not uniformly bounded below, away from zero. This is joint work with Paul Dupuis and Wei Wu.

Abstract

We consider the following dynamic Boolean model introduced by van den Berg, Meester and White (1997). At time 0, let the nodes of thegraphbe a Poisson point process in R^d with constant intensity and let each node move independently according to Brownian motion. At any time t, we put an edge between every pair of nodes if their distance is at most r. We study two features in this model: detection (the time until a target point--fixed or moving--is within distance r from some node of thegraph), isolation (the time until the origin is isolated) and percolation (the time until a given node belongs to the infinite connected component of thegraph). We obtain asymptotics for these features by combining ideas from stochasticgeometry, coupling and multi-scale analysis. (Based on joint works with Yuval Peres, Alistair Sinclair and Alexandre Stauffer)

Abstract

We are motivated by the problem of designing simple distributed algorithms for peer-to-peer streaming applications that can achieve high throughput and low delay, while maintaining a very small neighbor set for each peer. Our algorithm constructs multiplerandomdirected Hamiltoncyclesand disseminates content over the superposed graph of thecycles. We show that the algorithm achieves any arbitrary fraction of the maximum streaming capacity while maintaining a small streaming delay. The result is established by showing that the superposed graph is an expander with high probability.

Abstract

We propose a new model for peer-to-peer networking which takes the network bottlenecks into account beyond the access. This model allows one to cope with the fact that distant peers often have a smaller rate than nearby peers. We show that the spatial point process describing peers in their steady state then exhibits an interesting repulsion phenomenon. We study the implications of this phenomenon by analyzing two asymptotic regimes of the peer-to-peer network: the fluid regime and the hard-core regime. We get closed form expressions for the mean (and in some cases the law) of the peer latency and the download rate obtained by a peer as well as for the spatial density of peers in the steady state of each regime. The analytical results are based on a mix of stochastic and dimensional analysis and have important design implications.

Joint work with F. Mathieu and I. Norros.

Abstract

We consider the G/GI/N queue with multiple server pools, each possessing a pool-specific service time distribution. We then consider the class of non-idling routing policies referred to as u-greedy policies. These policies route incoming customers to the server pool with the longest weighted cumulative idle time. Our first set of results demonstrate that asymptotically in the Halfin-Whitt regime and under any u-greedy policy, the diffusion scaled cumulative idle time processes of each of the server pools are held in fixed proportion to one another. We next move on to providing a heavy-traffic limit theorem for the process keeping tracking of the total number of customers in the system. Our limit may be characterized as the solution to a stochastic convolution equation. As a first step to proving our main results, we also show that under any non-idling policy and under appropriate initial conditions, the fluid scaled total number of customers in the system and in each server pool is asymptotically constant. This is joint work with Yair Shaki.

Abstract

Large dynamic economic systems are all around us: financial markets, power markets, sponsored search auctions, online marketplaces such as eBay, and resource sharing systems (e.g., cloud computing platforms) are just a few timely examples. It is of central societal importance to have systematic approaches to management, design, and control of such systems. Unfortunately, classical methods of analysis suggested by economics suffer from two major flaws: they are both intractable and implausible. Computation of these equilibria is often impossible for the system analyst, and even computing best responses within the game may be intractable for individual agents. Further, these equilibrium concepts often place excessive demands on the rationality and foresight of agents in the system. This talk first surveys recent results on an alternative concept we call mean field equilibrium (MFE). In a mean field equilibrium, individuals take a simpler view of the world: they postulate that fluctuations in the empirical distribution of other players' states have "averaged out" due to large scale, and thus optimize holding the state distribution of other players fixed. MFE requires a consistency check: the postulated state distribution must arise from the optimal strategies agents compute. MFE is typically more tractable and more plausible than its classical counterparts. We discuss basic theoretical results related to MFE, as well as applications in a range of settings. We then focus our attention on MFE in multiarmed bandit games. These are a class of games where each agent solves a multiarmed bandit problem, but payoffs depend on how many other agents choose the same action at each time step. Such games are a reasonable economic model for a range of settings, from wireless spectrum allocation to product selection by competing firms. We study existence of MFE in such games; establish conditions under which MFE are unique; and show under the same conditions that agents converge to the unique MFE from any initial condition.

Abstract

In many of the challenges faced by the modern world, from overcrowded road networks to overstretched healthcare systems, large benefits for society come about from small changes by very many individuals. We survey the problems and the cost they impose on society. We then describe a series of pilot projects which aim to develop principles for inducing small changes in behavior in networks such as transportation, wellness and recycling. Pilots have been conducted with Infosys Technologies, Bangalore (commuting) and Accenture-USA (wellness), and two are ongoing: in Singapore (public transit congestion) and at Stanford (congestion and parking).

In this talk, we will describe this work and present results from the pilots. Some salient themes are the use of low-cost sensing and networking technology for sensing individual behavior, and the use incentives and social norming to influence the behavior.

Abstract

Regenerative processes occur naturally in queueing theory. They are essentially characterized by the law of their excursions, and it is therefore natural to expect the convergence of the excursions to characterize the convergence of the whole processes. In this talk I will discuss such ideas, give a general result along these lines and provide two examples of stochastic networks in heavy traffic that we have been able to study using this result.

Abstract

The (exogenous) traffic offered to a network significantly influences both its qualitative and quantitative behavior. For example, one commonly employed theoretical model is that of so-called renewal traffic. Its intrinsic statistical regularity has profound implications, ranging from fluid limits to the "square root staffing formula". In this talk, we will provide a brief survey of some of the historical developments in this area, and discuss some of the current work and potential future directions for research.

Abstract

Given the significant energy consumption of data centers, improving their energy efficiency is an important social problem. However, energy efficiency is necessary but not sufficient for sustainability, which demands reduced usage of energy from fossil fuels. In this talk, I will describe some recent work highlighting the algorithmic challenges associated with designing sustainable data centers. We will focus on two applications -- (i) dynamic resizing within a data center and (ii) geographical load balancing across an Internet-scale system. In both cases, the core algorithmic problem is that of "smoothed online convex optimization (SOCO)". SOCO is a variant of the class of "online convex optimization (OCO)" problems, and is strongly related to the class of "metrical task systems", each of which have been studied extensively. Prior literature on these problems has focused on two performance metrics: regret and competitive ratio. There exist known algorithms with sub-linear regret and known algorithms with constant competitive ratios (some of which we have developed); however no known algorithms achieve both. In this talk I will discuss some recent progress toward this goal.

Abstract

This talk includes joint work with Krzysztof Debicki, Peter Glynn, Offer Kella, Zbigniew Palmowski and Tomasz Rolski. In this talk I'll treat several topics related to the transient analysis of Levy-driven queues. I start by pointing out how, in terms of transforms, the transient distribution can be uniquely characterized for the (general) situation that jumps to both sides are allowed -- the resulting expressions are in terms of the Wiener-Hopf factors, and have an appealing intuitive interpretation. Then 'll analyze the so-called quasi-stationary workload of the Levy-driven queue: assuming the system is in stationarity, we study its behavior conditional on the event that the busy period in which time 0 is contained has not ended before time t, as t -> inf. For the spectrally one-sided cases explicit results are obtained; for instance in the case of Brownian input, we conclude that the corresponding workload distributions at time 0 and t are both Erlang(2). Then I'll present results on the workload correlation function, in terms of structural properties, as well as an efficient importance sampling algorithm. Time permitting, I'll conclude with an analysis of the transient workload in Levy-driven tandem systems.

Abstract

Stochastic processing networks (SPNs) are a significant generalization of conventional queueing networks that allow for flexible scheduling through dynamic sequencing and alternate routing. SPNs arise naturally in a variety of applications in operations management and their control and analysis present challenging mathematical problems. One approach to these problems, via approximate diffusion control problems, has been outlined by J. M. Harrison. Various aspects of this approach have been developed mathematically, including a reduction in dimension of the diffusion control problem. However, other aspects have been less explored, especially, solution of the diffusion control problem, derivation of policies by interpretating such solutions, and limit theorems that establish optimality of such policies in a suitable asymptotic sense.

In this talk, for a concrete class of networks called parallel server systems which arise in service network and computer science applications, we explore previously undeveloped aspects of Harrison's scheme and illustrate the use of the approach in obtaining simple control policies that are nearly optimal. Identification of a graphical structure for the network, an invariance principle and properties of local times of reflecting Brownian motion, will feature in our analysis. The talk will conclude with a summary of the current status and description of open problems associated with the further development of control of stochastic processing networks.

This talk will draw on aspects of joint work with M. Bramson, M. Reiman, W. Kang and V. Pesic.

Abstract

We shall demonstrate how a large class of stochastic networks that are of great interest in Operations Research are surprisingly quite amenable to efficient Monte Carlo simulation techniques. Take for instance reflected Brownian motion (RBM) in d dimensions in the positive quadrant with oblique reflection, and consider the following questions: a) Can one estimate quantities such as the maximum of the sum of the components during the time interval [0,T] without any bias? b) How much more difficult really is to estimate quantities such as those described in a) relative to the corresponding ones with standard Brownian motion? What about if the underlying dimensions are large? c)What about stationary expectations of RBM?Can we estimate them using Monte Carlo simulation without any bias? In this talk we will report good news (i.e. positive answers) to questions a) and c) above and we will see that, in fact, many models of interest in Operations Research share the convenient properties that make RBM "highly tractable" in a precise sense to be discussed in the talk and that relates to question b). In particular, we hope to convey that from a Monte Carlo standpoint really RBM and many other stochastic networks are not that much more different from standard Brownian motion.

Abstract

Levy networks are analogs of Brownian networks, arising as diffusion approximations when heavy tails are present. In this talk we will briefly summarize some approximation results and focus attention to the analysis of a fluid queue driven by the local time of a reflected Levy process. This can be thought of as a model of the low priority queue in a system with 2 priorities. Although the process is not Markovian, we manage, by combining fluctuation theory and Palm calculus to obtain explicit results for the distribution of various quantities in steady state. This is joint work with Andreas Kyprianou and Paavo Salminen.

Abstract

Proportional fairness (PF) is an algorithm for allocating bandwidth in communication networks, and it is known to have many desirable features. However, the steady-state delay performance of PF can be improved, at least in small examples, by putting greater emphasis on efficient utilization of network resources, as opposed to equitable treatment of users. Building on recent work by Kang, Kelly, Lee and Williams (Ann. Appl. Probab. 2009), which provides a strikingly simple heavy traffic approximation for steady-state delay performance under PF, this talk will illuminate further the fairness-versus-efficiency tradeoff. (Based on joint work with Chinmoy Mandayam and Yang Yang.)