Replication is a technique used in distributed systems to improve performance, availability, and reliability. In replication schemes, often a J out of $N$ voting pattern (also called quorum) is used in which the quorum waits for J replies to arrive. Integrating a quorum scheme into the Layered Queueing Network (LQN) performance modeling language necessitates the computation of the quorum response time as the Jth order statistic. To do so, we need the exact (or an accurate estimation of the) time distribution of individual replies. This distribution was estimated in previous work but only for the special case of (J=N) and yields large errors for J N. This paper presents a new analytic approach for the derivation of the distributions. Under a number of assumptions, we derive closed form expressions for the probability distribution functions of the replies. The application of our new approach on a number of LQN models shows that, even for models that violate those assumptions, it is far more accurate than previous approaches and it yields an error less than 10% for most example models. Copyright 2007 ACM.

, , , ,
doi.org/10.1145/1216993.1217007
6th International Workshop on Software and Performance, WOPS'07
Department of Systems and Computer Engineering

Omari, T. (Tariq), Derisavi, S. (Salem), & Franks, G. (2007). Deriving distribution of thread service time in layered queueing networks. Presented at the 6th International Workshop on Software and Performance, WOPS'07. doi:10.1145/1216993.1217007