Large Deviations for Performance Analysis

Queues, Communication, and Computing

by Adam Shwartz and Alan Weisspicture of the book
is out in a second reprint of the revised edition. It has now been reprinted (again) and is available for sale. The publisher allowed us to make a PDF available. Here is the introduction, describing what the book is about.

Large Deviations for Performance Analysis: Intro.

brief ad and sample chapter:

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 part of the published book, are available as a PDF file.

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

Alan Weiss was a member of the technical staff at Bell Laboratories, Murray Hill, NJ when the book was written. He is now with Mathworks, MA.

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

The book has since moved between publishers: the latest version is part of Routeledge Revival series, Taylor and Francis, 2018.

ISBN 978-1-138-31577-8

It is also available as an e-book.

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 files that contain all the changes. Here are the changes and new PS files, including the corrections that weren’t incoprorated into the second edition.

 

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 was a member of the technical staff at Bell Laboratories, Murray Hill, NJ. He is now with Mathworks.

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):
  1. Allocating Independent Subtasks
  2. Parallel Algorithms: Rollback
  3. The M/M/1 Queue
  4. Erlang’s Model
  5. The Anick-Mitra-Sondhi Model
  6. Aloha
  7. Priority Queues
  8. 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.