We consider an epidemic model formed by N elements, where $N\lt \infty$. More precisely, we analyze the susceptible-infected-recovered-susceptible (SIRS) with vaccinations, an extension of the susceptible-infected-recovered (SIR) model where the susceptible population can be vaccinated and a recovered element is again susceptible after a random time. In our model, susceptible elements can avoid getting the infection with some probability (i.e., with a lockdown probability). We assume that each infected element incurs a cost per unit of time and the susceptible population incurs a cost that is decreasing and linear on the lockdown probability. We investigate a non-cooperative game where each player is an element of the population that can select its lockdown probability and aims to minimize its expected cost. Our first contribution consists of formulating the best response lockdown strategy of one player to the strategy of the rest of the players as a Markov Decision Process, which combined with a simple fixed-point algorithm, allows us to compute a solution to this decentralized setting (i.e., a symmetric Nash equilibrium of the game under analysis). We also formulate the centralized problem of finding the global optimum of this model, i.e., the lockdown strategy that minimizes the cost of the whole population, as a Markov Decision Process. We establish some analytical results on the structure of the solution of the centralized and the decentralized problems. Furthermore, our numerical results show that both strategies have a switching curve. We also conclude that the derived Nash equilibria and the global optimum are very similar, i.e. the decentralized architecture is very close to optimal. Finally, we conclude that the global optimum strategy confines more than the solution of the decentralized system (i.e. than the Nash equilibrium).

We study a monitoring system in which a single source sends status updates to a monitor through a communication channel. The communication channel is modeled as a queueing system, and we assume that attacks occur following a random process. When an attack occurs, all packets in the queueing system are discarded. While one might expect attacks to always negatively impact system performance, we demonstrate in this paper that, from the perspective of Age of Information (AoI), attacks can in some cases reduce the AoI. Our objective is to identify the conditions under which AoI is reduced and to determine the attack rate that minimizes or reduces AoI. First, we analyze single and tandem M/M/1/1 queues with preemption and show that attacks cannot reduce AoI in these cases. Next, we examine a single M/M/1/1 queue without preemption and establish necessary and sufficient conditions for the existence of an attack rate that minimizes AoI. For this scenario, we also derive an upper bound for the optimal attack rate and prove that it becomes tight when the arrival rate of updates is very high. Through numerical experiments, we observe that attacks can reduce AoI in tandem M/M/1/1 queues without preemption, as well as in preemptive M/M/1/2 and M/M/1/3 queues. Furthermore, we show that the benefit of attacks on AoI increases with the buffer size.

We present a new framework for designing nonpreemptive and job-size oblivious scheduling policies in the multiserver-job queueing model. The main requirement is to identify astatic and balanced sub-partitionof the server set and ensure that the servers in each set of that sub-partition can only handle jobs of a givenclassand in a first-come first-served order. A job class is determined by the number of servers to which it has exclusive access during its entire execution and the probability distribution of its service time. This approach aims to reduce delays by preventing small jobs from being blocked by larger ones that arrived first, and it is particularly beneficial when the job size variability intra resp. inter classes is small resp. large. In this setting, we propose a new scheduling policy, Balanced-Splitting. In our main results, we provide a sufficient condition for the stability of Balanced-Splitting and show that the resulting queueing probability, i.e., the probability that an arriving job needs to wait for processing upon arrival, vanishes in both the subcritical (the load is kept fixed to a constant less than one) and critical (the load approaches one from below) many-server limiting regimes. Crucial to our analysis is a connection with the M/GI/$s$/$s$queue and Erlang’s loss formula, which allows our analysis to rely on fundamental results from queueing theory. Numerical simulations show that the proposed policy performs better than several preemptive/nonpreemptive size-aware/oblivious policies in various practical scenarios. This is also confirmed by simulations running on real traces from High Performance Computing (HPC) workloads. The delays induced by Balanced-Splitting are also competitive with those induced by state-of-the-art policies such as First-Fit-SRPT and ServerFilling-SRPT, though our approach has the advantage of not requiring preemption, nor the knowledge of job sizes.

