BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Rami Atar

Rami Atar appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.OCInformation Theorymath.IT

Catalog footprint

What is connected

20works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

20 published item(s)

preprint2022arXiv

Asymptotic optimality of switched control policies in a simple parallel server system under an extended heavy traffic condition

This paper studies a 2-class, 2-server parallel server system under the recently introduced extended heavy traffic condition, which states that the underlying 'static allocation' linear program (LP) is critical, but does not require that it has a unique solution. The main result is the construction of policies that asymptotically achieve a lower bound, proved in [1], on an expected discounted linear combination of diffusion-scaled queue lengths, and are therefore asymptotically optimal (AO). Each extreme point solution to the LP determines a control mode, i.e., a set of activities (class--server pairs) that are operational. When there are multiple solutions, these modes can be selected dynamically. It is shown that the number of modes required for AO is either one or two. In the latter case there is a switching point in the (normalized) workload domain, characterized in terms of a free boundary problem. Our policies are defined by identifying pairs of elementary policies and switching between them at this switching point. They provide the first example in the heavy traffic literature where weak limits under an AO policy are given by a diffusion process where both the drift and diffusion coefficients are discontinuous.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Scheduling in the high uncertainty heavy traffic regime

We propose a model uncertainty approach to heavy traffic asymptotics that allows for a high level of uncertainty. That is, the uncertainty classes of underlying distributions accommodate disturbances that are of order 1 at the usual diffusion scale, as opposed to asymptotically vanishing disturbances studied previously in relation to heavy traffic. A main advantage of the approach is that the invariance principle underlying diffusion limits makes it possible to define uncertainty classes in terms of the first two moments only. The model we consider is a single server queue with multiple job types. The problem is formulated as a zero sum stochastic game played between the system controller, who determines scheduling and attempts to minimize an expected linear holding cost, and an adversary, who dynamically controls the service time distributions of arriving jobs, and attempts to maximize the cost. The heavy traffic asymptotics of the game are fully solved. It is shown that an asymptotically optimal policy for the system controller is to prioritize according to an index rule and for the adversary it is to select distributions based on the system's current workload. The workload-to-distribution feedback mapping is determined by an HJB equation, which also characterizes the game's limit value. Unlike in the vast majority of results in the heavy traffic theory, and as a direct consequence of the diffusive size disturbances, the limiting dynamics under asymptotically optimal play are captured by a stochastic differential equation where both the drift and the diffusion coefficients may be discontinuous.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Customer-server population dynamics in heavy traffic

We study a many-server queueing model with server vacations, where the population size dynamics of servers and customers are coupled: a server may leave for vacation only when no customers await, and the capacity available to customers is directly affected by the number of servers on vacation. We focus on scaling regimes in which server dynamics and queue dynamics fluctuate at matching time scales, so that their limiting dynamics are coupled. Specifically, we argue that interesting coupled dynamics occur in (a) the Halfin-Whitt regime, (b) the nondegenerate slowdown regime, and (c) the intermediate, near Halfin-Whitt regime; whereas the dynamics asymptotically decouple in the other heavy traffic regimes. We characterize the limiting dynamics, which are different for each scaling regime. We consider relevant respective performance measures for regimes (a) and (b) --- namely, the probability of wait and the slowdown. While closed form formulas for these performance measures have been derived for models that do not accommodate server vacations, it is difficult to obtain closed form formulas for these performance measures in the setting with server vacations. Instead, we propose formulas that approximate these performance measures, and depend on the steady-state mean number of available servers and previously derived formulas for models without server vacations. We test the accuracy of these formulas numerically.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fluid limits for earliest-deadline-first networks

This paper analyzes fluid scale asymptotics of two models of generalized Jackson networks employing the earliest deadline first (EDF) policy. One applies the 'soft' EDF policy, where deadlines are used to determine priority but jobs do not renege, and the other implements 'hard' EDF, where jobs renege when deadlines expire, and deadlines are postponed with each migration to a new station. The arrival rates, deadline distribution and service capacity are allowed to fluctuate over time at the fluid scale. Earlier work on EDF network fluid limits, used as a tool to obtain stability of these networks, addressed only the soft version of the policy, and moreover did not contain a full fluid limit result. In this paper, tools that extend the notion of the measure-valued Skorokhod map are developed and used to establish for the first time fluid limits for both the soft and hard EDF network models.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large Deviations for the Single Server Queue and the Reneging Paradox

