Computing Publications

Publications Home » Performance Enhancement by Means ...

Performance Enhancement by Means of Task Replication

Peter G. Harrison, Zhan Qiu

Conference or Workshop Paper
10th European Workshop
September, 2013
Lecture Notes in Computer Science
Volume 8168
Springer Berlin / Heidelberg
ISBN 978-3-642-40725-3
ISSN 0302-9743
DOI 10.1007/978-3-642-40725-3_15

In order for systems in which tasks may fail to be fault tolerant, traditional methods deploy multiple servers as replicas to perform the same task. Further, in real time systems, computations have to meet strict time-constraints, a delayed output being unacceptable, even if correct. The effectiveness of sending task-replicas to multiple servers simultaneously, and using the results from whichever one responds first, is considered in this paper as a means of reducing response time and improving fault-tolerance. Once a request completes execution in one server successfully, it immediately cancels (kills) its replicas that remain at other servers. We assume a Markovian system and use the generating function method to determine the Laplace transform of the response time probability distribution, jointly with the probability that not all replicas fail, in the case of two replicas. When the failure rate of each task is greater than the service rate of the server, we make the approximation that the queues are independent, each with geometric queue length probability distributions at equilibrium. We compare our approximation with simulation results as well as with the exact solution in a truncated state space and find that for failure rates in that region, the approximation is generally good. At lower failure rates, the method of spectral expansion provides an excellent approximation in a truncated, multi mode, two dimensional Markov process.

BibTEX file for the publication
Copyright notice

2013 built & maintained by Ashok Argent-Katwala.