Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf)

PDF-файл Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf) Распределенные алгоритмы (63366): Книга - 10 семестр (2 семестр магистратуры)Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf) - PDF (63366) - СтудИзба2020-08-25СтудИзба

Описание файла

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.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5057
Авторов
на СтудИзбе
456
Средний доход
с одного платного файла
Обучение Подробнее