For the M/M/1+M model at the law-of-large-numbers scale, the long run reneging count per unit time does not depend on the individual (i.e., per customer) reneging rate. This paradoxical statement has a simple proof. Less obvious is a large deviations analogue of this fact, stated as follows: The decay rate of the probability that the long run reneging count per unit time is atypically large or atypically small does not depend on the individual reneging rate. In this paper, the sample path large deviations principle for the model is proved and the rate function is computed. Next, large time asymptotics for the reneging rate are studied for the case when the arrival rate exceeds the service rate. The key ingredient is a calculus of variations analysis of the variational problem associated with atypical reneging. A characterization of the aforementioned decay rate, given explicitly in terms of the arrival and service rate parameters of the model, is provided yielding a precise mathematical description of this paradoxical behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robust bounds and optimization at the large deviations scale for queueing models via Rényi divergence

This paper develops tools to obtain robust probabilistic estimates for queueing models at the large deviations (LD) scale. These tools are based on the recently introduced robust Rényi bounds, which provide LD estimates (and more generally risk-sensitive (RS) cost estimates) that hold uniformly over an uncertainty class of models, provided that the class is defined in terms of Rényi divergence with respect to a reference model and that estimates are available for the reference model. One very attractive quality of the approach is that the class to which the estimates apply may consist of hard models, such as highly non-Markovian models and ones for which the LD principle is not available. Our treatment provides exact expressions as well as bounds on the Rényi divergence rate on families of marked point processes, including as a special case renewal processes. Another contribution is a general result that translates robust RS control problems, where robustness is formulated via Rényi divergence, to finite dimensional convex optimization problems, when the control set is a finite dimensional convex set. The implications to queueing are vast, as they apply in great generality. This is demonstrated on two non-Markovian queueing models. One is the multiclass single-server queue considered as a RS control problem, with scheduling as the control process and exponential weighted queue length as cost. The second is the many-server queue with reneging, with the probability of atypically large reneging count as performance criterion. As far as LD analysis is concerned, no robust estimates or non-Markovian treatment were previously available for either of these models.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A note on non-existence of diffusion limits for serve-the-longest-queue when the buffers are equal in size

We consider the serve-the-longest-queue discipline for a multiclass queue with buffers of equal size, operating under (i) the conventional and (ii) the Halfin-Whitt heavy traffic regimes, and show that while the queue length process' scaling limits are fully determined by the first and second order data in case (i), they depend on finer properties in case (ii). The proof of the latter relies on the construction of a {\it deterministic} arrival pattern.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Skorokhod Map on Measure-Valued Paths with Applications to Priority Queues

The Skorokhod map on the half-line has proved to be a useful tool for studying processes with non-negativity constraints. In this work we introduce a measure-valued analog of this map that transforms each element $ζ$ of a certain class of càdlàg paths that take values in the space of signed measures on the half-line to a càdlàg path that takes values in the space of non-negative measures on $[0,\infty)$ in such a way that for each $x > 0$, the path $t \mapsto ζ_t[0,x]$ is transformed via a Skorokhod map on the half-line, and the regulating functions for different $x > 0$ are coupled. We establish regularity properties of this map and show that the map provides a convenient tool for studying queueing systems in which tasks are prioritized according to a continuous parameter. Three such well known models are the earliest-deadline-first, the shortest-job-first and the shortest-remaining-processing-time scheduling policies. For these applications, we show how the map provides a unified framework within which to form fluid model equations, prove uniqueness of solutions to these equations and establish convergence of scaled state processes to the fluid model. In particular, for these models, we obtain new convergence results in time-inhomogeneous settings, which appear to fall outside the purview of existing approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An $ε$-Nash equilibrium with high probability for strategic customers in heavy traffic