The COVID-19 pandemic exposed the importance of research on the spread of epidemic diseases. In the case of COVID-19, official data about infection prevalence was based on PCR and antigen tests reports, which can be unreliable. In our work, we construct prediction models based on Genetic Programming to estimate the SARS-Co V-2 seroprevalence of a given population from multiple estimates of the COVID-19 prevalence (official prevalence data, estimates derived from wastewater data, and estimates obtained from massive surveys with different rules and ML methods). To do that, we propose the use of stacking techniques based on Genetic Programming to obtain Machine Learning Ensemble Methods. Our approach produces more accurate prediction models than conventional stacking techniques based on Linear Regression.

The COVID-19 pandemic exposed the importance of research on the spread of epidemic diseases. In this paper, we apply Artificial Intelligence and statistics techniques to build prediction models to estimate the SARS-CoV-2 seroprevalence in the United States, using multiple estimates of COVID-19 prevalence and other explanatory variables. We propose the use of stacking techniques based on multiple model building techniques (Linear and Beta Regression, Genetic Programming and Neural Networks) to obtain Predictive Ensemble Models. There has been extensive research on this field, but there has not been in-depth research on the application of stacking methods to estimate and forecast seroprevalence in the USA specifically. This paper provides a novel comparison of the behaviour and performance of different building techniques for stacking ensemble models and presents which methods are better for different scenarios. We find that Genetic Programming and Neural Networks are the best models with trained data within single states, and when multiple states are considered Genetic Programming is still better than the Regression models, but Neural Networks fail to estimate the seroprevalence accurately. Another novelty of our work is the use of cross-state validation to evaluate the models with new data, as well as temporal forecasting. Depending on how the data is processed, Linear Regression performs very well with cross-state validation and temporal forecasting, and Genetic Programming is very accurate with the former while Neural Networks work better with the latter.

Energy Packet Networks (EPNs) model the interaction between renewable sources generating energy following a random process and communication devices that consume energy. This network is formed by cells and, in each cell, there is a queue that handles energy packets and another queue that handles data packets. We assume Poisson arrivals of energy packets and of data packets to all the cells and exponential service times. We consider an EPN model with a dynamic load balancing where a cell without data packets can poll other cells to migrate jobs. This migration can only take place when there is enough energy in both interacting cells, in which case a batch of data packets is transferred and the required energy is consumed (i.e. it disappears). We consider that data packet also consume energy to be routed to the next station. Our main result shows that the steady-state distribution of jobs in the queues admits a product form solution provided that a stable solution of a fixed point equation exists. We prove sufficient conditions for irreducibility. Under these conditions and when the fixed point equation has a solution, the Markov chain is ergodic. We also provide sufficient conditions for the existence of a solution of the fixed point equation. We then focus on layered networks and we study the polling rates that must be set to achieve a fair load balancing, i.e., such that, in the same layer, the load of the queues handling data packets is the same. Our numerical experiments illustrate that dynamic load balancing satisfies several interesting properties such as performance improvement or fair load balancing.

A dynamic bipartite matching model is given by a bipartite matching graph which determines the possible matchings between the various types of supply and demand items. Both supply and demand items arrive to the system according to a stochastic process. Matched pairs leave the system and the others wait in the queues, which induces a holding cost. We model this problem as a Markov Decision Process and study the discounted cost and the average cost problem. We assume that the cost function is linear on the queue sizes. We show that for the N-shaped matching graph, an optimal matching control prioritizes the matchings in the pendant edges and is of threshold type for the diagonal edge. In addition, for the average cost problem, we compute the optimal threshold value. We then show how the obtained results can be used to characterize the structure of an optimal matching control for a quasi-complete graph with an arbitrary number of nodes. For arbitrary bipartite graphs, we show that, when the cost of the pendant edges is larger than in the neighbors, an optimal matching policy prioritizes the items in the pendant edges. We also study the W-shaped matching graph and, when the cost of the pendant edges is larger than the cost of the middle edge, we conjecture that an optimal matching policy is also of threshold type with priority to the pendant edges; however, when the cost of the middle edge is larger, we present simulations that show that it is not optimal to prioritize items in the pendant edges.

