Mathematical and Algorithmic Foundations of the Internet (Chapman & Hall/CRC Applied Algorithms and Data Structures Series) [Paperback]

Review reported in Greenberg, ed.: Book Reviews INFORMS Journal on Computing 24(2), pp. BR1-BR10, (c) 2012 INFORMS.

Reviewed by: Allen G. Holder, Rose-Hulman Institute of Technology.

The internet's importance is arguably unrivaled in today's society: it supports a wealth of commerce, it is a major source of information, it almost instantaneously connects people over vast distances, and it is becoming influential in our geo-political paradigm. In Mathematical and Algorithmic Foundations of the Internet by F. Luccio and L. Pagli with G. Steel we have a succinct introduction to the technical side of the computational science that supports the internet. The presentation is rudimentary and appropriate for non-experts. The targeted audiences are students in introductory computer science courses, students in other courses, technical professionals, and curious people. I am a member of the last two of these groups, and I often teach students as they enter computer science and other technical disciplines, albeit as a mathematics and computational science instructor and not as a computer science educator.

The book begins with an introduction to graphs and networks, and the first few pages introduce graph theory from its inception as a problem of how to traverse the K 'onigsberg bridges. Topics are often introduced by linking them to a quaint historical story, a snippet of literature, an artistic aspect, or some ancient philosophical question. Such references are interesting if unknown, but at this point in my life they seem cliche' and somewhat of a nuisance. Other technical professionals will likely agree. However, beginning students and curious people will appreciate these historical and artistic notes.

By starting with a cursory introduction to graphs and networks (Chapter 1), followed by a discussion of exponential growth (Chapter 2), followed by a development of trees and sequence comparisons (Chapter 3), the authors introduce the mathematical foundations of the internet in a manner appropriate for anyone with a high school education. This introduction lends itself toward the general public and away from technical professionals. Indeed, for a student or professional of Operations Research (OR) this is a laborious introduction to topics that will already be known. Moreover, my editorial note well into the third chapter was that no material had directly applied to the internet. Readers should not expect a clear link to the mathematical and algorithmic foundations of the internet until the end of Chapter 3, where the DNS protocol is introduced.
The computational concerns of managing the immensity of the internet come to the forefront in Chapter 4, which introduces the concept of an algorithm. True to the text's style, Chapter 4 begins with a discussion of the infinite as a deep philosophical idea that traces itself back to the great philosophers of Greece. The discussion quickly turns to the subtle concept of computability and continues with a lucid introduction to computational complexity. Search algorithms are of particular interest. One note that the OR audience might not appreciate is that the authors conclude "that exponential algorithms are useless," but anyone who has made a career of solving linear programs with the simplex algorithm might disagree. The end of Chapter 4 mentions the emerging field of green computing, a topic of which I had been unaware. The topic was intriguing, and I used it in an OR course. Small teams of students worked on a problem in green computing of their choice. Students were engaged and piqued by their results. This is one of a few places where the authors point to the future, and I was glad for the exposition.

Chapter 5 covers the concept of a randomized algorithm. This development nicely articulates the reason why the use of a randomized algorithmic component is of paramount importance for internet sized problems, e.g. file sharing. The presentation on the undecidability of determining if a sequence is random is well done.

Chapters 6 and 7 work in concert. Network topology is the primary topic of Chapter 6, with the preponderance of focus being on topological measures of graphs as they develop randomly. Network topologies have been important to social scientists for many years, and the connection to the internet is clear. Chapter 7 discusses how topological measures apply to the internet, with concepts like a "small world" playing a major role. Power law relationships are also prominent. Chapter 7 ends with a brief discussion on community finding.

The book culminates in Chapters 8 and 9, which cover distributive computing and internet search algorithms. These two chapters are wonderfully developed, especially for those in the targeted audience of curious readers. Chapter 8 uses simple examples to illustrate the complication of sharing information among processes, and moreover, it highlights how computer scientists have found some clever solutions. Chapter 9 draws from many of the earlier chapters as it discusses the problems that have been overcome by modern internet search engines. For readers young enough to have always had search engines like Yahoo and Google, the presentation thankfully points to a not-so-distant past in which accessing information was a chore. The immensity of the computational burden to collect, organize, and search the entire web is clear. The authors discuss the need to have automated web-crawlers, massive data centers, and powerful distributed computing. The importance of a page-ranking algorithm is highlighted, and this discussion includes a presentation of the nefarious ways people have attempted to artificially influence such rankings.

The text concludes with an epilogue that positions the historical importance of the web as a repository of knowledge much like that of the great libraries of the past, but with the significant advantage of hypertext. The epilogue also foreshadows how navigation might become more intuitive.

The book's prose is exceptional. The authors are clearly skilled communicators and have undertaken a substantial effort to make the text enjoyable. As for their intended audiences, the book is a superb read for their targeted audience of curious people. However, for technical professionals like myself, the text lacks the mathematical and computational rigor that I was looking for. Of the courses in OR and computational science that I teach, I would not consider using this text as supplementary material, the main reason being that students taking such courses tend to already know more than what this text includes. I would consider using this text in a first year seminar within the undergraduate curriculum, a setting for which it seems perfectly well suited.