Material on distributed graph algorithms
20 Jun 2019This 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).
-
The current version of the original source is Principles of Distributed Computing, by Roger Wattenhofer (and more recently Mohsen Ghaffari but his part is covered below). In addition to the classic topics of synchronous computing, it covers some topics at the boundary with asynchronous computing (such as synchronizers), or fully asynchronous computing (such as shared objects).
-
A set of lecture notes by Fabian Kuhn is available chapter by chapter on the course webpage. The topics are very close from the ones of the bullet above. Two topics that appear only here: dynamic networks and network coding.
-
Another set of lecture notes is Theory of Distributed Systems, by Christoph Lenzen. It covers (in addition to the classic material) self-stabilization and routing.
-
Probably the most recent course is Distributed graph algorithms by Mohsen Ghaffari. It is a shorter text, with a focus on algorithmic techniques for the local model, e.g. network decomposition.
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.