In a system containing several distributed servers, messages of random sizes generated at different locations must be disseminated and processed in the same order by all hosts. A ring protocol is defined, where a number of folders carrying messages circulate in one direction without overtaking each other. A model involving parallel queues is analysed in the steady state and is solved approximately, allowing the computation of performance measures. A number of example systems are evaluated numerically and by simulations, leading to a heuristic for choosing the optimal number of folders.

Distributed OLTP systems execute the high-overhead, two-phase commit (2PC) protocol at the end of every distributed transaction. Epoch-based commit proposes that 2PC be executed only once for all transactions processed within a time interval called an epoch. Increasing epoch duration allows more transactions to be processed before the common 2PC. It thus reduces 2PC overhead per transaction, increases throughput but also increases average transaction latency. Therefore, required is the ability to choose the right epoch size that offers the desired trade-off between throughput and latency. To this end, we develop two analytical models to estimate throughput and average latency in terms of epoch size taking into account load and failure conditions. Simulations affirm their accuracy and effectiveness. We then present epoch-based multi-commit which, unlike epoch-based commit, seeks to avoid all transactions being aborted when failures occur, and also performs identically when failures do not occur. Our performance study identifies workload factors that make it more effective in preventing transaction aborts and concludes that the analytical models can be equally useful in predicting its performance as well.

Round robin (RR) is a widely adopted scheduling policy in modern computer systems. The scheduler handles the concurrency by alternating the run processes in such a way that they can use the processor continuously for at most a quantum of time. When the processor is assigned to another process, a context switch occurs. Although modern architectures handle context switches quite efficiently, the processes may incur in some indirect costs mainly due to cache overwriting.

In the last years, blockchains have become a popular technology to store immutable data validated in a peer-to-peer way. Software systems can take advantage of blockchains to publicly store data (organised in transactions) which is immutable by design. The most important consensus algorithm in public blockchains is the proof-of-work in which miners invest a huge computational power to consolidate new data in a ledger. Miners receive incentives for their work, i.e., a fee decided and paid for each transaction. Rational miners aim to maximise the profit generated by the mining activity, and thus choose the transactions offering the highest fee per byte for their consolidation. In this paper, we propose a queueing model to study the relation between the fee offered by a transaction and its expected consolidation time, i.e., the time required to be added to the blockchain by the miners. The solution of the queueing model, although approximate, is computationally and numerically efficient and software systems can use it online to analyse the trade-off between costs and response times. Indeed, a static configuration of the model would not account for the high variations in the blockchain workload and fees offered by other users.

A stream-processing server model consisting of an external queue and an internal queue, with instantaneous or non-instantaneous transfers between the two, is analysed in the steady state. Jobs are collected into batches of fixed size prior to being transferred, but there is also a timer mechanism that may preempt such a collection. Exact and approximate solutions are obtained. These are used in order to evaluate the trade-offs between holding costs and transfer costs. The results of several numerical experiments are presented.

We examine a system where servers can host several virtual machines in parallel and where some of the users are malicious. Arrivals and departures of both normal and malicious users are governed by random processes. The aim is to estimate the probability that a possible target will find itself sharing a server with an attacker. Two allocation policies for assigning virtual machines to servers are studied. In both cases, as well as attacks forming part of the arrival process, multiple simultaneous attacks are considered. Closed-form expressions for the desired estimates are obtained. Comparisons with simulations for purposes of validation are presented and the effect of increasing the number of available servers is illustrated.

Services of different types are provided to paying customers on servers hired from a cloud. Different virtual machines can share a server, subject to one or more resource constraints. Incoming jobs whose resource requirements cannot be satisfied are lost. The objective is to maximize the long-term average profit per unit time. A single-server model is analyzed exactly and the results provide approximations for the system with n servers. The latter is also solved exactly when the servers are dedicated and when the VMs can migrate instantaneously. Numerical examples and comparisons with simulations are presented.

Concurrent processing has become the default mode of operation in on-chip systems. Silicon has become cheap enough for having hardware facilities to support very large scale concurrent processing on chip. As a result the availability and applicability of power is becoming more of a limiting factor than logic. However, the advantage of parallelism in reducing power consumption will soon become unrealistic because of the limited scope of reducing Vdd beyond threshold voltage, leaving the reduction of concurrency (through the partial shut-down of system blocks) as a realistic means of reducing power consumption when needed. A stochastic modelling approach is presented in this paper which can integrate the degree of concurrency as a parameter into power and latency analysis. This will facilitate a system design and management regime where the degree of concurrency is used as a means of control to achieve power and performance goals.

We examine some of the problems associated with managing a server farm, that is, a collection of servers which are used to provide different types of services to paying customers. The users are charged for the services provided, but are also promised that certain Quality-of-Service (QoS) criteria will be met. Failure to satisfy those QoS undertakings incurs pre-specified penalties. In order to maximize the revenue obtained, the service provider must employ intelligent dynamic policies dealing with server allocation and job admission decisions. A number of such policies are surveyed.

We construct, analyze and solve models of systems where a number of servers offer services to an incoming stream of demands. Each server goes through alternating periods of being operative and inoperative. The objective is to evaluate and optimize performance and cost metrics. A large real-life data set containing information about server breakdowns is analyzed first. The results indicate that the durations of the operative periods are not distributed exponentially. However, hyper exponential distributions are found to be a good fit for the observed data. A model based on these distributions is then formulated, and is solved exactly using the method of spectral expansion. A simple approximation which is accurate for heavily loaded systems is also proposed. The results of a number of numerical experiments are reported

