**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=1W_{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`is the total service time for customer

_{i}`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`and

_{p}`W`·

_{q}`R`are therefore increased and decreased respectively by the product of the service times, and their sum remains constant. Kleinrock’s theorem follows by induction

_{q}* *

*

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

`t`1 we can define a “moment of inertia” of his service as

t1 ∫t0t·dt= ½ (t1^{2}−t0^{2}) = (t1−t0) · ⟮⟯ =t0 +t1 2R· (_{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`); our assumptions imply that

_{i}`C`is independent of the scheduling. If S(

_{i}`t`) is the number of customers served at moment

`t`, then the

`"`moment of inertia” of total service satisfies

Hence, Kleinrock’s theorem holds among schedules with the same “moment of inertia” of total service.T∫ 0 S(t) ·t·dt=N∑i=1R_{i}·W_{i}+N∑i=1C_{i}

**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