This book is 99 percent mathematical adventures and revolves around formal proofs. The author actually states that the topic selection criterion was “that the topic [...] involve some interesting mathematics.” It is, then, a book of advanced mathematical proofs, using computer performance analysis as the background.
The book is organized into five chapters and two appendices.
Chapter 1 introduces concepts that will later be used in the other chapters. It proposes a few ways of modeling disk drives, access patterns, and seek times. Chapter 1 then presents a mathematical model for generating input/output (I/O) traces called the independent reference model (IRM).
Chapter 2 builds a more sophisticated IRM using fractals. This chapter also briefly discusses cache hits and entropy. An optimal cache management algorithm is proved, although the author concludes that it is not robust and that the heuristics commonly used, such as least recently used (LRU) and first in, first out (FIFO), are both known to be robust and perform well. The claim that FIFO and LRU are robust is one of the few in this book that does not have a formal mathematical proof.
Using partially ordered sets and Lorentzian geometry, chapter 3 tackles the disk scheduling problem, or how to optimize a disk’s servicing time to improve throughput. This chapter discusses strategies to optimize airplane boarding times as an example. The same framework defined in this chapter can effectively provide algorithms to both problems.
Although the first three chapters considered single disk problems, chapter 4 models mirrored disk pairs using graphs. The modeling is used to propose load balancing algorithms to service read requests to either disk.
Chapter 5 is a deep dive into queueing theory and job distributions. It uses checkout counters in a mini-market as an example.
Appendix A contains definitions and facts related to topology, measure theory, probability, algebra, linear algebra, transforms, and graphs. Finally, in Appendix B, we find complete proofs of results from chapters 2, 3, and 4.