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
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
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... .
Adam Shwartz
is with the Faculty of Electrical
Engineering, Technion-Israel Institute
of Technology,
Alan Weiss
is a member of the technical staff at Bell Laboratories,
Contents:
- 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
Synopsis
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).
Courses
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.