A multiclass queue with many servers is considered, where customers make a join-or-leave decision upon arrival based on queue length information, without knowing the scheduling policy or the state of other queues. A game theoretic formulation is proposed and analyzed, that takes advantage of a phenomenon unique to heavy traffic regimes, namely Reiman's snaphshot principle, by which waiting times are predicted with high precision by the information available upon arrival. The payoff considered is given as a random variable, which depends on the customer's decision, accounting for waiting time in the queue and penalty for leaving. The notion of an equilibrium is only meaningful in an asymptotic framework, which is taken here to be the Halfin-Whitt heavy traffic regime. The main result is the identification of an $ε$-Nash equilibrium with probability approaching 1. On way to proving this result, new diffusion limit results for systems with finite buffers are obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An asymptotic optimality result for the multiclass queue with finite buffers in heavy traffic

For a multiclass G/G/1 queue with finite buffers, admission and scheduling control, and holding and rejection costs, we construct a policy that is asymptotically optimal in the heavy traffic limit. The policy is specified in terms of a single parameter which constitutes the free boundary point from the Harrison-Taksar free boundary problem, but otherwise depends "explicitly" on the problem data. The c mu priority rule is also used by the policy, but in a way that is novel, and, in particular, different than that used in problems with infinite buffers. We also address an analogous problem where buffer constraints are replaced by throughput time constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Control of the multiclass $G/G/1$ queue in the moderate deviation regime

A multi-class single-server system with general service time distributions is studied in a moderate deviation heavy traffic regime. In the scaling limit, an optimal control problem associated with the model is shown to be governed by a differential game that can be explicitly solved. While the characterization of the limit by a differential game is akin to results at the large deviation scale, the analysis of the problem is closely related to the much studied area of control in heavy traffic at the diffusion scale.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fluid limits of G/G/1+G queues under the non-preemptive earliest-deadline-first discipline

A single-server queuing model is considered with customers that have deadlines. If a customer's deadline elapses before service is offered, the customer abandons the system (customers do not abandon while being served). When the server becomes available, it offers service to the customer having earliest deadline among those that are in the queue. We obtain a fluid limit of the queue length and abandonment processes and for the occupation measure of deadlines, in the form of measure-valued processes. We characterize the limit by means of a Skorohod problem in a time-varying domain, which has an explicit solution. The fluid limits also describe a certain process called the frontier, that is well known to play a key role in systems operating under this scheduling policy.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Information-theoretic applications of the logarithmic probability comparison bound

A well-known technique in estimating probabilities of rare events in general and in information theory in particular (used, e.g., in the sphere-packing bound), is that of finding a reference probability measure under which the event of interest has probability of order one and estimating the probability in question by means of the Kullback-Leibler divergence. A method has recently been proposed in [2], that can be viewed as an extension of this idea in which the probability under the reference measure may itself be decaying exponentially, and the Renyi divergence is used instead. The purpose of this paper is to demonstrate the usefulness of this approach in various information-theoretic settings. For the problem of channel coding, we provide a general methodology for obtaining matched, mismatched and robust error exponent bounds, as well as new results in a variety of particular channel models. Other applications we address include rate-distortion coding and the problem of guessing.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scheduling parallel servers in the nondegenerate slowdown diffusion regime: Asymptotic optimality results

We consider the problem of minimizing queue-length costs in a system with heterogenous parallel servers, operating in a many-server heavy-traffic regime with nondegenerate slowdown. This regime is distinct from the well-studied heavy traffic diffusion regimes, namely the (single server) conventional regime and the (many-server) Halfin-Whitt regime. It has the distinguishing property that waiting times and service times are of comparable magnitudes. We establish an asymptotic lower bound on the cost and devise a sequence of policies that asymptotically attain this bound. As in the conventional regime, the asymptotics can be described by means of a Brownian control problem, the solution of which exhibits a state space collapse.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Robust bounds on risk-sensitive functionals via Renyi divergence