Encounter Gossip is a family of message propagation protocols for mobile ad-hoc networks. The coverage of propagation (the fraction of nodes that receive the message) can be made arbitrarily close to 1 at the cost of increased bandwidth overhead. This paper proposes several schemes to minimize this overhead without compromising the achieved coverage. The schemes can be timer based or history based. Their effectiveness is assessed through simulations performed in the context of two mobility models.

This paper presents and studies a reliable multicast protocol whose objective is to deliver a message to all intended destinations, despite possible crashes of the sender and other processes, and communication failures. The protocol enables QoS metrics such as absolute and relative latencies and the probability of reliable delivery, to be negotiated prior to service provisioning. Moreover, it adapts certain parameters dynamically in order to minimize the message traffic required to achieve the negotiated QoS metrics. The performance of the protocol is analyzed mathematically under simplifying assumptions. The accuracy of the approximations is evaluated by simulations.

No abstract available.

New methods are presented for parallel simulation of discrete event systems that, when applicable, can usefully employ a number of processors much larger than the number of objects in the system being simulated, Abandoning the distributed event list approach, the simulation problem is posed using recurrence relations.We bring three algorithmic ideas to bear on parallel simulation: parallel prefix computation, parallel merging, and iterative folding.Efficient parallel simulations are given for (in turn) the G/G/l queue, a variety of queueing networks having a global first come first served structure (e.g., a series of queues with finite buffers), acyclic networks of queues, and networks of queues with feedbacks and cycles.In particular, the problem of simulating the arrival and departure times for the first N jobs to a single G/G/l queue is solved in time proportional to N/P + log P using P processors.

New methods are presented for parallel simulation of discrete event systems that, when applicable, can usefully employ a number of processors much larger than the number of objects in the system being simulated. Abandoning the distributed event list approach, the simulation problem is posed using recurrence relations. We bring three algorithmic ideas to bear on parallel simulation: parallel prefix computation, parallel merging, and iterative folding. Efficient parallel simulations are given for (in turn) the G/G/1 queue, a variety of queueing networks having a global first come first served structure (e.g., a series of queues with finite buffers), acyclic networks of queues, and networks of queues with feedbacks and cycles. In particular, the problem of simulating the arrival and departure times for the first N jobs to a single G/G/1 queue is solved in time proportional to N/P + log P using P processors.

A distributed system in which a job can be broken into a number of subjobs which are processed sequentially at various processors is considered. The performance of such a system is then compared to the replicated (triple modular redundant, or TMR) version of the system in which each subjob will require concurrent replicated processing with majority voting. The effect of voting times and processor failure rates on the performance of the system is investigated with analytical approximations and computer simulations. The accuracy of the former is examined. The results indicate the possible existence of a threshold voting time, below which the TMR system performs better than the unreplicated one, and above which the situation is reversed. Such thresholds are observed, where possible, in systems with repairable servers, as well as in those with nonrepairable servers.>

We study systems consisting of a number of service cells in tandem, each containing a finite buffer. Several policies governing the operation of such systems are described and compared. These include traditional and novel blocking schemes, with applications to computer communications and production lines. In particular, it is shown that kanban, a novel discipline for coordinating cells in a manufacturing context, is obtained by combining two, more basic, concepts: a blocking policy introduced here as minimal blocking, and shared buffers. The Kanban discipline is superior in terms of throughput to the ordinary transfer blocking policy.

Models for local area networks of the slotted ring style of architecture are developed and evaluated. The hardware protocol is modeled using a BCMP network. The Basic Block protocol of the Cambridge ring is modeled using an approximate solution method of the fixed-point type. A limited comparison between the Cambridge Ring and another ring architecture—the token ring—is carried out.

The tradeoffs between efficiency and reliability in M / M / N queueing systems subject to breakdowns are studied numerically. The dependence of the optimal number of servers on the system parameters is investigated under two different sets of assumptions about the pattern of breakdowns and repairs.

Queuing networks are studied at selected points in the steady state, namely, at the moments when jobs of a given class arrive into a given node (either from the outside or from other nodes) and at the moments when jobs of a given class leave a given node (either for the outside or for other nodes).The processes defined by these points are known to be, in general, non-Potsson, interdependent, and serially correlated; therefore the relation between the distribution of the system state embedded at those moments and the steady-state (or random point) distribution is not obvious a priori.For a large class of networks having product-form equihbrium distribnttons it is shown that (a) if the given job class belongs to an open subchain, the state distributions at input pomts, output points, and random points are identical, and (b) if the job class belongs to a closed subchain, the distribution at input and output points ts the same as the steady-state distribution of a network with one less job in that subchain.

A single-server processor-sharing system with M job classes is analyzed in the steady state.The scheduling strategy considered divides the total processor capacity in unequal fractions among the different job classes.More precisely, if there are N~jobs of classj in the system, j = 1, 2 ..... M, each class k job receives a fraction gh/(~M.~giN~) of the processor capacity.Earlier analyses of this system are shown to be incorrect and new expressions for the conditional expected response times Wk(t) of class k jobs with required service time t are obtained (for general required service time distributions).These yield the asymptotic behavior of W~(t) as t ~ oo and rather simple formulas in the exponential case.The unconditional average response times are also obtained.

In this paper we study the problem of designing scheduling strategies when the demand on the system is known and waiting time requirements are pre-specified. This important synthesis problem has received little attention in the literature, and contrasts with the common analytical approach to the study of computer service systems. This latter approach contributes only in-directly to the problem of finding satisfactory scheduling rules when the desired (or required) response-time performance is specifiable in advance.

A simple cyclic-queue model of a multiprogramming system with a fixed number of tasks is analyzed in its steady state.Expressions for queue-size distribution, average rate of job completions, and average stay-in-the-system time are derived.A measure of system efficiency alternative to processor utilization is suggested and optimal values for the degree of multiprogramming are given for various values of the parameters.