Distributed Algorithms: An Intuitive Approach

This book offers students and researchers a guide to distributed algorithms that emphasizes examples and exercises rather than the intricacies of mathematical models. It avoids mathematical argumentation, often a stumbling block for students, teaching algorithmic thought rather than proofs and logic. This approach allows the student to learn a large number of algorithms within a relatively short span of time. Algorithms are explained through brief, informal descriptions, illuminating examples, and practical exercises. The examples and exercises allow readers to understand algorithms intuitively and from different perspectives. Proof sketches, arguing the correctness of an algorithm or explaining the idea behind fundamental results, are also included. An appendix offers pseudocode descriptions of many algorithms.

Distributed algorithms are performed by a collection of computers that send messages to each other or by multiple software threads that use the same shared memory. The algorithms presented in the book are for the most part “classics,” selected because they shed light on the algorithmic design of distributed systems or on key issues in distributed computing and concurrent programming.

Distributed Algorithms can be used in courses for upper-level undergraduates or graduate students in computer science, or as a reference for researchers in the field.

Table of Contents

Chapter 1 Introduction

Part I Message Passing
Chapter 2 Preliminaries
Chapter 3 Snapshots
Chapter 4 Waves
Chapter 5 Deadlock Detection
Chapter 6 Termination Detection
Chapter 7 Garbage Collection
Chapter 8 Routing
Chapter 9 Election
Chapter 10 Anonymous Networks
Chapter 11 Synchronous Networks
Chapter 12 Crash Failures
Chapter 13 Byzantine Failures
Chapter 14 Mutual Exclusion

Part II Shared Memory
Chapter 15 Preliminaries
Chapter 16 Mutual Exclusion II
Chapter 17 Barriers
Chapter 18 Self-Stabilization
Chapter 19 Online Scheduling