Book Review Department Editor Warren Keuffel

Information Is Power

Art Sedighi

Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance by Juraj Hromkovič,  Ralf Klasing,  Andrzej Pelc,  Peter Ružička, and Walter Unger, Springer, 2005, ISBN 3-540-00846-2, 361 pages, US$79.95.

Increases in computing power also increase the need to distribute load, data, and semantics across an enterprise. This in turn increases the need for better communication algorithm. It’s not uncommon for communicating information to take longer than computing that information. In addition, the Internet has brought a need for faster, more efficient ways of transferring data from point A to point B.

Dissemination of Information in Communication Networks is focused on just that—sending information from point A to point B. This topic is much harder and more involved than just a link between two points, and the authors discuss the various information dissemination classes in use today: broadcasting, gossiping, leader election, and fault tolerance. 

The book begins by discussing these topics in the telephone network and, after an in-depth discussion, moves to communication networks. Telephone networks pose the same challenges as communication networks—and because we’ve been dealing with telephone networks for many years, we can apply that experience to communication networks.Telephone networks are a bit easier because most of the communication is synchronous and deterministic. The asynchronous nature of what the authors refer to as distributed networks poses a greater challenge in fault tolerance, leader election, and broadcasting. When you flood the network with broadcast data, much care must be taken.

The book also discusses several algorithms that we all know and love, such as depth-first search, breath-first search, and their applications in various topologies such a hypercube and other graph models. The authors analyze the message and time complexity of the algorithms throughout the text. Especially useful is that, in addition to describing the algorithms’ upper and lower bounds, the authors discuss the best cases (or most likely scenarios) when appropriate.

Fault tolerance is probably the most complex topic in both synchronous telephone networks and asynchronous distributed networks. The authors pay special attention to classifying and explaining faults, including the notion of probabilistic fault models and permanent faults. The authors use graph theory and notations to support everything they discuss. The first chapters cover graph theory for those who are unfamiliar with the topic.

Those involved with IP network design or integrating legacy enterprise applications should find the discussion of leader election interesting. If you’ve ever designed around a messaging middleware, you can relate to scenarios in which you’re trying to achieve load balancing and fault tolerance while still determining the process responsible for handling a single message at any given point of time. The mathematical models throughout the text might be difficult to grasp initially, but they are represented well. 

I recommend Dissemination of Information in Communication Networks to anyone involved with distributed programming, networks, integration, high-performance computing, or data dissemination.

Art Sedighi is a senior consulting engineer at DataSynapse and a freelance writer. Contact him at sediga@alum.rpi.edu.