7.5 Hold and Wait Strategy: The LLR Algorithm
7.6 Wait and Release Strategy: The Wait/Release Algorithm
7.7 Wait and Release Strategy: A Randomized Algorithm
7.8 Chapter Notes
7.9 Self Review
8.1 The See-Saw Puzzle
8.2 Applications
8.3 The Kids’ First Plan
8.4 The Kids’ Second Plan
8.5 The Kids’ Final Plan
8.6 Further Explanations
8.7 Chapter Notes
8.8 Self Review
9.1 The Green-or-Blue Game
9.2 Applications
9.3 Two Observations
9.4 The Kids’ Plan
9.5 Further Explanations
9.6 An Alternative Plan
9.7 The Queen’s New Challenge
9.8 A Surprising Impossibility Result
9.9 The Queen’s Final Challenge
9.10 General Impossibility Results
9.11 Chapter Notes
9.12 Self Review
10 Getting the Service You Deserve
10.1 The Two Tellers Problem
10.2 Applications
10.3 First Attempt: A Solution Which Cannot Tolerate a Single Fault
10.4 Second Attempt: A Correct Solution
10.5 How Many Notes are Needed?
10.6 Chapter Notes
10.7 Self Review
Preface
The design of distributed systems where computing devices (like computers, smartphones, sensors) interact with one another is one of the most challenging problems in computer science. In this book, I have tried to gently introduce the general reader to some of the most fundamental issues and classical results of computer science underlying the design of algorithms for distributed systems, so that the reader can get a feel of the nature of this exciting and interesting field. The book will appeal to the educated layperson and requires no computer-related background at all. I strongly suspect that also most computer-knowledgeable readers will be able to learn something new.
While humans can see and hear each other, computing devices usually communicate by sending messages or reading from and writing to shared memory locations. As a result, it is far more difficult to synchronize interactions between computers than between humans. Based on this observation, fundamental principles that relate to interactions between computing devices that involve concurrency and synchronization are explained throughout the book.
Each chapter deals with a specific topic presented in terms of a story. I have compared the issues that arise when dealing with groups of computing devices to those that arise when a group of people has to share their resources and work as a team in order to solve various problems together. Most chapters can be read in isolation, but there is a logical grouping to the complete set of chapters. The topics covered are not an exhaustive survey of the field of distributed computing, but largely a subjective sampling of its highlights.
One hint about reading this book—do not go too fast, try to read at most one chapter per sitting. Most of the problems presented look deceptively simple at first glance. The only way to understand their tricky nature is by trying to solve them yourself. For that reason, I suggest that, as soon as a problem is posted, you stop reading and try to solve it yourself. Only after you have butted your head against a problem for some time, can you appreciate its beauty. I hope you will enjoy reading the book!
Contact Information: Please feel free to contact me with any criticism or comments which you might have. I would be glad to hear from you! I can be reached by email at [email protected] or by sending hardcopy mail to Prof. Gadi Taubenfeld, The Interdisciplinary Center, P.O.Box 167, Herzliya 46150, Israel.
Gadi Taubenfeld
May 2018
Acknowledgments
I would like to thank many of my colleagues for the influence they had on my work and therefore on this book. I thank Jennifer L. Welch and Michel Raynal for their helpful comments on a draft of the book. Most importantly, I thank my family for their love and support.
Gadi Taubenfeld
May 2018
CHAPTER 1
Distributed Computing
Two major developments that have happened in recent years are dramatically and irrevocably changing the computer landscape: the dramatic expansion in the use of the Internet, and the design of multicore computers where a single computer has multiple processors. A processor is the “brain” of the computer, and modern computers are now built with multiple “brains.” In each one of these cases, processors on the same or different computers have to work together as a team to achieve common goals.
In addition to personal computers, smartphones, laptops, tablets, and webcams, the Internet offers connectivity between many other computing devices. A few examples are sensors which enable environmental monitoring applications; sensors which are used for monitoring changes in structural conditions of infrastructures like bridges; wearable sensors that can remotely read
