Task replication has been advocated as a practical solution to reduce response times in parallel systems. The analysis of replication-based systems typically rests on some strong assumptions: Poisson arrivals, exponential service times, or independent service times of the replicas. This study is motivated not only by several studies which indicate that these assumptions are unrealistic, but also by some elementary observations highlighting some contriving behaviour. For instance, when service times are not exponential, adding a replication factor can stabilize an unstable system, i.e., having infinite delays, but a tempting higher replication factor can push the system back in a perilous unstable state. This behaviour disappears however if the replicas are sufficiently correlated, in which case any replication factor would even be detrimental.Motivated by the need to dispense with such common yet unrealistic and misleading assumptions, we provide a robust theoretical framework to compute stochastic bounds on response time distributions in general replication systems subject to Markovian arrivals, quite general service times, and correlated replicas. Numerical results show that our bounds are accurate and improve state-of-the-art bounds in the case of Markovian arrivals by as much as three orders of magnitude. We apply our results to a practical application and highlight that correctly setting the replication factor crucially depends on both the service time distributions of the replicas and the degree of correlation amongst.

Task replication has recently been advocated as a practical solution to reduce latencies in parallel systems. In addition to several convincing empirical studies, analytical results have been provided, yet under some strong assumptions such as independent service times of the replicas, which may lend themselves to some contrasting and perhaps contriving behavior. For instance, under the independence assumption, an overloaded system can be stabilized by a replication factor, but can be sent back in overload through further replication. Motivated by the need to dispense with such common and restricting assumptions, which may cause unexpected behavior, we develop a unified and general theoretical framework to compute tight bounds on the distribution of response times in general replication systems. These results immediately lend themselves to the optimal number of replicas minimizing response time quantiles, depending on the parameters of the system (e.g., the degree of correlation amongst replicas).

This paper analyzes queueing behavior subject to multiplexing a stochastic process M(n) of flows, and not a constant as conventionally assumed. By first considering the case when M(n) is iid, it is shown that flows' multiplexing `hurts' the queue size (i.e., the queue size increases in distribution). The simplicity of the iid case enables the quantification of the `best' and `worst' distributions of M(n), i.e., minimizing/maximizing the queue size. The more general, and also realistic, case when M(n) is Markov-modulated reveals an interesting behavior: flows' multiplexing `hurts' but only when the multiplexed flows are sufficiently long. An important caveat raised by such observations is that the conventional approximation of M(n) by a constant can be very misleading for queueing analysis.

This paper proposes a martingale extension of effective-capacity, a concept which has been instrumental in teletraffic theory to model the link-layer wireless channel and analyze QoS metrics. Together with a recently developed concept of an arrival-martingale, the proposed service-martingale concept enables the queueing analysis of a bursty source sharing a MAC channel. In particular, the paper derives the first rigorous and accurate stochastic delay bounds for a Markovian source sharing either an Aloha or CSMA/CA channel, and further considers two extended scenarios accounting for 1) in-source scheduling and 2) spatial multiplexing MIMO. By leveraging the powerful martingale methodology, the obtained bounds are remarkably tight and improve state-of-the-art bounds by several orders of magnitude. Moreover, the obtained bounds indicate that MIMO spatial multiplexing is subject to the fundamental power-of-two phenomena.

In a Fork-Join (FJ) queueing system an upstream fork station splits incoming jobs into N tasks to be further processed by N parallel servers, each with its own queue; the response time of one job is determined, at a downstream join station, by the maximum of the corresponding tasks' response times. This queueing system is useful to the modelling of multi-service systems subject to synchronization constraints, such as MapReduce clusters or multipath routing. Despite their apparent simplicity, FJ systems are hard to analyze.

The practicality of the stochastic network calculus (SNC) is often questioned on grounds of potential looseness of its performance bounds. In this paper, it is uncovered that for bursty arrival processes (specifically Markov-Modulated On-Off (MMOO)), whose amenability to per-flow analysis is typically proclaimed as a highlight of SNC, the bounds can unfortunately be very loose (e.g., by several orders of magnitude off). In response to this uncovered weakness of SNC, the (Standard) per-flow bounds are herein improved by deriving a general sample-path bound, using martingale based techniques, which accommodates FIFO, SP, and EDF scheduling. The obtained (Martingale) bounds capture an extra exponential decay factor of O (e−αn) in the number of flows n. Moreover, numerical comparisons against simulations show that the Martingale bounds are not only remarkably accurate, but they also improve the Standard SNC bounds by factors as large as 100 or even 1000.

This paper analyzes queueing behavior in queues with a random number of parallel flows, and not static as typically assumed. By deriving upper and lower bounds on the queue size distribution, the paper identifies extremal properties in such dynamic queues. The extremal best-case distribution (minimizing the queue) is simply the constant, whereas the worst-case distribution (maximizing the queue) has a bimodal structure. From a more practical point of view, this paper highlights an idiosyncrasy of dynamic queues: unlike in static queues whereby capacity dimensioning is dominated by average-values (subject to certain safety margins), in dynamic queues the capacity dimensioning is dominated instead by peak-values.

The practicality of the stochastic network calculus (SNC) is often questioned on grounds of potential looseness of its performance bounds. In this paper it is uncovered that for bursty arrival processes (specifically Markov-Modulated On-Off (MMOO)), whose amenability to per-flow analysis is typically proclaimed as a highlight of SNC, the bounds can unfortunately indeed be very loose (e.g., by several orders of magnitude off). In response to this uncovered weakness of SNC, the (Standard) per-flow bounds are herein improved by deriving a general sample-path bound, using martingale based techniques, which accommodates FIFO, SP, and EDF scheduling disciplines. The obtained (Martingale) bounds capture an additional exponential decay factor of O(e-α n) in the number of flows $n$, and are remarkably accurate even in multiplexing scenarios with few flows.