Distributed Algorithms

An Intuitive Approach

by Fokkink

ISBN: 9780262318938 | Copyright 2013

Click here to preview

Tabs

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.

I am always fascinated by distributed processes. How can we design algorithms or protocols for them that work? Fokkink gives a unique introduction to the many original concepts and methods in distributed computing that we know today. A truly insightful book.

Jan van Leeuwen Utrecht University

An original and thought-provoking new approach to teaching distributed algorithms.

Maurice Herlihy Brown University
Expand/Collapse All
Contents (pg. Cover)
Preface (pg. Cover)
1 Introduction (pg. Cover)
I Message Passing (pg. 5)
2 Preliminaries (pg. 7)
3 Snapshots (pg. 13)
4 Waves (pg. 19)
5 Deadlock Detection (pg. 27)
6 Termination Detection (pg. 37)
7 Garbage Collection (pg. 47)
8 Routing (pg. 53)
9 Election (pg. 73)
10 Anonymous Networks (pg. 87)
11 Synchronous Networks (pg. 101)
12 Crash Failures (pg. 111)
13 Byzantine Failures (pg. 121)
14 Mutual Exclusion (pg. 135)
II Shared Memory (pg. 143)
15 Preliminaries (pg. 145)
16 Mutual Exclusion II (pg. 147)
17 Barriers (pg. 161)
18 Self-Stabilization (pg. 171)
19 Online Scheduling (pg. 181)
Pseudocode Descriptions (pg. 193)
References (pg. 221)
Index (pg. 225)

Wan Fokkink

Wan Fokkink is Professor of Theoretical Computer Science at the VU University, Amsterdam, and Professor of Stochastics Design at Eindhoven University for Technology.


Instructors
You must have an instructor account and submit a request to access instructor materials for this book.
eTextbook
Go paperless today! Available online anytime, nothing to download or install.
Device Compatibility

Features

  • Bookmarking
  • Note taking
  • Highlighting
Support