We extend the duality between exponential integrals and relative entropy to a variational formula for exponential integrals involving the Renyi divergence. This formula characterizes the dependence of risk-sensitive functionals and related quantities determined by tail behavior to perturbations in the underlying distributions, in terms of the Renyi divergence. The characterization gives rise to upper and lower bounds that are meaningful for all values of a large deviation scaling parameter, allowing one to quantify in explicit terms the robustness of risk-sensitive costs. As applications we consider problems of uncertainty quantification when aspects of the model are not fully known, as well their use in bounding tail properties of an intractable model in terms of a tractable one.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A stochastic differential game for the inhomogeneous $\infty$-Laplace equation

Given a bounded $\mathcaligr{C}^2$ domain $G\subset{\mathbb{R}}^m$, functions $g\in\mathcaligr{C}(\partial G,{\mathbb{R}})$ and $h\in\mathcaligr {C}(\bar{G},{\mathbb{R}}\setminus\{0\})$, let $u$ denote the unique viscosity solution to the equation $-2Δ_{\infty}u=h$ in $G$ with boundary data $g$. We provide a representation for $u$ as the value of a two-player zero-sum stochastic differential game.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Mutual Information, Relative Entropy, and Estimation in the Poisson Channel

Let $X$ be a non-negative random variable and let the conditional distribution of a random variable $Y$, given $X$, be ${Poisson}(γ\cdot X)$, for a parameter $γ\geq 0$. We identify a natural loss function such that: 1) The derivative of the mutual information between $X$ and $Y$ with respect to $γ$ is equal to the \emph{minimum} mean loss in estimating $X$ based on $Y$, regardless of the distribution of $X$. 2) When $X \sim P$ is estimated based on $Y$ by a mismatched estimator that would have minimized the expected loss had $X \sim Q$, the integral over all values of $γ$ of the excess mean loss is equal to the relative entropy between $P$ and $Q$. For a continuous time setting where $X^T = \{X_t, 0 \leq t \leq T \}$ is a non-negative stochastic process and the conditional law of $Y^T=\{Y_t, 0\le t\le T\}$, given $X^T$, is that of a non-homogeneous Poisson process with intensity function $γ\cdot X^T$, under the same loss function: 1) The minimum mean loss in \emph{causal} filtering when $γ= γ_0$ is equal to the expected value of the minimum mean loss in \emph{non-causal} filtering (smoothing) achieved with a channel whose parameter $γ$ is uniformly distributed between 0 and $γ_0$. Bridging the two quantities is the mutual information between $X^T$ and $Y^T$. 2) This relationship between the mean losses in causal and non-causal filtering holds also in the case where the filters employed are mismatched, i.e., optimized assuming a law on $X^T$ which is not the true one. Bridging the two quantities in this case is the sum of the mutual information and the relative entropy between the true and the mismatched distribution of $Y^T$. Thus, relative entropy quantifies the excess estimation loss due to mismatch in this setting. These results parallel those recently found for the Gaussian channel.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Mirror couplings and Neumann eigenfunctions

We analyze a pair of reflected Brownian motions in a planar domain $D$, for which the increments of both processes form mirror images of each other when the processes are not on the boundary. We show that for $D$ in a class of smooth convex planar domains, the two processes remain ordered forever, according to a certain partial order. This is used to prove that the second eigenvalue is simple for the Laplacian with Neumann boundary conditions for the same class of domains.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Stability Properties of Constrained Jump-Diffusion Processes

We consider a class of jump-diffusion processes, constrained to a polyhedral cone $G\subset\R^n$, where the constraint vector field is constant on each face of the boundary. The constraining mechanism corrects for ``attempts'' of the process to jump outside the domain. Under Lipschitz continuity of the Skorohod map Γ, it is known that there is a cone \mathcalC such that the image Γϕof a deterministic linear trajectory ϕremains bounded if and only if \dotϕ\in\mathcalC. Denoting the generator of a corresponding unconstrained jump-diffusion by \cll, we show that a key condition for the process to admit an invariant probability measure is that for x\in G, \cll \id(x) belongs to a compact subset of \mathcalC^o.

0 citations0 reviewsNo code linkedOpen access