Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf)
Описание файла
PDF-файл из архива "Distributed Algorithms. Nancy A. Lynch (1993).pdf", который расположен в категории "". Всё это находится в предмете "распределенные алгоритмы" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
DISTRIBUTED ALGORITHMSLecture Notes for 6.852Fall 1992Nancy A. LynchBoaz Patt-ShamirJanuary 1993PrefaceThis report contains the lecture notes used by Nancy Lynch's graduate course in DistributedAlgorithms, during fall semester, 1992. The notes were prepared by Nancy Lynch andTeaching Assistant Boaz Patt-Shamir.The main part of this report is detailed lectures notes for the 25 regular class meetings.We think the reader will nd these to be reasonably well polished, and we would very muchappreciate comments about any errors, or suggestions on the presentation.
Following thesenotes are the homework assignments. Finally, we included an appendix that contains notesfor three additional lectures that were given after the regular term was over. The extralectures cover material that did not t into the scheduled number of class hours. Thesenotes are in a very rough shape.Many thanks go to the students who took the course this semester they contributedmany useful comments and suggestions on the technical content, and also had a very stronginuence on the pace and level of the presentation.
If these notes are understandable to otheraudiences, it is largely because of the feedback provided by this rst audience. Thanks alsogo to George Varghese for contributing an excellent lecture on self-stabilizing algorithms.We would also like to acknowledge the work of Ken Goldman and Isaac Saias in preparingearlier versions (1988 and 1990, respectively) of the notes for this course.
We were able toreuse much of their work. The students who took the course during those two years workedhard to prepare those earlier lecture notes, and also deserve a lot of thanks. Jennifer Welchand Mark Tuttle also contributed to earlier versions of the course. Finally, we would like tothank Joanne Talbot for her invaluable help.January, 1993Nancy Lynch, lynch@theory.lcs.mit.eduBoaz Patt-Shamir, boaz@theory.lcs.mit.edu12ContentsLECTURES13Lecture 1: September 10, 1992131.1 Introduction to the Course : : : : : : : : : : : : : : :1.1.1 The Subject Matter : : : : : : : : : : : : : : :1.1.2 Style : : : : : : : : : : : : : : : : : : : : : : :1.1.3 Overview of the Course : : : : : : : : : : : : :1.2 Synchronous Network Algorithms : : : : : : : : : : :1.2.1 Problem Example: Leader Election in a Ring1.2.2 Algorithm 1: LeLann, Chang-Roberts : : : : :Lecture 2: September 15, 19922.1 Leader Election on a Ring (cont.) : : : : : : : : : : :2.1.1 Algorithm 2: Hirshberg-Sinclair : : : : : : : :2.1.2 Counterexample Algorithms : : : : : : : : : :2.1.3 Lower Bound on Comparison-Based Protocols2.2 Leader Election in a General Network : : : : : : : : :2.3 Breadth-First Search : : : : : : : : : : : : : : : : : :2.3.1 Extensions : : : : : : : : : : : : : : : : : : : :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::131314152021222525252728323434Lecture 3: September 17, 199236Lecture 4: September 22, 1992463.1 Shortest Paths: Unweighted and Weighted : : : : : : : : : : : : : : : : : : : 363.2 Minimum Spanning Tree : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 373.3 Maximal Independent Set : : : : : : : : : : : : : : : : : : : : : : : : : : : : 404.1 Link Failures : : : : : : : : : : : : : : :4.1.1 The Coordinated Attack Problem4.1.2 Randomized Consensus : : : : : :4.2 Faulty Processors : : : : : : : : : : : : :3::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::464649554.2.1 Stop Failures : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56Lecture 5: September 24, 19925.1 Byzantine Failures : : : : : : : : :5.2 Reducing the Communication Cost5.2.1 Stopping Faults : : : : : : :5.2.2 The Byzantine Case : : : :5.2.3 The Turpin-Coan Algorithm::::::::::::::::::::::::::::::Lecture 6: September 29, 19926.16.26.36.4Number of Processes for Byzantine AgreementByzantine Agreement in General Graphs : : :Weak Byzantine Agreement : : : : : : : : : :Number of Rounds with Stopping Faults : : ::::::::::::::::::::::::::::Lecture 7: October 1, 19927.1 Number of Rounds With Stopping Failures (cont.) :7.2 The Commit Problem : : : : : : : : : : : : : : : :7.2.1 Two Phase Commit (2PC) : : : : : : : : : :7.2.2 Three-phase Commit (3PC) : : : : : : : : :7.2.3 Lower Bound on the Number of Messages :Lecture 8: October 6, 19928.1 Asynchronous Shared Memory : : : : :8.1.1 Informal Model : : : : : : : : :8.2 Mutual Exclusion Problem : : : : : : :8.3 Dijkstra's Mutual Exclusion Algorithm8.3.1 A Correctness Argument : : : :Lecture 9: October 8, 1992::::::::::::::::::::9.1 Dijkstra's Mutual Exclusion Algorithm (cont.)9.1.1 An Assertional Proof : : : : : : : : : :9.1.2 Running Time : : : : : : : : : : : : : :9.2 Improved Mutual Exclusion Algorithms : : : :9.2.1 No-Starvation Requirements : : : : : :9.2.2 Peterson's Two-Process Algorithm : :9.2.3 Tournament Algorithm : : : : : : : : :9.2.4 Iterative Algorithm : : : : : : : : : : :4:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::5959636365666868717677828284848587898989919597101101101104105105106108112Lecture 10: October 15, 199210.1 Atomic Objects : : : : : : : : : : : :10.1.1 Example: Read-Write Object10.1.2 Denition : : : : : : : : : : :10.2 Atomic Snapshots : : : : : : : : : : :10.2.1 Problem Statement : : : : : :10.2.2 Unbounded Algorithm : : : :10.2.3 Bounded Register Algorithm :Lecture 11: October 20, 1992::::::::::::::::::::::::::::::::::::::::::11.1 Burns' Mutual Exclusion Algorithm : : : : : : :11.2 Lamport's Bakery Algorithm : : : : : : : : : : :11.2.1 Analysis : : : : : : : : : : : : : : : : : :11.3 The Number of Registers for Mutual Exclusion :11.3.1 Two Processes and One Variable : : : :11.3.2 Three processes and Two Variables : : :11.3.3 The General Case : : : : : : : : : : : : :Lecture 12: October 22, 1992::::::::::::::::::::::::::::::::::::::::::::::::::::::::12.1 Consensus Using Read-Write Shared Memory : : : : :12.1.1 Impossibility for Arbitrary Stopping Faults : : :12.1.2 Impossibility for a Single Stopping Fault : : : :12.2 Modeling and Modularity for Shared Memory Systems12.2.1 The Basic Input/Output Automaton Model : :Lecture 13: October 27, 1992:::::::::::::::::::::::::::::::::::::::::::::::::::::::::13.1 I/O Automata (cont.) : : : : : : : : : : : : : : : : : : : : :13.1.1 Problem Specication : : : : : : : : : : : : : : : : : :13.1.2 Proof Techniques : : : : : : : : : : : : : : : : : : : :13.2 Shared Memory Systems as I/O Automata : : : : : : : : : :13.2.1 Instantaneous Memory Access : : : : : : : : : : : : :13.2.2 Object Model : : : : : : : : : : : : : : : : : : : : : :13.3 Modularity Results : : : : : : : : : : : : : : : : : : : : : : :13.3.1 Transforming from Instantaneous to Atomic Objects13.3.2 Composition in the Object Model : : : : : : : : : : :5::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::113113114114117117117120123123125127130131131133136136137140143143151151151153155155157158159161Lecture 14: October 29, 199214.1 Modularity (cont.) : : : : : : : : : : : : : : : : : :14.1.1 Wait-freedom : : : : : : : : : : : : : : : : :14.2 Concurrent Timestamp Systems : : : : : : : : : : :14.2.1 Denition of CTS Objects : : : : : : : : : :14.2.2 Bounded Label Implementation : : : : : : :14.2.3 Correctness Proof : : : : : : : : : : : : : : :14.2.4 Application to Lamport's Bakery AlgorithmLecture 15: November 3, 199215.1 Multi-Writer Register Implementation Using CTS15.1.1 The Algorithm : : : : : : : : : : : : : : :15.1.2 A Lemma for Showing Atomicity : : : : :15.1.3 Proof of the Multi-writer Algorithm : : : :15.2 Algorithms in the Read-Modify-Write Model : : :15.2.1 Consensus : : : : : : : : : : : : : : : : : :15.2.2 Mutual Exclusion : : : : : : : : : : : : : :Lecture 16: November 5, 1992:::::::16.1 Read-Modify-Write Algorithms (cont.) : : : : : : :16.1.1 Mutual Exclusion (cont.) : : : : : : : : : : :16.1.2 Other Resource Allocation Problems : : : :16.2 Safe and Regular Registers : : : : : : : : : : : : : :16.2.1 Denitions : : : : : : : : : : : : : : : : : : :16.2.2 Implementation Relationships for Registers :16.2.3 Register Constructions : : : : : : : : : : : :Lecture 17: November 10, 1992::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::16316316316416416517217617917917918018118218318419119119119220020020220320817.1 Register Constructions (cont.) : : : : : : : : : : : : : : : : : : : : : : : : : : 20817.1.1 Construction 3: Binary Regular Register from Binary Safe Register : 20817.1.2 Construction 4: K -ary Regular Register from Binary Regular Register 21017.1.3 Construction 5: 1-Reader K -ary Atomic Register from Regular Register21217.1.4 Multi-Reader Atomic Registers : : : : : : : : : : : : : : : : : : : : : 21317.2 Lamport's Bakery Revisited : : : : : : : : : : : : : : : : : : : : : : : : : : : 21317.3 Asynchronous Network Algorithms : : : : : : : : : : : : : : : : : : : : : : : 21517.3.1 Leader Election : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2176Lecture 18: November 12, 199218.1 Leader Election in Asynchronous Rings (cont.) :18.1.1 The LeLann-Chang Algorithm (cont.) : :18.1.2 The Hirshberg-Sinclair Algorithm : : : :18.1.3 The Peterson Algorithm : : : : : : : : :18.1.4 Burns' Lower Bound Result : : : : : : :18.2 Problems in General Asynchronous Networks : :18.2.1 Network Leader Election : : : : : : : : :18.2.2 Breadth-rst Search and Shortest Paths::::::::::::::::::::::::::::::::::::::::Lecture 19: November 17, 199219.1 Asynchronous Broadcast-Convergecast : : : : : : : : : :19.2 Minimum Spanning Tree : : : : : : : : : : : : : : : : : :19.2.1 Problem Statement : : : : : : : : : : : : : : : : :19.2.2 Connections Between MST and Other Problems :19.2.3 The Synchronous Algorithm: Review : : : : : : :19.2.4 The Gallager-Humblet-Spira Algorithm: Outline :19.2.5 In More Detail : : : : : : : : : : : : : : : : : : :19.2.6 A Summary of the Code in the GHS Algorithm :19.2.7 Complexity Analysis : : : : : : : : : : : : : : : :19.2.8 Proving Correctness for the GHS Algorithm : : :Lecture 20: November 19, 199220.1 Minimum Spanning Tree (cont.) : : : : : : : : : : : : : :20.1.1 Simpler \Synchronous" Strategy : : : : : : : : : :20.2 Synchronizers : : : : : : : : : : : : : : : : : : : : : : : :20.2.1 Synchronous Model : : : : : : : : : : : : : : : : :20.2.2 High-Level Implementation Using a Synchronizer20.2.3 Synchronizer Implementations : : : : : : : : : : :20.2.4 Hybrid Implementation : : : : : : : : : : : : : : :20.2.5 Applications : : : : : : : : : : : : : : : : : : : : :20.3 Lower Bound for Synchronizers : : : : : : : : : : : : : :Lecture 21: November 24, 1992:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::22022022022122122623323323423723724024024124224324524925125225325325325325425425625725926026421.1 Time, Clocks, etc.