Energy Packet Network (EPN) consists of a queueing network formed by N blocks, where each of them is formed by one data queue, that handles the workload, and one energy queue, that handles packets of energy. We study an EPN model where the energy packets start the transfer. In this model, energy packets are sent to the data queue of the same block. An energy packet routes one workload packet to the next block if the data queue is not empty, and it is lost otherwise. We assume that the energy queues have a finite buffer size and if an energy packet arrives to the system when the buffer is full, jump-over blocking (JOB) is performed, and therefore with some probability it is sent to the data queue and it is lost otherwise. We first provide a value of the jump-over blocking probability such that the steady-state probability distribution of packets in the queues admits a product form solution. The product form is established for multiserver and multiclass data packet queues under FCFS, preemptive LCFS and PS discipline. Moreover, in the case of a directed tree queueing network, we show that the number of data packets in each subtree decreases as the JOB probability increases for each block.

We investigate the performance of two size-based routing policies: the Size Interval Task Assignment (SITA) and Task Assignment based on Guessing Size (TAGS). We consider a system with two servers and Bounded Pareto distributed job sizes with tail parameter 1 where the difference between the size of the largest and the smallest job is finite. We show that the ratio between the mean waiting time of TAGS over the mean waiting time of SITA is unbounded when the largest job size is large and the arrival rate times the largest job size is less than one. We provide numerical experiments that show that our theoretical findings extend to Bounded Pareto distributed job sizes with tail parameter different to 1.

In a system formed by parallel servers and one dispatcher, we study the Task Assignment based on Guessing Size (TAGS) policy, an open loop task assignment policy where jobs are non-preemptive, servers are First-Come-First-Served and the size of incoming jobs is not known. This policy works as follows: all the incoming jobs are routed to the first server and jobs that complete service before s 1 units of time leave the system, but jobs that do not complete service before s 1 are killed and they are routed to the second server, where the service starts from scratch. Likewise, jobs that are executed in server i, if they complete service before s i units of time, leave the system, whereas jobs that do not complete service before s i units of time are killed and routed to the next server. For an arbitrary job size distribution, we provide a necessary and sufficient condition for the stability of a system operating under the TAGS policy. We also analyze the performance of the optimal TAGS policy, i.e., when the cutoffs s 1, s 2, . . . are chosen to minimize the waiting time of jobs for an arbitrary job size distribution and we show that it is lower bounded by the performance of the TAGS policy where the maximum queue length is minimized divided by the number of servers minus one. For Bounded Pareto distributed job sizes, we consider the asymptotic regime where the largest job size tends to infinity and we show that, when the system load is less than one, the performance of the optimal TAGS policy is, at most, two times worst than the performance of the optimal SITA policy, which a routing policy where the size of jobs is known. This result shows that the penalty caused by not knowing the size of incoming jobs is upper bounded by a factor of 2. For a higher system load, we show that the order of magnitude of the performance of the optimal TAGS policy in the asymptotic regime depends on the number of spare servers, i.e., the difference between the number of servers in the system and the minimum number of servers to stabilize the system. According to our numerical experiments, when the largest job size is finite, the difference on the performance between the TAGS policy and the SITA policy can be extremely large when the system load is higher than one, whereas it is small when the system load is less than one.

