Technical Program > Abstracts

Speaker: Elene Antone (IRIT-CNRS,  Toulouse INP)
Title: On the stability of redundancy models
Abstract: We investigate the stability condition of redundancy-$d$ multi-server systems. We assume there are $K$ servers each with their own queue  and implementing popular scheduling disciplines such as Processor Sharing (PS), First-Come-First-Serve (FCFS), and Random Order of Service (ROS). New jobs arrive at rate $\lambda$ and $d\leq K$ copies are sent to servers chosen uniformly at random. The service times of jobs are assumed to be exponentially distributed with parameter $\mu$. A job's service is completed as soon as one of its copies finishes its service.

Under the assumption that all $d$ copies are i.i.d., we show that for PS and ROS (for FCFS it is already known) sending redundant copies does not reduce the stability region, i.e., a sufficient condition for the system to be stable is $\lambda <K\mu$. We characterize the stability region when the $d$ copies of a given job are identical and show how it heavily depends on the scheduling discipline: under ROS, the system remains maximum stable, whereas under PS and FCFS, when $d=1$ it remains maximum stable and reduces significantly as $d$ approaches $K$, where the stability condition is $\lambda < \mu$. Through simulations we validate the previous results, provide insights into the stability condition when service times are non-exponential and when servers have heterogeneous speeds.

Speaker: Ramin Behzad (Department of Statistics, Faculty of Mathematical Sciences and Computer, Allameh Tabataba’i University, Tehran, Iran.)

Title: Minimum Waiting Time in Queues with Simultaneous Arrival of Customers in the cases of Independence and Dependence
Abstract:  We consider a queueing system where some customers decide to simultaneously wait in two queues, rather than in a single queue, to receive their service. In practice, when there exists a number of queues rendering the same service, the customers may tend to simultaneously wait in more than one queue in order to receive the service sooner and thus scale down their waiting time. In this framework, the customers may abandon one of the queues when they are called to receive the service from the other. We treat this situation as customer reneging or abandonment.  

We study the customer’s waiting time under this model for the cases of independence and dependence of the waiting time random variables of the queues. In conducting this study, a Copula approach is applied to take into account the dependence structure of the waiting time random variables. We compare the numerical results of the dependence with that of the independence.

Speaker: Yan Chen (Columbia University)

Title: Extremal GI/GI/1 Queues Given First Two Moments

Abstract: This paper studies bounds for the mean steady-state waiting time in the GI/GI/1 queue given the first two moments of the interarrival-time and service-time distributions. For distributions with support on bounded intervals, we show that the upper and lower bounds are attained at distributions with support on at most three points. We then apply relatively tractable numerical algorithms to identify the optimal distributions within that class. For distributions with support on the unbounded interval [0,∞), we show that the tight upper bounds are not attained directly, but are obtained asymptotically as the upper bound Ms of the support of the service-time distribution increases. For the upper-bound of the steady-state mean, we propose a simple formula and provide a numerical comparison of the approximations and bounds, showing that the formula for the bound is very accurate

Speaker: Celine Comte (Télécom ParisTech, Nokia Bell Labs [Nozay])   
Title: Dynamic Load Balancing with Tokens
Abstract: Efficiently exploiting the resources of data centers is a complex task that requires efficient and reliable load balancing and resource allocation algorithms. The former are in charge of assigning jobs to servers upon their arrival in the system, while the latter are responsible for sharing the server resources between their assigned jobs. These algorithms should adapt to various constraints, such as data locality, that restrict the feasible job assignments. In this presentation, we introduce a token-based algorithm that efficiently balances the load between the servers without requiring any knowledge on the job arrival rates and server capacities. Assuming a balanced fair sharing of the server resources, we show that the resulting dynamic load balancing is insensitive to the job size distribution. Its performance is compared to that obtained under the best static load balancing and in an ideal system that would constantly optimize the resource utilization. We also make the connection with other token-based algorithms such as Join-Idle-Queue and FCFS-ALIS. 

Speaker: Igor Kleiner (Haifa University)

Title: Generalizations of decomposition property for M^X/G/1  queues with vacations 

Abstract: We present some generalizations of the decomposition property that holds for wide spectrum of queues with vacations. In addition, we extend the decomposition property for the M^X/M/1 queue. For balking abandonment's vacation queue. we show the relation to hyper-geometric functions.

Based on joint work with David Perry (HIT)

Speaker: Binyamin Oz (School of Business Administration, the Hebrew University of Jerusalem)

Title: Strategic bidding in a discrete accumulating priority queue

Abstract: We consider an unobservable M/G/1 accumulating priority queue where homogeneous customers choose one of a finite number of priority classes. We show that there are either one or two pure Nash equilibrium strategies. In the latter case they are two consecutive classes and there exists an equilibrium strategy mixing between these two classes. We find the best-response function and show that it is unimodal, with follow-the-crowd and avoid-the-crowd instances.

Speaker: Youri Raaijmakers (Eindhoven University of Technology)

Title: Redundancy scheduling with scaled Bernoulli service requirements 

Abstract: Redundancy scheduling has emerged as a powerful strategy for improving response times in parallel-server systems.

The key feature in redundancy scheduling is replication of a job upon arrival by dispatching replicas to different servers.
Redundant copies are abandoned as soon as the first of these replicas finishes service. By creating multiple service opportunities, redundancy scheduling increases the chance of a fast response from a server that is quick to provide service, and mitigates the risk of a long delay incurred when a single selected server turns out to be slow.

