Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26421.1.1 Logical Time : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26421.1.2 Algorithms : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 265721.1.3 Applications : : : : : : : : : : : : :21.2 Simulating Shared Memory : : : : : : : :21.3 Mutual Exclusion and Resource Allocation21.3.1 Problem Denition : : : : : : : : :21.3.2 Mutual Exclusion Algorithms : : :Lecture 22: December 1, 1992:::::::::::::::22.1 Mutual Exclusion (cont.) : : : : : : : : : : : : :22.1.1 Ricart & Agrawala (1981) : : : : : : : :22.1.2 Carvalho & Roucairol (1983) : : : : : : :22.2 General Resource Allocation : : : : : : : : : : :22.2.1 Burns-Lynch Algorithm : : : : : : : : :22.2.2 Drinking Philosophers : : : : : : : : : :22.3 Stable Property Detection : : : : : : : : : : : :22.3.1 Termination for Diusing Computations22.3.2 Snapshots : : : : : : : : : : : : : : : : :Lecture 23: December 3, 1992::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::23.1 The Concept of Self-Stabilization : : : : : : : : : : : : : : : : : : : :23.1.1 Door Closing and Domain Restriction : : : : : : : : : : : : : :23.1.2 Self-Stabilization is attractive for Networks : : : : : : : : : : :23.1.3 Criticisms of Self-Stabilization : : : : : : : : : : : : : : : : : :23.2 Denitions of Stabilization : : : : : : : : : : : : : : : : : : : : : : : :23.2.1 Execution Denitions : : : : : : : : : : : : : : : : : : : : : : :23.2.2 Denitions of Stabilization based on External Behavior : : : :23.2.3 Discussion on the Stabilization Denitions : : : : : : : : : : :23.3 Examples from Dijkstra's Shared Memory Model : : : : : : : : : : :23.3.1 Dijkstra's Shared Memory Model and IOA : : : : : : : : : : :23.3.2 Dijkstra's Second Example as Local Checking and Correction23.3.3 Dijkstra's rst example as Counter Flushing : : : : : : : : : :23.4 Message Passing Model : : : : : : : : : : : : : : : : : : : : : : : : : :23.4.1 Modeling the Topology : : : : : : : : : : : : : : : : : : : : : :23.4.2 Modeling Links : : : : : : : : : : : : : : : : : : : : : : : : : :23.4.3 Modeling Network Nodes and Networks : : : : : : : : : : : : :23.4.4 Implementing the Model in Real Networks : : : : : : : : : : :23.5 Local Checking and Correction in our Message Passing Model : : : :23.5.1 Link Subsystems and Local Predicates : : : : : : : : : : : : :8::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::26627027127127327827827828028028028128628729129829829830130230330330330430430530630931231231231431531631623.623.723.823.923.5.2 Local Checkability : : : : : : : : : : : : : : : : : : : : : :23.5.3 Local Correctability : : : : : : : : : : : : : : : : : : : : : :Local Correction Theorem : : : : : : : : : : : : : : : : : : : : : :23.6.1 Theorem Statement : : : : : : : : : : : : : : : : : : : : : :23.6.2 Overview of the Transformation Code : : : : : : : : : : : :Intuitive Proof of Local Correction Theorem : : : : : : : : : : : :23.7.1 Intuition Behind Local Snapshots : : : : : : : : : : : : : :23.7.2 Intuition Behind Local Resets : : : : : : : : : : : : : : : :23.7.3 Intuition Behind Local Correction Theorem : : : : : : : :Implementing Local Checking in Real Networks: Timer Flushing :Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :Lecture 24: December 8, 199224.1 Self-Stabilization and Termination : : : : : : : : : : :24.2 Self-Stabilization and Finite State : : : : : : : : : : :24.3 Self-stabilizing Reset Protocol : : : : : : : : : : : : :24.3.1 Problem statement : : : : : : : : : : : : : : :24.3.2 Unbounded-registers Reset : : : : : : : : : : :24.3.3 Example: Link Reset : : : : : : : : : : : : : :24.3.4 Reset Protocol : : : : : : : : : : : : : : : : :24.3.5 Analysis : : : : : : : : : : : : : : : : : : : : :24.3.6 Comments : : : : : : : : : : : : : : : : : : : :24.4 Application: Network Synchronization : : : : : : : :24.4.1 Implementation with Bounded Pulse NumbersLecture 25: December 10, 199225.1 Fischer-Lynch-Paterson Impossibility Result25.2 Ben-Or Randomized Protocol for Consensus25.2.1 Correctness : : : : : : : : : : : : : :25.3 Parliament of Paxos : : : : : : : : : : : : :HOMEWORK ASSIGNMENTSHomework Assignment 1Homework Assignment 2Homework Assignment 3Homework Assignment 4Homework Assignment 5::::::::::::::::::::::::::::::::::::::::::::::::::9:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::317318320320321323323324325326327328328329329329331331331338341341346348348356356358361361363365366367Homework Assignment 6 :Homework Assignment 7 :Homework Assignment 8 :Homework Assignment 9 :Homework Assignment 10Homework Assignment 11::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::369370371372373374APPENDIX375Lecture 26: January 5, 1993375A.1 Implementing Reliable Point-to-Point Communication in terms of UnreliableChannels : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :A.1.1 Stenning's Protocol : : : : : : : : : : : : : : : : : : : : : : : : : : : :A.1.2 Alternating Bit Protocol : : : : : : : : : : : : : : : : : : : : : : : : :A.1.3 Bounded-Header Protocols Tolerating Reordering : : : : : : : : : : :Lecture 27: January 19, 1993B.1 Reliable Communication Using Unreliable Channels : : :B.1.1 Bounded-Header Protocols Tolerating ReorderingB.1.2 Tolerating Node Crashes : : : : : : : : : : : : : :B.2 5-packet Handshake Internet Protocol : : : : : : : : : : :Lecture 28: January 26, 1993C.1 MMT Model Denition : : : : : : :C.1.1 Timed Automata : : : : : :C.2 Simple Mutual Exclusion ExampleC.3 Basic Proof Methods : : : : : : : :C.4 Consensus : : : : : : : : : : : : : :C.5 More Mutual Exclusion : : : : : : :C.6 Clock Synchronization : : : : : : :BIBLIOGRAPHYD.1 Introduction : : : : : : : : :D.2 Models and Proof Methods :D.2.1 Automata : : : : : :D.2.2 Invariants : : : : : ::::::::::::::::::::::::::::10::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::375376383392398398398403407413413414416416417417418419419420420420D.3D.4D.5D.6D.2.3 Mapping Methods : : : : : : : : : : : : : :D.2.4 Shared Memory Models : : : : : : : : : :D.2.5 I/O Automata : : : : : : : : : : : : : : : :D.2.6 Temporal Logic : : : : : : : : : : : : : : :D.2.7 Timed Models : : : : : : : : : : : : : : : :D.2.8 Algebra : : : : : : : : : : : : : : : : : : :Synchronous Message-Passing Systems : : : : : :D.3.1 Computing in a Ring : : : : : : : : : : : :D.3.2 Network Protocols : : : : : : : : : : : : :D.3.3 Consensus : : : : : : : : : : : : : : : : : :Asynchronous Shared Memory Systems : : : : : :D.4.1 Mutual Exclusion : : : : : : : : : : : : : :D.4.2 Resource Allocation : : : : : : : : : : : : :D.4.3 Atomic Registers : : : : : : : : : : : : : :D.4.4 Snapshots : : : : : : : : : : : : : : : : : :D.4.5 Timestamp Systems : : : : : : : : : : : :D.4.6 Consensus : : : : : : : : : : : : : : : : : :D.4.7 Shared Memory for Multiprocessors : : : :Asynchronous Message-Passage Systems : : : : :D.5.1 Computing in Static Networks : : : : : : :D.5.2 Network Synchronization : : : : : : : : : :D.5.3 Simulating Asynchronous Shared MemoryD.5.4 Resource Allocation : : : : : : : : : : : : :D.5.5 Delecting Stable Properties : : : : : : : :D.5.6 Deadlock Detection : : : : : : : : : : : : :D.5.7 Consensus : : : : : : : : : : : : : : : : : :D.5.8 Datalink : : : : : : : : : : : : : : : : : : :D.5.9 Special-Purpose Network Building Blocks :D.5.10 Self-Stabilization : : : : : : : : : : : : : :D.5.11 Knowledge : : : : : : : : : : : : : : : : : :Timing-Based Systems : : : : : : : : : : : : : : :D.6.1 Resource Allocation : : : : : : : : : : : : :D.6.2 Shared Memory for Multiprocessors : : : :D.6.3 Consensus : : : : : : : : : : : : : : : : : :D.6.4 Communication : : : : : : : : : : : : : : :D.6.5 Clock Synchronization : : : : : : : : : : :11::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::420420421421421422422422423423426426427427428428429429430430431432432433433434435436436437437437437438438438D.6.6 Applications of Synchronized Clocks : : : : : : : : : : : : : : : : : : 439126.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchSeptember 10, 1992Lecture 11.1 Introduction to the Course1.1.1 The Subject MatterThis course is about \distributed algorithms".

Distributed algorithms include a wide rangeof parallel algorithms, which can be classied by a variety of attributes:Interprocess Communication (IPC) method: shared memory, message-passing, dataow.Timing Model: synchronous, asynchronous, partially synchronous.Failure Model: reliable system, faulty links, faulty processors.Problems addressed: resource allocation, communication, agreement, database concurrency control, deadlock detection, and many more.Some of the major intended application areas of distributed algorithms arecommunication systems,shared-memory multiprocessor computation,distributed operating systems,distributed database systems,digital circuits, andreal-time process-control systems.Some kinds of parallel algorithms are studied in other courses and will not be coveredin this course, e.g., PRAM algorithms and algorithms for xed-connection networks such asButtery.

The algorithms to be studied in this course are distinguished by having a higherdegree of uncertainty, and more independence of activities: Some of the types of uncertaintythat we will consider are:13unknown number of processors,unknown shape of network,independent inputs at dierent locations,several programs executing at once, starting at dierent times, going at dierent speeds,nondeterministic processors,uncertain message delivery times,unknown message ordering,failures: processor (stopping, transient omission, Byzantine) link (message loss, duplication, reordering)Because of all this uncertainty, no component of a distributed system \knows" the entiresystem state.

Характеристики

Список файлов книги