Picture by Freddy Bruckstein

The book

Large Deviations for Performance Analysis

Queues, Communication, and Computing

by Adam Shwartz and Alan Weiss
is out in a revised edition. Here is the relevant information.
If you haven't see the book before, take a look at a brief ad and sample chapter

Published by Chapman & Hall
Now part of CRC press
April 1995: 6 x 9: 576 pp
Cloth: ISBN 0 412 06311 5: #B8827.
CRC Catalogue number C6311
Probability/ Applied Mathematics/ Operations Research

 New Order Numbers

Order (800) 272-7737 from the US and Canada

Fax 800 374 3401

Europe, Middle Each and Africa:

Telephone 44 1462 488900, Fax 44 1462 483011

Australia and New Zeland:

Telephone 61 3 9210 7777, Fax 61 3 9210 7778

 Or you can even order on the web from the publisher, or from an online bookstore: Melville, or Amazon.

 The new edition (early 1997) incorporates a number of corrections. Unfortunately, Chapman Hall also raised the price (several times). If you have the first edition, feel free to download PostScript files that contain all the changes. Here are the changes and new PS files.

 Here are the corrections that weren't incoprorated into the second edition.

 Brief ad (followed by Table of Contents, Synopsis, and suggestions for courses based on the book):

 The book is designed to be an introduction to the theory, and a compelling collection of real engineering applications, for advanced undergraduate and graduate students in engineering and applied mathematics. The book is also a reference resource for mathematicians, researchers, and engineers. The book is self-contained, with detailed appendices to cover all the major tools used in the book, and over 60 figures.

 The table of contents, Chapter 0 (Introduction/Preface), and Chapter 1 (together with a unique cover that is not included with the printed version!) are available as a PostScript or PDF file

We have an errata page with all errata which are incorporated into the second printing. We shall create an errata page for the second printing as soon as errors are found... (Updated September 9, 1996).


Adam Shwartz is with the Faculty of Electrical Engineering, Technion-Israel Institute of Technology, Haifa, Israel.

Alan Weiss is a member of the technical staff at Bell Laboratories, Murray Hill, NJ.


  • Theory (pages 1-242):

1. Large Deviations of Random Variables
2. General Principles
3. Random Walks, branching processes
4. Poisson and Related Processes
5. Large Deviations for Processes
6. Freidlin-Wentzell Theory
7. Applications and Extensions
8. Boundary Theory

  • Applications (pages 243-470):

9. Allocating Independent Subtasks
10. Parallel Algorithms: Rollback
11. The M/M/1 Queue
12. Erlang's Model
13. The Anick-Mitra-Sondhi Model
14. Aloha
15. Priority Queues
16. The Flatto-Hahn-Wright model

  • Appendices (pages 471-538):

A. Analysis and Probability
B. Discrete-Space Markov Processes
C. Calculus of Variations
D. Large Deviations Techniques

  • References
  • Index

 Back to the top


This book consists of two synergistic parts.

 The first half is the theory of large deviations developed from the beginning (i.i.d. random variables) through recent results on the theory for processes with boundaries, keeping to a very narrow path: continuous-time, discrete-state processes. By developing only what we need for the applications we present, we to keep the theory to a manageable level, both in terms of length and in terms of difficulty. Since our scope is limited to a class of relatively simple processes, the theory is accessible, and less demanding mathematically, than more general treatments. Within our scope, our treatment is detailed, comprehensive and self-contained. As the book shows, there are sufficienty many interesting applications of jump Markov processes to warrant a special treatment. After all, we live in continuous time, and the events that occur in digital equipment are discrete.

 We firmly believe that the large deviations of processes should be taught first for jump Markov processes: more difficult processes can be studied once the foundations and the intuition are established. Diffusions are complicated objects, and the student does not need the extra burden of a subtle process to hinder the understanding of large deviations. Discrete time presents another unnecessarily difficult process, because the jumps are usually more general than those of the processes we consider.

 The second half of the book is a collection of applications developed at AT&T Bell Laboratories. Our applications cover large areas of the theory of communication networks: circuit-switched transmission (Chapter 12), packet transmission (Chapter 13), multiple access channels (Chapter 14), and the M/M/1 queue (Chapter 11). We cover aspects of parallel computation in a much more spotty fashion: basics of job allocation (Chapter 9), rollback-based parallel simulation (Chapter 10), assorted priority queuing models (Chapter 15) that may be used in performance models of various computer architectures, and asymptotic coupling of processors (Chapter 16).

 Back to the top


This book can be used as a basis for two types of one-semester courses. The first is an introduction to the theory of large deviations, through jump Markov processes. This course should cover most of Chapters 1, 2, 5, 6, possibly the advanced material in Chapter 8, and Appendix A. Such a course would prepare the student to read the more mathematical theory, and to fully appreciate the applications worked out in the rest of the book. It would be wise (in our opinion) to sprinkle such a theory-oriented course with some of the applications.

 The second course is application-oriented. Such a course should probably start with Chapter 1 (at least Sections 1 through 3), so that some flavor of the theory is provided. Many results can then be stated without proof, with or without intuitive explanations. Some basic tools from the calculus of variations, at least as summarized in Appendix C, should be covered. Then applications can be presented.

 Back to the top