The diversity enabled by redundant requests has been found to strongly improve the response time performance, especially in case of highly variable service requirements. Analytical results for redundancy scheduling are unfortunately scarce however, and even the stability condition has largely remained elusive so far, except for exponentially distributed service requirements. In order to gain further insight in the role of the service requirement distribution, we explore the behavior of redundancy scheduling for scaled Bernoulli service requirements. We establish the stability condition and show that it drastically differs from the exponential case, indicating that the stability condition depends on the service requirements in a sensitive and intricate manner.

Speaker: Ziv Scully (Carnegie Mellon University)

Title: Optimal Scheduling and Exact Response Time Analysis for Multistage Jobs

Abstract: Scheduling to minimize mean response time in an M/G/1 queue is a classic problem. The problem is usually addressed in one of two scenarios. In the perfect-information scenario, the scheduler knows each job's exact size, or service requirement. In the zero-information scenario, the scheduler knows only each job's size distribution. The well-known shortest remaining processing time (SRPT) policy is optimal in the perfect-information scenario, and the more complex Gittins index policy is optimal in the zero-information scenario.

In real systems the scheduler often has partial but incomplete information about each job's size. We introduce a new job model, that of multistage jobs, to capture the partial-information scenario. A multistage job consists of a sequence of stages, where both the sequence of stages and stage sizes are unknown, but the scheduler always knows which stage of a job is in progress. We give an optimal algorithm for scheduling multistage jobs and an exact response time analysis of our algorithm.

Speaker: Matteo Sfragara (Leiden University) 
Title:  Transition time asymptotics of queue-based activation protocols in random-access networks
Abstract: We study queue-based activation protocols in random-access networks. The network is modeled as an interference graph. Each node of the graph represents a server with a queue. Packets arrive at the nodes as independent Poisson processes and have independent exponentially distributed sizes. Each node can be either active or inactive. When a node is active, it deactivates at unit rate. When a node is inactive, it activates at a rate that depends on its current queue length, provided none of its neighboring nodes is active. Thus, two nodes that are connected by a bond cannot be active simultaneously. This situation arises in random-access wireless networks where, due to interference, servers that are close to each other cannot use the same frequency band. In the limit as the queue lengths at the nodes become very large, we compute the transition time between the two states where one half of the network is active and the other half is inactive.

We compare the transition time with that of a network in which the activation rates are not controlled by the queue length but are externally driven, a situation that was dealt with in an earlier paper. Namely, we first sandwich the transition time between that of two networks in which the activation rates are small perturbations of a certain prescribed function of the mean queue length. After that we show that, as the perturbation tends to zero, the two transition times become asymptotically similar. We focus on a complete bipartite network: we identify the scale of the transition time in terms of the model parameters and we show that its law on the scale of its mean has a trichotomy depending on the aggressiveness of the activation rates. Our aim in future work is to use similar comparison techniques for more general bipartite networks and for more complicated queue-based activation protocols.

Speaker: Lulai Zhu (Imperial College London)

Title: Fluid Approximation of Closed Queueing Networks with Discriminatory Processor Sharing

Abstract: As a multi-class variant of the classical egalitarian processor-sharing (EPS) discipline, discriminatory processor sharing (DPS) provides a suitable paradigm to model time-sharing operating systems and packet-switched communication networks in which share exists to control the service access of heterogeneous jobs. Under the DPS discipline, each class-k job in the system is assigned a positive weight wk, and the service capacity is divided among all the jobs in proportion to their weights. If there are nl(t) class-l jobs in the system at time t, then each class-k job is allotted a fraction wk/ P l wlnl(t) of the service capacity. By adjusting the class-dependent weights, one can therefore effectively control the instantaneous service shares of jobs belonging to different classes. Although DPS is a more general scheduling discipline than EPS, little attention has been paid to closed queueing networks (QNs) with DPS. We propose in this presentation a fluid approach for approximating the transient and steady-state behavior of closed QNs consisting of delay and DPS queueing stations. With a generic definition, our reference model can fit an arbitrary topology. It assumes the service time distributions of each class to be of phase type, and allows a job to switch from one class to another upon service completion at a station. Particularly, we manage to remove the discontinuity inherent in the system of ordinary differential equations resulting from fluid approximation. The proposed approach has been validated against simulation on a large set of model instances for steady-state analysis and on typical examples for transient analysis. Apart from that, we also introduce a refined method and its extension for approximating through transient analysis response time distributions at station and system levels respectively.

Speaker: Alessandro Zocca (California Institute of Technology),

Title: The ghost MCMC algorithm: rare event sampling and applications to power systems reliability

Abstract: In this talk I will introduce a novel algorithm, ghost MCMC, which is designed to efficiently sample from a given distribution restricted on a certain subset of the support, describing for instance a rare event of interest. Our algorithm is easy to implement and improves the performances of the standard MCMC sampling, especially in the case in which the target rare event has multiple well separated modes or, even worse, corresponds to a non-connected subset.
Our main motivation is addressing some important questions arising in power systems reliability, for which the increasing penetration of renewable energy sources is posing serious operational challenges. Our method can perform conditional sampling from any joint distribution of power injections fluctuations (including, for instance, correlated and non-Gaussian disturbances) and, thus, help to understand how overloads or frequency violations could arise from unusually large power disturbance