Discrete notes    About    Archive

Material on distributed graph algorithms

This post is a list of pointers to books and surveys about distributed graph algorithms (LOCAL model, CONGEST model, and friends). I probably missed some references, as typing “local model” in a search engine is not very helpful if you are not looking for top model agencies. Other references are most welcome!

Distributed computing: a locality-sensitive approach, by Peleg, and other references

Distributed computing: a locality-sensitive approach by David Peleg is the classic book about the local model. It’s from 2000, so it’s getting a bit outdated in terms of results.

Distributed graph coloring, by Barenboim and Elkin

Distributed graph coloring by Leonid Bareboim and Michael Elkin, is a more recent book, with a focus on coloring. It explains quite a few techniques, and has a list of open problems (some of these problems have been solved already).

Survey of local algorithms, by Suomela

The survey of local algorithms by Jukka Suomela is the reference for results about constant-time computations in the local model.

Distributed algorithms, by Suomela

A neat online textbook is Distributed algorithm by Jukka Suomela. In addition to the classic topics such as coloring, that are contained in most references listed here, it has a focus on showing the similarities and differences between different models (such as port numbers and unique identifiers), and on the graph theory tools that can be used (such as covering maps and Ramsey theory).

The Swiss-German lecture notes

There are several courses related to the local model that are taught in Switzerland and South Germany. They are rather close one from another, as they stem from the same Zurich source (but then they evolved on their own).

Material covering only the basics, or only specialized content

A standard book is Distributed Algorithms by Nancy Lynch, but most of the book is off-topic for this post, because it deals with asynchronous systems.

Yet another reference (with little material on the LOCAL model) is the online textbook Notes on Theory of Distributed Systems by James Aspnes.

If you look for self-stabilizing algorithms then a reference from 2000 is Self-Stabilization by Shlomi Dolev, and a very recent one is Introduction to Distributed Self-Stabilizing Algorithms by Karine Altisen, Stéphane Devismes, Swan Dubois, and Franck Petit.

In French

Also, if you read French, you may be interested in Algorithmique distribuée pour les réseaux by Pierre Fraigniaud, and Algorithmes distribués by Cyril Gavoille.

Thanks to Jukka Suomela for pointing out some references.