EWD775

On Kleinrock’s Theorem.

The following has been triggered by C.A.R. Hoare’s “A general conservation law for queuing disciplines” (Information Processing Letters 2 (1972) 82–85); this article refers to L. Kleinrock, “A conservation law for queuing disciplines”, Naval Research Logistics Quarterly (June 1965) 181–192, and has been submitted because it offers for Kleinrock’s theorem a proof that is simpler than the original one.

In Hoare’s formulation, Kleinrock’s theorem is as follows. Assume (1) No server is idle when there is a waiting customer. (2) Arrival times and service times of both customers and servers are not affected by the decision who is to receive service at what time (i.e. they are independent of the scheduling). (3) Preemption is not used. Then

N ∑ i=1 W_i ·R_i

is independent of the choice of non-preemptive scheduling method. Here the customers are numbered from 1 through N, W_i is the total waiting time for customer i, and R_i is the total service time for customer i.

This note is written to point out that (1) for a single-server system the proof is trivial, and (2) for a multi-server system the theorem is not quite correct.

*              *
*

Consider a schedule in which customer q is served immediately after customer p, with W_q > W_p. The possible decision to service these two customers in the other order would have affected the waiting time as follows.

W_p, W_q := W_p+ R_q, W_q− R_p

The products W_p· R_p and W_q· R_q are therefore increased and decreased respectively by the product of the service times, and their sum remains constant. Kleinrock’s theorem follows by induction

*               *
*

Consider a two-server system in which three customers, with service times =1, =1, and =2 respectively, arrive simultaneously. Two schedules are possible with ∑W_i · R_i = 1 and = 2 respectively. For customer i, which is served from t 0 till t1 we can define a “moment of inertia” of his service as

   t1 ∫ t 0 t ·dt  =  ½ (t1²−t 0²)  =  (t1−t 0) · ⟮

t 0 + t1 / 2

⟯  =  R_i · (A_i + W_i  + ½ R_i)  =  R_i · W_i + C_i

where A_i is the moment of arrival of customer i and C_i = R_i · (A_i + ½R_i); our assumptions imply that C_i is independent of the scheduling. If S(t) is the number of customers served at moment t, then the "moment of inertia” of total service satisfies

   T ∫ 0 S(t) ·t ·dt   =   N ∑ i=1 R_i ·W_i + N ∑ i=1 C_i

Hence, Kleinrock’s theorem holds among schedules with the same “moment of inertia” of total service.

Acknowledgement. I am indebted to C.A.R. Hoare for having invited me to try to simplify is proof (which was already a simplification of Kleinrock’s). (End of acknowledgement.)

Plantaanstraat 5	4 February 1982
5671 AL NUENEN	prof. dr. Edsger W. Dijkstra
The Netherlands	Burroughs Research Fellow

---

Transcribed by Martin P.M. van der Burgt
Last revision 12-Nov-2015 .