Distributed Algorithms: A Verbose Tour

Distributed Algorithms, a non-trivial and highly evolving field of active research, is often presented in most publications using a heavy accompaniment of mathematical techniques and notations. Aimed squarely at beginners as well as experienced practitioners, this book attempts to demystify and explicate the subject of distributed algorithms using a highly expansive and verbose style of treatment. Covering scores of landmark algorithms in the field of distributed computing, the approach is to present and analyse each topic using a minimum of mathematical exposition, reverting instead to a fluid style of description in plain English. A mathematical presentation is avoided altogether whenever such a move does not reduce the quality of the analysis at hand. Elsewhere, the effort always is to talk and guide the reader through the relevant math without resorting to a series of equations. To backup such a style of treatment, each topic is accompanied by a multitude of examples, flowcharts, and diagrams.

The book is divided into three parts; the first part deals with fundamentals, the second and largest of the three is all about algorithms specific to message passing networks, while the last one focuses on shared memory algorithms. The beginning of the book dedicates a few chapters to the basics - including a quick orientation on the underlying platform, i.e. distributed systems, their characteristics, advantages, challenges, and so on. Some of the earlier chapters also address basic algorithms and techniques relevant to distributed computing environments before moving on to progressively complex algorithms and results - en route to the later chapters in the second part which deal with widely used 'industrial-strength' protocols such as Paxos and Raft. The third part of the book does assume a basic orientation towards computer programming, and presents numerous shared memory algorithms where each one is accompanied by a detailed description, analysis, pseudo code, and in some cases, code (C or C++). Whenever actual code is used, the syntax is kept as basic as possible - incorporating only elementary features of the language - so that newbie programmers can follow the presentation smoothly.

Lastly, the target audience of the book is wide enough to cover beginners such as students or graduates joining the industry, experienced professionals wishing to migrate from monolithic frameworks to distributed ones, as well as readers with years of experience on the subject of distributed computing. The style of presentation is selected with the first two classes of readers in mind: those who wish to quickly ramp up on the subject of distributed algorithms for professional reasons or personal ones. While staying true to the stated aim, the book does not shy away from dealing with complex topics. A concise list of content information follows:

• Introduction to distributed systems
• Properties of distributed data stores and Brewer's theorem
• Building blocks: unicast, broadcast, algorithms in cubes
• Leader election algorithms: for ring/generic networks
• Consensus algorithms: synchronous/asynchronous variants for message passing and shared memory systems
• Distributed commits, Paxos, Raft
• Graph algorithms
• Routing algorithms
• Time and order
• Mutual exclusion: for message passing networks
• Debug algorithms: snapshot, deadlock/termination detection
• Shared memory: practical problems, mutual exclusion, consensus, resource allocation

About the author

Fourré Sigs is an industry veteran with over 25 years of experience in systems programming, networking, and highly scalable and secure distributed service architectures.