We consider a parallel-server system with homogeneous servers where incoming tasks, arriving at rate λ, are dispatched by n dispatchers, each of them balancing a fraction 1/n of the load to K/n servers. Servers are first-come-first-served (FCFS) queues and dispatchers implement size interval task assignment policy with equal load (SITA-E), a size-based policy such that the servers are equally loaded. We compare the performance of a system with n > 1 dispatchers and a single dispatcher. We show that the performance of a system with n dispatchers, K servers, and arrival rate λ coincides with that of a system with one dispatcher, K/n servers, and arrival rate λ/n. We define the degradation factor as the ratio between the performance of a system with K servers and arrival rate λ and the performance of a system with K/n servers and arrival rate λ/n. We establish a partial monotonicity on n for the degradation factor and, therefore, the degradation factor is lower bounded by one. We then investigate the upper bound of the degradation factor for particular distributions. We consider two continuous service time distributions: uniform and bounded Pareto and a discrete distribution with two values, which is the distribution that maximizes the variance for a given mean. We show that the performance degradation is small for uniformly distributed job sizes but that for Bounded Pareto and two points distributions it can be unbounded. We have investigated the degradation using the distribution obtained from real traces.

Size-based routing provides robust strategies to improve the performance of computer and communication systems with highly variable workloads because it is able to isolate small jobs from large ones in a static manner. The basic idea is that each server is assigned all jobs whose sizes belong to a distinct and continuous interval. In the literature, dispatching rules of this type are referred to as SITA (Size Interval Task Assignment) policies. Though their evident benefits, the problem of finding a SITA policy that minimizes the overall mean (steady-state) waiting time is known to be intractable. In particular it is not clear when it is preferable to balance or unbalance server loads and, in the latter case, how. In this paper, we provide an answer to these questions in the celebrated limiting regime where the system capacity grows linearly with the system demand to infinity. Within this framework, we prove that the minimum mean waiting time achievable by a SITA policy necessarily converges to the mean waiting time achieved by SITA-E, the SITA policy that equalizes server loads, provided that servers are homogeneous. However, within the set of SITA policies we also show that SITA-E can perform arbitrarily bad if servers are heterogeneous. In this case we prove that there exist exactly C! asymptotically optimal policies, where C denotes the number of server types, and all of them are linked to the solution of a single strictly convex optimization problem. It turns out that the mean waiting time achieved by any of such asymptotically optimal policies does not depend on how job-size intervals are mapped to servers. Our theoretical results are validated by numerical simulations with respect to realistic parameters and suggest that the above insights are also accurate in small systems composed of a few servers, i.e., ten.

We consider a parallel-server system with K homogeneous servers where incoming tasks, arriving at rate λ, are dispatched by n dispatchers. Servers are FCFS queues and dispatchers implement a size-based policy such that the servers are equally loaded. We compare the performance of a system with n> 1 dispatchers and of a system with a single dispatcher. Every dispatcher handles a fraction 1/n of the incoming traffic and balances the load to K/n servers. We show that the performance of a system with n dispatchers, K servers and arrival rate λ coincides with that of a system with one dispatcher, K/n servers and arrival rate λ/n. Therefore, the performance comparison can be interpreted as the economies of scale in a system with one dispatcher when we scale up the number of servers and the arrival rate proportionately. We consider two continuous service time distributions: uniform and Bounded Pareto that have increasing and decreasing failure rates, respectively; and a discrete distribution with two values, which is the distribution that maximizes the variance for a given mean. We show that the performance degradation is small for uniformly distributed job sizes, but that for Bounded Pareto and two points distributions it can be unbounded.

Price of anarchy is an oft-used worst-case measure of the inefficiency of noncooperative decentralized architectures. For a noncooperative load-balancing game with two classes of servers and for a finite or infinite number of dispatchers, we show that the price of anarchy is an overly pessimistic measure that does not reflect the performance obtained in most instances of the problem. We explicitly characterize the worst-case traffic conditions for the efficiency of noncooperative load-balancing schemes and show that, contrary to a common belief, the worst inefficiency is in general not achieved in heavy traffic.