Distributed Computing Pearls. Gadi Taubenfeld
Чтение книги онлайн.

Читать онлайн книгу Distributed Computing Pearls - Gadi Taubenfeld страница 2

СКАЧАТЬ randomized algorithms, Byzantine agreement, choice coordination, the see-saw puzzle, the two lovers problem, the two generals problem, the too much bread problem, deadlock, dining philosophers, mutual exclusion, barrier synchronization, crash failures, Byzantine failures

      To Miki,the love of my life.

       Contents

       Preface

       Acknowledgments

       1 Distributed Computing

       1.1 Winds of Change

       1.2 The Internet

       1.3 Computers with Multiple Processors

       1.4 Synchronization

       1.5 Why is Synchronization Difficult?

       1.6 Algorithms and Programs

       1.7 Concurrent and Distributed Algorithms

       1.8 Impossibility Results

       1.9 Chapter Notes

       2 One Loaf of Bread, Please

       2.1 The Too Much Bread Problem

       2.2 Applications

       2.3 First Attempt

       2.4 Second Attempt

       2.5 Third Attempt

       2.6 Fourth Attempt: A Correct Solution

       2.7 Communicating by Reading and Writing of Notes

       2.8 Chapter Notes

       2.9 Self Review

       3 A Tale of Two Lovers

       3.1 The Two Lovers Problem

       3.2 Applications

       3.3 A Surprising Impossibility Result

       3.4 Further Explanations

       3.5 Chapter Notes

       3.6 Self Review

       4 A Night at the Movies

       4.1 The Movie Agreement Problem

       4.2 Applications

       4.3 A Surprising Impossibility Result

       4.4 A More General Result

       4.5 An Algorithm

       4.6 Further Explanations

       4.7 How Many Rounds are Needed?

       4.8 Chapter Notes

       4.9 Self Review

       5 The Fall of the Byzantine Empire

       5.1 The Byzantine Generals Problem

       5.2 Applications

       5.3 A Surprising Result

       5.4 An Algorithm

       5.5 Further Explanations

       5.6 Chapter Notes

       5.7 Self Review

       6 Sightseeing in Paris

       6.1 The Choice Coordination Problem

       6.2 Applications

       6.3 A Randomized Algorithm

       6.4 Further Explanations

       6.5 A Simple Deterministic Algorithm

       6.6 Perfectionism, It Seems, Does Not Pay!

       6.7 Chapter Notes

       6.8 Self Review

       7 Food for Thought

       7.1 The Dining Philosophers Problem

       7.2 Applications

       7.3 Deadlock Prevention: The Total Order Technique

       7.4 Hold and Wait Strategy: The LR Algorithm

       СКАЧАТЬ