Wan Fokkink - distributed Algorithms: An Intuitive Approach An Intuitive Approach

This textbook is meant to be used in a course on distributed algorithms for senior-level undergraduate or graduate students in computer science or software engineering and as a quick reference for researchers in the field. On the one hand it focuses on fundamental and instructive algorithms and results in distributed computing, while on the other hand it aims to exhibit the versatility of distributed and parallel computer systems. The distributed algorithms treated in this book are largely classics that were selected mainly because they are instructive with regard to the algorithmic design of distributed systems or shed light on key issues in distributed computing and concurrent programming. The book also discusses topics that are the focus of exciting new developments, notably transactional memory, blockchains, and quantum cryptography.

There are two very different ways to structure a course on algorithms. One way is to discuss algorithms and their analysis in great detail. The advantage of this approach is that students may gain deep insight into the algorithms and at the same time acquire experience in mathematical reasoning regarding their correctness and performance. Another way is to discuss algorithms and their correctness in an informal manner, and let students get acquainted with an algorithm from different angles by means of examples and exercises, without a need to understand the intricacies of the corresponding model and its underlying assumptions. Mathematical argumentations, which can be a stumbling block for many students, are thus avoided. An additional advantage is that a large number of algorithms can be discussed within a relatively short time, providing students with many different views on, and solutions to, challenges in distributed computing. In 10 years of teaching about distributed algorithms, I have converged on the latter approach, most of all because the students in my lectures tend to have hands-on experience and practical interests with regard to distributed systems. As a result, the learning objective of my course has been algorithmic thought rather than proofs and logic.

This book provides a Cooks tour of distributed algorithms. This phrase, meaning a rapid but extensive survey, refers to Thomas Cook, the visionary tour operator (and not the great explorer James Cook). Accordingly, this book is intended to be a travel guide through the world of distributed algorithms. A notable difference from other books in this area is that it does not emphasize correctness proofs. Algorithms are explained by means of brief, informal descriptions, illuminating examples, and exercises. The exercises have been carefully selected to make students well acquainted with the intricacies of distributed algorithms. Proof sketches, arguing the correctness of an algorithm or explaining the idea behind a fundamental result, are presented at a rather superficial level.

A thorough correctness proof, of course, is important in order to understand an algorithm in full detail. My research area is automated correctness proofs of distributed algorithms and communication protocols, and I have written two textbooks devoted to this topic. In the current textbook, however, intuition prevails. Readers who want to get a more detailed description of distributed algorithms in this book are recommended to consult the original papers, mentioned in the bibliographical notes at the end of each chapter. Moreover, pseudocode descriptions of a considerable number of algorithms are provided as an appendix.

I gratefully acknowledge the support of Helle Hvid Hansen, Jeroen Ketema, and David van Moolenbroek with providing detailed solutions to the exercises in this book, and am thankful for suggested improvements by students regarding earlier versions of these lecture notes. Special thanks go to Stefan Vijzelaar for his feedback on the description of blockchains and to Gerard Tel for his useful comments over the years.

Wan Fokkink

Amsterdam, November 2017